login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A006958 Number of parallelogram polyominoes with n cells (also called staircase polyominoes, although that term is overused).
(Formerly M1175)
33
1, 2, 4, 9, 20, 46, 105, 242, 557, 1285, 2964, 6842, 15793, 36463, 84187, 194388, 448847, 1036426, 2393208, 5526198, 12760671, 29466050, 68041019, 157115917, 362802072, 837759792, 1934502740, 4467033943, 10314998977, 23818760154, 55000815222, 127004500762 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

Same as: number of skew Ferrers diagrams. - Joerg Arndt, Mar 18 2014

A coin fountain is an arrangement of coins in numbered rows such that the bottom row (row 0) contains contiguous coins and such that each coin in a higher row touches exactly two coins in the next lower row. See A005169. a(n) equals the number of coin fountains with exactly n coins in the even-numbered rows of the fountain. See the illustration in the Links section. See A161492 for a refinement of this sequence. - Peter Bala, Jul 20 2019

REFERENCES

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

LINKS

Seiichi Manyama, Table of n, a(n) for n = 1..2752 (terms 1..1000 from Robert Israel)

P. Bala, Illustration for the initial terms of the sequence

P. Bala, Fountains of coins and skew Ferrers diagrams

E. A. Bender, Convex n-ominoes, Discrete Math., 8 (1974), 219-226.

M. P. Delest, J. M. Fedou, Enumeration of skew Ferrers diagrams, Discrete Mathematics, vol. 112 (1993), no. 1-3, pp. 65-79.

P. Flajolet, Email to N. J. A. Sloane & S. Plouffe, Aug. 1991

P. Flajolet, Polya Festoons, INRIA Research Report, No 1507, September 1991. 6pp.

P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 661

D. Gouyou-Beauchamps and P. Leroux, Enumeration of symmetry classes of convex polyominoes on the honeycomb lattice, arXiv:math/0403168 [math.CO], 2004.

D. A. Klarner and R. L. Rivest, Asymptotic bounds for the number of convex n-ominoes, Discrete Math., 8 (1974), 31-40.

FORMULA

