A107428 Number of gap-free compositions of n.

1, 2, 4, 6, 11, 21, 39, 71, 141, 276, 542, 1070, 2110, 4189, 8351, 16618, 33134, 66129, 131937, 263483, 526453, 1051984, 2102582, 4203177, 8403116, 16800894, 33593742, 67174863, 134328816, 268624026, 537192064, 1074288649, 2148414285, 4296543181, 8592585289

Offset

1,2

Comments

A gap-free composition contains all the parts between its smallest and largest part. a(5)=11 because we have: 5, 3+2, 2+3, 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

Links

Alois P. Heinz, Table of n, a(n) for n = 1..1000

Alois P. Heinz, Plot of (a(n)-2^(n-2))/2^(n-2) for n = 42..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). - Alois P. Heinz, Dec 07 2014

Example

From Gus Wiseman, Oct 04 2022: (Start)
The a(0) = 1 through a(5) = 11 gap-free compositions:
  ()  (1)  (2)   (3)    (4)     (5)
           (11)  (12)   (22)    (23)
                 (21)   (112)   (32)
                 (111)  (121)   (122)
                        (211)   (212)
                        (1111)  (221)
                                (1112)
                                (1121)
                                (1211)
                                (2111)
                                (11111)
(End)

Maple

b:= proc(n, i, t) option remember; `if`(n=0, t!,
      `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}], Length[Union[#]]==Max[#]-Min[#]+1&]], {n, 1, 20}] (* Geoffrey Critzer, Apr 13 2014 *)
b[n_, i_, t_] := b[n, i, t] = If[n == 0, t!, 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

The unordered version (partitions) is A034296, ranked by A073491.

The initial case is A107429, unordered A000009, ranked by A333217.

The unordered complement is counted by A239955, ranked by A073492.

These compositions are ranked by A356841.

The complement is counted by A356846, ranked by A356842

A356230 ranks gapless factorization lengths, firsts A356603.

A356233 counts factorizations into gapless numbers.

Cf. A055932, A073493, A137921, A251729, A356224, A356843, A356845.

Sequence in context: A049870 A093970 A333098 * A086379 A096460 A322051

Adjacent sequences: A107425 A107426 A107427 * A107429 A107430 A107431

Keyword

nonn

Author

N. J. A. Sloane, May 26 2005

Extensions

More terms from Vladeta Jovovic, May 26 2005

Status

approved