A112319 -id:A112319 - cp's OEIS frontend

A122888 Triangle, read by rows, where row n lists the coefficients of x^k, k=1..2^n, in the n-th iteration of (x + x^2) for n>=0.

1, 1, 1, 1, 2, 2, 1, 1, 3, 6, 9, 10, 8, 4, 1, 1, 4, 12, 30, 64, 118, 188, 258, 302, 298, 244, 162, 84, 32, 8, 1, 1, 5, 20, 70, 220, 630, 1656, 4014, 8994, 18654, 35832, 63750, 105024, 160120, 225696, 293685, 352074, 387820, 391232, 359992, 300664, 226580

Offset: 0

Paul D. Hanna, Sep 18 2006

T(n, k) is the number of strings of length k-1 on the alphabet {1, 2, ..., n} such that between every two occurrences of a letter i there is an occurrence of a letter strictly larger than i. For example, for n = 3, k = 4 we have the strings 121, 131, 232 and the six permutations of 123. - Joel B. Lewis, May 06 2008

			Triangle begins:
  1;
  1, 1;
  1, 2, 2, 1;
  1, 3, 6, 9, 10, 8, 4, 1;
  1, 4, 12, 30, 64, 118, 188, 258, 302, 298, 244, 162, 84, 32, 8, 1;
  1, 5, 20, 70, 220, 630, 1656, 4014, 8994, 18654, 35832, 63750,...;
  1, 6, 30, 135, 560, 2170, 7916, 27326, 89582, 279622, 832680,...;
  1, 7, 42, 231, 1190, 5810, 27076, 121023, 520626, 2161158,...;
  1, 8, 56, 364, 2240, 13188, 74760, 409836, 2179556, 11271436,...;
  1, 9, 72, 540, 3864, 26628, 177744, 1153740, 7303164, 45179508,...;
  1, 10, 90, 765, 6240, 49260, 378312, 2836548, 20817588,...; ...
Multiplying the g.f. of column k by (1-x)^k, k>=1, with leading zeros,
 yields the g.f. of row k in the triangle A122890:
  1;
  0, 1;
  0, 0, 2;
  0, 0, 1, 5;
  0, 0, 0, 10, 14;
  0, 0, 0, 8, 70, 42;
  0, 0, 0, 4, 160, 424, 132;
  0, 0, 0, 1, 250, 1978, 2382, 429;
  0, 0, 0, 0, 302, 6276, 19508, 12804, 1430; ...
in which the main diagonal is the Catalan numbers,
 and the row sums form the factorials.

Paul D. Hanna, Table of n, a(n) for n = 0..2046 (rows 0..10)
Art of Problem Solving forum, Strings on [n] with certain restrictions.
Eunmi Choi, Obtuse matrix of arithmetic table, East Asian Math. J. (2024) Vol. 40, No. 3, 329-339. See p. 11.

Cf. A007018 (row sums), diagonals: A112317, A112319, A122887; A092123 (largest term in row); A122889 (antidiagonal sums); A122890 (related triangle).

b:= proc(n) option remember; `if`(n=0, x,
      expand((x-> x+x^2)(b(n-1))))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=1..degree(p)))(b(n)):
seq(T(n), n=0..5);  # Alois P. Heinz, Mar 14 2016

f[0][x_] = x; f[n_][x_] := f[n][x] = f[n-1][x+x^2]; row[n_] := CoefficientList[f[n][x], x] // Rest; Table[row[n], {n, 0, 5} ] // Flatten (* Jean-François Alcover, Sep 10 2012 *)

T(m,n):=if m=0 and n=1 then 1 else if m=0 and n>1 then 0 else  if m=1 then binomial(1,n-1) else sum(binomial(i,n-i)*T(m-1,i),i,1,n); /* Vladimir Kruchinin, May 19 2012 */

{T(n,k)=local(F=x+x^2, G=x+x*O(x^k)); if(n<0, 0, for(i=1, n, G=subst(F, x, G)); return(polcoeff(G, k, x)))}
for(n=0, 6, for(k=1, 2^n, print1(T(n, k), ", ")); print(""))

