A057051 Number of polyominoes of 2n-1 cells that span an n X n square.
1, 1, 6, 18, 73, 255, 950, 3473, 13006, 48840, 185353, 706404, 2706608, 10404625, 40126430, 155133811, 601119492, 2333671638, 9075290555, 35345525798, 137847145330, 538258922839, 2104101413400, 8233434921693, 32247613423563, 126410623214720, 495918571702575
Offset: 1
Keywords
Links
- D. E. Knuth, Animals in a cage, Problem 10875, Amer. Math. Monthly, 110 (March 2003), 243-245.
- R. J. Mathar, Corrigendum to "Polyomino Enumeration Results (Parkin et al, SIAM Fall Meeting 1967)" viXra:1905.0474 (2019)
- R. Parkin, L. J. Lander, and D. R. Parkin, Polyomino Enumeration Results, presented at SIAM Fall Meeting, 1967, and accompanying letter from T. J. Lander (annotated scanned copy) page 9 (incorrect at n=15).
Programs
-
Maple
A057051 := proc(n) if n mod 2 = 0 then binomial(2*n-2,n-1)+2^(n-2)-(3*n^2-2*n+8)/8; else binomial(2*n-2,n-1)+2^(n-2)-(3*n^2-4*n+9)/8+(1/2)*binomial(n-1,(n-1)/2); end if; end proc;
-
Mathematica
f[n_] := If[EvenQ[n], Binomial[2n-2, n-1] + 2^(n-2) - (3n^2-2n+8)/8, Binomial[2n-2, n-1] + 2^(n-2) - (3n^2-4n+9)/8 + (1/2) Binomial[n-1, (n-1)/2]]; Table[f[n], {n, 1, 27}] (* Jean-François Alcover, Mar 18 2017, translated from Maple *)
Formula
See Maple code.