A188575 Number of non-complete compositions of n.

0, 1, 1, 4, 8, 14, 31, 63, 129, 248, 509, 1011, 2044, 4089, 8167, 16360, 32725, 65482, 131017, 262176, 524167, 1048678, 2096985, 4194358, 8387802, 16776408, 33550943, 67101615, 134199983, 268399122, 536793004, 1073590077, 2147187353, 4294419287, 8588940438

Offset

1,4

Links

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

M. Archibald and A. Knopfmacher, The largest missing value in a composition of an integer, Discrete Math., 311 (2011), 723-731.

Alois P. Heinz, Plot of (a(n)-2^(n-2))/2^(n-2) for n = 60..1000

Formula

a(n) = 2^(n-1) - A107429(n) ~ 2^(n-2). - Alois P. Heinz, Dec 06 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-> 2^(n-1) -add(b(n, i, 0), i=1..n):
seq(a(n), n=1..40);  # Alois P. Heinz, Dec 06 2014

Mathematica

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_] := 2^(n-1)-Sum[b[n, i, 0], {i, 1, n} ]; Table[a[n], {n, 1, 40}] (* Jean-François Alcover, Mar 09 2015, after Alois P. Heinz *)

Crossrefs

Cf. A107429, A188576, A188577, A251729.

Sequence in context: A183977 A153364 A124743 * A324585 A242519 A174554

Adjacent sequences: A188572 A188573 A188574 * A188576 A188577 A188578

Keyword

nonn

Author

N. J. A. Sloane, Apr 04 2011

Extensions

More terms from Alois P. Heinz, Dec 06 2014

Status

approved