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

Author

N. J. A. Sloane, Apr 04 2011

Keywords

• nonn

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

Crossrefs

Cf. A107429, A188576, A188577, A251729.

Programs

Maple

b:= proc(n, i, t) option remember; `if`(n=0, `if`(i=0, t!, 0),
      `if`(i<1 or 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 || nJean-François Alcover, Mar 09 2015, after Alois P. Heinz *)

Formula

a(n) = 2^(n-1) - A107429(n) ~ 2^(n-2). - Alois P. Heinz, Dec 06 2014

Extensions

More terms from Alois P. Heinz, Dec 06 2014