login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A107429 Number of complete compositions of n. 4
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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 14 06:14 EST 2018. Contains 317162 sequences. (Running on oeis4.)