login
Triangle, read by rows, where the g.f. of row n divided by (1-x)^n yields the g.f. of column n in the triangle A122888, for n>=1.
7

%I #32 Apr 08 2023 09:53:28

%S 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,

%T 0,0,1,250,1978,2382,429,0,0,0,0,302,6276,19508,12804,1430,0,0,0,0,

%U 298,15674,106492,168608,66946,4862,0,0,0,0,244,33148,451948,1445208,1337684,343772,16796

%N Triangle, read by rows, where the g.f. of row n divided by (1-x)^n yields the g.f. of column n in the triangle A122888, for n>=1.

%C Main diagonal forms the Catalan numbers (A000108). Row sums gives the factorials. In table A122888, row n lists the coefficients of x^k, k = 1..2^n, in the n-th self-composition of (x + x^2) for n >= 0.

%C Parker gave the following combinatorial interpretation of the numbers: For n > 0, T(n, j) is the number of sequences c_1c_2...c_n of positive integers such that 1 <= c_i <= i for each i in {1, 2, .., n} with exactly j - 1 values of i such that c_i <= c_{i+1}. - _Peter Luschny_, May 05 2013

%H Toufik Mansour, Mark Shattuck, <a href="https://www.dmlett.com/archive/v4/DML20_v4_p42_49.pdf">Statistics on bargraphs of inversion sequences of permutations</a>, Discrete Math. Lett. (2020) Vol. 4, 42-49.

%H Toufik Mansour, Howard Skogman, Rebecca Smith, <a href="https://arxiv.org/abs/1704.04288">Passing through a stack k times</a>, arXiv:1704.04288 [math.CO], 2017.

%H Susan Field Parker, <a href="http://people.brandeis.edu/~gessel/homepage/students/parkerthesis.pdf">The Combinatorics of Functional Composition and Inversion</a>, Ph.D. Dissertation, Brandeis Univ. (1993) (Section 2.3.4, p. 27,28.)

%F From _Paul D. Hanna_, Apr 11 2009: (Start)

%F G.f. of row n: (1-x)^n*[g.f. of column n of A122888] where the g.f. of row n of A122888 is the n-th iteration of x+x^2.

%F Row-reversal forms triangle A158830 where g.f. of row n of A158830 = (1-x)^n*[g.f. of column n of A158825], and 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. (End)

%e Triangle begins:

%e 1;

%e 0,1;

%e 0,0,2;

%e 0,0,1,5;

%e 0,0,0,10,14;

%e 0,0,0,8,70,42;

%e 0,0,0,4,160,424,132;

%e 0,0,0,1,250,1978,2382,429;

%e 0,0,0,0,302,6276,19508,12804,1430;

%e 0,0,0,0,298,15674,106492,168608,66946,4862;

%e 0,0,0,0,244,33148,451948,1445208,1337684,343772,16796;

%e 0,0,0,0,162,61806,1614906,9459090,16974314,10003422,1744314,58786;

%e 0,0,0,0,84,103932,5090124,51436848,161380816,180308420,71692452,8780912,208012; ...

%e Table A122888 starts:

%e 1;

%e 1, 1;

%e 1, 2, 2, 1;

%e 1, 3, 6, 9, 10, 8, 4, 1;

%e 1, 4, 12, 30, 64, 118, 188, 258, 302, 298, 244, 162, 84, 32, 8, 1;

%e 1, 5, 20, 70, 220, 630, 1656, 4014, 8994, 18654, 35832, 63750,...;

%e 1, 6, 30, 135, 560, 2170, 7916, 27326, 89582, 279622, 832680,...;

%e where row n gives the g.f. of the n-th self-composition of (x+x^2).

%e From _Paul D. Hanna_, Apr 11 2009: (Start)

%e ROW-REVERSAL yields triangle A158830:

%e 1;

%e 1, 0;

%e 2, 0, 0;

%e 5, 1, 0, 0;

%e 14, 10, 0, 0, 0;

%e 42, 70, 8, 0, 0, 0;

%e 132, 424, 160, 4, 0, 0, 0;

%e 429, 2382, 1978, 250, 1, 0, 0, 0; ...

%e where

%e g.f. of row n of A158830 = (1-x)^n*[g.f. of column n of A158825];

%e g.f. of row n of A158825 = n-th iteration of x*Catalan(x).

%e RELATED ARRAY A158825 begins:

%e 1,1,2,5,14,42,132,429,1430,4862,16796,58786,...;

%e 1,2,6,21,80,322,1348,5814,25674,115566,528528,...;

%e 1,3,12,54,260,1310,6824,36478,199094,1105478,...;

%e 1,4,20,110,640,3870,24084,153306,993978,...;

%e 1,5,30,195,1330,9380,67844,500619,3755156,...;

%e 1,6,42,315,2464,19852,163576,1372196,11682348,...;

%e 1,7,56,476,4200,38052,351792,3305484,31478628,...;

%e 1,8,72,684,6720,67620,693048,7209036,75915708,...; ...

%e which consists of successive iterations of x*Catalan(x).

%e (End)

%t nmax = 11;

%t 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}];

%t row[n_] := CoefficientList[(1-x)^n*(T[[All, n]].x^Range[0, nmax])+O[x]^nmax, x];

%t Table[row[n], {n, 1, nmax}] // Flatten (* _Jean-François Alcover_, Jul 13 2018 *)

%Y Cf. A122888; A122891 (column sums); diagonals: A122892, A000108.

%Y Cf. related tables: A158830, A158825. [_Paul D. Hanna_, Apr 11 2009]

%K nonn,tabl

%O 0,6

%A _Paul D. Hanna_, Sep 18 2006