betaFeedback

WorksMathematics

Alternating Sums in Compositions

Abstract

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,…,αℓ)\alpha=(\alpha_1,\ldots,\alpha_\ell) of positive integers with parts α1,…,αℓ\alpha_1,\ldots,\alpha_\ell, length ℓ(α):=ℓ\ell(\alpha):=\ell, and size of ∣α∣:=α1+⋯+αℓ|\alpha|:=\alpha_1+\cdots+\alpha_\ell. If ∣α∣=n|\alpha|=n then we say α\alpha is a composition of nn and write α⊨n\alpha\vDash n. It is well known that the number of compositions of nn is 2n−12^{n-1} since there is a bijection between these compositions and binary strings of length n−1n-1.

A partition λ=(λ1≥⋯≥λℓ>0)\lambda=(\lambda_1\geq\cdots\geq\lambda_\ell>0) is a composition with weakly decreasing parts. If ∣λ∣=n|\lambda|=n then we say λ\lambda is a partition of nn and write λ⊢n\lambda\vdash n. Although partitions are prevalent in many fields, no closed formula is known for p(n)p(n), the number of partitions of nn. This is in sharp contrast to the aforementioned simple formula 2n−12^{n-1} for the number of compositions of nn.

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 nn into odd parts equals the number of partitions of nn into distinct parts. Analogously, the number of compositions of nn with odd parts equals the number of compositions of n+1n+1 with parts greater than one. In fact, both of these numbers are equal to the Fibonacci number FnF_n, which is defined recursively by Fn:=nF_n:=n for n=0,1n=0,1 and Fn:=Fn−1+Fn−2F_n:=F_{n-1}+F_{n-2} for n≥2n\geq2; 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 nn into distinct parts minus the number of odd partitions of nn 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λℓa(\lambda):=\lambda_1-\lambda_2+\lambda_3-\cdots+(-1)^{\ell-1}\lambda_\ell, the alternating sum of parts of a partition λ=(λ1,…,λℓ)\lambda=(\lambda_1,\ldots,\lambda_\ell). It is known that a(λ)a(\lambda) counts odd parts in the conjugate partition λt\lambda^t. For instance, (54331)t=54421(54331)^t=54421 as shown by the Young diagram below, and its number of odd parts equals a(54331)=5−4+3−3+1=2a(54331)=5-4+3-3+1=2.

Figure 1.

Recently, Craig and Li [4] established the following asymptotic formula for the mmth moment of a(λ)a(\lambda):

Em(n):=∑λ⊢na(λ)mp(n)∼(6n)m/2(2π)mlog⁡m(6nπ).E_m(n):=\sum_{\lambda\vdash n}\frac{a(\lambda)^m}{p(n)}\sim\frac{(6n)^{m/2}}{(2\pi)^m}\log^m\left(\frac{\sqrt{6n}}{\pi}\right).

It is natural to investigate a(α):=α1−α2+α3−⋯+(−1)ℓ−1αℓa(\alpha):=\alpha_1-\alpha_2+\alpha_3-\cdots+(-1)^{\ell-1}\alpha_\ell, the alternating sum of parts of a composition α=(α1,…,αℓ)\alpha=(\alpha_1,\ldots,\alpha_\ell), and its mmth moment

Emc(n):=∑α⊨na(α)m2n−1.E_m^c(n):=\sum_{\alpha\models n}\frac{a(\alpha)^m}{2^{n-1}}.

Table 1 shows a(α)a(\alpha) for all compositions α⊨4\alpha\models4 with mean E1c(4)=1E_1^c(4)=1 and second moment E2c(4)=4E_2^c(4)=4 (hence variance E2c(4)−E1c(4)2=3E_2^c(4)-E_1^c(4)^2=3).

α\alpha43113222111211121111
a(α)a(\alpha)42-202020

Table 1. Alternating sum of parts in compositions of n=4n=4

In an undergraduate research project mentored by the second author, Kitamura [10] computed Emc(n)E_m^c(n) for small values of mm and nn with result suggesting that Emc(n)E_m^c(n) is not only always a positive integer but also a polynomial in nn:

E1c(n)=1,E2c(n)=n,E3c(n)=3n−2,E4c(n)=3n2−2n,E5c(n)=15n2−30n+16,E6c(n)=15n3−30n2+16n,E7c(n)=105n3−420n2+588n−272,E8c(n)=105n4−420n3+588n2−272n,E9c(n)=945n4−6300n3+16380n2−18960n+7936,E10c(n)=945n5−6300n4+16380n3−18960n2+7936n,E11c(n)=10395n6−103950n5+429660n4−893640n3+911328n2−353792.\begin{aligned} E_1^c(n)&=1,\\ E_2^c(n)&=n,\\ E_3^c(n)&=3n-2,\\ E_4^c(n)&=3n^2-2n,\\ E_5^c(n)&=15n^2-30n+16,\\ E_6^c(n)&=15n^3-30n^2+16n,\\ E_7^c(n)&=105n^3-420n^2+588n-272,\\ E_8^c(n)&=105n^4-420n^3+588n^2-272n,\\ E_9^c(n)&=945n^4-6300n^3+16380n^2-18960n+7936,\\ E_{10}^c(n)&=945n^5-6300n^4+16380n^3-18960n^2+7936n,\\ E_{11}^c(n)&=10395n^6-103950n^5+429660n^4-893640n^3+911328n^2-353792. \end{aligned}

Now we confirm the above polynomial expressions of Emc(n)E_m^c(n) for small values of mm by establishing two closed formulas of Emc(n)E_m^c(n) for all m≥0m\geq0 and n≥1n\geq1:

Theorem 1.1. For m≥0m\geq0 and n≥1n\geq1 we have

Emc(n)=12n−1∑i=0n−1(n−1i)(n−2i)m.(1)E_m^c(n)=\frac{1}{2^{n-1}}\sum_{i=0}^{n-1}\binom{n-1}{i}(n-2i)^m. \tag*{(1)}

Theorem 1.2. For m≥0m\geq0 and n≥1n\geq1 we have

