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

Author

Joerg Arndt and Alois P. Heinz, Feb 26 2014

Keywords

• nonn

Examples

			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 ]
		

Links

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

Crossrefs

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

Programs

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 *)

Formula

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