cp's OEIS Frontend

A107429 Number of complete compositions of n.

%I A107429 #56 May 26 2024 12:17:28
%S A107429 1,1,3,4,8,18,33,65,127,264,515,1037,2052,4103,8217,16408,32811,65590,
%T A107429 131127,262112,524409,1048474,2097319,4194250,8389414,16778024,
%U A107429 33557921,67116113,134235473,268471790,536948820,1073893571,2147779943,4295515305,8590928746
%N A107429 Number of complete compositions of n.
%C A107429 A composition is complete if it is gap-free and contains a 1. - _Geoffrey Critzer_, Apr 13 2014
%H A107429 Alois P. Heinz, <a href="/A107429/b107429.txt">Table of n, a(n) for n = 1..1000</a> (first 70 terms from Daniel Reimhult)
%H A107429 Alois P. Heinz, <a href="/A107429/a107429.jpg">Plot of (a(n)-2^(n-2))/2^(n-2) for n = 40..1000</a>
%H A107429 P. Hitczenko and A. Knopfmacher, <a href="http://dx.doi.org/10.1016/j.disc.2005.02.008">Gap-free compositions and gap-free samples of geometric random variables</a>, Discrete Math., 294 (2005), 225-239.
%F A107429 a(n) ~ 2^(n-2). - _Vaclav Kotesovec_, Sep 05 2014
%F A107429 G.f.: Sum_{k>0} C({1..k},x) where C({s},x) = Sum_{i in {s}} (C({s}-{i},x)*x^i)/(1 - Sum_{i in {s}} (x^i)) is the g.f. for compositions such that the set of parts equals {s} with C({},x) = 1. - _John Tyler Rascoe_, May 24 2024
%e A107429 a(5)=8 because we have: 2+2+1, 2+1+2, 1+2+2, 2+1+1+1, 1+2+1+1, 1+1+2+1, 1+1+1+2, 1+1+1+1+1. - _Geoffrey Critzer_, Apr 13 2014
%p A107429 b:= proc(n, i, t) option remember; `if`(n=0, `if`(i=0, t!, 0),
%p A107429       `if`(i<1 or n<i, 0, add(b(n-i*j, i-1, t+j)/j!, j=1..n/i)))
%p A107429     end:
%p A107429 a:= n-> add(b(n, i, 0), i=1..n):
%p A107429 seq(a(n), n=1..40);  # _Alois P. Heinz_, Apr 14 2014
%t A107429 Table[Length[Select[Level[Map[Permutations,IntegerPartitions[n]],{2}],MemberQ[#,1]&&Length[Union[#]]==Max[#]-Min[#]+1&]],{n,1,20}] (* _Geoffrey Critzer_, Apr 13 2014 *)
%t A107429 b[n_, i_, t_] := b[n, i, t] = If[n == 0, If[i == 0, t!, 0], If[i < 1 || n < i, 0, Sum[b[n - i*j, i - 1, t + j]/j!, {j, 1, n/i}]]];
%t A107429 a[n_] := Sum[b[n, i, 0], {i, 1, n}];
%t A107429 Table[a[n], {n, 1, 40}] (* _Jean-François Alcover_, Aug 30 2016, after _Alois P. Heinz_ *)
%o A107429 (PARI)
%o A107429 C_x(s,N)={my(x='x+O('x^N), g=if(#s <1,1, sum(i=1,#s, C_x(setminus(s,[s[i]]),N) * x^(s[i]) )/(1-sum(i=1,#s, x^(s[i]))))); return(g)}
%o A107429 B_x(N)={my(x='x+O('x^N), j=1, h=0); while((j*(j+1))/2 <= N, h += C_x(vector(j,i,i),N+1); j+=1); my(a = Vec(h)); vector(N,i,a[i])}
%o A107429 B_x(35) \\ _John Tyler Rascoe_, May 25 2024
%Y A107429 Cf. A107428, A034296, A188575, A251729.
%Y A107429 Row sums of A371417 and of A373118.
%K A107429 nonn
%O A107429 1,3
%A A107429 _N. J. A. Sloane_, May 26 2005
%E A107429 More terms from _Vladeta Jovovic_, May 26 2005