A107429 Number of complete compositions of n.

1, 1, 3, 4, 8, 18, 33, 65, 127, 264, 515, 1037, 2052, 4103, 8217, 16408, 32811, 65590, 131127, 262112, 524409, 1048474, 2097319, 4194250, 8389414, 16778024, 33557921, 67116113, 134235473, 268471790, 536948820, 1073893571, 2147779943, 4295515305, 8590928746

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

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 *)

Crossrefs

Cf. A107428, A034296, A188575, A251729.

Sequence in context: A215095 A192474 A183494 * A372489 A061273 A254715

Adjacent sequences: A107426 A107427 A107428 * A107430 A107431 A107432

Keyword

nonn

Author

N. J. A. Sloane, May 26 2005

Extensions

More terms from Vladeta Jovovic, May 26 2005

Status

approved