A075125 Number of parallelogram polyominoes of site-perimeter n (also called staircase polyominoes, although that term is overused).

0, 0, 0, 1, 0, 2, 2, 5, 10, 21, 46, 102, 230, 526, 1216, 2838, 6678, 15825, 37734, 90469, 217962, 527418, 1281250, 3123603, 7639784, 18740795, 46096732, 113666820, 280928470, 695796891, 1726744166, 4293121609, 10692145390, 26671959375, 66634602702

Offset: 1

Author

Andrew Rechnitzer (a.rechnitzer(AT)ms.unimelb.edu.au), Sep 09 2002

Keywords

• nonn

Comments

a(n) is the number of Dyck n-paths with no UDU's and no DUD's (A004148) whose first ascent is of length 3. For example, a(5)=2 counts UUUDDUUDDD, UUUDDDUUDD. - David Callan, May 08 2007

From Emeric Deutsch, Nov 07 2009: (Start)

a(n) = Sum_{k>=0} k*A166299(n-2,k).

Number of UUDD's starting at level 0 in all Dyck paths of semilength n-2 that have no ascents and no descents of length 1. Example: a(6)=2 because in UUDDUUDD and UUUUDDDD we have 2 + 0 = 2 UUDD's starting at level 0. (The Dyck paths having no ascents and no descents of length 1 are enumerated by the secondary structure numbers A004148).

(End)

References

• M. P. Delest, D. Gouyou-Beauchamps and B. Vauquelin, Enumeration of parallelogram polyominoes with given bond and site parameter, Graphs and Combinatorics, 3(1987),325-339. [From Emeric Deutsch, Nov 07 2009]

Links

• Vincenzo Librandi, Table of n, a(n) for n = 1..1000
• M. Bousquet-Mélou and A. Rechnitzer, The site-perimeter of bargraphs, Adv. in Appl. Math. 31 (2003), 86-112.

Crossrefs

Cf. A004148, A006958, A075126, A166299.

Programs

Maple

G := 4*z^4/(1+z-z^2+sqrt((1+z+z^2)*(1-3*z+z^2)))^2: Gser := series(G, z = 0, 32): seq(coeff(Gser, z, n), n = 1 .. 30); # Emeric Deutsch, Nov 07 2009

Mathematica

Rest[CoefficientList[Series[4 x^4/(1 + x - x^2 + Sqrt[(1 + x + x^2) (1 - 3 x + x^2)])^2, {x, 0, 40}], x]] (* Vaclav Kotesovec, Mar 21 2014 *)

Maxima

a(n):=2*sum((binomial(k-2,2*k-n+2)*binomial(k+1,n-k-3))/(k+1),k,floor((n-2)/2),n-3); /* Vladimir Kruchinin, Oct 12 2020 */

Formula

G.f.: p^2/2*(1-p^2-2*p^3+p^4-(1+p-p^2)*sqrt((1+p+p^2)*(1-3*p+p^2)));

a(n) ~ sqrt(2) * ((3+sqrt(5))/2)^n / (sqrt(377 + 843/sqrt(5)) * sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Mar 21 2014. Equivalently, a(n) ~ 5^(1/4) * phi^(2*n - 7) / (sqrt(Pi) * n^(3/2)), where phi = A001622 is the golden ratio. - Vaclav Kotesovec, Dec 07 2021

Conjecture: -(2*n-11)*(n-2)*(2*n-9)*a(n) +4*(2*n-11)*(n-3)*(n-5)*a(n-1) +(4*n^3-60*n^2+317*n-582)*a(n-2) +2*(2*n-7)*(2*n^2-26*n+81)*a(n-3) -(n-10)*(2*n-7)*(2*n-9)*a(n-4)=0. - R. J. Mathar, May 30 2016

a(n) = 2 * Sum_{k=floor((n-2)/2)..n-3} C(k-2,2*k-n+2)*C(k+1,n-k-3)/(k+1). - Vladimir Kruchinin, Oct 12 2020

Extensions

Offset changed to 1 by Emeric Deutsch, Nov 07 2009

More terms from Vincenzo Librandi, Mar 22 2014

Name modified by Alois P. Heinz, Sep 21 2016