login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A107429 Number of complete compositions of n. 38
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,3

COMMENTS

A composition is complete if it is gap-free and contains a 1. - Geoffrey Critzer, Apr 13 2014

LINKS

Daniel Reimhult and 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 * A061273 A254715 A107328

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

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 16 18:21 EDT 2021. Contains 343050 sequences. (Running on oeis4.)