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

Links

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

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

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

Crossrefs

Cf. A114900, A114902.

Sequence in context: A085864 A060935 A141522 * A038054 A003180 A002080

Adjacent sequences: A114900 A114901 A114902 * A114904 A114905 A114906

Keyword

nonn

Author

Christian G. Bower, Jan 05 2006

Status

approved