A125128 -id:A125128 - cp's OEIS frontend

A360202 Array read by antidiagonals: T(m,n) is the number of (non-null) induced trees in the grid graph P_m X P_n.

1, 3, 3, 6, 12, 6, 10, 33, 33, 10, 15, 78, 138, 78, 15, 21, 171, 533, 533, 171, 21, 28, 360, 2003, 3568, 2003, 360, 28, 36, 741, 7453, 23686, 23686, 7453, 741, 36, 45, 1506, 27643, 156614, 277606, 156614, 27643, 1506, 45, 55, 3039, 102432, 1034875, 3234373, 3234373, 1034875, 102432, 3039, 55

Offset: 1

Andrew Howroyd, Feb 22 2023

			Array begins:
=============================================================
m\n|  1   2     3       4        5          6           7 ...
---+---------------------------------------------------------
1  |  1   3     6      10       15         21          28 ...
2  |  3  12    33      78      171        360         741 ...
3  |  6  33   138     533     2003       7453       27643 ...
4  | 10  78   533    3568    23686     156614     1034875 ...
5  | 15 171  2003   23686   277606    3234373    37643572 ...
6  | 21 360  7453  156614  3234373   66136452  1349087217 ...
7  | 28 741 27643 1034875 37643572 1349087217 48136454388 ...
     ...

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

Main diagonal is A360203.
Rows 1..2 are A000217, 3*A125128.
Cf. A287151 (connected induced subgraphs), A116469 (spanning trees), A360196 (induced cycles), A360199 (induced paths), A360918 (maximum induced trees).

T(m,n) = T(n,m).

A077802 Sum of products of parts increased by 1 in hook partitions of n, where hook partitions are of the form h*1^(n-h).

Original entry on oeis.org

1, 2, 7, 18, 41, 88, 183, 374, 757, 1524, 3059, 6130, 12273, 24560, 49135, 98286, 196589, 393196, 786411, 1572842, 3145705, 6291432, 12582887, 25165798, 50331621, 100663268, 201326563, 402653154, 805306337, 1610612704

Offset: 0

Alford Arnold, Dec 02 2002

It is not clear whether a(0) should be 1 or 0; this depends on whether the empty partition is a hook partition. By strict interpretation of the definition above, it is not; and except for n=0, there are exactly n hook partitions for each n. On the other hand, if defined as "a partition in whose Ferrers diagram every point is on the first row or column", the empty partition is a hook partition. - Franklin T. Adams-Watters, Jul 11 2009

			The hook partitions of 4 are 4, 3+1, 2+1+1, 1+1+1+1; the corresponding products when parts are increased by 1 are 5, 8, 12, 16; and their sum is a(4) = 41.

Index entries for linear recurrences with constant coefficients, signature (4,-5,2).

Cf. A074141, A055010 (first differences), A042950 (second differences).
Cf. A132048.
Same as A095151 except for a(0). - Franklin T. Adams-Watters, Jul 11 2009

s=0;lst={1};Do[s+=(s-n);AppendTo[lst, Abs[s]], {n, 2, 4!}];lst (* Vladimir Joseph Stephan Orlovsky, Oct 10 2008 *)

a(n)=if(n>0, 3*2^n - n - 3, 1) \\ Charles R Greathouse IV, Aug 08 2016

From Vladeta Jovovic, Dec 05 2002: (Start)
a(n) = 3*2^n - n - 3, n > 0.
G.f.: x*(2-x)/(1-2*x)/(1-x)^2.
Recurrence: a(n) = 4*a(n-1) - 5*a(n-2) + 2*a(n-3). (End)
Row sums of triangle A132048. Equals binomial transform of [1, 1, 4, 2, 4, 2, 4, 2, 4, ...]. - Gary W. Adamson, Aug 08 2007
a(n) = A125128(n) + A000225(n), n >= 1. - Miquel Cerda, Aug 07 2016

More terms from John W. Layman, Dec 05 2002

