Klarner's theorem

Question

Klarner's theorem (http://mathworld.wolfram.com/KlarnersTheorem.html) says in a special case that you cannot tile a $10 \times 10$-board with $1\times 4$-tiles (that can also be rotated and used as $4 \times 1$-tiles). The reason is simple, for $1 \leq n,m \leq 10$, there are more pairs $(n,m)$ with $n+m=2$ modulo $4$ than pairs $(n,m)$ with $n+m=0$ modulo $4$, whereas each $1 \times 4$-tile covers every congruence class exactly once.

The proof can be easily visualized by coloring the board according to the congruence class of $n+m$ modulo $4$. This is the basis of a model in the math museum "Erlebnisland Mathematik" in Dresden (see http://www.erlebnisland-mathematik.de/en/portfolio/der-satz-von-klarner/), where you can try to tile the board and the coloring appears after pressing the "help"-button.

Now, recently, when showing the model to a group of pupils I claimed that the abstract argument above has the virtue of saving a lot of time, since the number of maximal coverings by $1 \times 4$-tiles (the end of each attempt to cover the whole board) is so large, that it is impossible to try them all in order to see that none is covering the whole board. But was I right?

Question: How large is the number of maximal coverings of an $10 \times 10$-board by $1 \times 4$-tiles approximately.

I do not know if this is a research question, but I also do not know where to start looking for estimates.

Answer 1

This is not exactly the same thing, but it is similar.

Let $\lambda = (10,10,\dotsc,10)$, and $\mu=(4,4,\dotsc,4)$. The non-tileability implies that the irreducible character, $\chi^{\lambda}(\mu)$ is $0$. Furthermore, since $\mu$ has all entries equal, turns out that $|\chi^{\lambda}(\mu)|$ is an upper bound on the number of tilings. See the Murnaghan-Nakayama rule for the connection.

Now, $|\chi^{\lambda}(\mu)|$ can in this case be computed via a Hook formula, see On the Number of Rim Hook Tableaux by Fomin & Lulov

With $n=100$, $r=4$, $m=25$, the first theorem in their paper then states that $$ f^{\lambda}_r \leq \frac{m! r^m}{(n!)^{1/r}} (f^\lambda)^{1/r} $$ and since $|\chi^{\lambda}(\mu)| = f^{\lambda}_r$ in this case, we get $\approx 2.78073*10^{16}$.

The number $f^{\lambda}_r$ count the number of ways to cover the the $10\times 10$-square with rim-hooks of size $4$, and it keeps track of the order one adds the pieces, such that the first $k$ pieces always form a Young diagram. This disallow for some configurations, but since the order matters, $f^{\lambda}_r$ should be an upper bound.

EDIT: The following Mathematica code gives a "slightly" better bound of 3086:

EMPTY=0;
BLOCKED=-1;
ModTetrisCoverings[pieces_List][board_List/;FreeQ[board,EMPTY],depth_:1]:=1;
ModTetrisCoverings[pieces_List][board_List,depth_:0]:=Module[
{putpos,IsOnBoardQ,IsEmptySpaceQ,w,h,shiftedPieces,goodPieces,newBoard,validConfs},

IsOnBoardQ[piece_]:=And@@Flatten@{Thread[1<=(First/@piece)<=h],Thread[1<=(Last/@piece)<=w]};

(* Check if piece only covers empty places. *)
IsEmptySpaceQ[piece_]:=Union[board[[#1,#2]]&@@@piece]==={EMPTY};

{h,w}=Dimensions[board];
putpos=First@Position[board,EMPTY,2,1];

shiftedPieces=Map[#+putpos&,pieces,{2}];
goodPieces=Select[shiftedPieces,IsOnBoardQ[#]&&IsEmptySpaceQ[#]&];
(* These are pieces that we may add so that they do not exceed board bounds,
and covers only empty entries. *)

(* If we found a leaf, return 1, otherwise, 
return number of leaves of the branch process *)
If[goodPieces=={},
1
,
Sum[
newBoard=ReplacePart[board,Thread[p->depth+1]];
ModTetrisCoverings[pieces][newBoard,depth+1]
,
{p,goodPieces}]
]
];
i4={{{0,0},{1,0},{2,0},{3,0}},{{0,0},{0,1},{0,2},{0,3}}};
ModTetrisCoverings[i4][ConstantArray[EMPTY,{10,10}],1]