Search: a158830 -id:a158830
|
|
A158825
|
|
Square array of coefficients in the successive iterations of x*C(x) = (1-sqrt(1-4*x))/2 where C(x) is the g.f. of the Catalan numbers (A000108); read by antidiagonals.
|
|
+10
24
|
|
|
1, 1, 1, 1, 2, 2, 1, 3, 6, 5, 1, 4, 12, 21, 14, 1, 5, 20, 54, 80, 42, 1, 6, 30, 110, 260, 322, 132, 1, 7, 42, 195, 640, 1310, 1348, 429, 1, 8, 56, 315, 1330, 3870, 6824, 5814, 1430, 1, 9, 72, 476, 2464, 9380, 24084, 36478, 25674, 4862, 1, 10, 90, 684, 4200, 19852, 67844, 153306, 199094, 115566, 16796
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,5
|
|
LINKS
|
|
|
FORMULA
|
G.f. of column n = (g.f. of row n of A158830)/(1-x)^n.
Row k equals the first column of the k-th matrix power of Catalan triangle A033184; thus triangle A033184 transforms row n into row n+1 of this array (A158825). - Paul D. Hanna, Mar 30 2009
|
|
EXAMPLE
|
Square array of coefficients in iterations of x*C(x) begins:
1, 1, 2, 5, 14, 42, 132, 429, 1430, ... A000108;
1, 2, 6, 21, 80, 322, 1348, 5814, 25674, ... A121988;
1, 3, 12, 54, 260, 1310, 6824, 36478, 199094, ... A158826;
1, 4, 20, 110, 640, 3870, 24084, 153306, 993978, ... A158827;
1, 5, 30, 195, 1330, 9380, 67844, 500619, 3755156, ... A158828;
1, 6, 42, 315, 2464, 19852, 163576, 1372196, 11682348, ...;
1, 7, 56, 476, 4200, 38052, 351792, 3305484, 31478628, ...;
1, 8, 72, 684, 6720, 67620, 693048, 7209036, 75915708, ...;
1, 9, 90, 945, 10230, 113190, 1273668, 14528217, 167607066, ...;
1, 10, 110, 1265, 14960, 180510, 2212188, 27454218, 344320262, ...;
1, 11, 132, 1650, 21164, 276562, 3666520, 49181418, 666200106, ...;
1, 12, 156, 2106, 29120, 409682, 5841836, 84218134, 1225314662, ...;
1, 13, 182, 2639, 39130, 589680, 8999172, 138755799, 2157976392, ...;
1, 14, 210, 3255, 51520, 827960, 13464752, 221101608, 3660331064, ...;
1, 15, 240, 3960, 66640, 1137640, 19640032, 342179672, 6007747368, ...;
1, 16, 272, 4760, 84864, 1533672, 28012464, 516105720, 9578580504, ...;
ILLUSTRATE ITERATIONS.
Let G(x) = x*C(x), then the first few iterations of G(x) are:
G(x) = x + x^2 + 2*x^3 + 5*x^4 + 14*x^5 + ...;
G(G(x)) = x + 2*x^2 + 6*x^3 + 21*x^4 + 80*x^5 + ...;
G(G(G(x))) = x + 3*x^2 + 12*x^3 + 54*x^4 + 260*x^5 + ...;
G(G(G(G(x)))) = x + 4*x^2 + 20*x^3 + 110*x^4 + 640*x^5 + ...;
...
RELATED TRIANGLES.
The g.f. of column n is (g.f. of row n of A158830)/(1-x)^n
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;
...
Triangle A158835 transforms one diagonal into the next:
1;
1, 1;
4, 2, 1;
27, 11, 3, 1;
254, 94, 21, 4, 1;
3062, 1072, 217, 34, 5, 1;
45052, 15212, 2904, 412, 50, 6, 1;
783151, 257777, 47337, 6325, 695, 69, 7, 1; ...
so that:
where the diagonals start:
A158831 = [1, 1, 6, 54, 640, 9380, 163576, 3305484, ...];
A158832 = [1, 2, 12, 110, 1330, 19852, 351792, 7209036, ...];
A158833 = [1, 3, 20, 195, 2464, 38052, 693048, 14528217, ...];
A158834 = [1, 4, 30, 315, 4200, 67620, 1273668, 27454218, ...].
|
|
MATHEMATICA
|
Clear[row]; nmax = 12;
row[n_]:= row[n]= CoefficientList[Nest[(1-Sqrt[1-4#])/2&, x, n] + O[x]^(nmax+1), x] //Rest;
T[n_, k_]:= row[n][[k]];
Table[T[n-k+1, k], {n, nmax}, {k, n}]//Flatten (* Jean-François Alcover, Jul 13 2018, updated Aug 09 2018 *)
|
|
PROG
|
(PARI) {T(n, k)= local(F=serreverse(x-x^2+O(x^(k+2))), G=x);
for(i=1, n, G=subst(F, x, G)); polcoeff(G, k)}
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|
|
A122890
|
|
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.
|
|
+10
7
|
|
|
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, 0, 0, 0, 0, 298, 15674, 106492, 168608, 66946, 4862, 0, 0, 0, 0, 244, 33148, 451948, 1445208, 1337684, 343772, 16796
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,6
|
|
COMMENTS
|
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.
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
|
|
LINKS
|
|
|
FORMULA
|
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.
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)
|
|
EXAMPLE
|
Triangle begins:
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;
0,0,0,0,298,15674,106492,168608,66946,4862;
0,0,0,0,244,33148,451948,1445208,1337684,343772,16796;
0,0,0,0,162,61806,1614906,9459090,16974314,10003422,1744314,58786;
0,0,0,0,84,103932,5090124,51436848,161380816,180308420,71692452,8780912,208012; ...
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,...;
where row n gives the g.f. of the n-th self-composition of (x+x^2).
ROW-REVERSAL yields triangle A158830:
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; ...
where
g.f. of row n of A158825 = n-th iteration of x*Catalan(x).
1,1,2,5,14,42,132,429,1430,4862,16796,58786,...;
1,2,6,21,80,322,1348,5814,25674,115566,528528,...;
1,3,12,54,260,1310,6824,36478,199094,1105478,...;
1,4,20,110,640,3870,24084,153306,993978,...;
1,5,30,195,1330,9380,67844,500619,3755156,...;
1,6,42,315,2464,19852,163576,1372196,11682348,...;
1,7,56,476,4200,38052,351792,3305484,31478628,...;
1,8,72,684,6720,67620,693048,7209036,75915708,...; ...
which consists of successive iterations of x*Catalan(x).
(End)
|
|
MATHEMATICA
|
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];
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|
|
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.
|
|
+10
0
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
This counts the permutations of length n that avoid the permutations 24153, 24513, 24531, 34251, 35241, 42513, 42531, 45231, 261453, 231564, 523164.
|
|
REFERENCES
|
Toufik Mansour, Howard Skogman, and Rebecca Smith. "Passing through a stack k times." Discrete Mathematics, Algorithms and Applications 11.01 (2019): 1950003.
|
|
LINKS
|
|
|
FORMULA
|
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
|
|
MATHEMATICA
|
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 *)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
Search completed in 0.008 seconds
|