A380176 Number of pairs of adjacent equal parts in all gap-free compositions of n.

0, 0, 1, 2, 6, 12, 26, 56, 124, 266, 563, 1204, 2573, 5468, 11559, 24370, 51281, 107720, 225867, 472660, 987378, 2059180, 4287932, 8916624, 18517398, 38406486, 79563118, 164636582, 340308519, 702713844, 1449664783, 2987870476, 6152930738, 12660419370, 26030245642

Offset: 0

Author

John Tyler Rascoe, Jan 14 2025

Keywords

• nonn

Comments

An integer composition is gap-free if its set of parts covers an interval.

Examples

			The gap-free compositions of n = 4 are: (4), (2,2), (1,1,2), (1,2,1), (2,1,1), and (1,1,1,1); having a total of 6 pairs of equal adjacent parts giving a(4) = 6.
		

Crossrefs

Cf. A011782, A106356, A107428, A107429, A373306, A374147, A374726, A377823.

Programs

PARI

C_xz(s,N) = {my(x='x+O('x^N), g=if(#s <1,1, sum(i=1,#s, C_xz(s[^i],N+1) * x^(s[i])/(1-(x^(s[i]))*(z-1)) )/(1-sum(i=1,#s, x^(s[i])/(1-(x^(s[i]))*(z-1)))))); return(g)}
B_xz(N) = {my(x='x+O('x^N), j=1, h=0); while((j*(j+1))/2 <= N, for(k=0,N, h += C_xz([(1+k)..(j+k)], N+1)); j+=1); h}
P_xz(N) = Pol(B_xz(N), {x})
B_x(N) = {my(cx = deriv(P_xz(N),z), z=1); Vecrev(eval(cx))}
B_x(20)

Formula

G.f.: B(x) = d/dz Sum_{j>0} Sum_{k>=j} C({j..k},x,z)|{z=1} where C({s},x,z) = Sum{i in {s}} ( C({s}-{i},x,z)*(x^i)/(1-(x^i)*(z-1)) )/(1 - Sum_{i in {s}} (x^i)/(1-(x^i)*(z-1))) with C({},x,z) = 1.