Emc(n)=∑k=0mS(m+1,k+1)∑π∈ΠkB∈π⇒∣B∣>1(n−1)∣π∣2∣π∣∏B∈π(−1)∣B∣∣B∣!.(2)E_m^c(n)=\sum_{k=0}^{m}S(m+1,k+1)\sum_{\substack{\pi\in\Pi_k\\B\in\pi\Rightarrow|B|>1}}\frac{(n-1)_{|\pi|}}{2^{|\pi|}}\prod_{B\in\pi}(-1)^{|B|}|B|!. \tag*{(2)}

Here Πm\Pi_m is the set of all partitions of {1,2,…,m}\{1,2,\ldots,m\}, ∣π∣|\pi| is the number of blocks of π\pi, ∣B∣|B| is the size of the block B∈πB\in\pi, and (n−1)∣π∣:=(n−1)(n−2)⋯(n−∣π∣)(n-1)_{|\pi|}:=(n-1)(n-2)\cdots(n-|\pi|) is the falling factorial.

In particular, the mean and variance of a(α)a(\alpha) for all α⊨n\alpha\models n are E1c(n)=1E_1^c(n)=1 and E2c(n)−E1c(n)2=n−1E_2^c(n)-E_1^c(n)^2=n-1, respectively. To prove the above theorems, we first obtain a generating function

∑α⊨nxa(α)=x(x+x−1)n−1.(3)\sum_{\alpha\models n}x^{a(\alpha)}=x(x+x^{-1})^{n-1}. \tag*{(3)}

Then we apply the operator Ω:=xddx\Omega:=x\frac{d}{dx} exactly mm 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)E_m^c(n). For the second formula (2), we apply a slightly different operator Ψ:=ddxx\Psi:= \frac{d}{dx}x 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)E_m^c(n) is

∑m=0∞Emc(n)tmm!=etcosh⁡n−1(t).(4)\sum_{m=0}^{\infty}\frac{E_m^c(n)t^m}{m!}=e^t\cosh^{n-1}(t). \tag*{(4)}

Separating the even and odd powers in the above generating function, we obtain the following result.

Theorem 1.3. For m≥1m \ge1, we have

E2mc(n)=∑i=1m(−1)m−iTm−1,i−1ni=nE2m−1c(n).E_{2m}^c(n)=\sum_{i=1}^{m}(-1)^{m-i}T_{m-1,i-1}n^i=nE_{2m-1}^c(n).

where Tm,iT_{m,i} is the sequence [12 A085734] with exponential generating function sec⁡n(t)\sec^n(t).

In particular, E2mc(n)E_{2m}^c(n) is a polynomial in nn of degree mm 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,iT_{m,i} [12 A085734], such as the following:

  • As a polynomial of nn, E2mc(n)E_{2m}^c(n) coincides with the zeta polynomial for the poset of even-sized subsets of {1,2,…,2m}\{1,2,\ldots,2m\} ordered by inclusion (see Remark 6.3).

  • The number Tm,iT_{m,i} enumerates down-up permutations on {1,2,…,2m+2}\{1,2,\ldots,2m+2\} with i+1i+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)E_m^c(n) using a coin-flipping model.

Theorem 1.4. If we begin with n−1n-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 mm steps is Emc(n)E_m^c(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)E_m^c(n). We then derive the first formula (1) of Emc(n)E_m^c(n) given in Theorem 1.1 by applying the operator Ω:=xddx\Omega:= x\frac{d}{dx} exactly mm 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 Ψ:=ddxx\Psi:= \frac{d}{dx}x instead of Ω\Omega to establish the second formula (2) of Emc(n)E_m^c(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)E_m^c(n) and prove Theorem 1.3. In Section 7 we prove Theorem 1.4, which provides a combinatorial interpretation for Emc(n)E_m^c(n) by flipping n−1n-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)E_m^c(n).

Proposition 2.1. For n≥1n \ge1, we have

∑α⊨nxa(α)=x(x+x−1)n−1.\sum_{\substack{\alpha\models n}} x^{a(\alpha)}=x\left(x+x^{-1}\right)^{n-1}.

Analytic Proof. We can write down the generating function for compositions using a variable tt to keep track of the parts and another variable xx to keep track of the alternating sum of parts. For compositions with even lengths we have

∑n=0∞∑α⊨nℓ(α)=2ℓxa(α)tn=∑ℓ=0∞(xt+x2t2+⋯ )ℓ(x−1t+x−2t2+⋯ )ℓ.\sum_{n=0}^{\infty}\sum_{\substack{\alpha\models n\\ \ell(\alpha)=2\ell}}x^{a(\alpha)}t^n =\sum_{\ell=0}^{\infty}\left(xt+x^2t^2+\cdots\right)^\ell\left(x^{-1}t+x^{-2}t^2+\cdots\right)^\ell.

For compositions with odd lengths we have

∑n=0∞∑α⊨nℓ(α)=2ℓ+1xa(α)tn=∑ℓ=0∞(xt+x2t2+⋯ )ℓ(x−1t+x−2t2+⋯ )ℓ(xt+x2t2+⋯ ).\sum_{n=0}^{\infty}\sum_{\substack{\alpha\models n\\ \ell(\alpha)=2\ell+1}}x^{a(\alpha)}t^n =\sum_{\ell=0}^{\infty}\left(xt+x^2t^2+\cdots\right)^\ell\left(x^{-1}t+x^{-2}t^2+\cdots\right)^\ell\left(xt+x^2t^2+\cdots\right).

It follows that