A307393 Square array A(n,k), n >= 0, k >= 1, read by antidiagonals, where column k is the expansion of g.f. ((1-x)^(k-4))/((1-x)^k-x^k).

Original entry on oeis.org

1, 1, 5, 1, 4, 16, 1, 4, 11, 42, 1, 4, 10, 26, 99, 1, 4, 10, 21, 57, 219, 1, 4, 10, 20, 42, 120, 466, 1, 4, 10, 20, 36, 84, 247, 968, 1, 4, 10, 20, 35, 64, 169, 502, 1981, 1, 4, 10, 20, 35, 57, 120, 340, 1013, 4017, 1, 4, 10, 20, 35, 56, 93, 240, 682, 2036, 8100

Offset: 0

Seiichi Manyama, Apr 07 2019

			Square array begins:
     1,   1,   1,   1,   1,   1,   1,   1, ...
     5,   4,   4,   4,   4,   4,   4,   4, ...
    16,  11,  10,  10,  10,  10,  10,  10, ...
    42,  26,  21,  20,  20,  20,  20,  20, ...
    99,  57,  42,  36,  35,  35,  35,  35, ...
   219, 120,  84,  64,  57,  56,  56,  56, ...
   466, 247, 169, 120,  93,  85,  84,  84, ...
   968, 502, 340, 240, 165, 130, 121, 120, ...

Seiichi Manyama, Antidiagonals n = 0..139, flattened

Columns 1-5 give A002662(n+3), A125128(n+1), A111927(n+3), A000749(n+3), A139748(n+3).

Cf. A306915, A306846, A307078, A307394.

T[n_, k_] := Sum[Binomial[n+3, k*j + 3], {j, 0, Floor[n/k]}]; Table[T[n - k, k], {n, 0, 11}, {k, n, 1, -1}] // Flatten (* Amiram Eldar, May 20 2021 *)

A(n,k) = Sum_{j=0..floor(n/k)} binomial(n+3,k*j+3).

A(n,2*k) = Sum_{i=0..n} Sum_{j=0..n-i} binomial(i+1,k*j+1) * binomial(n-i+1,k*j+1).

A233295 Riordan array ((1+x)/(1-x)^3, 2*x/(1-x)).

Original entry on oeis.org

1, 4, 2, 9, 10, 4, 16, 28, 24, 8, 25, 60, 80, 56, 16, 36, 110, 200, 216, 128, 32, 49, 182, 420, 616, 560, 288, 64, 64, 280, 784, 1456, 1792, 1408, 640, 128, 81, 408, 1344, 3024, 4704, 4992, 3456, 1408, 256, 100, 570, 2160, 5712, 10752, 14400, 13440, 8320, 3072, 512

Offset: 0

Philippe Deléham, Dec 07 2013

Subtriangle of the triangle in A208532.
Row sums are A060188(n+2).
Diagonal sums are A000295(n+2)=A125128(n+1)=A130103(n+2).

			Triangle begins :
1
4, 2
9, 10, 4
16, 28, 24, 8
25, 60, 80, 56, 16
36, 110, 200, 216, 128, 32
49, 182, 420, 616, 560, 288, 64
64, 280, 784, 1456, 1792, 1408, 640, 128
81, 408, 1344, 3024, 4704, 4992, 3456, 1408, 256
100, 570, 2160, 5712, 10752, 14400, 13440, 8320, 3072, 512

Cf. Columns: A000290, A006331, A112742.

Cf. Diagonal: A000079.

