A114902 Number of compositions of {1,..,n} such that no two adjacent parts are of equal size (labeled Carlitz compositions).

1, 1, 1, 7, 21, 81, 793, 4929, 33029, 388537, 3751311, 37585989, 523395777, 6814401361, 90789460427, 1486639926417, 24213653736389, 403184436319401, 7665459211898263, 149067938821523349, 2971265450045056871, 64800464138121854877, 1460876941168812354947

Offset

0,4

Links

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

Formula

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

Maple

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

Mathematica

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

Crossrefs

Cf. A000670, A003242, A007837, A032011.

Column k=1 of A261959.

Sequence in context: A147003 A110683 A092785 * A177369 A164544 A100025

Adjacent sequences: A114899 A114900 A114901 * A114903 A114904 A114905

Keyword

nonn

Author

Christian G. Bower, Jan 05 2006

Status

approved