login
A251729
Number of gap-free but not complete compositions of n.
8
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,4
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.
LINKS
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) = A107428(n) - A107429(n).
lim_{n -> oo} a(n)/a(n-1) = (1+sqrt(5))/2 = phi = A001622.
EXAMPLE
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].
MAPLE
b:= proc(n, i, t) option remember; `if`(n=0, `if`(i=0, 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..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 *)
KEYWORD
nonn
AUTHOR
Alois P. Heinz, Dec 07 2014
STATUS
approved