T(n,k) = [x^k] F_n(x) where F_{n+1}(x) = F_n(x+x^2) for n>=1, with F_0(x)=x.

Name changed slightly by Paul D. Hanna, Apr 29 2013

A135080 Triangle, read by rows, that transforms diagonals in the table of coefficients in the successive iterations of x+x^2 (cf. A122888).

Original entry on oeis.org

1, 1, 1, 2, 2, 1, 8, 7, 3, 1, 50, 40, 15, 4, 1, 436, 326, 112, 26, 5, 1, 4912, 3492, 1128, 240, 40, 6, 1, 68098, 46558, 14373, 2881, 440, 57, 7, 1, 1122952, 744320, 221952, 42604, 6135, 728, 77, 8, 1, 21488640, 13889080, 4029915, 748548, 103326, 11565, 1120, 100

Offset: 0

Paul D. Hanna, Nov 18 2007

			Triangle begins:
1;
1, 1;
2, 2, 1;
8, 7, 3, 1;
50, 40, 15, 4, 1;
436, 326, 112, 26, 5, 1;
4912, 3492, 1128, 240, 40, 6, 1;
68098, 46558, 14373, 2881, 440, 57, 7, 1;
1122952, 744320, 221952, 42604, 6135, 728, 77, 8, 1;
21488640, 13889080, 4029915, 748548, 103326, 11565, 1120, 100, 9, 1; ...
Coefficients in iterations of (x+x^2) form table A122888:
1;
1, 1;
1, 2, 2, 1;
1, 3, 6, 9, 10, 8, 4, 1;
1, 4, 12, 30, 64, 118, 188, 258, 302, 298, 244, 162, 84, 32, 8, 1;
1, 5, 20, 70, 220, 630, 1656, 4014, 8994, 18654, 35832, 63750,...;
1, 6, 30, 135, 560, 2170, 7916, 27326, 89582, 279622, 832680,...; ...
This triangle T transforms one diagonal in the above table into another;
start with the main diagonal of A122888, A112319, which begins:
[1, 1, 2, 9, 64, 630, 7916, 121023, 2179556, 45179508, ...];
then the transform T*A112319 equals A112317, which begins:
[1, 2, 6, 30, 220, 2170, 27076, 409836, 7303164, 149837028, ...];
and the transform T*A112317 equals A112320, which begins:
[1, 3, 12, 70, 560, 5810, 74760, 1153740, 20817588, 430604724, ...].

Paul D. Hanna, Table of n, a(n) for n=0..495 (rows 0..30)

Cf. columns: A135081, A135082, A135083.
Cf. related tables: A122888, A166900, A187005, A187115, A187120.
Cf. related sequences: A112319, A112317, A112320, A187009.

{T(n,k)=local(F=x,M,N,P,m=max(n,k)); M=matrix(m+2,m+2,r,c,F=x;for(i=1,r+c-2,F=subst(F,x,x+x^2+x*O(x^(m+2))));polcoeff(F,c)); N=matrix(m+1,m+1,r,c,M[r,c]);P=matrix(m+1,m+1,r,c,M[r+1,c]);(P~*N~^-1)[n+1,k+1]}

/* Generate by method given in A187005, A187115, A187120 (faster): */
{T(n,k)=local(Ck=x);for(m=1,n-k+1,Ck=(1/x^k)*subst(truncate(x^k*Ck),x,x+x^2 +x*O(x^m)));polcoeff(Ck,n-k+1,x)}

Columns may be generated by a method illustrated by triangles A187005, A187115, and A187120. The main diagonal of triangles A187005, A187115, and A187120, equals columns 0, 1, and 2, respectively.

Added cross-reference; example corrected and name changed by Paul D. Hanna, Feb 04 2011

A112317 Coefficients of x^n in the n-th iteration of (x + x^2) for n>=1.

