A140662 -id:A140662 - cp's OEIS frontend

A287151 Array read by antidiagonals: T(m,n) = number of nonzero m X n binary arrays with all 1's connected.

1, 3, 3, 6, 13, 6, 10, 40, 40, 10, 15, 108, 218, 108, 15, 21, 275, 1126, 1126, 275, 21, 28, 681, 5726, 11506, 5726, 681, 28, 36, 1664, 28992, 116166, 116166, 28992, 1664, 36, 45, 4040, 146642, 1168586, 2301877, 1168586, 146642, 4040, 45, 55, 9779, 741556, 11749134, 45280509, 45280509, 11749134, 741556, 9779, 55

Offset: 1

Andrew Howroyd, May 20 2017

Also the number of connected induced (non-null) subgraphs of the grid graph P_m X P_n.

All rows (or columns) are linear recurrences with constant coefficients and the order of the recurrence of row m is at most 1 + A378941(m+1). At least for columns up to 7, this bound gives the actual order of the recurrence. The second differences of any column give those arrays that touch the top and bottom boundaries and have a recurrence order of 2 less since a finite state machine to enumerate these does not require states for empty rows. The number of states required is also considered in A140662 but does not take symmetry into account. - Andrew Howroyd, Dec 18 2024

			Table starts:
====================================================================
m\n|  1    2      3        4         5           6             7
---|----------------------------------------------------------------
1  |  1    3      6       10        15          21            28 ...
2  |  3   13     40      108       275         681          1664 ...
3  |  6   40    218     1126      5726       28992        146642 ...
4  | 10  108   1126    11506    116166     1168586      11749134 ...
5  | 15  275   5726   116166   2301877    45280509     889477656 ...
6  | 21  681  28992  1168586  45280509  1732082741   66037462454 ...
7  | 28 1664 146642 11749134 889477656 66037462454 4872949974666 ...
...

Andrew Howroyd, Table of n, a(n) for n = 1..435
Eric Weisstein's World of Mathematics, Connected Graph
Eric Weisstein's World of Mathematics, Grid Graph
Eric Weisstein's World of Mathematics, Induced Subgraph

Rows 2..5 are A059020, A059021, A059524, A378940.
Main diagonal is A059525.
Cf. A116469, A140662, A286139, A286189, A292357, A378941.

A203717 A Catalan triangle by rows.

Original entry on oeis.org

1, 1, 1, 1, 3, 1, 1, 8, 4, 1, 1, 20, 15, 5, 1, 1, 50, 53, 21, 6, 1, 1, 126, 182, 84, 28, 7, 1, 1, 322, 616, 326, 120, 36, 8, 1, 1, 834, 2070, 1242, 495, 165, 45, 9, 1, 1, 2187, 6930, 4680, 1997, 715, 220, 55, 10, 1, 1, 5797, 23166, 17512, 7942, 3003, 1001, 286, 66, 11, 1

Offset: 1

Gary W. Adamson, Jan 04 2012

Row sums = the Catalan sequence starting with offset 1: (1, 2, 5, 14, 42,...).
T(n,k) is the number of Dyck n-paths whose maximum ascent length is k. - David Scambler, Aug 22 2012
T(n,k) is the number of ordered rooted trees with n non-root nodes and maximal outdegree k. T(4,3) = 4:
.    o      o      o      o
.    |     /|\    /|\    /|\
.    o    o o o  o o o  o o o
.   /|\   |        |        |
.  o o o  o        o        o   - Alois P. Heinz, Jun 29 2014
T(n,k) also is the number of permutations p of [n] such that in 0p the largest up-jump equals k and no down-jump is larger than 1. An up-jump j occurs at position i in p if p_{i} > p_{i-1} and j is the index of p_i in the increasingly sorted list of those elements in {p_{i}, ..., p_{n}} that are larger than p_{i-1}. A down-jump j occurs at position i in p if p_{i} < p_{i-1} and j is the index of p_i in the decreasingly sorted list of those elements in {p_{i}, ..., p_{n}} that are smaller than p_{i-1}. First index in the lists is 1 here. T(4,3) = 4: 1432, 3214, 3241, 3421. - Alois P. Heinz, Aug 29 2017

			First few rows of the array begin:
