Skip to main content
added code
Source Link
Per Alexandersson
  • 15.8k
  • 10
  • 74
  • 133

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]

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.

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]
Source Link
Per Alexandersson
  • 15.8k
  • 10
  • 74
  • 133

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.