A239561 Number of compositions of n such that the first part is 1 and the second differences of the parts are in {-n,...,n}.

1, 1, 1, 2, 4, 8, 16, 31, 63, 125, 252, 504, 1013, 2027, 4069, 8141, 16318, 32650, 65381, 130801, 261791, 523677, 1047780, 2095796, 4192533, 8385623, 16773321, 33547917, 67100362, 134203614, 268417029, 536840509, 1073702131, 2147418493, 4294882224, 8589795592

Offset: 0

Author

Alois P. Heinz, Mar 21 2014

Keywords

• nonn

Examples

			There are 2^5 = 32 compositions of 7 with first part = 1.  Exactly one of these has second differences not in {-7,...,7}, namely [1,5,1].  Thus a(7) = 32 - 1 = 31.
		

Links

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

Crossrefs

Main diagonal of A239550.

Programs

Maple

b:= proc(n) option remember; `if`(n<5, [1, 1, 3, 4, 8][n+1],
      (-(n^3+3*n^2+184*n-348) *b(n-1)
       +(2*n^4+23*n^3-155*n^2-166*n+3776) *b(n-2)
       +(n^4+14*n^3-5*n^2+122*n+768) *b(n-3)
       +(2*n^3+10*n^2-64*n-1328) *b(n-4)
       -(2*n^4+28*n^3-78*n^2-272*n+2320) *b(n-5))/
      (n^4+10*n^3-75*n^2-20*n+1244))
    end:
a:= n-> `if`(n<7, ceil(2^(n-2)), 2^(n-2)-b(n-7)):
seq(a(n), n=0..40);

Mathematica

b[n_, i_, j_, k_] := b[n, i, j, k] = If[n == 0, 1, If[i == 0, Sum[b[n - h, j, h, k], {h, 1, n}], Sum[b[n - h, j, h, k], {h, Max[1, 2*j - i - k], Min[n, 2*j - i + k]}]]];
a[n_] := If[n == 0, 1, b[n - 1, 0, 1, n]];
a /@ Range[0, 40] (* Jean-François Alcover, Jan 03 2021, after Alois P. Heinz *)

Formula

a(n) ~ 2^(n-2). - Vaclav Kotesovec, May 01 2014