G.f. for the column k: 2^k*(1+x)/(1-x)^(k+3).
T(n,k) = 2^k*(binomial(n,k)+3*binomial(n,k+1)+2*binomial(n,k+2)), 0<=k<=n.
T(n,0) = 2*T(n-1,0)-T(n-2,0)+2, T(n,k)=2*T(n-1,k)+2*T(n-1,k-1)-2*T(n-2,k-1)-T(n-2,k) for k>=1, T(0,0)=1, T(1,0)=4, T(1,1)=2, T(n,k)=0 if k<0 or if k>n.
Sum_{k=0..n} T(n,k) = A060188(n+2).
Sum_{k=0..n} T(n,k)*(-1)^k = n+1.
T(n,k) = 2*sum_{j=1..n-k+1} T(n-j,k-1).
T(n,k) = 2^k*A125165(n,k).
T(n,n) = 2^n=A000079(n).
T(n,0) = (n+1)^2=A000290(n+1).
exp(2*x) * e.g.f. for row n = e.g.f. for diagonal n. For example, for n = 3 we have exp(2*x)*(16 + 28*x + 24*x^2/2! + 8*x^3/3!) = 16 + 60*x + 200*x^2/2! + 616*x^3/3! + 1792*x^4/4! + .... The same property holds more generally for Riordan arrays of the form ( f(x), 2*x/(1 - x) ). Cf. A125165. - Peter Bala, Dec 21 2014

A355282 Triangle read by rows: T(n, k) = Sum_{i=1..n-k} qStirling1(n-k, i) * qStirling2(n-1+i, n-1) for 0 < k < n with initial values T(n, 0) = 0^n and T(n, n) = 1 for n >= 0, here q = 2.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 9, 4, 1, 0, 343, 79, 11, 1, 0, 50625, 6028, 454, 26, 1, 0, 28629151, 1741861, 68710, 2190, 57, 1, 0, 62523502209, 1926124954, 38986831, 656500, 9687, 120, 1, 0, 532875860165503, 8264638742599, 84816722571, 734873171, 5760757, 40929, 247, 1

Offset: 0

Werner Schulte, Jun 26 2022

We aim at a q-generalization of the Comtet-Lehmer numbers A354794, which are the case q = 1. Here we consider the case q = 2. The generalization is based on the qStirling numbers, for qStirling1 see A342186 and for qStirling2 see A139382. The general construction is as follows:
Let q <> 1 be a fixed integer and f_q(k) = (q^k - 1)/(q - 1) for k >= 0. Define triangle M(q; n, k) for 0 <= k <= n by M(q; n, 0) = 0^n for n >= 0, and M(q; n, k) = 0 for k > n, and M(q; n, k) = M(q; n-1, k-1) + M(q; n-1, k) * f_q(k) for 0 < k <= n. Then M(q; n, n) = 1 for n >= 0 and the matrix inverse I_q = M_q^(-1) exists. Next define the triangle T(q; n, k) for 0 <= k <= n by T(q; n, 0) = 0^n for n >= 0 and T(q; n, k) = Sum_{i=0..n-k} I(q; n-k, i) * M(q; n-1+i, n-1) for 0 < k <= n. Take account of lim_{q->1} (q^n - 1)/(q - 1) = n for n >= 0.
Conjecture: T(q; n+1, 1) = Sum_{i=0..n} I(q; n, i) * M(q; n+i, n) = (f_q(n))^n = ((q^n - 1)/(q - 1))^n for n >= 0.
Conjecture: T(q; n, k) = (Sum_{i=0..n-k} (-1)^i * q-binomial(n-1-i, k-1) * binomial(n-1, i) * q^((n-k)*(n-k-i))) / (q - 1)^(n-k) for 0 < k <= n.

			Triangle T(n, k) for 0 <= k <= n starts:
n\k : 0               1             2           3         4       5     6   7 8
===============================================================================
  0 : 1
  1 : 0               1
  2 : 0               1             1
  3 : 0               9             4           1
  4 : 0             343            79          11         1
  5 : 0           50625          6028         454        26       1
  6 : 0        28629151       1741861       68710      2190      57     1
  7 : 0     62523502209    1926124954    38986831    656500    9687   120   1
  8 : 0 532875860165503 8264638742599 84816722571 734873171 5760757 40929 247 1
  etc.

Cf. A022166, A139382, A342186, A354794, A055601 (column 1), A125128 (1st subdiagonal).

