login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 59th year, we have over 358,000 sequences, and we’ve crossed 10,300 citations (which often say “discovered thanks to the OEIS”).

Other ways to Give
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

Row sums of triangle A177517.

LINKS

Vincenzo Librandi and Alois P. Heinz, Table of n, a(n) for n = 0..1000 (first 201 terms from Vincenzo Librandi)

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.

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

a(n) ~ c * 2^(n-1), where c = 0.288788095086602421... (see constant A048651). - Vaclav Kotesovec, Mar 17 2014

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)=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):

seq(a(n), n=0..50); # Alois P. Heinz, Mar 25 2014

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

Cf. A048285, A177517.

Sequence in context: A351972 A298118 A339292 * A339151 A164362 A329667

Adjacent sequences: A008927 A008928 A008929 * A008931 A008932 A008933

KEYWORD

nonn

AUTHOR

Mauro Torelli (torelli(AT)hermes.mc.dsi.unimi.it)

EXTENSIONS

More terms from Paul D. Hanna, Mar 20 2003

Corrected offset to 0, Joerg Arndt, Mar 24 2014

New name (using comment by David Callan) from Joerg Arndt, Mar 25 2014

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 9 23:05 EST 2022. Contains 358710 sequences. (Running on oeis4.)