A001169 Number of board-pile polyominoes with n cells.

1, 2, 6, 19, 61, 196, 629, 2017, 6466, 20727, 66441, 212980, 682721, 2188509, 7015418, 22488411, 72088165, 231083620, 740754589, 2374540265, 7611753682, 24400004911, 78215909841, 250726529556, 803721298537, 2576384425157, 8258779154250, 26474089989299

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• nice
• easy

Comments

The inverse binomial transform is 1,1,3,6,..., i.e., the unsigned version of A077926. - R. J. Mathar, May 15 2008

a(n+1)/a(n) tends to a limit which is equal to the largest real root of the denominator of the g.f., 3.20556943040... = A246773 . - Robert G. Wilson v, Feb 01 2015

References

• W. F. Lunnon, Counting polyominoes, pp. 347-372 of A. O. L. Atkin and B. J. Birch, editors, Computers in Number Theory. Academic Press, NY, 1971.
• N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
• R. P. Stanley, Enumerative Combinatorics I, p. 259.

Links

• T. D. Noe, Table of n, a(n) for n = 1..200
• I. G. Enting and A. J. Guttmann, On the area of square lattice polygons, J. Statist. Phys., 58 (1990), 475-484.
• P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 367
• Dean Hickerson, Counting Horizontally Convex Polyominoes, J. Integer Sequences, Vol. 2 (1999), #99.1.8.
• David A. Klarner, Some results concerning polyominoes, Fibonacci Quarterly 3 (1965), 9-20.
• David A. Klarner, The number of graded partially ordered sets, Journal of Combinatorial Theory, vol.6, no.1, pp.12-19, (January-1969).
• Todd Mullen, On Variants of Diffusion, Dalhousie University (Halifax, NS Canada, 2020).
• R. Pemantle and M. C. Wilson, Twenty Combinatorial Examples of Asymptotics Derived from Multivariate Generating Functions, SIAM Rev., 50 (2008), no. 2, 199-272. See p. 239
• Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
• Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
• G. Pólya, On the number of certain lattice polygons, J. Combinatorial Theory 6 1969 102--105. MR0236031 (38 #4329) - From _N. J. A. Sloane_, Jun 05 2012
• K. A. Van'kov, V. M. Zhuravlyov, Regular tilings and generating functions, Mat. Pros. Ser. 3, issue 22, 2018 (127-157) [in Russian]. See page 128. - _N. J. A. Sloane_, Jan 09 2019
• Kirill Vankov, Valerii Zhuravlev, Regular and semiregular (uniform) tilings and generating functions, hal-02535947, [math.CO], 2020.
• Eric Weisstein's World of Mathematics, Column-Convex Polyomino.
• D. Zeilberger, Automated counting of LEGO towers, arXiv:math/9801016 [math.CO], 1998.
• V. M. Zhuravlev, Horizontally-convex polyiamonds and their generating functions, Mat. Pros. 17 (2013), 107-129 (in Russian).
• Index entries for linear recurrences with constant coefficients, signature (5, -7, 4).

Crossrefs

Cf. A049219, A049220 (partial sums), A049221, A049222, A246773, A273895.

Programs

Magma

I:=[1,2,6,19,61]; [n le 5 select I[n] else 5*Self(n-1)-7*Self(n-2)+4*Self(n-3): n in [1..30]]; // Vincenzo Librandi, Feb 15 2015

Mathematica

a[n_] := a[n] = If[n<5, {1, 2, 6, 19}[[n]], 5a[n-1] - 7a[n-2] + 4a[n-3]]; Table[a[n], {n, 30}]
Join[{1},LinearRecurrence[{5,-7,4},{2,6,19},40]] (* Harvey P. Dale, Sep 11 2014 *)
Rest@ CoefficientList[ Series[x (1 - x)^3/(1 - 5x + 7x^2 - 4x^3), {x, 0, 28}], x] (* Robert G. Wilson v, Feb 01 2015 *)

Maxima

makelist(sum(sum(binomial(k,i)*binomial(n+2*i-1,4*k-i),i,0,k),k,0,n-1),n,0,24); /* Emanuele Munarini, May 19 2011 */

PARI

{a(n) = if( n<0, 0, polcoeff( x * (1 - x)^3 / (1 - 5*x + 7*x^2 - 4*x^3) + x * O(x^n), n))}; /* Michael Somos, Jun 02 2016 */

Formula

G.f.: x*(1-x)^3/(1 - 5*x + 7*x^2 - 4*x^3). - Simon Plouffe in his 1992 dissertation

a(n) = 5*a(n-1) - 7*a(n-2) + 4*a(n-3) for n >= 5.

a(n) = sum(k=0..n-1, sum(i=0..k, binomial(k,i)*binomial(n+2*i-1,4*k-i))). - Emanuele Munarini, May 19 2011

a(n) = a(n-1) + A049219(n) + A049220(n) for n >= 2.

Row sums of A273895. - Michael Somos, Jun 02 2016

Extensions

More terms from Dean Hickerson