A122890 -id:A122890 - cp's OEIS frontend

A122892 Secondary diagonal of triangle A122890.

1, 10, 70, 424, 2382, 12804, 66946, 343772, 1744314, 8780912, 43976688, 219546976, 1094132461, 5448766458, 27135655714, 135218356264, 674461583180, 3368432133000, 16847360404260, 84396523333080, 423485559461250

Offset: 4

Paul D. Hanna, Sep 18 2006

nonn

The main diagonal of triangle A122890 equals the Catalan numbers (A000108); this is the diagonal immediately below (with leading zeros omitted).

Cf. A122890, A122888; A122887.

A135723 A122890 + A000012 - I, I = Identity matrix.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 1, 2, 5, 1, 1, 1, 11, 14, 1, 1, 1, 9, 71, 42, 1, 1, 1, 5, 161, 425, 132, 1, 1, 1, 2, 251, 1979, 2383, 429, 1, 1, 1, 1, 303, 6277, 19509, 12805, 1430, 1, 1, 1, 1, 299, 15675, 106493, 168609, 66947, 4862

Offset: 0

Gary W. Adamson, Nov 25 2007

Row sums = A005095: (1, 2, 4, 9, 28, 125, 726, ...).

Main diagonal = A000108, the Catalan numbers: (1, 1, 2, 5, 14, 42, 132, ...).

			First few rows of the triangle:
  1;
  1, 1;
  1, 1, 2;
  1, 1, 2,  5;
  1, 1, 1, 11,  14;
  1, 1, 1,  9,  71,   42;
  1, 1, 1,  5, 161,  425,  132;
  1, 1, 1,  2, 251, 1979, 2383, 429;
  ...

Cf. A122890, A005095, A000108.

A122890 + A000012 - Identity matrix; as infinite lower triangular matrices.

A122891 Column sums of triangle A122890.

Original entry on oeis.org

1, 1, 3, 28, 1625, 3247268, 10649997137454, 113423713055030979289411081, 12864938683278671740537137672878980378983810317967737

Offset: 0

Paul D. Hanna, Sep 18 2006

nonn

Cf. A122890, A122888; A007018.

{A122890(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)); polcoeff(G, k, x))}
/* Takes first 2^m terms in column m of A122890 to compute a(m): */
{for(m=0,8,print1(polcoeff(sum(N=1,2^m,sum(n=0,2^m,A122890(n,N)*x^n)*(1-x)^N+O(x^12)),m),","))}

A135722 A000012 * A122890.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 1, 3, 5, 1, 1, 3, 15, 14, 1, 1, 3, 23, 84, 42, 1, 1, 3, 27, 244, 466, 132, 1, 1, 3, 28, 494, 2444, 2514, 429, 1, 1, 3, 28, 796, 8720, 22022, 13233, 1430, 1, 1, 3, 28, 1094, 24394, 128514, 181841, 68376, 4862

Offset: 0

Gary W. Adamson, Nov 25 2007

Row sums = A003422: (1, 2, 4, 10, 34, 154, 874, ...).

Main diagonal = A000108, the Catalan numbers: (1, 1, 2, 5, 14, 42, 132, ...).

			First few rows of the triangle:
 1;
  1, 1;
  1, 1, 2;
  1, 1, 3,  5;
  1, 1, 3, 15,  14;
  1, 1, 3, 23,  84,   42;
  1, 1, 3, 27, 244,  466,  132;
  1, 1, 3, 28, 494, 2444, 2514, 429;
  ...

Cf. A003422, A122890, A000108.

A000012 * A122890 as infinite lower triangular matrices.

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.

Original entry on oeis.org

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

A158830 Triangle, read by rows n>=1, where row n is the n-th differences of column n of array A158825, where the g.f. of row n of A158825 is the n-th iteration of x*Catalan(x).

Original entry on oeis.org

1, 1, 0, 2, 0, 0, 5, 1, 0, 0, 14, 10, 0, 0, 0, 42, 70, 8, 0, 0, 0, 132, 424, 160, 4, 0, 0, 0, 429, 2382, 1978, 250, 1, 0, 0, 0, 1430, 12804, 19508, 6276, 302, 0, 0, 0, 0, 4862, 66946, 168608, 106492, 15674, 298, 0, 0, 0, 0, 16796, 343772, 1337684, 1445208, 451948

Offset: 1

Paul D. Hanna, Mar 28 2009

			Triangle begins:
.1;
.1,0;
.2,0,0;
.5,1,0,0;
.14,10,0,0,0;
.42,70,8,0,0,0;
.132,424,160,4,0,0,0;
.429,2382,1978,250,1,0,0,0;
.1430,12804,19508,6276,302,0,0,0,0;
.4862,66946,168608,106492,15674,298,0,0,0,0;
.16796,343772,1337684,1445208,451948,33148,244,0,0,0,0;
.58786,1744314,10003422,16974314,9459090,1614906,61806,162,0,0,0,0;
.208012,8780912,71692452,180308420,161380816,51436848,5090124,103932,84,0,0,0,0;
....
where the g.f. of row n is (1-x)^n*[g.f. of column n of A158825];
g.f. of row n of array A158825 is the n-th iteration of x*C(x):
.1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,...;
.1,2,6,21,80,322,1348,5814,25674,115566,528528,2449746,...;
.1,3,12,54,260,1310,6824,36478,199094,1105478,6227712,...;
.1,4,20,110,640,3870,24084,153306,993978,6544242,43652340,...;
.1,5,30,195,1330,9380,67844,500619,3755156,28558484,...;
.1,6,42,315,2464,19852,163576,1372196,11682348,100707972,...;
.1,7,56,476,4200,38052,351792,3305484,31478628,303208212,...;
.1,8,72,684,6720,67620,693048,7209036,75915708,807845676,...;
....
ROW-REVERSAL yields 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; ...
where g.f. of row n = (1-x)^n*[g.f. of column n of A122888];
g.f. of row n of A122888 is the n-th iteration of x+x^2:
.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; ...