∑n=0∞∑α⊨na(α)tn=∑ℓ=0∞(xt+x2t2+⋯ )ℓ(x−1t+x−2t2+⋯ )ℓ(1+xt+x2t2+⋯ )=(1−xt1−xt−x−1t1−x−1t)−1(1−xt)−1=(1−xt−t21−x−1t)−1=1−x−1t1−xt−x−1t=1+xt1−xt−x−1t=1+xt∑n=0∞(xt+x−1t)n.\begin{aligned} \sum_{n=0}^{\infty}\sum_{\alpha\vDash n} a(\alpha)t^n=\sum_{\ell=0}^{\infty}(xt+x^2t^2+\cdots)^\ell(x^{-1}t+x^{-2}t^2+\cdots)^\ell(1+xt+x^2t^2+\cdots) \\ &=\left(1-\frac{xt}{1-xt}-\frac{x^{-1}t}{1-x^{-1}t}\right)^{-1}(1-xt)^{-1} \\ &=\left(1-xt-\frac{t^2}{1-x^{-1}t}\right)^{-1} \\ &=\frac{1-x^{-1}t}{1-xt-x^{-1}t} \\ &=1+\frac{xt}{1-xt-x^{-1}t} \\ &=1+xt\sum_{n=0}^{\infty}(xt+x^{-1}t)^n. \end{aligned}

Extracting the coefficient of tnt^n gives the desired result. □

Combinatorial Proof. A compositions α⊨n\alpha\vDash n corresponds to a row of nn boxes with the first box colored black and each other box colored either black or white. The alternating sum of parts of α\alpha equals the number of black boxes minus the number of white boxes. The result follows immediately. □

Now we can derive Emc(n)E_m^c(n) by applying certain differential operators.

Corollary 2.2. Define Ω:=xddx\Omega:=x\frac{d}{dx}, Ψ:=ddxx\Psi:=\frac{d}{dx}x, and u:=x+x−1u:=x+x^{-1}. Then

Emc(n)=12n−1Ωm(xun−1)∣x=1=12n−1Ψm(un−1)∣x=1.E_m^c(n)=\left.\frac{1}{2^{n-1}}\Omega^m(xu^{n-1})\right|_{x=1}=\left.\frac{1}{2^{n-1}}\Psi^m(u^{n-1})\right|_{x=1}.

Proof. Applying the operator Ω\Omega exactly mm times to Eq. (3) and substituting in x=1x=1 we obtain

∑α⊨na(α)m=Ωm(xun−1)∣x=1.\sum_{\alpha\vDash n}a(\alpha)^m=\left.\Omega^m(xu^{n-1})\right|_{x=1}.

Divide both sides by 2n−12^{n-1} gives Emc(n)E_m^c(n). It is similar for the operator Ψ\Psi. □

Proof of Theorem 1.1 by matrix diagonalization

In this section we derive the closed formula (1) of Emc(n)E_m^c(n) from Corollary 2.2 using matrix diagonalization. We first define v:=Ωu=x−x−1v:=\Omega u=x-x^{-1}. Then Ωv=u\Omega v=u and

Ω(xun−1)=xun−1+(n−1)xun−2v,\Omega(xu^{n-1})=xu^{n-1}+(n-1)xu^{n-2}v,
Ω(xun−2v)=xun−1+xun−2v+(n−2)xun−3v2,\Omega(xu^{n-2}v)=xu^{n-1}+xu^{n-2}v+(n-2)xu^{n-3}v^2,
Ω(xun−3v2)=2xun−2v+xun−3v2+(n−3)xun−4v3,\Omega(xu^{n-3}v^2)=2xu^{n-2}v+xu^{n-3}v^2+(n-3)xu^{n-4}v^3,
⋯⋯\cdots\qquad\cdots
Ω(xuvn−2)=(n−2)xu2vn−3+xuvn−2+xvn−1,\Omega(xuv^{n-2})=(n-2)xu^2v^{n-3}+xuv^{n-2}+xv^{n-1},
Ω(xvn−1)=(n−1)xuvn−2+xvn−1.\Omega(xv^{n-1})=(n-1)xuv^{n-2}+xv^{n-1}.

This is summarized in the proposition below, which is routine to prove.

Proposition 3.1. For k=0,1,…,n−1k=0,1,\ldots,n-1, we have

Ω(xun−k−1vk)=kxun−kvk−1+xun−k−1vk+(n−k−1)xun−k−2vk+1.\Omega(xu^{n-k-1}v^k)=kxu^{n-k}v^{k-1}+xu^{n-k-1}v^k+(n-k-1)xu^{n-k-2}v^{k+1}.

A lemma follows immediately.

Lemma 3.2. For m≥0m\ge0, we have

Ωm(xun−1)=∑k=0n−1am,kxun−k−1vk\Omega^m(xu^{n-1})=\sum_{k=0}^{n-1}a_{m,k}xu^{n-k-1}v^k

where [am,0,am,1,…,am,n−1]T=Am[1,0,…,0]T[a_{m,0},a_{m,1},\ldots,a_{m,n-1}]^{T}=A^{m}[1,0,\ldots,0]^{T} with A=[Akj]k,j=0n−1A=[A_{k j}]_{k,j=0}^{n-1} defined by

