|
| |
|
|
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; internal format)
|
|
|
|
OFFSET
| 1,4
|
|
|
COMMENTS
| a(n+1)=number of compositions (a_1,a_2,...) of n with 1<=a_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 (callan(AT)stat.wisc.edu), Feb 18 2004
|
|
|
REFERENCES
| M. Torelli, Increasing integer sequences and Goldbach's conjecture, preprint, 1996.
|
|
|
FORMULA
| G.f.: A(x)=1 + sum(n>0, (x^n)*product(k=1..n, (1-x^k)/(1-x) ) ). - Paul D. Hanna (pauldhanna(AT)juno.com), Mar 20 2003
limit(n->infinity) a(n+1)/a(n) = 2. - Mats Granvik, Feb 22 2011
|
|
|
EXAMPLE
| 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)+...
|
|
|
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 (pauldhanna(AT)juno.com), Mar 20 2003
|
| |
|
|
