A251729 Number of gap-free but not complete compositions of n.

0, 1, 1, 2, 3, 3, 6, 6, 14, 12, 27, 33, 58, 86, 134, 210, 323, 539, 810, 1371, 2044, 3510, 5263, 8927, 13702, 22870, 35821, 58750, 93343, 152236, 243244, 395078, 634342, 1027876, 1656543, 2676693, 4325727, 6982440, 11299457, 18232217, 29518334, 47641410

Offset: 1

Author

Alois P. Heinz, Dec 07 2014

Keywords

• nonn

Comments

A composition is gap-free but not complete if all integers in the interval defined by the smallest and the largest part are parts but 1 is not a part.

Examples

			a(6) = 3: [6], [3,3], [2,2,2].
a(7) = 6: [7], [3,4], [4,3], [2,2,3], [2,3,2], [3,2,2].
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..1000
• Alois P. Heinz, Plot of (a(n)+a(n+1)-a(n+2))/a(n+2) for n = 150..1000
• P. Hitczenko and A. Knopfmacher, Gap-free compositions and gap-free samples of geometric random variables, Discrete Math., 294 (2005), 225-239.

Crossrefs

Cf. A001622, A034296, A107428, A107429, A188575, A238353, A264396.

Programs

Maple

b:= proc(n, i, t) option remember; `if`(n=0, `if`(i=0, 0, t!),
     `if`(i<1 or n add(b(n, i, 0), i=1..n):
seq(a(n), n=1..50);

Mathematica

b[n_, i_, t_] := b[n, i, t] = If[n == 0, If[i == 0, 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}];
Array[a, 50] (* Jean-François Alcover, Jan 25 2021, after Alois P. Heinz *)

Formula

a(n) = A107428(n) - A107429(n).

lim_{n -> oo} a(n)/a(n-1) = (1+sqrt(5))/2 = phi = A001622.