Akj:={1,if j=k;k+1,if j=k+1;n−k,if j=k−1;0,otherwise.A_{k j}:=\begin{cases} 1, & \text{if } j=k;\\ k+1, & \text{if } j=k+1;\\ n-k, & \text{if } j=k-1;\\ 0, & \text{otherwise.} \end{cases}

The matrix AA has eigenvalues λi:=n−2i\lambda_i:=n-2i for i=0,1,…,n−1i=0,1,\ldots,n-1, and the eigenvector associated with λi\lambda_i consists of the Krawtchouk polynomial

Pk,i=Pk,i(n−1):=∑j=0k(−1)j(ij)(n−1−ik−j).P_{k,i}=P_{k,i}(n-1):=\sum_{j=0}^{k}(-1)^j\binom{i}{j}\binom{n-1-i}{k-j}.

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(k+1)P_{k+1,i}=(n-1-2i)P_{k,i}-(n-k)P_{k-1,i}

implies that AP=PΛAP=P\Lambda, where P:=[Pk,i]k,i=0n−1P:=[P_{k,i}]_{k,i=0}^{n-1} and Λ=diag⁡(λi)i=0n−1\Lambda=\operatorname{diag}(\lambda_i)_{i=0}^{n-1}. For more properties of the Krawtchouk polynomials, see Coleman [3] (note that our Pk,i(n−1)P_{k,i}(n-1) is their Kk,n−1,2(i)K_{k,n-1,2}(i)).

We can also find Q:=P−1Q:=P^{-1} using the orthogonality of the Krawtchouk polynomials [3 Prop. 3.1]:

∑i=0n−1(n−1i)Pk,iPj,i=2n−1(n−1j)δj,k.\sum_{i=0}^{n-1}\binom{n-1}{i}P_{k,i}P_{j,i}=2^{n-1}\binom{n-1}{j}\delta_{j,k}.

Here δi,j\delta_{i,j} is the Kronecker delta. We have

Qi,k=12n−1(n−1i)(n−1k)−1Pk,iQ_{i,k}=\frac{1}{2^{n-1}}\binom{n-1}{i}\binom{n-1}{k}^{-1}P_{k,i}

since

(PQ)kj=∑i=0n−1PkiQij=∑i=0n−112n−1(n−1i)(n−1j)−1PkiPji=δjk.(PQ)_{k j}=\sum_{i=0}^{n-1}P_{k i}Q_{i j}=\sum_{i=0}^{n-1}\frac{1}{2^{n-1}}\binom{n-1}{i}\binom{n-1}{j}^{-1}P_{k i}P_{j i}=\delta_{j k}.

In summary, we have the following result.

Proposition 3.3. The diagonalization of the matrix AA is given by A=PΛQA=P\Lambda Q.

Now we can apply Am=PΛmQA^{m}=P\Lambda^{m}Q to the initial vector [1,0,…,0]T[1,0,\ldots,0]^{T} to find am,ka_{m,k}.

Theorem 3.4. For m≥0m\ge0 and k=0,1,…,n−1k=0,1,\ldots,n-1 we have

am,k=12n−1∑i=0n−1(n−1i)(n−2i)m∑j=0k(−1)j(ij)(n−1−ik−j).a_{m,k}=\frac{1}{2^{n-1}}\sum_{i=0}^{n-1}\binom{n-1}{i}(n-2i)^{m}\sum_{j=0}^{k}(-1)^j\binom{i}{j}\binom{n-1-i}{k-j}.

Proof. This follows immediately from am,k=Pk,iQi,0λima_{m,k}=P_{k,i}Q_{i,0}\lambda_i^{m}, the kkth component of Am[1,0,…,0]TA^{m}[1,0,\ldots,0]^{T}. □

Now we are ready to provide the first proof of Theorem 1.1.

First proof of Theorem 1.1. Since u∣x=1=2u|_{x=1}=2 and v∣x=1=0v|_{x=1}=0, it follows from Corollary 2.2 and Lemma 3.2 that

Emc(n)=12n−1Ωm(xun−1)∣x=1=am,0.E_m^{c}(n)=\frac{1}{2^{n-1}}\Omega^{m}(xu^{n-1})\big|_{x=1}=a_{m,0}.

Thus taking k=0k=0 in Theorem 3.4 gives Theorem 1.1. □

Remark 3.5. Computations suggests that am,ka_{m,k} involves the falling factorial (n−1)k:=(n−1)(n−2)⋯(n−k)(n-1)_k:=(n-1)(n-2)\cdots(n-k). In fact, we can define [bm,0,bm,1,…,bm,n−1]T=Bm[1,0,…,0]T[b_{m,0},b_{m,1},\ldots,b_{m,n-1}]^{T}=B^{m}[1,0,\ldots,0]^{T} where B=[Bk,j]k,j=0n−1B=[B_{k,j}]_{k,j=0}^{n-1} is defined by

Bkj:={1,if k=j or k=j+1;(k+1)(n−k−1),if k=j−1;0,otherwise.B_{k j}:=\begin{cases} 1, & \text{if } k=j\text{ or }k=j+1;\\ (k+1)(n-k-1), & \text{if } k=j-1;\\ 0, & \text{otherwise.} \end{cases}

One can check that B=DAD−1B=DAD^{-1}, where D:=diag⁡((n−k−1)!)k=0n−1D:=\operatorname{diag}((n-k-1)!)_{k=0}^{n-1}. It follows that BDP=DAP=DPΛBDP=DAP=DP\Lambda. Thus we can apply Bm=DPΛmQD−1B^{m}=DP\Lambda^{m}QD^{-1} to the initial vector [1,0,…,0]T[1,0,\ldots,0]^{T} and obtain

bm,k=∑i=0m(DP)k,i(QD−1)i,0λim=am,k(n−1)k=12n−1(n−1)k∑i=0n−1(n−1i)(n−2i)m∑j=0k(−1)j(ij)(n−1−ik−j).\begin{aligned} b_{m,k}=\sum_{i=0}^{m}(DP)_{k,i}(QD^{-1})_{i,0}\lambda_{i}^{m}=\frac{a_{m,k}}{(n-1)_{k}} \\ &=\frac{1}{2^{n-1}(n-1)^{k}}\sum_{i=0}^{n-1}\binom{n-1}{i}(n-2i)^{m}\sum_{j=0}^{k}(-1)^{j}\binom{i}{j}\binom{n-1-i}{k-j}. \end{aligned}

Setting k=0k=0 gives the same formula for Emc(n)=bm,0E^{c}_{m}(n)=b_{m,0} as in Theorem 1.1.

Proof of Theorem 1.1 by differential equations

We can also use differential equation techniques to derive the closed formula (1) of Emc(n)E^{c}_{m}(n) in Theorem 1.1.

Lemma 4.1. Define c0,0:=1c_{0,0}:=1, cm,k:=0c_{m,k}:=0 whenever k<0k<0 or m<km<k, and

cm,k:=(n−k)cm−1,k−1+cm−1,k+(k+1)cm−1,k+1c_{m,k}:=(n-k)c_{m-1,k-1}+c_{m-1,k}+(k+1)c_{m-1,k+1}

for m≥1m\geq1 and 0≤k≤m0\leq k\leq m. Then

Ωm(xun−1)=∑k=0mcm,kxun−k−1vk.\Omega^{m}(xu^{n-1})=\sum_{k=0}^{m}c_{m,k}xu^{n-k-1}v^{k}.

Proof. We prove the result by induction on mm. It is trivial when m=0m=0. Assume the result holds for m≥0m\geq0. This together with Proposition 3.1 implies

Ωm+1(xun−1)=∑k=0mcm,kΩ(xun−k−1vk)=∑k=0mcm,k(kxun−kvk−1+xun−k−1vk+(n−k−1)xun−k−2vk+1)=∑k=0m+1((n−k)cm,k−1+cm,k+(k+1)cm,k+1)xun−k−1vk=∑k=0m+1cm+1,kxun−k−1vk.\begin{aligned} \Omega^{m+1}(xu^{n-1})&=\sum_{k=0}^{m}c_{m,k}\Omega(xu^{n-k-1}v^{k})\\ &=\sum_{k=0}^{m}c_{m,k}\left(kxu^{n-k}v^{k-1}+xu^{n-k-1}v^{k}+(n-k-1)xu^{n-k-2}v^{k+1}\right)\\ &=\sum_{k=0}^{m+1}\left((n-k)c_{m,k-1}+c_{m,k}+(k+1)c_{m,k+1}\right)xu^{n-k-1}v^{k}\\ &=\sum_{k=0}^{m+1}c_{m+1,k}xu^{n-k-1}v^{k}. \end{aligned}

We use differential equations to derive a closed formula for cm,kc_{m,k}, which agrees with the formula of am,ka_{m,k} in Theorem 3.4.

Theorem 4.2. For m≥0m\geq0 and 0≤k≤m0\leq k\leq m we have

cm,k=12n−1∑i=0n−1(n−1i)(n−2i)m∑j=0k(−1)j(ij)(n−1−ik−j).c_{m,k}=\frac{1}{2^{n-1}}\sum_{i=0}^{n-1}\binom{n-1}{i}(n-2i)^{m}\sum_{j=0}^{k}(-1)^{j}\binom{i}{j}\binom{n-1-i}{k-j}.

Proof. Let Cm(z):=∑k=0mc(m,k)zkC_{m}(z):=\sum_{k=0}^{m}c(m,k)z^{k}. We have

Cm(z)=∑k(n−k)cm−1,k−1zk+∑kcm−1,kzk+∑k(k+1)cm−1,k+1zk=(n−1)zCm−1(z)−z2Cm−1′(z)+Cm−1(z)+Cm−1′(z)=(1+(n−1)z)Cm−1(z)+(1−z2)Cm−1′(z).\begin{aligned} C_{m}(z)&=\sum_{k}(n-k)c_{m-1,k-1}z^{k}+\sum_{k}c_{m-1,k}z^{k}+\sum_{k}(k+1)c_{m-1,k+1}z^{k}\\ &=(n-1)zC_{m-1}(z)-z^{2}C'_{m-1}(z)+C_{m-1}(z)+C'_{m-1}(z)\\ &=(1+(n-1)z)C_{m-1}(z)+(1-z^{2})C'_{m-1}(z). \end{aligned}

The differential operator L:=1+(n−1)z+(1−z2)ddzL:=1+(n-1)z+(1-z^{2})\frac{d}{dz} has eigenvalues λi:=n−2i\lambda_{i}:=n-2i and corresponding eigenfunctions wi(z):=(1−z)i(1+z)n−1−iw_{i}(z):=(1-z)^{i}(1+z)^{n-1-i} for i=0,1,…,n−1i=0,1,\ldots,n-1. This can be obtained by solving the differential equation Lw=λwLw=\lambda w, which is equivalent to

(1−z2)dwdz=(λ−1−(n−1)z)w.(1-z^{2})\frac{dw}{dz}=(\lambda-1-(n-1)z)w.

Separating ww and zz gives

1w dw=λ−1−(n−1)z1−z2 dz.\frac{1}{w}\,dw=\frac{\lambda-1-(n-1)z}{1-z^2}\,dz.

Using partial fractions we obtain

∫1w dw=∫(λ−n2(1−z)+λ+n−22(1+z)) dz.\int\frac{1}{w}\,dw=\int\left(\frac{\lambda-n}{2(1-z)}+\frac{\lambda+n-2}{2(1+z)}\right)\,dz.

With i:=−(λ−n)/2i:=-(\lambda-n)/2, we have

ln⁡w=iln⁡(1−z)+(n−1−i)ln⁡(1+z)+c.\ln w=i\ln(1-z)+(n-1-i)\ln(1+z)+c.

Exponentiate both sides gives the eigenfunctions wi=(1−z)i(1+z)n−1−iw_i=(1-z)^i(1+z)^{n-1-i} for i=0,1,…,n−1i=0,1,\ldots,n-1.

Now we expand C0(z)=1=(1−z+1+z)/2C_0(z)=1=(1-z+1+z)/2 in terms of these eigenfunctions:

1=12n−1(1−z+1+z)n−1=12n−1∑i=0n−1(n−1i)(1−z)i(1+z)n−1−i.\begin{aligned} 1=\frac{1}{2^{n-1}}(1-z+1+z)^{n-1} \\ &=\frac{1}{2^{n-1}}\sum_{i=0}^{n-1}\binom{n-1}{i}(1-z)^i(1+z)^{n-1-i}. \end{aligned}

Applying LmL^m amounts to multiplying each eigenfunction by the mmth power of the associated eigenvalue:

Cm(z)=Lm(1)=12n−1∑i=0n−1(n−1i)(n−2i)m(1−z)i(1+z)n−1−i.C_m(z)=L^m(1)=\frac{1}{2^{n-1}}\sum_{i=0}^{n-1}\binom{n-1}{i}(n-2i)^m(1-z)^i(1+z)^{n-1-i}.

Extracting the coefficient of zkz^k gives the desired formula for cm,kc_{m,k}. □

Now we present another proof of Theorem 1.1.

Second Proof of Theorem 1.1. We have Emc(n)=12n−1Ωm(xun−1)∣x=1=cm,0E_m^c(n)=\left.\frac{1}{2^{n-1}}\Omega^m(xu^{n-1})\right|_{x=1}=c_{m,0} by Corollary 2.2 and Lemma 4.1. Setting k=0k=0 in Theorem 4.2 proves Theorem 1.1. □

Remark 4.3. One can shows by induction on mm that

Ωm(xun−1)=∑k=0m(n−1)kdm,kxun−k−1vk,\Omega^m(xu^{n-1})=\sum_{k=0}^{m}(n-1)_k d_{m,k}xu^{n-k-1}v^k,

where d0,0:=1d_{0,0}:=1, dm,k:=0d_{m,k}:=0 whenever k<0k<0 or m<km<k, and

dm,k:=dm−1,k−1+dm−1,k+(k+1)(n−k−1)dm−1,k+1d_{m,k}:=d_{m-1,k-1}+d_{m-1,k}+(k+1)(n-k-1)d_{m-1,k+1}

for m≥1m\ge1 and 0≤k≤m0\le k\le m. Setting k=0k=0 gives the same formula for Emc(n)=dm,0E_m^c(n)=d_{m,0} as in Theorem 1.1. It might be interesting to study dm,kd_{m,k} as a polynomial in nn for k≥1k\ge1 (see Table 2 for small values of mm and kk), although we cannot find its coefficients in OEIS [12].

m\km\backslash k012345
01
111
2nn21
33n−23n-23n−23n-231
43n2−2n3n^2-2n12n−1612n-166n−86n-841
515n2−30n+1615n^2-30n+1615n2−30n+1615n^2-30n+1630n−6030n-6010n−2010n-2051
615n3−30n2+16n15n^3-30n^2+16n90n2−300n+27290n^2-300n+27245n2−150n+13645n^2-150n+13660n−16060n-16015n−4015n-406

Table 2. dm,kd_{m,k} for small values of mm and kk

Remark 4.4. One may notice that Lemma 3.2 and Lemma 4.1 are identical. In fact, for any given positive integer nn, we have cm,k=0c_{m,k}=0 for k≥nk\ge n by either the definition or the formula of cm,kc_{m,k}, and am,k=cm,ka_{m,k}=c_{m,k} for k=0,1,…,n−1k=0,1,\ldots,n-1. Similarly, bm,k=dm,kb_{m,k}=d_{m,k} for k=0,1,…,n−1k=0,1,\ldots,n-1 and dm,k=0d_{m,k}=0 for k≥nk\ge n.

Proof of Theorem 1.2 by Faà di Bruno’s formula

In this section we derive another formula for Emc(n)E_m^c(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 ddx\frac{d}{dx} to a composite function f∘gf \circ g exactly mm times gives the following for all m≥1m \ge1 (assuming the existence of all necessary derivatives of ff and gg):

dmdxm(f∘g)=∑π∈Πm(f(∣π∣)∘g)∏B∈πg∣B∣.\frac{d^m}{dx^m}(f \circ g)=\sum_{\pi\in\Pi_m}\left(f^{(|\pi|)}\circ g\right)\prod_{B\in\pi}g^{|B|}.

Here Πm\Pi_m is the set of all partitions of {1,2,…,m}\{1,2,\ldots,m\}, ∣π∣|\pi| is the number of blocks of π\pi, and ∣B∣|B| is the size of the block B∈πB\in\pi.

We first apply the operator Ψ:=ddxx\Psi:=\frac{d}{dx}x repeatedly to h(x):=(x+x−1)n−1h(x):=(x+x^{-1})^{n-1} and obtain

Ψ(h(x))=h(x)+xh′(x),\Psi(h(x))=h(x)+xh'(x),
Ψ2(h(x))=h(x)+xh′(x)+2xh′(x)+x2h′′(x)=h(x)+3xh′(x)+x2h′′(x),\Psi^2(h(x))=h(x)+xh'(x)+2xh'(x)+x^2h''(x) =h(x)+3xh'(x)+x^2h''(x),
Ψ3(h(x))=h(x)+xh′(x)+6xh′(x)+3x2h′′(x)+3x2h′′(x)+x3h′′′(x)=h(x)+7xh′(x)+6x2h′′(x)+x3h′′′(x),\Psi^3(h(x))=h(x)+xh'(x)+6xh'(x)+3x^2h''(x)+3x^2h''(x)+x^3h'''(x) =h(x)+7xh'(x)+6x^2h''(x)+x^3h'''(x),

and so on. In general, we have the following result.

Proposition 5.2. Let S(m,k)S(m,k) be the Stirling number of the second kind. Then

Ψm(h(x))=∑k=0mS(m+1,k+1)xkh(k)(x).\Psi^m(h(x))=\sum_{k=0}^{m}S(m+1,k+1)x^kh^{(k)}(x).

Proof. The result is trivial when m=0m=0. For m≥1m\ge1, using the inductive hypothesis we have

Ψm(h(x))=∑k=0m−1S(m,k+1)Ψ(xkh(k)(x))=∑k=0m−1S(m,k+1)((k+1)xkh(k)(x)+xk+1h(k+1)(x))=∑k=0m(S(m,k)+(k+1)S(m,k+1))xkh(k)(x)=∑k=0mS(m+1,k+1)xkh(k)(x).\begin{aligned} \Psi^m(h(x))=\sum_{k=0}^{m-1}S(m,k+1)\Psi\left(x^kh^{(k)}(x)\right) \\ &=\sum_{k=0}^{m-1}S(m,k+1)\left((k+1)x^kh^{(k)}(x)+x^{k+1}h^{(k+1)}(x)\right) \\ &=\sum_{k=0}^{m}\left(S(m,k)+(k+1)S(m,k+1)\right)x^kh^{(k)}(x) \\ &=\sum_{k=0}^{m}S(m+1,k+1)x^kh^{(k)}(x). \end{aligned}

Now we provide a proof for Theorem 1.2, which is rephrased below.

Theorem 5.3. Using the falling factorial (n−k):=(n−1)(n−2)⋯(n−k)(n-k):=(n-1)(n-2)\cdots(n-k), we have

Emc(n)=∑k=0mS(m+1,k+1)∑π∈ΠkB∈π⇒∣B∣>1(n−1)∣π∣2∣π∣∏B∈π(−1)∣B∣∣B∣!.E_m^c(n)=\sum_{k=0}^{m}S(m+1,k+1)\sum_{\substack{\pi\in\Pi_k\\B\in\pi\Rightarrow|B|>1}}\frac{(n-1)_{|\pi|}}{2^{|\pi|}}\prod_{B\in\pi}(-1)^{|B|}|B|!.

Proof. By Corollary 2.2, Emc(n)=12n−1Ψm(h(x))∣x=1E_m^c(n)=\frac{1}{2^{n-1}}\left.\Psi^m(h(x))\right|_{x=1}. We use Proposition 5.2 to calculate Ψm(h(x))\Psi^m(h(x)). Since h(x)=f(g(x))h(x)=f(g(x)) with f(u)=un−1f(u)=u^{n-1} and u=g(x)=x+x−1u=g(x)=x+x^{-1}, we can apply Faà di Bruno’s formula to h(k)(x)h^{(k)}(x). We have g′(x)=1−x−2g'(x)=1-x^{-2}, g′′(x)=2x−3g''(x)=2x^{-3}, g′′′(x)=−2⋅3x−4g'''(x)=-2\cdot3x^{-4}, and in general,

g(k)(x)=(−1)kk!x−k−1for k≥2.g^{(k)}(x)=(-1)^kk!x^{-k-1}\qquad\text{for }k\ge2.

Thus g′(1)=0g'(1)=0 and g(k)(1)=(−1)kk!g^{(k)}(1)=(-1)^kk! for k≥2k\ge2. We also have f(k)(u)=(n−1)(n−2)⋯(n−k)un−k−1f^{(k)}(u)=(n-1)(n-2)\cdots(n-k)u^{n-k-1}, which becomes (n−1)k2n−k−1(n-1)_k2^{n-k-1} when x=1x=1. The desired formula for Emc(n)E_m^c(n) follows.

Exponential Generating function of Emc(n)E_m^c(n)

To better understand Emc(n)E_m^c(n), we study its exponential generating function.

Corollary 6.1. The exponential generating function of Emc(n)E_m^c(n) is

∑m=0∞Emc(n)tmm!=etcosh⁡n−1(t).\sum_{m=0}^{\infty}\frac{E_m^c(n)t^m}{m!}=e^t\cosh^{n-1}(t).

Proof. By Theorem 1.1 we have

∑m=0∞Emc(n)tmm!=12n−1∑m=0∞∑i=0n−1(n−1i)(n−2i)mtmm!=12n−1∑i=0n−1(n−1i)∑m=0∞(n−2i)mtmm!=12n−1∑i=0n−1(n−1i)e(n−2i)t=ent2n−1(1+e−2t)n−1=etcosh⁡n−1(t).\begin{aligned} \sum_{m=0}^{\infty}\frac{E_m^c(n)t^m}{m!} =\frac{1}{2^{n-1}}\sum_{m=0}^{\infty}\sum_{i=0}^{n-1}\binom{n-1}{i}\frac{(n-2i)^m t^m}{m!} \\ &=\frac{1}{2^{n-1}}\sum_{i=0}^{n-1}\binom{n-1}{i}\sum_{m=0}^{\infty}\frac{(n-2i)^m t^m}{m!} \\ &=\frac{1}{2^{n-1}}\sum_{i=0}^{n-1}\binom{n-1}{i}e^{(n-2i)t} \\ &=\frac{e^{nt}}{2^{n-1}}(1+e^{-2t})^{n-1} \\ &=e^t\cosh^{n-1}(t). \end{aligned}

Now we can identify the coefficients of Emc(n)E_m^c(n) as a polynomial in nn with a sequence Tm,kT_{m,k} [12 A085734] defined by T0,0:=1T_{0,0}:=1 and

Tm,k:=∑j=0m−k2j(k+jj+1)+(k+j+1j+1)Tm−1,k+j−1.T_{m,k}:=\sum_{j=0}^{m-k}2^j\binom{k+j}{j+1}+\binom{k+j+1}{j+1}T_{m-1,k+j-1}.

For small values of mm and kk, see Table 3.

m\im \backslash i012345
01
123
2163015
3272588420105
4793618960163806300945
535379291132889364042966010395010395

Table 3. Tm,kT_{m,k} for small values of mm and kk

Corollary 6.2. For m≥1m\geq1, we have

E2mc(n)=∑i=1m(−1)m−iTm−1,i−1ni=nE2m−1c(n).E_{2m}^c(n)=\sum_{i=1}^{m}(-1)^{m-i}T_{m-1,i-1}n^i=nE_{2m-1}^c(n).

Proof. We have etcosh⁡n−1(t)=cosh⁡n(t)+sinh⁡(t)cosh⁡n−1(t)e^t\cosh^{n-1}(t)=\cosh^n(t)+\sinh(t)\cosh^{n-1}(t). Thus the even powers of tt in etcosh⁡n−1(t)e^t\cosh^{n-1}(t) are given by cosh⁡n(t)\cosh^n(t), that is,

∑m=0∞E2mc(n)t2m(2m)!=cosh⁡n(t).\sum_{m=0}^{\infty}\frac{E_{2m}^c(n)t^{2m}}{(2m)!}=\cosh^n(t).

Substituting in −n-n for nn and −t2-t^2 for t2t^2 we have

∑m=0∞E2mc(−n)(−1)mt2m(2m)!=cos⁡−n(t)=sec⁡n(t).\sum_{m=0}^{\infty}\frac{E_{2m}^c(-n)(-1)^m t^{2m}}{(2m)!}=\cos^{-n}(t)=\sec^n(t).

This is the exponential generating function of the sequence Tm,iT_{m,i} [12 A085734]. Therefore we have the desired expression of E2mc(n)E_{2m}^c(n) as a polynomial in nn.

On the other hand, the odd powers tt in etcosh⁡n−1(t)e^t\cosh^{n-1}(t) are given by sinh⁡(t)cosh⁡n−1(t)\sinh(t)\cosh^{n-1}(t), and the derivative of cosh⁡n(t)\cosh^n(t) is nsinh⁡(t)cosh⁡n−1(t)n\sinh(t)\cosh^{n-1}(t). Thus E2mc(n)=nE2m−1c(n)E^c_{2m}(n)=nE^c_{2m-1}(n). □

Remark 6.3. By Corollary 6.2, E2mc(n)E^c_{2m}(n) is a polynomial in nn with degree mm, leading coefficient (2m−1)!!(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}\{1,2,\ldots,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,kT_{m,k} enumerates down-up permutations on {1,2,…,2m+2}\{1,2,\ldots,2m+2\} with k+1k+1 left-to-right maxima. For example, T1,1T_{1,1} counts the following 3 down-up permutations on {1,2,3,4}\{1,2,3,4\} each with 2 left-to-right maxima: 2143, 3142, 3241. Also, Tm,k/2mT_{m,k}/2^m 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)E^c_{2m}(n).

Proof of Theorem 1.4: combinatorial interpretation of Ecm(n)

In this section we build a coin-flipping model to interpret Emc(n)E^c_m(n) and the more general number cm,kc_{m,k} as defined in Lemma 4.1.

Proposition 7.1. If we begin with n−1n-1 coins all showing tails and flip at most one of them at each step, then the number of ways to have exactly kk tails right after mm steps is the number cm,kc_{m,k} defined in Lemma 4.1.

Proof. Let cm,k′c'_{m,k} be the number of ways to have exactly kk heads right after mm steps. One can check that c0,0′=1c'_{0,0}=1 and cm,k′=0c'_{m,k}=0 whenever k<0k<0 or k>mk>m. For m≥1m\ge1, we have

cm,k′=(n−k)cm−1,k−1′+cm−1,k′+(k+1)cm−1,k+1′c'_{m,k}=(n-k)c'_{m-1,k-1}+c'_{m-1,k}+(k+1)c'_{m-1,k+1}

since there are exactly kk heads at step mm if and only if one of the following occurs.

  • There are k−1k-1 heads at step m−1m-1, and one of the n−kn-k tails is flipped at step mm.

  • There are kk heads at step m−1m-1, and nothing is changed at step mm.

  • There are k+1k+1 heads at step m−1m-1, one of which is flipped at step mm.

It follows that cm,k′=cm,kc'_{m,k}=c_{m,k}. □

Taking k=0k=0 gives Theorem 1.4: beginning with n−1n-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 mm steps is cm,0=Emc(n)c_{m,0}=E^c_m(n).

Remark 7.2. It seems interesting to study cm,kc_{m,k} as a polynomial in nn for k≥1k\ge1, although we cannot find its coefficients in OEIS [12] (see Table 4 for small values of mm and kk). Note that cm,k=(n−1)kdm,kc_{m,k}=(n-1)^k d_{m,k} by Remark 3.5.

m\km\backslash k0123
01
11n−1n-1
2nn2n−22n-2n2−3n+2n^2-3n+2
33n−23n-23n2−5n+23n^2-5n+23n2−9n+63n^2-9n+6n3−6n2+11n−6n^3-6n^2+11n-6
43n2−2n3n^2-2n12n2−28n+1612n^2-28n+166n3−26n2+36n−166n^3-26n^2+36n-164n3−24n2+44n−244n^3-24n^2+44n-24
515n2−30n+1615n^2-30n+1615n3−45n2+46n−1615n^3-45n^2+46n-1630n3−150n2+240n−12030n^3-150n^2+240n-12010n4−80n3+230n2−280n+12010n^4-80n^3+230n^2-280n+120
615n3−30n2+16n15n^3-30n^2+16n90n3−390n2+572n−27290n^3-390n^2+572n-27245n4−285n3+676n2−708n+27245n^4-285n^3+676n^2-708n+27260n4−520n3+1620n2−2120n+96060n^4-520n^3+1620n^2-2120n+960

Table 4. cm,kc_{m,k} for small values of mm and kk

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. [1]G. E. Andrews and K. Eriksson, Integer partitions, Cambridge University Press, Cambridge, 2004.
  2. [2]A. Cayley, Theorems in trigonometry and on partitions, Collected Mathematical Papers, vol. 10, 16.
  3. [3]R. Coleman, On Krawtchouk polynomials, arXiv preprint (2011), arXiv:1101.1798v1.arxiv.org/abs/1101.1798
  4. [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. [5]R. P. Grimaldi, Compositions with odd summands, Congr. Numer. 142 (2000), 113–127.
  6. [6]D. Grinberg and V. Reiner, Hopf algebras in combinatorics, arXiv preprint (2020), arXiv:1409.8356v7.
  7. [7]S. Heubach and T. Mansour, Combinatorics of compositions and words, Discrete Mathematics and its Applications (Boca Raton), CRC Press, Boca Raton, FL, 2010.
  8. [8]J. Huang, Compositions with restricted parts, Discrete Math. 343 (2020), no. 7, 111875, 9 pp.arxiv.org/abs/1812.11010
  9. [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. [10]S. Kitamura, Alternating Sums of Parts in Compositions, UNK Undergraduate Research Fellows Program, 2025–2026.
  11. [11]A. O. Munagi, Euler-type identities for integer compositions via zig-zag graphs, Integers 12 (2012), Paper No. A60, 10 pp.
  12. [12]N. J. A. Sloane, editor, The On-Line Encyclopedia of Integer Sequences, published electronically at https://oeis.org, 2018.
  13. [13]R. P. Stanley, Enumerative combinatorics. Volume 1, second edition, Cambridge Studies in Advanced Mathematics, 49, Cambridge University Press, Cambridge, 2012.

Paper details

vlnc:W_d6f8eta2
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 9

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents