|
%I #76 Feb 17 2024 11:27:07
%S 1,1,1,2,3,6,11,21,41,80,157,310,614,1218,2421,4819,9602,19147,38204,
%T 76266,152307,304256,607941,1214970,2428482,4854630,9705518,19405030,
%U 38800412,77585314,155145677,310251190,620437691,1240771141,2481374234
%N Number of compositions (p_1, p_2, p_3, ...) of n with 1 <= p_i <= i for all i.
%C 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
%C Row sums of triangle A177517.
%H Alois P. Heinz, <a href="/A008930/b008930.txt">Table of n, a(n) for n = 0..3324</a> (first 201 terms from Vincenzo Librandi)
%H Margaret Archibald, Aubrey Blecher, Arnold Knopfmacher, and Stephan Wagner, <a href="https://doi.org/10.26493/2590-9770.1675.fe8">Subdiagonal and superdiagonal compositions</a>, Art Disc. Appl. Math. (2024). See p. 5.
%H Roland Bacher, <a href="https://hal.archives-ouvertes.fr/hal-03221466">Generic numerical semigroups</a>, hal-03221466 [math.CO], 2021.
%H Sergi Elizalde, <a href="https://arxiv.org/abs/2008.05669">Symmetric peaks and symmetric valleys in Dyck paths</a>, arXiv:2008.05669 [math.CO], 2020.
%H M. Torelli, <a href="https://doi.org/10.1051/ita:2006017">Increasing integer sequences and Goldbach's conjecture</a>, RAIRO - Theoretical Informatics and Applications, vol.40, no.02 (April 2006), pp.107-121.
%F G.f.: A(x) = Sum_{n>=0} x^n * Product_{k=1..n} (1-x^k)/(1-x). - _Paul D. Hanna_, Mar 20 2003
%F 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
%F Limit_{n->oo) a(n+1)/a(n) = 2. - _Mats Granvik_, Feb 22 2011
%F a(n) ~ c * 2^(n-1), where c = 0.288788095086602421... (see constant A048651). - _Vaclav Kotesovec_, Mar 17 2014
%e G.f.: A(x) = 1 + x + x^2 + 2*x^3 + 3*x^4 + 6*x^5 + 11*x^6 + 21*x^7 + ...
%e The g.f. equals the following series involving q-factorials:
%e 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) + ...
%e From _Joerg Arndt_, Dec 28 2012: (Start)
%e There are a(7)=21 compositions p(1)+p(2)+...+p(m) = 7 such that p(k) <= k:
%e [ 1] [ 1 1 1 1 1 1 1 ]
%e [ 2] [ 1 1 1 1 1 2 ]
%e [ 3] [ 1 1 1 1 2 1 ]
%e [ 4] [ 1 1 1 1 3 ]
%e [ 5] [ 1 1 1 2 1 1 ]
%e [ 6] [ 1 1 1 2 2 ]
%e [ 7] [ 1 1 1 3 1 ]
%e [ 8] [ 1 1 1 4 ]
%e [ 9] [ 1 1 2 1 1 1 ]
%e [10] [ 1 1 2 1 2 ]
%e [11] [ 1 1 2 2 1 ]
%e [12] [ 1 1 2 3 ]
%e [13] [ 1 1 3 1 1 ]
%e [14] [ 1 1 3 2 ]
%e [15] [ 1 2 1 1 1 1 ]
%e [16] [ 1 2 1 1 2 ]
%e [17] [ 1 2 1 2 1 ]
%e [18] [ 1 2 1 3 ]
%e [19] [ 1 2 2 1 1 ]
%e [20] [ 1 2 2 2 ]
%e [21] [ 1 2 3 1 ]
%e (End)
%p b:= proc(n, i) option remember; `if`(i>=n,
%p ceil(2^(n-1)), add(b(n-j, i+1), j=1..min(i, n)))
%p end:
%p a:= n-> b(n, 1):
%p seq(a(n), n=0..50); # _Alois P. Heinz_, Mar 25 2014, revised Jun 26 2023
%t Sum[x^n*Product[(1-x^k)/(1-x), {k, 1, n}], {n, 0, 40}]+O[x]^41
%t 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 *)
%t 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_ *)
%o (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_
%o (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
%Y Cf. A000707, A048285, A177517.
%K nonn
%O 0,4
%A Mauro Torelli (torelli(AT)hermes.mc.dsi.unimi.it)
%E More terms from _Paul D. Hanna_, Mar 20 2003
%E Offset corrected to 0 by _Joerg Arndt_, Mar 24 2014
%E New name (using comment by _David Callan_) from _Joerg Arndt_, Mar 25 2014
|
