A292357 -id:A292357 - cp's OEIS frontend

A378941 Number of Motzkin paths of length n up to reversal.

1, 1, 2, 3, 7, 13, 32, 70, 179, 435, 1142, 2947, 7889, 21051, 57192, 155661, 427795, 1179451, 3271214, 9102665, 25434661, 71282431, 200406472, 564905068, 1596435581, 4521772933, 12835116530, 36504093693, 104012240063, 296871993373, 848694481664, 2429882584254, 6966789756243

Offset: 0

Andrew Howroyd, Dec 17 2024

nonn

A Motzkin path of length n is a path from (0,0) to (n,0) using only steps U = (1,1), H = (1,0) and D = (1,-1). This sequence considers a path and its reversal to be the same. The number of symmetric paths of length 2n (and also 2n+1) is given by A005773(n+1).

a(n) + 1 is an upper bound on the order of the linear recurrence of column n-1 of A287151. At least for columns up to 7, this bound gives the actual order of the recurrence. For example, a(5) = 13 and the order of the recurrence of column 4 (=A059524) is 14.

			The Motzkin paths for a(1)..a(5) are:
a(1) = 1: H;
a(2) = 2: HH, UD;
a(3) = 3: HHH, UHD, HUD=UDH;
a(4) = 7: HHHH, HUDH, UHHD, UUDD, UDUD, HHUD=UDHH, HUHD=UHDH.
a(5) = 13: HHHHH, HUHDH, UHHHD, UUHDD, UDHUD, HHHUD=UDHHH, HHUHD=UHDHH, HHUDH=HUDHH, HUHHD=UHHDH, HUUDD=UUDDH, HUDUD=UDUDH, UHUDD=UUHDD, UHDUD=UPUHD.

Andrew Howroyd, Table of n, a(n) for n = 0..1000

Cf. A001006, A005773, A007123 (similar for Dyck paths), A175954, A185100, A287151, A292357.

Vec(-3/(4*x)-(1+sqrt(1-2*x-3*x^2+O(x^40)))/(4*x^2)+(1+x)/(-1+3*x^2+sqrt(1-2*x^2-3*x^4+O(x^40)))) \\ Thomas Scheuerle, Dec 18 2024

a(n) = (A001006(n) + A005773(floor(1 + n/2))) / 2.

A334552 Array read by antidiagonals: T(m,n) is the number of fixed polyominoes that have a width of m and height of n and m + n - 1 cells.

Original entry on oeis.org

1, 1, 1, 1, 4, 1, 1, 8, 8, 1, 1, 12, 25, 12, 1, 1, 16, 50, 50, 16, 1, 1, 20, 83, 120, 83, 20, 1, 1, 24, 124, 230, 230, 124, 24, 1, 1, 28, 173, 388, 497, 388, 173, 28, 1, 1, 32, 230, 602, 932, 932, 602, 230, 32, 1, 1, 36, 295, 880, 1591, 1924, 1591, 880, 295, 36, 1

Offset: 1

Andrew Howroyd, Jun 06 2020

A polyomino with a width of m and height of n must have at least m + n - 1 cells.

			Array begins:
=====================================================
m\n | 1  2   3    4    5     6     7     8      9
----+------------------------------------------------
  1 | 1  1   1    1    1     1     1     1      1 ...
  2 | 1  4   8   12   16    20    24    28     32 ...
  3 | 1  8  25   50   83   124   173   230    295 ...
  4 | 1 12  50  120  230   388   602   880   1230 ...
  5 | 1 16  83  230  497   932  1591  2538   3845 ...
  6 | 1 20 124  388  932  1924  3588  6212  10156 ...
  7 | 1 24 173  602 1591  3588  7265 13582  23859 ...
  8 | 1 28 230  880 2538  6212 13582 27288  51290 ...
  9 | 1 32 295 1230 3845 10156 23859 51290 102745 ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..1275

Columns 2..3 are A008574(n-1), A164754(n+1).
Main diagonal is A334551.
Cf. A292357.

A334552[m_,n_]:=Max[1,8Binomial[m+n-2,m-1]-3m*n+2m+2n-8];
Table[A334552[m-n+1,n],{m,15},{n,m}] (* Paolo Xausa, Dec 20 2023 *)

T(m, n)={if(m==1||n==1, 1, 8*binomial(m+n-2, m-1) - 3*m*n + 2*m + 2*n - 8)} \\ Andrew Howroyd, Dec 30 2020, after Peter J. Taylor

T(m,n) = 2*binomial(m+n-2, m-1) + 2*(m+n-4) + (m-2)*(n-2)*(m+n-5) + 2*Sum_{i=1..m-2} Sum_{j=1..n-2} ((m-2-i)*(n-2-j)+2)*binomial(i+j,i) for m > 1, n > 1.