Original entry on oeis.org

1, 2, 6, 30, 220, 2170, 27076, 409836, 7303164, 149837028, 3479498880, 90230486346, 2584679465160, 81056989408928, 2762187020749144, 101633218030586364, 4015771398425994048, 169588657820702174728

Offset: 1

Paul D. Hanna, Sep 03 2005

nonn

Forms a diagonal of the tables A122888 and A185755.

			The initial iterations of x + x^2 begin:
F(x) = (1)*x + x^2;
F(F(x)) = x + (2)*x^2 + 2*x^3 + x^4;
F(F(F(x))) = x + 3*x^2 + (6)*x^3 + 9*x^4+ 10*x^5+ 8*x^6+ 4*x^7+ x^8;
F(F(F(F(x)))) = x + 4*x^2 + 12*x^3 + (30)*x^4 + 64*x^5 +...;
F(F(F(F(F(x))))) = x + 5*x^2 + 20*x^3 + 70*x^4 + (220)*x^5 +...;
F(F(F(F(F(F(x)))))) = x + 6*x^2 + 30*x^3 + 135*x^4 + 560*x^5 + (2170)*x^6 +...;
where the terms in parenthesis illustrate how to form this sequence.

Paul D. Hanna and Vaclav Kotesovec, Table of n, a(n) for n = 1..300 (first 100 terms from Paul D. Hanna)

Cf. A112319, A112320, A122888, A185755, A135080, A166900.

{a(n)=local(F=x+x^2, G=x+x*O(x^n));if(n<1,0, for(i=1,n,G=subst(F,x,G));return(polcoeff(G,n,x)))}
for(n=1, 30, print1(a(n), ", "))

a(n) = [x^n] F_n(x) where F_n(x) = F_{n-1}(x+x^2) with F_1(x) = x+x^2.

Added cross-references and comments; name and example changed by Paul D. Hanna, Feb 04 2011

A166900 Triangle, read by rows, that transforms rows into diagonals in the table of coefficients of successive iterations of x+x^2 (cf. A122888).

Original entry on oeis.org

1, 1, 1, 2, 4, 1, 9, 21, 9, 1, 64, 156, 84, 16, 1, 630, 1540, 935, 230, 25, 1, 7916, 19160, 12480, 3564, 510, 36, 1, 121023, 288813, 196623, 61845, 10465, 987, 49, 1, 2179556, 5123608, 3591560, 1207696, 228800, 25864, 1736, 64, 1, 45179508, 104657520

Offset: 0

Paul D. Hanna, Nov 27 2009

Compare to the triangle A071207 that transforms rows into diagonals in the table of iterations of x/(1-x), where A071207(n,k) gives the number of labeled free trees with n vertices and k children of the root that have a label smaller than the label of the root. Does this triangle have a similar interpretation?

			Triangle begins:
1;
1, 1;
2, 4, 1;
9, 21, 9, 1;
64, 156, 84, 16, 1;
630, 1540, 935, 230, 25, 1;
7916, 19160, 12480, 3564, 510, 36, 1;
121023, 288813, 196623, 61845, 10465, 987, 49, 1;
2179556, 5123608, 3591560, 1207696, 228800, 25864, 1736, 64, 1;
45179508, 104657520, 74847168, 26415840, 5426949, 695079, 56511, 2844, 81, 1;
1059312264, 2420186616, 1755406674, 642448632, 140247810, 19683060, 1830080, 112520, 4410, 100, 1; ...
Coefficients in self-compositions of (x+x^2) form table A122888:
1;
1, 1;
1, 2, 2, 1;
1, 3, 6, 9, 10, 8, 4, 1;
1, 4, 12, 30, 64, 118, 188, 258, 302, 298, 244, 162, 84, 32, 8, 1;
1, 5, 20, 70, 220, 630, 1656, 4014, 8994, 18654, 35832, 63750,...;
1, 6, 30, 135, 560, 2170, 7916, 27326, 89582, 279622, 832680,...; ...
This triangle T transforms rows of A122888 into diagonals of A122888;
the initial diagonals begin:
A112319: [1, 1, 2, 9, 64, 630, 7916, 121023, 2179556, 45179508, ...];
A112317: [1, 2, 6, 30, 220, 2170, 27076, 409836, 7303164, 149837028,..];
A112320: [1, 3, 12, 70, 560, 5810, 74760, 1153740, 20817588, 430604724, ...].
For example:
T * [1, 0, 0, 0, 0, 0, 0,...]~ = A112319;
T * [1, 1, 0, 0, 0, 0, 0,...]~ = A112317;
T * [1, 2, 2, 1, 0, 0, 0,...]~ = A112320.

