OFFSET
1,3
COMMENTS
A composition is complete if it is gap-free and contains a 1. - Geoffrey Critzer, Apr 13 2014
LINKS
Alois P. Heinz, Table of n, a(n) for n = 1..1000 (first 70 terms from Daniel Reimhult)
Alois P. Heinz, Plot of (a(n)-2^(n-2))/2^(n-2) for n = 40..1000
P. Hitczenko and A. Knopfmacher, Gap-free compositions and gap-free samples of geometric random variables, Discrete Math., 294 (2005), 225-239.
FORMULA
a(n) ~ 2^(n-2). - Vaclav Kotesovec, Sep 05 2014
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
EXAMPLE
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
MAPLE
b:= proc(n, i, t) option remember; `if`(n=0, `if`(i=0, t!, 0),
`if`(i<1 or n<i, 0, add(b(n-i*j, i-1, t+j)/j!, j=1..n/i)))
end:
a:= n-> add(b(n, i, 0), i=1..n):
seq(a(n), n=1..40); # Alois P. Heinz, Apr 14 2014
MATHEMATICA
Table[Length[Select[Level[Map[Permutations, IntegerPartitions[n]], {2}], MemberQ[#, 1]&&Length[Union[#]]==Max[#]-Min[#]+1&]], {n, 1, 20}] (* Geoffrey Critzer, Apr 13 2014 *)
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}]]];
a[n_] := Sum[b[n, i, 0], {i, 1, n}];
Table[a[n], {n, 1, 40}] (* Jean-François Alcover, Aug 30 2016, after Alois P. Heinz *)
PROG
(PARI)
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)}
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])}
B_x(35) \\ John Tyler Rascoe, May 25 2024
CROSSREFS
KEYWORD
nonn
AUTHOR
N. J. A. Sloane, May 26 2005
EXTENSIONS
More terms from Vladeta Jovovic, May 26 2005
STATUS
approved