Paul D. Hanna, Table of n, a(n), n = 1..1326 (rows 1..51).
Toufik Mansour, Howard Skogman, Rebecca Smith, Passing through a stack k times, arXiv:1704.04288 [math.CO], 2017.

Cf. A158825, A122890 (row-reversal), A122888, columns: A000108, A122892.

nmax = 11;
f[0][x_] := x; f[n_][x_] := f[n][x] = f[n - 1][x + x^2] // Expand;
T = Table[SeriesCoefficient[f[n][x], {x, 0, k}], {n, 0, nmax}, {k, 1, nmax}];
row[n_] := CoefficientList[(1-x)^n*(T[[All, n]].x^Range[0, nmax])+O[x]^nmax, x] // Reverse;
Table[row[n], {n, 1, nmax}] // Flatten (* Jean-François Alcover, Oct 26 2018 *)

{T(n, k)=local(F=x, CAT=serreverse(x-x^2+x*O(x^(n+2))), M, N, P); M=matrix(n+2, n+2, r, c, F=x; for(i=1, r, F=subst(F, x, CAT)); polcoeff(F, c)); Vec(truncate(Ser(vector(n+1,r,M[r,n+1])))*(1-x)^(n+1) +x*O(x^k))[k+1]}

Row sums equal the factorial numbers.
G.f. of row n = (1-x)^n*[g.f. of column n of A158825] where the g.f. of row n of array A158825 is the n-th iteration of x*C(x) and C(x) is the g.f. of the Catalan sequence A000108.
Row-reversal is triangle A122890 where g.f. of row n of A122890 = (1-x)^n*[g.f. of column n of A122888], and the g.f. of row n of array A122888 is the n-th iteration of x+x^2.

Edited by N. J. A. Sloane, Oct 04 2010, to make entries, offset, b-file and link to b-file all consistent.

A308726 The number of permutations of length n and tier at most 1, that is, the number of permutations of length n sortable by two passes through a stack where outputting the longest prefix matching the identity permutation is prioritized.

Original entry on oeis.org

1, 1, 2, 6, 24, 112, 556, 2811, 14234, 71808, 360568, 1803100, 8988924, 44719588, 222221416, 1103827306, 5484124128, 27265300504, 135695994964, 676228846370, 3374996253420, 16871826671280, 84488005896720, 423828619074900, 2129868537725916, 10722045181336524

Offset: 0

Rebecca Smith, Jun 20 2019

nonn

This counts the permutations of length n that avoid the permutations 24153, 24513, 24531, 34251, 35241, 42513, 42531, 45231, 261453, 231564, 523164.

Toufik Mansour, Howard Skogman, and Rebecca Smith. "Passing through a stack k times." Discrete Mathematics, Algorithms and Applications 11.01 (2019): 1950003.

Toufik Mansour, Howard Skogman, and Rebecca Smith, Passing through a stack k times, arXiv:1704.04288 [math.CO], 2017-2018.

Cf. A122890 (sum of last two rows), A158830 (sum of first two rows).

CoefficientList[Series[(2 + (2*x - 1)/Sqrt[1 - 4*x] - Sqrt[2*Sqrt[1 - 4*x] - 1])/(2*x), {x, 0, 25}], x] (* Vaclav Kotesovec, Jun 30 2019 *)

G.f.: (2 + (2*x-1)/sqrt(1-4*x) - sqrt(2*sqrt(1-4*x) - 1)) / (2*x). - Vaclav Kotesovec, Jun 30 2019
a(n) ~ 2^(4*n + 3/2) / (sqrt(Pi) * n^(3/2) * 3^(n + 1/2)). - Vaclav Kotesovec, Jun 30 2019
Conjecture: D-finite with recurrence: 3*n*(n-1)*(n+1)*a(n) -n*(n-1)*(67*n-101)*a(n-1) +2*(n-1)*(286*n^2-1112*n+1089)*a(n-2) +4*(-580*n^3+4200*n^2-10106*n+8049)*a(n-3) +24*(184*n^3-1784*n^2+5770*n-6221)*a(n-4) -96*(4*n-15)*(2*n-9)*(4*n-17)*a(n-5)=0. - R. J. Mathar, Jan 27 2020

More terms from Vaclav Kotesovec, Jun 30 2019

cp's OEIS Frontend

A122892 Secondary diagonal of triangle A122890.

Views

Author

Keywords

Comments

Crossrefs

A135723 A122890 + A000012 - I, I = Identity matrix.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A122891 Column sums of triangle A122890.

Views

Author

Keywords

Crossrefs

Programs

PARI

A135722 A000012 * A122890.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

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

A158830 Triangle, read by rows n>=1, where row n is the n-th differences of column n of array A158825, where the g.f. of row n of A158825 is the n-th iteration of x*Catalan(x).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A308726 The number of permutations of length n and tier at most 1, that is, the number of permutations of length n sortable by two passes through a stack where outputting the longest prefix matching the identity permutation is prioritized.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions