A114903 Number of compositions of {1,..,n} such that no two adjacent parts are of equal size (labeled Carlitz compositions), allowing parts to be of size 0.

2, 4, 12, 76, 572, 5204, 59340, 782996, 11707324, 197988340, 3720933092, 76811352116, 1730660689580, 42251140165108, 1110607948991028, 31279537587370916, 939737174809843644, 29996522608581396788, 1013814287146517455812, 36168456215193554061044

Offset: 0

Author

Christian G. Bower, Jan 05 2006

Keywords

• nonn

Links

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

Crossrefs

Cf. A114900, A114902.

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))*binomial(n, j)), j=0..n))
    end:
a:= n-> b(n, -1):
seq(a(n), n=0..25);  # 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]]*Binomial[n, j]], {j, 0, n}]]; a[n_] := b[n, -1]; Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Feb 25 2017, after Alois P. Heinz *)

Formula

E.g.f.: 2*B(x)/(2-B(x)) where B(x) is e.g.f. of A114902.

a(n) ~ c * d^n * n^(n + 1/2), where d = 0.6907524084725166379194613015033714490019226066943600905783847741049876032..., c = 4.71633079866926561049991146534865892961540468329142429184529629611133729... - Vaclav Kotesovec, Sep 21 2019