1,...1,...1,...1,...1,...;
1,...2,...4,...9,..21,...; = A001006
1,...2,...5,..13,..36,...; = A036765
1,...2,...5,..14,..41,...; = A036766
1,...2,...5,..14,..42,...; = A036767
... Taking finite differences of array terms starting from the top by columns, we obtain row terms of the triangle. First few rows of the triangle are:
  1;
  1,    1;
  1,    3,    1;
  1,    8,    4,    1;
  1,   20,   15,    5,    1;
  1,   50,   53,   21,    6,   1;
  1,  126,  182,   84,   28,   7,   1;
  1,  322,  616,  326,  120,  36,   8,  1;
  1,  834, 2070, 1242,  495, 165,  45,  9,  1;
  1, 2187, 6930, 4680, 1997, 715, 220, 55, 10, 1;
  ...
Example: Row 4 of the triangle = (1, 8, 4, 1) = the finite differences of (1, 9, 13, 14), column 4 of the array. Term (3,4) = 13 of the array is the upper left term of M^4, where M is an infinite square production matrix with four diagonals of 1's starting at (1,2), (1,1), (2,1), and (3,1); with the rest zeros.

Alois P. Heinz, Rows n = 1..141, flattened

Cf. A000108, A001006, A036765, A036766, A036767, A291680, A288942.
Columns k=1-3 give: A057427, A140662(n-1) for n>1, A303271.
T(2n,n) gives A291662.
T(2n+1,n+1) gives A005809.
T(n,ceiling(n/2)) gives A303259.

b:= proc(n, t, k) option remember; `if`(n=0, 1, `if`(t>0,
      add(b(j-1, k$2)*b(n-j, t-1, k), j=1..n), b(n-1, k$2)))
    end:
T:= (n, k)-> b(n, k-1$2) -`if`(k=1, 0, b(n, k-2$2)):
seq(seq(T(n, k), k=1..n), n=1..14);  # Alois P. Heinz, Jun 29 2014
# second Maple program:
b:= proc(u, o, k) option remember; `if`(u+o=0, 1,
      add(b(u-j, o+j-1, k), j=1..min(1, u))+
      add(b(u+j-1, o-j, k), j=1..min(k, o)))
    end:
T:= (n, k)-> b(0, n, k)-`if`(k=0, 0, b(0, n, k-1)):
seq(seq(T(n, k), k=1..n), n=1..14);  # Alois P. Heinz, Aug 28 2017

b[n_, t_, k_] := b[n, t, k] = If[n == 0, 1, If[t > 0, Sum[b[j-1, k, k]*b[n - j, t-1, k], {j, 1, n}], b[n-1, k, k]]]; T[n_, k_] := b[n, k-1, k-1] - If[k == 1, 0, b[n, k-2, k-2]]; Table[T[n, k], {n, 1, 14}, {k, 1, n}] // Flatten (* Jean-François Alcover, May 27 2016, after Alois P. Heinz *)

from sympy.core.cache import cacheit
@cacheit
def b(u, o, k): return 1 if u + o==0 else sum([b(u - j, o + j - 1, k) for j in range(1, min(1, u) + 1)]) + sum([b(u + j - 1, o - j, k) for j in range(1, min(k, o) + 1)])
def T(n, k): return b(0, n, k) - (0 if k==0 else b(0, n, k - 1))
for n in range(1, 16): print([T(n, k) for k in range(1, n + 1)]) # Indranil Ghosh, Aug 30 2017

Finite differences of antidiagonals of an array in which n-th array row is generated from powers of M, extracting successive upper left terms. M for n-th row of the array is an infinite square production matrix composed of (n+1) diagonals of 1's and the rest zeros. Given the upper left term of the array is (1,1), the diagonals begin at (1,2), (1,1), (2,1), (3,1), (4,1),...

T(n,k) = A288942(n,k) - A288942(n,k-1). - Alois P. Heinz, Sep 01 2017

A167630 Riordan array (1/(1-x),xm(x)) where m(x) is the g.f. of Motzkin numbers A001006.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 4, 3, 1, 1, 8, 8, 4, 1, 1, 17, 20, 13, 5, 1, 1, 38, 50, 38, 19, 6, 1, 1, 89, 126, 107, 63, 26, 7, 1, 1, 216, 322, 296, 196, 96, 34, 8, 1, 1, 539, 834, 814, 588, 326, 138, 43, 9, 1, 1, 1374, 2187, 2236, 1728, 1052, 507, 190, 53, 10, 1

Offset: 0

