A008930 Number of compositions (p_1, p_2, p_3, ...) of n with 1 <= p_i <= i for all i.
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
Offset: 0
Keywords
Examples
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)=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)
Links
- Alois P. Heinz, Table of n, a(n) for n = 0..3324 (first 201 terms from Vincenzo Librandi)
- Margaret Archibald, Aubrey Blecher, Arnold Knopfmacher, and Stephan Wagner, Subdiagonal and superdiagonal compositions, Art Disc. Appl. Math. (2024). See p. 5.
- Roland Bacher, Generic numerical semigroups, hal-03221466 [math.CO], 2021.
- Sergi Elizalde, Symmetric peaks and symmetric valleys in Dyck paths, arXiv:2008.05669 [math.CO], 2020.
- M. Torelli, Increasing integer sequences and Goldbach's conjecture, RAIRO - Theoretical Informatics and Applications, vol.40, no.02 (April 2006), pp.107-121.
Programs
-
Maple
b:= proc(n, i) option remember; `if`(i>=n, ceil(2^(n-1)), add(b(n-j, i+1), j=1..min(i, n))) end: a:= n-> b(n, 1): seq(a(n), n=0..50); # Alois P. Heinz, Mar 25 2014, revised Jun 26 2023 -
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 *) -
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
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->oo} a(n+1)/a(n) = 2. - Mats Granvik, Feb 22 2011
a(n) ~ c * 2^(n-1), where c = 0.288788095086602421... (see constant A048651). - Vaclav Kotesovec, Mar 17 2014
Extensions
More terms from Paul D. Hanna, Mar 20 2003
Offset corrected to 0 by Joerg Arndt, Mar 24 2014
New name (using comment by David Callan) from Joerg Arndt, Mar 25 2014
Comments