T(m,n) = max(1, 8*binomial(m+n-2, m-1) - 3*m*n + 2*m + 2*n - 8). - Peter J. Taylor, Dec 15 2020

A377593 Number of aligned fixed polyominoes that will fit in a square of size n X n.

Original entry on oeis.org

1, 8, 151, 9472, 2081051, 1643823600, 4742607132499, 50303895480064088, 1966122506151835674303, 283294196554063138439927568, 150432366492029200690537003170367, 294212995394376069103067524948055548348, 2117957146063247996594586658579155551318256103, 56084287855193446153928896349599388059636859288133588, 5460061052459125116800111315595463810654508452342242195388707

Offset: 1

John Mason, Nov 02 2024

nonn

a(n) is the number of fixed polyominoes that have both width and height <= n. The word "aligned" in the title refers to the restriction that the polyominoes have edges parallel to the sides of the square.

			a(2) = 8 because of the monomino, 2 alignments of the domino, 4 alignments of the L-shaped tromino, and the square tetromino.

Cf. A292357, A268416, A268404.

a(n) = Sum_{i=1..n,j=1..n} A292357(i,j).

A378947 Number of row states in an automaton for the enumeration of the number of fixed polyominoes with bounding box of width n.

Original entry on oeis.org

1, 2, 6, 16, 40, 99, 247, 625, 1605, 4178, 11006, 29292, 78652, 212812, 579672, 1588242, 4374282, 12103404, 33628824, 93786966, 262450878, 736710357, 2073834417, 5853011847, 16558618507, 46949351272, 133390812252, 379708642286, 1082797114046, 3092894319075, 8848275403639

Offset: 0

Louis Marin, Dec 11 2024

The states track the non-crossing partitions of the connected components and whether each side of the bounding rectangle has been reached.

a(n) is an upper bound on the order of the generating function of row n of A292357.

Louis Marin, Counting Polyominoes in a Rectangle b x h, arXiv:2406.16413 [cs.DM], 2024; EPTCS 403, 2024, pp. 145-149.

Cf. A000108, A001006, A069010, A140662, A292357.

a:= proc(n) option remember; `if`(n<3, [1, 2, 6][n+1],
       ((3*n^2+2*n-12)*a(n-1)+(n^2-13*n+15)*a(n-2)
        -3*(n-3)*(n-1)*a(n-3))/((n-2)*(n+3)))
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, Dec 20 2024

a[n_] := a[n] = If[n < 3, {1, 2, 6}[[n+1]],
   ((3*n^2 + 2*n - 12)*a[n-1] + (n^2 - 13*n + 15)*a[n-2]
   - 3*(n-3)*(n-1)*a[n-3])/((n-2)*(n+3))];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Jan 26 2025, after Alois P. Heinz *)

b(n) = (1 + (hammingweight(bitxor(n, n>>1)))) >> 1;
C(n) = binomial(2*n, n)/(n+1);
a(n) = 1 + sum(m=1, 2^n-1, C(b(m)) * 2^((m % 2)==0) * 2^(m<2^(n-1))); \\ Michel Marcus, Dec 12 2024

a(n) = {1 + sum(k=1, (n+1)\2, (binomial(n+1, 2*k)+2*binomial(n,2*k)+binomial(n-1,2*k))*binomial(2*k, k)/(k+1))} \\ Andrew Howroyd, Dec 17 2024

a(n) = 1 + Sum_{m=1..2^n-1} A000108(A069010(m)) * 2^[m=0 mod 2] * 2^[m<2^(n-1)], where [] is the Iverson bracket.
From Andrew Howroyd, Dec 17 2024: (Start)
a(n) = 1 + Sum_{k=1..floor((n+1)/2)} (binomial(n+1, 2*k) + 2*binomial(n,2*k) + binomial(n-1,2*k)) * binomial(2*k, k)/(k+1).
a(n) = A001006(n+1) + 2*A001006(n) + A001006(n-1) - 3 for n > 0. (End)

More terms from Michel Marcus, Dec 12 2024

a(26) onwards from Andrew Howroyd, Dec 17 2024

cp's OEIS Frontend

A378941 Number of Motzkin paths of length n up to reversal.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A334552 Array read by antidiagonals: T(m,n) is the number of fixed polyominoes that have a width of m and height of n and m + n - 1 cells.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A377593 Number of aligned fixed polyominoes that will fit in a square of size n X n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A378947 Number of row states in an automaton for the enumeration of the number of fixed polyominoes with bounding box of width n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

Extensions