Philippe Deléham, Nov 07 2009

			Triangle begins:
  1;
  1,  1;
  1,  2,  1;
  1,  4,  3,  1;
  1,  8,  8,  4,  1;
  1, 17, 20, 13,  5, 1;
  1, 38, 50, 38, 19, 6, 1;
  ...

Alois P. Heinz, Rows n = 0..200, flattened

Antidiagonal sums give A082395.
Row sums give A383527.
Diagonals include: A006416, A034856, A086615, A140662.
Cf. A001006, A003462, A064189, A082397, A094531.

T:= proc(n, k) option remember; `if`(k=0, 1,
      `if`(k>n, 0, T(n-1, k-1)+T(n-1, k)+T(n-1, k+1)))
    end:
seq(seq(T(n, k), k=0..n), n=0..12);  # Alois P. Heinz, Apr 20 2018

T[, 0] = T[n, n_] = 1;
T[n_, k_] /; 0, ] = 0;
Table[T[n, k], {n, 0, 12}, {k, 0, n}] // Flatten (* Jean-François Alcover, Dec 09 2019 *)

T(n,0)=1, T(0,k)=0 for k>0, T(n,k)=0 if k>n, T(n,k)=T(n-1,k-1)+T(n-1,k)+T(n-1,k+1).
Sum_{k=0..n} k * T(n,k) = A003462(n). - Alois P. Heinz, Apr 20 2018
Sum_{k=0..n} (-1)^(k+1) * T(n,k) = A082397(n-2) for n>=2. - Alois P. Heinz, May 02 2025

A379838 Triangle read by rows: T(n,k) is the total number of humps with height k in all Motzkin paths of order n, n >= 2 and 1 <= k <= n/2.

Original entry on oeis.org

1, 3, 8, 1, 20, 5, 50, 19, 1, 126, 63, 7, 322, 196, 34, 1, 834, 588, 138, 9, 2187, 1728, 507, 53, 1, 5797, 5016, 1749, 253, 11, 15510, 14454, 5786, 1067, 76, 1, 41834, 41470, 18590, 4147, 416, 13, 113633, 118690, 58487, 15223, 1976, 103, 1, 310571, 339274, 181181, 53599, 8528, 635, 15

Offset: 2

Xiaomei Chen, Jan 04 2025

			Triangle begins:
   [2]     1;
   [3]     3;
   [4]     8,    1;
   [5]    20,    5;
   [6]    50,   19,   1;
   [7]   126,   63,   7;
   [8]   322,  196,  34,  1;
   [9]   834,  588, 138,  9;
  [10]  2187, 1728, 507, 53, 1;
  ...

Xiaomei Chen, Table of n, a(n) for n = 2..401
Xiaomei Chen, Counting humps and peaks in Motzkin paths with height k, arXiv:2412.00668 [math.CO], Dec 2024.
David He and Daniel Tubbenhauer, Tensor powers of representations of (diagram) monoids, arXiv:2508.04054 [math.RT], 2025. See p. 10.

Row lengths give A004526.
Row sums give A097861.
Column 1 gives A140662.
Cf. A064189.

def A379838_triangel(dim):
    M = matrix(ZZ, dim, dim)
    for n in (2..dim+1):
        for k in (1..math.floor(n/2)+1):
            for i in range(n-2*k+1):
                if ((n-i)%2)==0:
                    M[n-2,k-1]=M[n-2, k-1]+(4*k)/(n-i+2*k)*binomial(n,i)*binomial(n-i-1,(n-i)/2+k-1)
    return M

G.f.: Sum_{n>=2, k>=1} T(n,k) * x^n * y^k = x^2 * M^2(x) * y / ((1-x) * (1 - x^2 * M^2(x) * y)), where M(x) is the g.f. for A001006.
T(n,k) = Sum_{i=0..n-2*k, i==n (mod 2)} (4*k) / (n-i+2*k) * binomial(n,i) * binomial(n-i-1,(n-i)/2+k-1).
T(n,k) = Sum_{i=2k-1..n-1} A064189(i,2k-1).
T(n,k) + T(n,k+1) = A064189(n,2k).

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

A287151 Array read by antidiagonals: T(m,n) = number of nonzero m X n binary arrays with all 1's connected.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A203717 A Catalan triangle by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

A167630 Riordan array (1/(1-x),xm(x)) where m(x) is the g.f. of Motzkin numbers A001006.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A379838 Triangle read by rows: T(n,k) is the total number of humps with height k in all Motzkin paths of order n, n >= 2 and 1 <= k <= n/2.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Sage

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