G.f.: 1+A(x) = 1/(1-x/(1-x/(1-x^2/(1-x^2/(1-x^3/(1-x^3/(1-...)))))) (continued fraction). - Paul D. Hanna, May 14 2005

The continued fraction given by P. Flajolet, "Polya Festoons", is derived from a q-expansion, C(x, y;q), where C(1, 1;q) = q/(1-2*q-q^3/(1-2*q^2-q^5/(1-2*q^3-q^7/(1-2*q^4-q^9/(1-...))))) = q + 2*q^2 + 4*q^3 + 9*q^4 + 20*q^5 + 46*q^6 + 105*q^7 + ... - Paul D. Hanna, May 14 2005

G.f.: 1/x/G(0) -1/x, where G(k)= 1 - x^(k+1)/(1 - x^(k+1)/G(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Jun 29 2013

G.f.: W(0)/x - 1/x, where W(k) = 1 - x^(k+1)/( x^(k+1) - 1/(1 - x^(k+1)/( x^(k+1) - 1/W(k+1) ))); R=1 (continued fraction). - Sergei N. Gladkovskii, Aug 27 2013

a(n) ~ c * d^n, where d = A276994 = 2.309138593330494731098720305017212531911814472581628401694402900284456440748..., c = 0.29745350581112195107675842441785013227507248969090226252518932405713367... . - Vaclav Kotesovec, Sep 21 2016

From Peter Bala, Jul 21 2019: (Start)

O.g.f. as a ratio of q-series: 1 + A(q) = N(q)/D(q) = 1 + q + 2*q^2 + 4*q^3 + ..., where N(q) = Sum_{n >= 0} (-1)^n*q^((n^2 + 3*n)/2)/Product_{k = 1..n} (1 - q^k)^2 and D(q) = Sum_{n >= 0} (-1)^n*q^((n^2 + n)/2)/Product_{k = 1..n} (1 - q^k)^2.

The constant d = 2.30913... in the above asymptotic formula is a zero of D(q) (as is 1/d).

Continued fraction representations for the o.g.f.:

1 + A(q) = 1/(1 - q/(1  - q/(1 + q*(1 - q) - q/( 1 + q*(1 - q^2) - q/(1 + q*(1 - q^3) - (...) ))))).

1 + A(q) = 1/(1 - q - q^2/(1 - q*(1 + q) - q^4/(1 - q^2*(1 + q) - q^6/(1 - q^3(1 + q) - q^8/( (...) ))))).

1 + A(q) =  1/(1 - q - q^2/(1 - q^2 - q/(1 - q^3 - q^5/(1 - q^4 - q^2/(1 - q^5 - q^8/ (1 - q^6 - q^3/(1 - q^7 - q^11/(1 - q^8 - (...) )))))))). (End)

EXAMPLE

G.f. may be expressed by the continued fraction: 1/(1-x/(1-x/(1-x^2/(1-x^2/(1-x^3/(1-x^3/(1-x^4/(1-...))))))))) = 1 + x + 2*x^2 + 4*x^3 + 9*x^4 + 20*x^5 + 46*x^6 + 105*x^7 + ...

From Michael B. Porter, Sep 21 2016; corrected by Riccardo Moschetti, Aug 11 2017: (Start)

Here are the nine parallelogram polyominoes with 4 cells, i.e., polygons convex according to the -45-degree direction, according to "Polya Festoons" of P. Flajolet:

                          _      _  _

             _  _     _ /_ /   /_ /_ /

         _ /_ /_ /  /_ /_ /   /_ /      _  _  _  _

       /_ /_ /     /_ /      /_ /     /_ /_ /_ /_ /

                     _

              _    /_ /    _  _  _            _  _

            /_ /  /_ /   /_ /_ /_ /    _    /_ /_ /

         _ /_ /  /_ /   /_ /    _  _ /_ /  /_ /_ /

       /_ /_ /  /_ /          /_ /_ /_ /

(End)

MAPLE

N:= 100: # to get a(1) to a(N)

M:= ceil(sqrt(N+1)):

C:= 1:

for j from M to 1 by -1 do C:= 1/(1-x^j/(1-x^j*C)) od:

S:= series(C, x, N+1):

seq(coeff(S, x, j), j=1..N); # Robert Israel, Sep 20 2016

MATHEMATICA

NN = 100; (* to get a(1) to a(NN) *) M = Ceiling[Sqrt[NN+1]]; c = 1; For[j = M, j >= 1, j--, c = 1/(1-x^j/(1-x^j*c))]; c = Series[c, {x, 0, NN+1}]; CoefficientList[c, x][[2 ;; NN+1]] (* Jean-Fran├žois Alcover, Sep 27 2016, adapted from Robert Israel's Maple code *)

nmax = 40; CoefficientList[Series[1/Fold[(1 - #2/#1) &, 1, Reverse[x^(Range[nmax + 1] - Floor[Range[nmax + 1]/2])]], {x, 0, nmax}], x] (* Vaclav Kotesovec, Sep 05 2017 *)

PROG

(PARI) {a(n)=local(CF=1+x*O(x^n), m); for(k=0, n\2, m=n\2-k+1; CF=(1-x^((m+1)\2)/CF)); polcoeff(1/CF, n)} \\ Paul D. Hanna, May 14 2005

(PARI) /* From the Delest/Fedou reference: */

N=44;  q='q+O('q^N);  t=1;

qn(n) = prod(k=1, n, 1-q^k );

nm = sum(n=0, N, (-1)^n* q^(n*(n+1)/2) / ( qn(n) * qn(n+1) ) * (t*q)^(n+1) );

dn = sum(n=0, N, (-1)^n* q^(n*(n-1)/2) / ( qn(n)^2 ) * (t*q)^n );

Vec(nm/dn)  \\ Joerg Arndt, Mar 18 2014

CROSSREFS

Cf. A075125, A276994, A275761, A275762, A161492.

Sequence in context: A000632 A090245 A274965 * A036617 A007902 A057417

Adjacent sequences:  A006955 A006956 A006957 * A006959 A006960 A006961

KEYWORD

nonn,nice

AUTHOR

N. J. A. Sloane, Simon Plouffe

EXTENSIONS

More terms from Paul D. Hanna, May 14 2005

Definition modified by Don Knuth, Sep 20 2016

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 24 07:18 EST 2020. Contains 331189 sequences. (Running on oeis4.)