A075126 -id:A075126 - cp's OEIS frontend

A273720 Number of horizontal steps in the peaks of all bargraphs having semiperimeter n (n>=2).

1, 3, 8, 21, 57, 162, 479, 1458, 4528, 14259, 45349, 145289, 468121, 1515128, 4922145, 16040310, 52411294, 171646085, 563266323, 1851661113, 6096654978, 20101681834, 66362538332, 219336702948, 725692113292, 2403295565913, 7966021263923, 26425616887971

Offset: 2

Emeric Deutsch, Jun 01 2016

nonn

			a(4) = 8 because the 5 (=A082582(4)) bargraphs of semiperimeter 4 correspond to the compositions [1,1,1], [1,2], [2,1], [2,2], [3] and the corresponding drawings show that they have 3,1,1,2,1 horizontal steps in their peaks.

Alois P. Heinz, Table of n, a(n) for n = 2..1000
A. Blecher, C. Brennan, and A. Knopfmacher, Peaks in bargraphs, Trans. Royal Soc. South Africa, 71, No. 1, 2016, 97-103.
M. Bousquet-Mélou and A. Rechnitzer, The site-perimeter of bargraphs, Adv. in Appl. Math. 31 (2003), 86-112.

Cf. A075126, A082582, A273719.

g := (1/2)*z^2*(1-2*z+2*z^2-2*z^3+z^4+Q)/((1-z)^2*Q): Q := sqrt((1-z)^5*(1-3*z-z^2-z^3)): gser := series(g, z = 0, 35): seq(coeff(gser, z, n), n = 2 .. 32);
# second Maple program:
a:= proc(n) option remember; `if`(n<6, [0$2, 1, 3, 8, 21][n+1],
     ((2*(3*n-7))*(2*n-9)*a(n-1) -(254-155*n+22*n^2)*a(n-2)
      +(2*(101-58*n+8*n^2))*a(n-3) -(86-47*n+6*n^2)*a(n-4)
      +(2*(n-6))*(2*n-5)*a(n-5)-(n-6)*(2*n-5)*a(n-6))/
      ((n-2)*(2*n-9)))
    end:
seq(a(n), n=2..40);  # Alois P. Heinz, Jun 01 2016

a[n_] := a[n] = If[n<6, {0, 0, 1, 3, 8, 21}[[n+1]], ((2*(3*n-7))*(2*n - 9)*a[n-1] - (254 - 155*n + 22*n^2)*a[n-2] + (2*(101 - 58*n + 8*n^2))*a[n - 3] - (86 - 47*n + 6*n^2)*a[n-4] + (2*(n-6))*(2*n - 5)*a[n-5] - (n-6)*(2*n - 5)*a[n-6])/((n-2)*(2*n - 9))]; Table[a[n], {n, 2, 40}] (* Jean-François Alcover, Nov 29 2016 after Alois P. Heinz *)

G.f.: g(z) = z^2*(1-2*z+2*z^2-2*z^3+z^4+Q)/(2*Q*(1-z)^2), where Q = sqrt((1-z)^5*(1-3*z-z^2-z^3)).
a(n) = Sum(k*A273719(n,k), k>=1).
a(n) = ((2*(3*n-7))*(2*n-9)*a(n-1) -(254-155*n+22*n^2)*a(n-2) +(2*(101 -58*n +8*n^2))*a(n-3) -(86-47*n+6*n^2)*a(n-4) +(2*(n-6))*(2*n-5)*a(n-5) -(n-6)*(2*n-5)*a(n-6))/((n-2)*(2*n-9)) for n>=6. - Alois P. Heinz, Jun 01 2016

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

Original entry on oeis.org

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

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

nonn

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)

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]

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.

Cf. A004148, A006958, A075126, A166299.

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

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 *)

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 */

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

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

A274207 Number T(n,k) of bargraphs of site-perimeter n having area k; triangle T(n,k), n>=4, floor((n-1)/2)<=k<=floor(((n-1)^2+3)/12), read by rows.

Original entry on oeis.org

1, 2, 2, 2, 2, 4, 4, 2, 4, 7, 1, 6, 6, 10, 4, 2, 9, 13, 14, 12, 2, 8, 13, 22, 18, 24, 10, 2, 2, 15, 27, 40, 29, 38, 28, 12, 2, 10, 24, 45, 65, 59, 58, 56, 40, 16, 4, 2, 23, 52, 84, 104, 112, 100, 95, 88, 56, 28, 7, 1, 12, 40, 92, 148, 181, 205, 191, 172, 163, 132, 96, 48, 16, 4

Offset: 4

Alois P. Heinz, Jun 13 2016

A bargraph is a polyomino whose bottom is a segment of the nonnegative x-axis and whose upper part is a lattice path starting at (0,0) and ending with its first return to the x-axis using steps U=(0,1), D=(0,-1) and H=(1,0), where UD and DU are not allowed.

The site-perimeter of a polyomino is the number of exterior cells having a common edge with at least one polyomino cell.

			              _
T(4,1) = 1:  |_|
              _
             | |     ___
T(6,2) = 2:  |_|    |___|
              _        _
             | |_    _| |
T(7,3) = 2:  |___|  |___|
              _
             | |
             | |     _____
T(8,3) = 2:  |_|    |_____|
              ___      _
             |   |   _| |_
T(8,4) = 2:  |___|  |_____|
              _        _
             | |      | |   _            _
             | |_    _| |  | |___    ___| |
T(9,4) = 4:  |___|  |___|  |_____|  |_____|
              _        _
             | |_    _| |   ___        ___
             |   |  |   |  |   |_    _|   |
T(9,5) = 4:  |___|  |___|  |_____|  |_____|
                _
              _| |_
             |     |
