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,1

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.

Formula

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

Example

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.

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

Crossrefs

Cf. A003242, A114903.

Sequence in context: A361726 A333971 A231721 * A264570 A115115 A026097

Adjacent sequences: A114897 A114898 A114899 * A114901 A114902 A114903

Keyword

nonn

Author

Christian G. Bower, Jan 05 2006

Extensions

Replaced broken link, Vaclav Kotesovec, May 01 2014

Status

approved