A238422 Number of compositions of n where no consecutive parts differ by 1.

1, 1, 2, 2, 5, 7, 15, 23, 43, 70, 128, 214, 383, 651, 1149, 1971, 3457, 5961, 10412, 18011, 31384, 54384, 94639, 164163, 285454, 495452, 861129, 1495126, 2597970, 4511573, 7838280, 13613289, 23649355, 41076088, 71354998, 123939602, 215294730, 373962643, 649597906, 1128352145

Offset

0,3

Links

Joerg Arndt and Alois P. Heinz, Table of n, a(n) for n = 0..1000

Formula

a(n) ~ c * d^n, where c = 0.501153706040308227351395770679776260606990346633815... and d = 1.737029107886986816124470304294547513896522086125645631179... - Vaclav Kotesovec, Feb 26 2014

Example

The a(6) = 15 such compositions are:
01:  [ 1 1 1 1 1 1 ]
02:  [ 1 1 1 3 ]
03:  [ 1 1 3 1 ]
04:  [ 1 1 4 ]
05:  [ 1 3 1 1 ]
06:  [ 1 4 1 ]
07:  [ 1 5 ]
08:  [ 2 2 2 ]
09:  [ 2 4 ]
10:  [ 3 1 1 1 ]
11:  [ 3 3 ]
12:  [ 4 1 1 ]
13:  [ 4 2 ]
14:  [ 5 1 ]
15:  [ 6 ]

Maple

# b(n, i): number of compositions of n where the leftmost part j
#          and i do not have distance 1
b:= proc(n, i) option remember; `if`(n=0, 1,
      add(`if`(abs(i-j)=1, 0, b(n-j, j)), j=1..n))
    end:
a:= n-> b(n, -1):
seq(a(n), n=0..50);

Mathematica

b[n_, i_] := b[n, i] = If[n == 0, 1, Sum[If[Abs[i - j] == 1, 0, b[n - j, j]], {j, 1, n}]]; a[n_] := b[n, -1]; Table[a[n], {n, 0, 50}] (* Jean-François Alcover, Nov 06 2014, after Maple *)

Crossrefs

Cf. A116931 (partitions where no consecutive parts differ by 1).

Sequence in context: A255063 A195964 A375079 * A047083 A327019 A035085

Adjacent sequences: A238419 A238420 A238421 * A238423 A238424 A238425

Keyword

nonn

Author

Joerg Arndt and Alois P. Heinz, Feb 26 2014

Status

approved