# using qStirling2 from A333143.
A355282 := proc(n, k) if k = 0 then 0^n elif n = k then 1 else
add(A342186(n - k, i)*qStirling2(n + i - 2, n - 2, 2), i = 1..n-k) fi end:
seq(print(seq(A355282(n, k), k = 0..n)), n = 0..8); # Peter Luschny, Jun 28 2022

mat(nn) = my(m = matrix(nn, nn)); for (n=1, nn, for(k=1, nn, m[n, k] = if (n==1, if (k==1, 1, 0), if (k==1, 1, (2^k-1)*m[n-1, k] + m[n-1, k-1])); ); ); m; \\ A139382
tabl(nn) = my(m=mat(3*nn), im=1/m); matrix(nn, nn, n, k, n--; k--; if (k==0, 0^n, kMichel Marcus, Jun 27 2022

Conjecture: T(n+1, 1) = (2^n - 1)^n for n >= 0.

Conjecture: T(n, k) = Sum_{i=0..n-k} (-1)^i * binomial(n-1, i) * [n-1-i, k-1]_2 * 2^((n-k)*(n-k-i)) for 0 < k <= n and T(n, 0) = 0^n for n >= 0, where [x, y]_2 = A022166(x, y).

A368506 Square array T(n,k), n >= 0, k >= 0, read by antidiagonals downwards, where T(n,k) = Sum_{j=0..n} k^(n-j) * binomial(j+k-1,j).

Original entry on oeis.org

1, 1, 0, 1, 2, 0, 1, 4, 3, 0, 1, 6, 11, 4, 0, 1, 8, 24, 26, 5, 0, 1, 10, 42, 82, 57, 6, 0, 1, 12, 65, 188, 261, 120, 7, 0, 1, 14, 93, 360, 787, 804, 247, 8, 0, 1, 16, 126, 614, 1870, 3204, 2440, 502, 9, 0, 1, 18, 164, 966, 3810, 9476, 12900, 7356, 1013, 10, 0

Offset: 0

Seiichi Manyama, Dec 27 2023

			Square array begins:
  1, 1,   1,    1,     1,     1,      1, ...
  0, 2,   4,    6,     8,    10,     12, ...
  0, 3,  11,   24,    42,    65,     93, ...
  0, 4,  26,   82,   188,   360,    614, ...
  0, 5,  57,  261,   787,  1870,   3810, ...
  0, 6, 120,  804,  3204,  9476,  23112, ...
  0, 7, 247, 2440, 12900, 47590, 139134, ...

Columns k=0..3 give A000007, A000027(n+1), A125128(n+1), A052150.
Main diagonal gives A293574.
Cf. A008949, A368487.

T(n, k) = sum(j=0, n, k^(n-j)*binomial(j+k-1, j));

G.f. of column k: 1/((1-k*x) * (1-x)^k).

cp's OEIS Frontend

A360202 Array read by antidiagonals: T(m,n) is the number of (non-null) induced trees in the grid graph P_m X P_n.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A077802 Sum of products of parts increased by 1 in hook partitions of n, where hook partitions are of the form h*1^(n-h).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A307393 Square array A(n,k), n >= 0, k >= 1, read by antidiagonals, where column k is the expansion of g.f. ((1-x)^(k-4))/((1-x)^k-x^k).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A233295 Riordan array ((1+x)/(1-x)^3, 2*x/(1-x)).

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A355282 Triangle read by rows: T(n, k) = Sum_{i=1..n-k} qStirling1(n-k, i) * qStirling2(n-1+i, n-1) for 0 < k < n with initial values T(n, 0) = 0^n and T(n, n) = 1 for n >= 0, here q = 2.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

PARI

Formula

A368506 Square array T(n,k), n >= 0, k >= 0, read by antidiagonals downwards, where T(n,k) = Sum_{j=0..n} k^(n-j) * binomial(j+k-1,j).

Views

Author

Keywords

Examples

Crossrefs

Programs

PARI

Formula