A374147 Number of complete Carlitz compositions of n.

1, 0, 2, 1, 1, 8, 7, 9, 20, 49, 72, 115, 202, 349, 695, 1171, 2009, 3530, 6203, 10818, 19320, 33961, 59449, 104349, 183370, 321635, 564081, 992513, 1741441, 3057547, 5363570, 9410785, 16516575, 28967505, 50798456, 89106542, 156276871, 274037619, 480437247, 842350671, 1476760717, 2588651452, 4537418431, 7952741429, 13938276465

Offset

1,3

Comments

These are integer compositions such that no adjacent parts are equal and their set of parts covers an initial interval.

Links

Table of n, a(n) for n=1..45.

Formula

G.f.: Sum_{k>0} Ca({1..k},x) where Ca({s},x) = Sum_{i in {s}} ( (Ca({s}-{i},x)*x^i)/(1 + x^i) )/(1 - Sum_{i in {s}} ( (x^i)/(1 + x^i) )) is the g.f. for Carlitz compositions such that their set of parts equals {s} with Ca({},x) = 1.

Example

a(7) = 7 counts: (1,2,1,3), (1,2,3,1), (1,3,2,1), (1,3,1,2), (2,1,3,1), (3,2,1,2), (1,2,1,2,1).

Prog

(PARI)
Ca_x(s, N)={my(x='x+O('x^N), g=if(#s <1, 1, sum(i=1, #s, (Ca_x(s[^i], N) * x^(s[i])/(1+x^(s[i]))))/(1-sum(i=1, #s, (x^(s[i]))/(1+x^(s[i])))))); return(g)}
B_x(N)={my(x='x+O('x^N), j=1, h=0); while((j*(j+1))/2 <= N, h += Ca_x([1..j], N+1); j+=1); my(a = Vec(h)); vector(N, i, a[i])}
B_x(45)

Crossrefs

Cf. A003242, A107428, A107429.

Sequence in context: A291084 A229922 A051428 * A176698 A129276 A156901

Adjacent sequences: A374143 A374144 A374145 * A374148 A374150 A374151

Keyword

nonn

Author

John Tyler Rascoe, Jun 28 2024

Status

approved