|
| |
|
|
A008930
|
|
Number of compositions (p_1, p_2, p_3, ...) of n with 1 <= p_i <= i for all i.
|
|
36
|
|
|
|
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
|
0,4
|
|
|
COMMENTS
|
Previous name was: Number of increasing sequences of permutation type with maximal element n.
a(n) is the number of compositions (p_1,p_2,...) of n with 1<=p_i<=i for all i. a(n) is the 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
|
|
|
LINKS
|
|
|
|
FORMULA
|
G.f.: A(x) = Sum_{n>=0} 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) +...
There are a(7)=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)
|
|
|
MAPLE
|
b:= proc(n, i) option remember; `if`(n=0, 1,
add(b(n-j, i+1), j=1..min(i, n)))
end:
a:= n-> b(n, 1):
|
|
|
MATHEMATICA
|
Sum[x^n*Product[(1-x^k)/(1-x), {k, 1, n}], {n, 0, 40}]+O[x]^41
Table[SeriesCoefficient[1+Sum[x^j*Product[(1-x^k)/(1-x), {k, 1, j}], {j, 1, n}], {x, 0, n}], {n, 0, 40}] (* Vaclav Kotesovec, Mar 17 2014 *)
b[n_, i_] := b[n, i] = If[n == 0, 1, Sum[b[n-j, i+1], {j, 1, Min[i, n]}]]; a[n_] := b[n, 1]; Table[a[n], {n, 0, 50}] (* Jean-François Alcover, Apr 15 2015, after Alois P. Heinz *)
|
|
|
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
(PARI) N=66; q='q+O('q^N); Vec( sum(n=0, N, q^n * prod(k=1, n, (1-q^k)/(1-q) ) ) ) \\ Joerg Arndt, Mar 24 2014
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
Mauro Torelli (torelli(AT)hermes.mc.dsi.unimi.it)
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