Paul D. Hanna, Table of n, a(n) for n=0..495 (rows 0..30)

Cf. A112319, A166901, A166902, A166903, A122888, A135080.

{T(n, k)=local(F=x, M, N, P, m=n); M=matrix(m+2, m+2, r, c, F=x;for(i=1, r+c-2, F=subst(F, x, x+x^2+x*O(x^(m+2)))); polcoeff(F, c)); N=matrix(m+1, m+1, r, c, F=x;for(i=1, r, F=subst(F, x, x+x^2+x*O(x^(m+2)))); polcoeff(F, c)); P=matrix(m+1, m+1, r, c, M[r+1, c]); (P~*N~^-1)[n+1, k+1]}
for(n=0, 10, for(k=0, n, print1(T(n, k), ", ")); print(""))

A112320 Coefficient of x^n in the (n+1)-th iteration of (x + x^2) for n>=1.

Original entry on oeis.org

1, 3, 12, 70, 560, 5810, 74760, 1153740, 20817588, 430604724, 10052947476, 261595087182, 7509722346204, 235808741944100, 8040824716606176, 295914258931377276, 11690732617035570008, 493527339623630078552

Offset: 1

Paul D. Hanna, Sep 06 2005

nonn

			The first few iterations of (x+x^2) begin:
F(x) = x + x^2;
F(F(x)) = (1)*x + 2*x^2 + 2*x^3 + x^4;
F(F(F(x))) = x + (3)*x^2 + 6*x^3 + 9*x^4 + 10*x^5 +...;
F(F(F(F(x)))) = x + 4*x^2 + (12)*x^3 + 30*x^4 + 64*x^5 +...;
F(F(F(F(F(x))))) = x + 5*x^2 + 20*x^3 + (70)*x^4 + 220*x^5 +...;
F(F(F(F(F(F(x)))))) = x + 6*x^2 + 30*x^3 + 135*x^4 + (560)*x^5 +...;
coefficients enclosed in parenthesis form the initial terms of this sequence.

Cf. A112317, A112319.

{a(n)=local(F=x+x^2, G=x+x*O(x^n));if(n<1,0, for(i=1,n+1,G=subst(F,x,G));return(polcoeff(G,n,x)))}
for(n=1,25,print1(a(n),", "))

a(n) = [x^n] F_{n+1}(x) where F_{n+1}(x) = F_n(x+x^2) with F_1(x) = x+x^2 and F_0(x)=x for n>=1.

cp's OEIS Frontend

A122888 Triangle, read by rows, where row n lists the coefficients of x^k, k=1..2^n, in the n-th iteration of (x + x^2) for n>=0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

PARI

Formula

Extensions

A135080 Triangle, read by rows, that transforms diagonals in the table of coefficients in the successive iterations of x+x^2 (cf. A122888).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

PARI

Formula

Extensions

A112317 Coefficients of x^n in the n-th iteration of (x + x^2) for n>=1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A166900 Triangle, read by rows, that transforms rows into diagonals in the table of coefficients of successive iterations of x+x^2 (cf. A122888).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A112320 Coefficient of x^n in the (n+1)-th iteration of (x + x^2) for n>=1.

Views

Author

Keywords

Examples

Crossrefs

Programs

PARI

Formula