A114900 Number of compositions of n such that no two adjacent parts are equal, allowing 0.

2, 4, 8, 24, 60, 152, 400, 1032, 2656, 6876, 17776, 45912, 118664, 306680, 792480, 2047984, 5292564, 13677160, 35345112, 91340568, 236046088, 610000528, 1576390448, 4073776744, 10527631456, 27205966108, 70306845872, 181690021616, 469531293752, 1213383282936

Offset: 0

Author

Christian G. Bower, Jan 05 2006

Keywords

• nonn

Examples

			The 8 compositions of 2 are 2, 2+0, 1+0+1, 1+0+1+0, 0+2, 0+2+0, 0+1+0+1, 0+1+0+1+0.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1000
• A. Knopfmacher and H. Prodinger, On Carlitz compositions, European Journal of Combinatorics, Vol. 19, No. 5, Jul 1998, pp. 579-589.

Crossrefs

Cf. A003242, A114903.

Programs

Maple

b:= proc(n, i) option remember; `if`(n=0, `if`(i=0, 1, 2),
      add(`if`(i=j, 0, b(n-j, `if`(j>n-j, -1, j))), j=0..n))
    end:
a:= n-> b(n, -1):
seq(a(n), n=0..30);  # Alois P. Heinz, Sep 04 2015

Mathematica

b[n_, i_] := b[n, i] = If[n==0, If[i==0, 1, 2], Sum[If[i==j, 0, b[n-j, If[j > n-j, -1, j]]], {j, 0, n}]]; a[n_] := b[n, -1]; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Feb 08 2017, after Alois P. Heinz *)

Formula

G.f.: 2*B(x)/(2-B(x)) where B(x) is g.f. of A003242.

Extensions

Replaced broken link, Vaclav Kotesovec, May 01 2014