login
A075125
Number of parallelogram polyominoes of site-perimeter n (also called staircase polyominoes, although that term is overused).
4
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,6
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
M. Bousquet-Mélou and A. Rechnitzer, The site-perimeter of bargraphs, Adv. in Appl. Math. 31 (2003), 86-112.
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
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 *)
PROG
(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 */
CROSSREFS
KEYWORD
nonn
AUTHOR
Andrew Rechnitzer (a.rechnitzer(AT)ms.unimelb.edu.au), Sep 09 2002
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
STATUS
approved