Motivated by the recent asymptotic formula for the moment of the alternating sum of parts in partitions by Craig and Li, we study the moment of the alternating sum of parts in compositions. We establish closed formulas for this moment using techniques involving generating functions, matrix diagonalization, Krawtchouk polynomials, differential equations, and Faà di Bruno's formula. Our result is connected with some known integer sequences in the OEIS and admits a combinatorial interpretation by coin flipping.
Introduction
Partitions and compositions are fundamental concepts widely used in mathematics and sciences, including discrete mathematics, representation theory, symmetric function theory, statistical mechanics, genetics, etc. See, for example, the monographs by Andrews–Eriksson [1], Grinberg–Reiner [6], and Heubach–Mansour [7].
Recall that a composition is a sequence α=(α1,…,αℓ) of positive integers with parts α1,…,αℓ, length ℓ(α):=ℓ, and size of ∣α∣:=α1+⋯+αℓ. If ∣α∣=n then we say α is a composition of n and write α⊨n. It is well known that the number of compositions of n is 2n−1 since there is a bijection between these compositions and binary strings of length n−1.
A partitionλ=(λ1≥⋯≥λℓ>0) is a composition with weakly decreasing parts. If ∣λ∣=n then we say λ is a partition of n and write λ⊢n. Although partitions are prevalent in many fields, no closed formula is known for p(n), the number of partitions of n. This is in sharp contrast to the aforementioned simple formula 2n−1 for the number of compositions of n.
On the other hand, many results on partitions have analogues for compositions. For example, Euler’s partition theorem asserts that the number of partitions of n into odd parts equals the number of partitions of n into distinct parts. Analogously, the number of compositions of n with odd parts equals the number of compositions of n+1 with parts greater than one. In fact, both of these numbers are equal to the Fibonacci numberFn, which is defined recursively by Fn:=n for n=0,1 and Fn:=Fn−1+Fn−2 for n≥2; see Cayley [2], Grimaldi [5], and Stanley [13 Exercise 1.35]. Moreover, generalizations of Euler’s partition theorem by Glaisher and Franklin also have composition analogues by Munagi [11] and the second author [8], respectively. Another example is Legendre’s theorem (also a consequence of Euler’s pentagonal number theorem) on the number of even partitions of n into distinct parts minus the number of odd partitions of n into distinct parts, which admits a composition analogue by the second author [9].
This paper is motivated by studies on a(λ):=λ1−λ2+λ3−⋯+(−1)ℓ−1λℓ, the alternating sum of parts of a partition λ=(λ1,…,λℓ). It is known that a(λ) counts odd parts in the conjugate partition λt. For instance, (54331)t=54421 as shown by the Young diagram below, and its number of odd parts equals a(54331)=5−4+3−3+1=2.
Recently, Craig and Li [4] established the following asymptotic formula for the mth moment of a(λ):
Em(n):=λ⊢n∑p(n)a(λ)m∼(2π)m(6n)m/2logm(π6n).
It is natural to investigate a(α):=α1−α2+α3−⋯+(−1)ℓ−1αℓ, the alternating sum of parts of a composition α=(α1,…,αℓ), and its mth moment
Emc(n):=α⊨n∑2n−1a(α)m.
Table 1 shows a(α) for all compositions α⊨4 with mean E1c(4)=1 and second moment E2c(4)=4 (hence variance E2c(4)−E1c(4)2=3).
α
4
31
13
22
211
121
112
1111
a(α)
4
2
-2
0
2
0
2
0
Table 1. Alternating sum of parts in compositions of n=4
In an undergraduate research project mentored by the second author, Kitamura [10] computed Emc(n) for small values of m and n with result suggesting that Emc(n) is not only always a positive integer but also a polynomial in n:
Here Πm is the set of all partitions of {1,2,…,m}, ∣π∣ is the number of blocks of π, ∣B∣ is the size of the block B∈π, and (n−1)∣π∣:=(n−1)(n−2)⋯(n−∣π∣) is the falling factorial.
In particular, the mean and variance of a(α) for all α⊨n are E1c(n)=1 and E2c(n)−E1c(n)2=n−1, respectively. To prove the above theorems, we first obtain a generating function
α⊨n∑xa(α)=x(x+x−1)n−1.(3)
Then we apply the operator Ω:=xdxd exactly m times and derive the result in two ways, one using matrix diagonalization and the other using differential equations, both giving the first formula (1) of Emc(n). For the second formula (2), we apply a slightly different operator Ψ:=dxdx and use the chain rule for higher order derivatives, which is known as Faà di Bruno’s formula. We also show that the exponential generating function of Emc(n) is
m=0∑∞m!Emc(n)tm=etcoshn−1(t).(4)
Separating the even and odd powers in the above generating function, we obtain the following result.
Theorem 1.3. For m≥1, we have
E2mc(n)=i=1∑m(−1)m−iTm−1,i−1ni=nE2m−1c(n).
where Tm,i is the sequence [12 A085734] with exponential generating function secn(t).
In particular, E2mc(n) is a polynomial in n of degree m with leading term given by the double factorial and constant term given by the tangent number [12 A000182]. It would be interesting to explore the connections with various interpretations of the sequence Tm,i[12 A085734], such as the following:
As a polynomial of n, E2mc(n) coincides with the zeta polynomial for the poset of even-sized subsets of {1,2,…,2m} ordered by inclusion (see Remark 6.3).
The number Tm,i enumerates down-up permutations on {1,2,…,2m+2} with i+1 left-to-right maxima.
It might be worth checking some closely related sequences [12 A083061, A094665] as well. Finally, we provide a combinatorial interpretation for Emc(n) using a coin-flipping model.
Theorem 1.4. If we begin with n−1 coins all showing tails and flip at most one of them at each step, then the number of ways to have all tails right after m steps is Emc(n).
This paper is structured as follows. In Section 2 we prove the generating function (3) for the alternating sum of parts in compositions and show that applying certain differential operators leads to Emc(n). We then derive the first formula (1) of Emc(n) given in Theorem 1.1 by applying the operator Ω:=xdxd exactly m times to Eq. (3) and simplify the result in two ways: by matrix diagonalization in Section 3 and by differential equations in Section 4. In Section 5 we use the operator Ψ:=dxdx instead of Ω to establish the second formula (2) of Emc(n) appearing in Theorem 1.2 with the help of Faà di Bruno’s formula. In Section 6 we obtain the exponential generating function (4) of Emc(n) and prove Theorem 1.3. In Section 7 we prove Theorem 1.4, which provides a combinatorial interpretation for Emc(n) by flipping n−1 coins.
Generating function
In this section we establish the generating function (3) for the alternating sum of parts in compositions, from which we can derive Emc(n).
Proposition 2.1. For n≥1, we have
α⊨n∑xa(α)=x(x+x−1)n−1.
Analytic Proof. We can write down the generating function for compositions using a variable t to keep track of the parts and another variable x to keep track of the alternating sum of parts. For compositions with even lengths we have
Extracting the coefficient of tn gives the desired result. □
Combinatorial Proof. A compositions α⊨n corresponds to a row of n boxes with the first box colored black and each other box colored either black or white. The alternating sum of parts of α equals the number of black boxes minus the number of white boxes. The result follows immediately. □
Now we can derive Emc(n) by applying certain differential operators.
Corollary 2.2. Define Ω:=xdxd, Ψ:=dxdx, and u:=x+x−1. Then
Emc(n)=2n−11Ωm(xun−1)x=1=2n−11Ψm(un−1)x=1.
Proof. Applying the operator Ω exactly m times to Eq. (3) and substituting in x=1 we obtain
α⊨n∑a(α)m=Ωm(xun−1)x=1.
Divide both sides by 2n−1 gives Emc(n). It is similar for the operator Ψ. □
Proof of Theorem 1.1 by matrix diagonalization
In this section we derive the closed formula (1) of Emc(n) from Corollary 2.2 using matrix diagonalization. We first define v:=Ωu=x−x−1. Then Ωv=u and
Ω(xun−1)=xun−1+(n−1)xun−2v,
Ω(xun−2v)=xun−1+xun−2v+(n−2)xun−3v2,
Ω(xun−3v2)=2xun−2v+xun−3v2+(n−3)xun−4v3,
⋯⋯
Ω(xuvn−2)=(n−2)xu2vn−3+xuvn−2+xvn−1,
Ω(xvn−1)=(n−1)xuvn−2+xvn−1.
This is summarized in the proposition below, which is routine to prove.
The matrix A has eigenvalues λi:=n−2i for i=0,1,…,n−1, and the eigenvector associated with λi consists of the Krawtchouk polynomial
Pk,i=Pk,i(n−1):=j=0∑k(−1)j(ji)(k−jn−1−i).
In fact, the following recursive relation of the Krawtchouk polynomials [3 Theorem 4.1]
(k+1)Pk+1,i=(n−1−2i)Pk,i−(n−k)Pk−1,i
implies that AP=PΛ, where P:=[Pk,i]k,i=0n−1 and Λ=diag(λi)i=0n−1. For more properties of the Krawtchouk polynomials, see Coleman [3] (note that our Pk,i(n−1) is their Kk,n−1,2(i)).
We can also find Q:=P−1 using the orthogonality of the Krawtchouk polynomials [3 Prop. 3.1]:
Remark 3.5. Computations suggests that am,k involves the falling factorial(n−1)k:=(n−1)(n−2)⋯(n−k). In fact, we can define [bm,0,bm,1,…,bm,n−1]T=Bm[1,0,…,0]T where B=[Bk,j]k,j=0n−1 is defined by
Bkj:=⎩⎨⎧1,(k+1)(n−k−1),0,if k=j or k=j+1;if k=j−1;otherwise.
One can check that B=DAD−1, where D:=diag((n−k−1)!)k=0n−1. It follows that BDP=DAP=DPΛ. Thus we can apply Bm=DPΛmQD−1 to the initial vector [1,0,…,0]T and obtain
The differential operator L:=1+(n−1)z+(1−z2)dzd has eigenvalues λi:=n−2i and corresponding eigenfunctions wi(z):=(1−z)i(1+z)n−1−i for i=0,1,…,n−1. This can be obtained by solving the differential equation Lw=λw, which is equivalent to
(1−z2)dzdw=(λ−1−(n−1)z)w.
Separating w and z gives
w1dw=1−z2λ−1−(n−1)zdz.
Using partial fractions we obtain
∫w1dw=∫(2(1−z)λ−n+2(1+z)λ+n−2)dz.
With i:=−(λ−n)/2, we have
lnw=iln(1−z)+(n−1−i)ln(1+z)+c.
Exponentiate both sides gives the eigenfunctions wi=(1−z)i(1+z)n−1−i for i=0,1,…,n−1.
Now we expand C0(z)=1=(1−z+1+z)/2 in terms of these eigenfunctions:
for m≥1 and 0≤k≤m. Setting k=0 gives the same formula for Emc(n)=dm,0 as in Theorem 1.1. It might be interesting to study dm,k as a polynomial in n for k≥1 (see Table 2 for small values of m and k), although we cannot find its coefficients in OEIS [12].
m\k
0
1
2
3
4
5
0
1
1
1
1
2
n
2
1
3
3n−2
3n−2
3
1
4
3n2−2n
12n−16
6n−8
4
1
5
15n2−30n+16
15n2−30n+16
30n−60
10n−20
5
1
6
15n3−30n2+16n
90n2−300n+272
45n2−150n+136
60n−160
15n−40
6
Table 2. dm,k for small values of m and k
Remark 4.4. One may notice that Lemma 3.2 and Lemma 4.1 are identical. In fact, for any given positive integer n, we have cm,k=0 for k≥n by either the definition or the formula of cm,k, and am,k=cm,k for k=0,1,…,n−1. Similarly, bm,k=dm,k for k=0,1,…,n−1 and dm,k=0 for k≥n.
Proof of Theorem 1.2 by Faà di Bruno’s formula
In this section we derive another formula for Emc(n) using the following chain rule for higher order derivatives, which is known as Faà di Bruno’s formula.
Theorem 5.1 (Faà di Bruno’s formula). Applying dxd to a composite function f∘g exactly m times gives the following for all m≥1 (assuming the existence of all necessary derivatives of f and g):
dxmdm(f∘g)=π∈Πm∑(f(∣π∣)∘g)B∈π∏g∣B∣.
Here Πm is the set of all partitions of {1,2,…,m}, ∣π∣ is the number of blocks of π, and ∣B∣ is the size of the block B∈π.
We first apply the operator Ψ:=dxdx repeatedly to h(x):=(x+x−1)n−1 and obtain
Proof. By Corollary 2.2, Emc(n)=2n−11Ψm(h(x))∣x=1. We use Proposition 5.2 to calculate Ψm(h(x)). Since h(x)=f(g(x)) with f(u)=un−1 and u=g(x)=x+x−1, we can apply Faà di Bruno’s formula to h(k)(x). We have g′(x)=1−x−2, g′′(x)=2x−3, g′′′(x)=−2⋅3x−4, and in general,
g(k)(x)=(−1)kk!x−k−1for k≥2.
Thus g′(1)=0 and g(k)(1)=(−1)kk! for k≥2. We also have f(k)(u)=(n−1)(n−2)⋯(n−k)un−k−1, which becomes (n−1)k2n−k−1 when x=1. The desired formula for Emc(n) follows.
Exponential Generating function of Emc(n)
To better understand Emc(n), we study its exponential generating function.
Corollary 6.1. The exponential generating function of Emc(n) is
Proof. We have etcoshn−1(t)=coshn(t)+sinh(t)coshn−1(t). Thus the even powers of t in etcoshn−1(t) are given by coshn(t), that is,
m=0∑∞(2m)!E2mc(n)t2m=coshn(t).
Substituting in −n for n and −t2 for t2 we have
m=0∑∞(2m)!E2mc(−n)(−1)mt2m=cos−n(t)=secn(t).
This is the exponential generating function of the sequence Tm,i[12 A085734]. Therefore we have the desired expression of E2mc(n) as a polynomial in n.
On the other hand, the odd powers t in etcoshn−1(t) are given by sinh(t)coshn−1(t), and the derivative of coshn(t) is nsinh(t)coshn−1(t). Thus E2mc(n)=nE2m−1c(n). □
Remark 6.3. By Corollary 6.2, E2mc(n) is a polynomial in n with degree m, leading coefficient (2m−1)!!, and constant term given by the tangent number[12 A000182]. It agrees with the zeta polynomial for the poset of even-sized subsets of {1,2,…,2m} ordered by inclusion by a comment of Geoffrey Critzer (Apr 22 2023) in OEIS [12 A085734]. Another comment by David Callan (Oct 25 2004) in OEIS [12 A085734] asserts that Tm,k enumerates down-up permutations on {1,2,…,2m+2} with k+1 left-to-right maxima. For example, T1,1 counts the following 3 down-up permutations on {1,2,3,4} each with 2 left-to-right maxima: 2143, 3142, 3241. Also, Tm,k/2m is an integer with various properties [12 A083061, A094665]. It would be interesting to explore connections between these results and our definition of E2mc(n).
Proof of Theorem 1.4: combinatorial interpretation of Ecm(n)
In this section we build a coin-flipping model to interpret Emc(n) and the more general number cm,k as defined in Lemma 4.1.
Proposition 7.1.If we begin with n−1 coins all showing tails and flip at most one of them at each step, then the number of ways to have exactly k tails right after m steps is the number cm,k defined in Lemma 4.1.
Proof. Let cm,k′ be the number of ways to have exactly k heads right after m steps. One can check that c0,0′=1 and cm,k′=0 whenever k<0 or k>m. For m≥1, we have
cm,k′=(n−k)cm−1,k−1′+cm−1,k′+(k+1)cm−1,k+1′
since there are exactly k heads at step m if and only if one of the following occurs.
There are k−1 heads at step m−1, and one of the n−k tails is flipped at step m.
There are k heads at step m−1, and nothing is changed at step m.
There are k+1 heads at step m−1, one of which is flipped at step m.
It follows that cm,k′=cm,k. □
Taking k=0 gives Theorem 1.4: beginning with n−1 coins all showing tails and flipping at most one of them at each step, the number of ways to have all tails right after m steps is cm,0=Emc(n).
Remark 7.2. It seems interesting to study cm,k as a polynomial in n for k≥1, although we cannot find its coefficients in OEIS [12] (see Table 4 for small values of m and k). Note that cm,k=(n−1)kdm,k by Remark 3.5.
m\k
0
1
2
3
0
1
1
1
n−1
2
n
2n−2
n2−3n+2
3
3n−2
3n2−5n+2
3n2−9n+6
n3−6n2+11n−6
4
3n2−2n
12n2−28n+16
6n3−26n2+36n−16
4n3−24n2+44n−24
5
15n2−30n+16
15n3−45n2+46n−16
30n3−150n2+240n−120
10n4−80n3+230n2−280n+120
6
15n3−30n2+16n
90n3−390n2+572n−272
45n4−285n3+676n2−708n+272
60n4−520n3+1620n2−2120n+960
Table 4. cm,k for small values of m and k
Acknowledgment
The authors used SageMath to help discover and verify some of the results in this paper.
Department of Mathematics and Statistics, University of Nebraska at Kearney, NE 68849, USA Email address:[email protected]
Department of Mathematics and Statistics, University of Nebraska at Kearney, NE 68849, USA Email address:[email protected]
References
[1]G. E. Andrews and K. Eriksson, Integer partitions, Cambridge University Press, Cambridge, 2004.
[2]A. Cayley, Theorems in trigonometry and on partitions, Collected Mathematical Papers, vol. 10, 16.
[3]R. Coleman, On Krawtchouk polynomials, arXiv preprint (2011), arXiv:1101.1798v1.arxiv.org/abs/1101.1798
[4]W. Craig and R. Li, Distribution of alternating sums of parts in partitions, Ramanujan J. 68 (2025), no. 3, Paper No. 81, 24 pp.arxiv.org/abs/2501.17065
[5]R. P. Grimaldi, Compositions with odd summands, Congr. Numer. 142 (2000), 113–127.
[6]D. Grinberg and V. Reiner, Hopf algebras in combinatorics, arXiv preprint (2020), arXiv:1409.8356v7.
[7]S. Heubach and T. Mansour, Combinatorics of compositions and words, Discrete Mathematics and its Applications (Boca Raton), CRC Press, Boca Raton, FL, 2010.
[9]J. Huang, Even and odd compositions with restricted parts, J. Integer Seq. 27 (2024), no. 6, Art. 24.6.5, 10 pp.arxiv.org/abs/2405.03477
[10]S. Kitamura, Alternating Sums of Parts in Compositions, UNK Undergraduate Research Fellows Program, 2025–2026.
[11]A. O. Munagi, Euler-type identities for integer compositions via zig-zag graphs, Integers 12 (2012), Paper No. A60, 10 pp.
[12]N. J. A. Sloane, editor, The On-Line Encyclopedia of Integer Sequences, published electronically at https://oeis.org, 2018.
[13]R. P. Stanley, Enumerative combinatorics. Volume 1, second edition, Cambridge Studies in Advanced Mathematics, 49, Cambridge University Press, Cambridge, 2012.