T(10,7) = 1: |_____|
.
Triangle T(n,k) begins:
n\k: 1 2 3 4 5 6  7  8  9 10  11  12  13 14 15 16 17 . .
---+----------------------------------------------------
04 : 1
05 :
06 :   2
07 :     2
08 :     2 2
09 :       4 4
10 :       2 4 7  1
11 :         6 6 10  4
12 :         2 9 13 14 12  2
13 :           8 13 22 18 24  10   2
14 :           2 15 27 40 29  38  28  12  2
15 :             10 24 45 65  59  58  56 40 16  4
16 :              2 23 52 84 104 112 100 95 88 56 28 7 1

Alois P. Heinz, Rows n = 4..100, flattened
M. Bousquet-Mélou and A. Rechnitzer, The site-perimeter of bargraphs, Adv. in Appl. Math. 31 (2003), 86-112.
Wikipedia, Polyomino

Row sums give A075126.
Column sums give A000079(k-1).
Cf. A001787, A273346, A274208, A274217.

b:= proc(n, y, t, w) option remember; `if`(n<0, 0, `if`(n=0, (1-t),
     `if`(t<0, 0, b(n-`if`(w>0 or t=0, 1, 2), y+1, 1, max(0, w-1)))+
     `if`(t>0 or y<2, 0, b(n, y-1, -1, `if`(t=0, 1, w+1))) +expand(
     `if`(y<1, 0, z^y*b(n-`if`(t<0, 1, 2), y, 0, `if`(t<0, w, 0))))))
    end:
T:= n-> (p-> seq(coeff(p, z, i),
         i= iquo(n-1, 2)..iquo((n-1)^2+3, 12)))(b(n, 0, 1, 0)):
seq(T(n), n=4..20);

b[n_, y_, t_, w_] := b[n, y, t, w] = If[n<0, 0, If[n==0, (1-t), If[t<0, 0, b[n - If[w>0 || t==0, 1, 2], y+1, 1, Max[0, w-1]]] + If[t>0 || y<2, 0, b[n, y-1, -1, If[t==0, 1, w+1]]] + Expand[If[y<1, 0, z^y*b[n - If[t<0, 1, 2], y, 0, If[t<0, w, 0]]]]]];
T[n_] := Function[p, Table[Coefficient[p, z, i], {i, Quotient[n-1, 2], Quotient[(n-1)^2 + 3, 12]}]][b[n, 0, 1, 0]];
Table[T[n], {n, 4, 20}] // Flatten (* Jean-François Alcover, Apr 28 2018, after Alois P. Heinz *)

Sum_{k=floor((n-1)/2)..floor(((n-1)^2+3)/12)} k * T(n,k) = A274208(n).
Sum_{n>=4} k * T(n,k) = A001787(k).
Sum_{n>=4} n * T(n,k) = A274217(k).

A274208 Sum of the areas of all bargraphs of site-perimeter n.

Original entry on oeis.org

0, 0, 0, 0, 1, 0, 4, 6, 14, 36, 77, 168, 395, 851, 1921, 4254, 9461, 20991, 46619, 103360, 229461, 508731, 1128706, 2503028, 5552197, 12313707, 27313442, 60581866, 134384684, 298097515, 661300177, 1467072716, 3254847737, 7221496901, 16023112774, 35553756328

Offset: 0

Alois P. Heinz, Jun 13 2016

nonn

A bargraph is a polyomino whose bottom is a segment of the nonnegative x-axis and whose upper part is a lattice path starting at (0,0) and ending with its first return to the x-axis using steps U=(0,1), D=(0,-1) and H=(1,0), where UD and DU are not allowed.
The site-perimeter of a polyomino is the number of exterior cells having a common edge with at least one polyomino cell.
a(n)^(1/n) tends to 2.222118... . - Vaclav Kotesovec, Jun 26 2016

Alois P. Heinz, Table of n, a(n) for n = 0..820
M. Bousquet-Mélou and A. Rechnitzer, The site-perimeter of bargraphs, Adv. in Appl. Math. 31 (2003), 86-112.
Wikipedia, Polyomino

Cf. A075126, A273347, A274207.

a(n) = Sum_{k=floor((n-1)/2)..floor(((n-1)^2+3)/12)} k * A274207(n,k).

A274217 Sum of the site-perimeters of all bargraphs of area n.

Original entry on oeis.org

0, 4, 12, 30, 72, 166, 376, 837, 1844, 4025, 8723, 18789, 40263, 85892, 182515, 386488, 815890, 1717604, 3606854, 7556995, 15800562, 32974263, 68694801, 142882147, 296749381, 615468930, 1274878193, 2637637046, 5451035408, 11253593442, 23210232132, 47826554753

Offset: 0

Alois P. Heinz, Jun 14 2016

nonn

The site-perimeter of a polyomino is the number of exterior cells having a common edge with at least one polyomino cell.

M. Bousquet-Mélou and A. Rechnitzer, The site-perimeter of bargraphs, Adv. in Appl. Math. 31 (2003), 86-112.
Wikipedia, Polyomino

Cf. A075126, A274207.

a(n) = Sum_{k>=4} k * A274207(k,n).

cp's OEIS Frontend

A273720 Number of horizontal steps in the peaks of all bargraphs having semiperimeter n (n>=2).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

Formula

Extensions

A274207 Number T(n,k) of bargraphs of site-perimeter n having area k; triangle T(n,k), n>=4, floor((n-1)/2)<=k<=floor(((n-1)^2+3)/12), read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A274208 Sum of the areas of all bargraphs of site-perimeter n.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A274217 Sum of the site-perimeters of all bargraphs of area n.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula