|
| |
|
|
A008930
|
|
Number of increasing sequences of permutation type with maximal element n.
|
|
4
|
|
|
|
1, 1, 1, 2, 3, 6, 11, 21, 41, 80, 157, 310, 614, 1218, 2421, 4819, 9602, 19147, 38204, 76266, 152307, 304256, 607941, 1214970, 2428482, 4854630, 9705518, 19405030, 38800412, 77585314, 155145677, 310251190, 620437691, 1240771141, 2481374234
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,4
|
|
|
COMMENTS
|
a(n+1)=number of compositions (p_1,p_2,...) of n with 1<=p_i<=i for all i. a(n+1)=number of Dyck n-paths with strictly increasing peaks. To get the correspondence, given such a Dyck path, split the path after the first up step reaching height i, i=1,2,...,h where h is the path's maximum height and count up steps in each block. Example: U-U-DUU-U-DDDD has been split as specified, yielding the composition (1,1,2,1). - David Callan, Feb 18 2004
|
|
|
REFERENCES
|
M. Torelli, Increasing integer sequences and Goldbach's conjecture, RAIRO - Theoretical Informatics and Applications, vol.40, no.02 (April 2006), pp.107-121, http://dx.doi.org/10.1051/ita:2006017
|
|
|
LINKS
|
Table of n, a(n) for n=1..35.
|
|
|
FORMULA
|
G.f.: A(x) = 1 + Sum_{n>=1} x^n * Product_{k=1..n} (1-x^k)/(1-x). - Paul D. Hanna, Mar 20 2003
G.f.: A(x) = 1/(1 - x/(1+x) /(1 - x/(1+x+x^2) /(1 - x/(1+x+x^2+x^3) /(1 - x/(1+x+x^2+x^3+x^4) /(1 - x/(1+x+x^2+x^3+x^4+x^5) /(1 -...)))))), a continued fraction. - Paul D. Hanna, May 15 2012
limit(n->infinity) a(n+1)/a(n) = 2. - Mats Granvik, Feb 22 2011
|
|
|
EXAMPLE
|
G.f.: A(x) = 1 + x + x^2 + 2*x^3 + 3*x^4 + 6*x^5 + 11*x^6 + 21*x^7 +...
The g.f. equals the following series involving q-factorials:
A(x) = 1 + x + x^2*(1+x) + x^3*(1+x)*(1+x+x^2) + x^4*(1+x)*(1+x+x^2)*(1+x+x^2+x^3) + x^5*(1+x)*(1+x+x^2)*(1+x+x^2+x^3)*(1+x+x^2+x^3+x^4) +...
From Joerg Arndt, Dec 28 2012: (Start)
There are a(7+1)=21 compositions p(1)+p(2)+...+p(m)=7 such that p(k)<=k:
[ 1] [ 1 1 1 1 1 1 1 ]
[ 2] [ 1 1 1 1 1 2 ]
[ 3] [ 1 1 1 1 2 1 ]
[ 4] [ 1 1 1 1 3 ]
[ 5] [ 1 1 1 2 1 1 ]
[ 6] [ 1 1 1 2 2 ]
[ 7] [ 1 1 1 3 1 ]
[ 8] [ 1 1 1 4 ]
[ 9] [ 1 1 2 1 1 1 ]
[10] [ 1 1 2 1 2 ]
[11] [ 1 1 2 2 1 ]
[12] [ 1 1 2 3 ]
[13] [ 1 1 3 1 1 ]
[14] [ 1 1 3 2 ]
[15] [ 1 2 1 1 1 1 ]
[16] [ 1 2 1 1 2 ]
[17] [ 1 2 1 2 1 ]
[18] [ 1 2 1 3 ]
[19] [ 1 2 2 1 1 ]
[20] [ 1 2 2 2 ]
[21] [ 1 2 3 1 ]
(End)
|
|
|
MATHEMATICA
|
Sum[x^n*Product[(1-x^k)/(1-x), {k, 1, n}], {n, 0, 40}]+O[x]^41
|
|
|
PROG
|
(PARI) { n=8; v=vector(n); for (i=1, n, v[i]=vector(i!)); v[1][1]=1; for (i=2, n, k=length(v[i-1]); for (j=1, k, for (a=0, i-1, v[i][j+a*k]=v[i-1][j]+a+1))); c=vector(n); for (i=1, n, for (j=1, i!, if (v[i][j]<=n, c[v[i][j]]++))); c } (Jon Perry)
|
|
|
CROSSREFS
|
Cf. A048285.
Row sums of triangle A177517.
Sequence in context: A191789 A006861 A052956 * A164362 A026742 A018268
Adjacent sequences: A008927 A008928 A008929 * A008931 A008932 A008933
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
torelli(AT)hermes.mc.dsi.unimi.it (Mauro Torelli)
|
|
|
EXTENSIONS
|
More terms from Paul D. Hanna, Mar 20 2003
|
|
|
STATUS
|
approved
|
| |
|
|
