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,4

Comments

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

Links

Table of n, a(n) for n=0..34.

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.

Example

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.

Prog

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

Crossrefs

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

Sequence in context: A245264 A327477 A350294 * A052971 A364423 A289443

Adjacent sequences: A380173 A380174 A380175 * A380177 A380178 A380179

Keyword

nonn,new

Author

John Tyler Rascoe, Jan 14 2025

Status

approved