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

Author

Christian G. Bower, Jan 05 2006

Keywords

• nonn

Links

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

Crossrefs

Cf. A000670, A003242, A007837, A032011.

Column k=1 of A261959.

Programs

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

Formula

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