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

Author

John Tyler Rascoe, Jun 28 2024

Keywords

• nonn

Comments

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

Examples

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

Crossrefs

Cf. A003242, A107428, A107429.

Programs

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)

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.