[Math] Generating Functions and Linear Diophantine Inequalities

Question

The following exercise is from Analytic Combinatorics by Philippe Flajolet and Robert Sedgewick, page 46.

A $k$-composition of $n$ is an ordered $k$-tuple of non-negative integers whose sum is $n$.

Consider the class $\mathcal{F}$ of compositions of integers into four summands $(x_1, x_2, x_3, x_4)$ such that
$$ x_1 \ge 0, \, x_2 \ge 2 x_1, \, x_3 \ge 2 x_2, x_4 \ge 2 x_3,$$
where the $x_j$ are in $\mathbb{Z}_{\ge 0}$.The ordinary generating function is
$$F(z) = \dfrac{1}{(1 − z)(1 − z^3)(1 − z^7)(1 − z^{15})}.$$

Generalize to $r \ge 4$ summands and a similar system of inequalities. Work out elementarily the OGFs corresponding to the following systems of inequalities:
$$\{x_1+x_2 \le x_3\},\,\, \{x_1 + x_2 \ge x_3\},\,\, \{x_1+x_2 \le x_3 + x_4\}, \,\,\{x_1 \ge x_2, x_2 \ge x_3,x_3 \le x_4\}.$$
More generally, the OGF of compositions into a fixed number of summands (in $\mathbb{Z} \ge 0$), con- strained to satisfy a linear system of equations and inequalities with coefficients in $\mathbb{Z}$, is rational; its denominator is a product of factors of the form $(1 − z^j)$.

I am looking for help developing a systematic approach to determine the generating functions of these types of inequalities. I have tried working out the first two, and my proposed OGF's are respectively

$$\dfrac{1}{(1-z)(1-z^2)^2}$$
and
$$\dfrac{1 + z + z^2}{(1-z)(1-z^2)^2}$$

However, I did not use the so-called symbolic method, instead I looked at a few elementary cases and then reasoned about what the coefficients should be in a combinatorial manner. If you are experienced with generating functions, I would truly appreciate any insight you could shed on these problems.

Even if you approach the problem differently than Sedgewick, but can still give combinatorial interpretations of each of the generating functions corresponding to the above restricted partitions, I would accept your answer. All I really want is help building intuition on this subject.

Thank you.

Answer 1

Changes 2014-09-07:

• I removed the section explaining Flajolets symbolic method since it was not helpful for @A.E and streamlined the other text.

• I completed the examples with the constraints and added a few notes about the relationship of the constraints and the related generating functions.

---

The following answer is based upon the paper Five Guidelines for Partition Analysis from Sylvie Corteel, Sunyoung Lee and Carla Savage which provides a systematic treatment to find generating functions for linear diophantine equations when certain constraints (systems of linear inequalities) are specified.

• First we calculate the generating functions for the number of compositions with the four constraints

\begin{align*} &\{x_1+x_2 \leq x_3\}\\ &\{x_1 + x_2 \geq x_3\}\\ &\{x_1+x_2\leq x_3+x_4\}\\ &\{x_2\leq x_1,x_3\leq x_2,x_3\leq x_4\} \end{align*}

• Then you may find some notes about the method presented in the paper and about the relationship between the constraints and the corresponding generating functions.

---

Example 1: We consider the system of constraints \begin{align*} \mathcal{C}=[x_1+x_2 \leq x_3; \quad x_1,x_2,x_3\geq 0] \end{align*} and the corresponding generating function \begin{align*} F_{\mathcal{C}}(z)=\sum_{x_1+x_2 \leq x_3}z^{x_1+x_2+x_3} \end{align*}

Note: In the following calculations we always assume $x_r\geq 0$ and typically omit them when writing indices of the sums.

Strategy: Repeated usage of guideline 3 and 4 from the paper:

• One idea presented in the paper is to split complex constraints into simpler ones by adding additional constraints of the form $[x_j \leq x_i]$ (guideline 4).

• Then we are able to substitute parameters $(x_i \leftarrow x_i+x_j)$ and remove the newly introduced additional constraint and also remove one parameter from the complex constraint so that this constraint becomes simpler (guideline 3).

• Repeating these steps will remove all complex constraints leaving only constraints of the form $x_r \geq 0$ so that the generating function can be easily derived.

We follow the recipes from section 7 and introduce the additional constraint:

\begin{align*} \mathcal{C}_1=[x_3 \leq x_1] \end{align*}

Using guideline 4 we observe

\begin{align*} F_{\mathcal{C}}(z)&=F_{\mathcal{C}\cup\mathcal{C}_1}(z)+F_{\mathcal{C}\cup\neg\mathcal{C}_1}(z)\\ &=\sum_{{x_1+x_2 \leq x_3}\atop{x_3 \leq x_1}}z^{x_1+x_2+x_3}+\sum_{{x_1+x_2 \leq x_3}\atop{x_1 < x_3}}z^{x_1+x_2+x_3} \end{align*}

and calculating $F_{\mathcal{C}\cup\mathcal{C}_1}(z)$ and $F_{\mathcal{C}\cup\neg\mathcal{C}_1}(z)$ gives

\begin{align*} F_{\mathcal{C}\cup\mathcal{C}_1}(z)&=\sum_{{x_1+x_2 \leq x_3}\atop{x_3 \leq x_1}}z^{x_1+x_2+x_3}\\ &=\sum_{x_1+x_2 \leq 0}z^{x_1+x_2+2x_3}&(\text{guideline 3: } x_1 \leftarrow x_1+x_3)\\ &&(\text{constraints imply: }x_1=x_2=0)\\ &=\sum_{x_3 \geq 0}z^{2x_3}\\ &=\frac{1}{1-z^2} \end{align*}

Now the second summand

\begin{align*} F_{\mathcal{C}\cup\neg\mathcal{C}_1}(z)&=\sum_{{x_1+x_2 \leq x_3}\atop{x_1 < x_3}}z^{x_1+x_2+x_3}\\ &=\sum_{{x_2 \leq x_3}\atop{0<x_3}}z^{2x_1+x_2+x_3}&(\text{guideline 3: } x_3 \leftarrow x_3+x_1)\\ &=\sum_{x_2 \leq x_3}z^{2x_1+x_2+x_3}-\sum_{{x_2 \leq x_3}\atop{x_3\leq 0}}z^{2x_1+x_2+x_3}&(\text{right sum implies: } x_2=x_3=0)\\ &=\sum_{x_2 \leq x_3}z^{2x_1+x_2+x_3}-\sum_{x_1 \geq 0}z^{2x_1}\\ &=\sum_{x_1,x_2,x_3\geq 0}z^{2x_1+2x_2+x_3}-\sum_{x_1 \geq 0}z^{2x_1}&(\text{guideline 3: } x_3 \leftarrow x_3+x_2)\\ &=\frac{1}{\left(1-z^2\right)^2}\frac{1}{1-z}-\frac{1}{1-z^2} \end{align*}

It follows: \begin{align*} F_{\mathcal{C}}(z)&=F_{\mathcal{C}\cup\mathcal{C}_1}(z)+F_{\mathcal{C}\cup\neg\mathcal{C}_1}(z)\\ &=\frac{1}{1-z^2}+\left(\frac{1}{\left(1-z^2\right)^2}\frac{1}{1-z}-\frac{1}{1-z^2}\right)\\ &=\frac{1}{\left(1-z^2\right)^2(1-z)} \end{align*}

---

Example 2: We consider the system of constraints \begin{align*} \mathcal{C}=[x_3 \leq x_1+x_2;\quad x_1, x_2\, x_3\geq 0] \end{align*} and the corresponding generating function \begin{align*} F_{\mathcal{C}}(z)=\sum_{x_3 \leq x_1+x_2}z^{x_1+x_2+x_3} \end{align*}

We follow the recipes from section 7 again and introduce the additional constraint

\begin{align*} \mathcal{C}_1=[x_1 \leq x_3] \end{align*}

Using guideline 4 we observe

\begin{align*} F_{\mathcal{C}}(z)&=F_{\mathcal{C}\cup\mathcal{C}_1}(z)+F_{\mathcal{C}\cup\neg\mathcal{C}_1}(z)\\ &=\sum_{{ x_3 \leq x_1+x_2}\atop{x_1 \leq x_3}}z^{x_1+x_2+x_3}+\sum_{{x_3 \leq x_1+x_2}\atop{x_3<x_1}}z^{x_1+x_2+x_3} \end{align*}

and calculating $F_{\mathcal{C}\cup\mathcal{C}_1}(z)$ and $F_{\mathcal{C}\cup\neg\mathcal{C}_1}(z)$ gives

\begin{align*} F_{\mathcal{C}\cup\mathcal{C}_1}(z)&=\sum_{{x_3 \leq x_1+x_2 }\atop{x_1 \leq x_3}}z^{x_1+x_2+x_3}\\ &=\sum_{x_3 \leq x_2 }z^{2x_1+x_2+x_3}&(\text{guideline 3: } x_3 \leftarrow x_3+x_1)\\ &=\sum_{x_1,x_2,x_3 \geq 0 }z^{2x_1+x_2+2x_3}&(\text{guideline 3: } x_2 \leftarrow x_2+x_3)\\ &=\frac{1}{(1-z^2)^2}\frac{1}{1-z} \end{align*}

Now the second summand

\begin{align*} F_{\mathcal{C}\cup\neg\mathcal{C}_1}(z)&=\sum_{{x_3 \leq x_1+x_2 }\atop{x_3 < x_1}}z^{x_1+x_2+x_3}\\ &=\sum_{{0 \leq x_1+x_2}\atop{0<x_1}}z^{x_1+x_2+2x_3}&(\text{guideline 3: } x_1 \leftarrow x_1+x_3)\\ &=\sum_{0 \leq x_1+x_2}z^{x_1+x_2+2x_3}-\sum_{{0 \leq x_1+x_2}\atop{x_1\leq 0}}z^{x_1+x_2+2x_3}&(\text{right sum implies: } x_1=0)\\ &=\sum_{x_1,x_2,x_3 \geq 0}z^{x_1+x_2+2x_3}-\sum_{x_2,x_3 \geq 0}z^{x_2+2x_3}\\ &=\frac{1}{\left(1-z\right)^2}\frac{1}{1-z^2}-\frac{1}{(1-z)(1-z^2)} \end{align*}

It follows: \begin{align*} F_{\mathcal{C}}(z)&=F_{\mathcal{C}\cup\mathcal{C}_1}(z)+F_{\mathcal{C}\cup\neg\mathcal{C}_1}(z)\\ &=\frac{1}{\left(1-z^2\right)^2(1-z)}+\left(\frac{1}{\left(1-z\right)^2}\frac{1}{1-z^2}-\frac{1}{(1-z)(1-z^2)}\right)\\ &=\frac{1-z^3}{\left(1-z^2\right)^2(1-z)^2}\\ &=\frac{1+z+z^2}{\left(1-z^2\right)^2(1-z)} \end{align*}

---

Example 3: We consider the system of constraints \begin{align*} \mathcal{C}=[x_1+x_2 \leq x_3+x_4; \quad x_1, x_2, x_3,x_4\geq 0] \end{align*} and the corresponding generating function \begin{align*} F_{\mathcal{C}}(z)=\sum_{x_1+x_2 \leq x_3+x_4}z^{x_1+x_2+x_3+x_4} \end{align*}

We follow the recipes from section 7 again and introduce the additional constraint

\begin{align*} \mathcal{C}_1=[x_3 \leq x_1] \end{align*}

Using guideline 4 we observe

\begin{align*} F_{\mathcal{C}}(z)&=F_{\mathcal{C}\cup\mathcal{C}_1}(z)+F_{\mathcal{C}\cup\neg\mathcal{C}_1}(z)\\ &=\sum_{{ x_1+x_2 \leq x_3+x_4}\atop{x_3 \leq x_1}}z^{x_1+x_2+x_3+x_4}+\sum_{{x_1+x_2 \leq x_3+x_4}\atop{x_1<x_3}}z^{x_1+x_2+x_3+x_4} \end{align*}

and calculating $F_{\mathcal{C}\cup\mathcal{C}_1}(z)$ and $F_{\mathcal{C}\cup\neg\mathcal{C}_1}(z)$ gives

\begin{align*} F_{\mathcal{C}\cup\mathcal{C}_1}(z)&=\sum_{{x_1+x_2 \leq x_3+x_4 }\atop{x_3 \leq x_1}}z^{x_1+x_2+x_3+x_4}\\ &=\sum_{x_1+x_2 \leq x_4 }z^{x_1+x_2+2x_3+x_4}&(\text{guideline 3: } x_1 \leftarrow x_1+x_3)\\ &=\sum_{x_3\geq 0}z^{2x_3}\sum_{x_1+x_2 \leq x_4 }z^{x_1+x_2+x_4}\\ &=\frac{1}{1-z^2}\frac{1}{\left(1-z^2\right)^2(1-z)}&(\text{result from example 1})\\ &=\frac{1}{\left(1-z^2\right)^3(1-z)} \end{align*}

Observe, that we could use the result from example 1 in the calculation above. Now the second summand

\begin{align*} F_{\mathcal{C}\cup\neg\mathcal{C}_1}(z)&=\sum_{{x_1+x_2 \leq x_3+x_4 }\atop{x_1 < x_3}}z^{x_1+x_2+x_3+x_4}\\ &=\sum_{{x_2 \leq x_3+x_4}\atop{0<x_3}}z^{2x_1+x_2+x_3+x_4}\qquad(\text{guideline 3: } x_3 \leftarrow x_3+x_1)\\ &=\sum_{x_1\geq 0}z^{2x_1}\sum_{{x_2 \leq x_3+x_4}\atop{0<x_3}}z^{x_2+x_3+x_4}\\ &=\sum_{x_1\geq 0}z^{2x_1}\sum_{x_2 \leq x_3+x_4}z^{x_2+x_3+x_4}-\sum_{x_1\geq 0}z^{2x_1}\sum_{{x_2 \leq x_3+x_4}\atop{x_3\leq 0}}z^{x_2+x_3+x_4}\\ &=\frac{1}{1-z^2}\frac{1+z+z^2}{\left(1-z^2\right)^2(1-z)}\qquad(\text{result from example 2})\\ &\qquad-\frac{1}{1-z^2}\sum_{x_2 \leq x_4}z^{x_2+x_4}\qquad(\text{constraints imply }x_3=0)\\ &=\frac{1}{1-z^2}\frac{1+z+z^2}{\left(1-z^2\right)^2(1-z)}\\ &\qquad-\frac{1}{1-z^2}\sum_{x_2,x_4\geq 0}z^{2x_2+x_4}\qquad(\text{guideline 3: } x_4 \leftarrow x_4+x_2)\\ &=\frac{1}{1-z^2}\frac{1+z+z^2}{\left(1-z^2\right)^2(1-z)}-\frac{1}{1-z^2}\frac{1}{(1-z)(1-z^2)}\\ &=\frac{z+2z^2}{\left(1-z^2\right)^3(1-z)}\\ \end{align*}

It follows: \begin{align*} F_{\mathcal{C}}(z)&=F_{\mathcal{C}\cup\mathcal{C}_1}(z)+F_{\mathcal{C}\cup\neg\mathcal{C}_1}(z)\\ &=\frac{1}{\left(1-z^2\right)^3(1-z)}+\frac{z+2z^2}{\left(1-z^2\right)^3(1-z)}\\ &=\frac{1+z+2z^2}{\left(1-z^2\right)^3(1-z)}\\ \end{align*}

---

Example 4: We consider the system of constraints \begin{align*} \mathcal{C}=[x_2 \leq x_1, x_3\leq x_2, x_3\leq x_4;\quad x_1, x_2, x_3, x_4\geq 0] \end{align*} and the corresponding generating function \begin{align*} F_{\mathcal{C}}(z)=\sum_{{x_2 \leq x_1}\atop{{x_3\leq x_2}\atop{x_3\leq x_4}}}z^{x_1+x_2+x_3+x_4} \end{align*}

Here we will simply apply guideline 3 three times in order to remove the constraints of the form $x_i \leq x_j$.

We observe:

\begin{align*} F_{\mathcal{C}}(z)&=\sum_{{x_2 \leq x_1}\atop{{x_3\leq x_2}\atop{x_3\leq x_4}}}z^{x_1+x_2+x_3+x_4}\\ &=\sum_{{x_3\leq x_2}\atop{x_3\leq x_4}}z^{x_1+2x_2+x_3+x_4}&(\text{guideline 3: } x_1 \leftarrow x_1+x_2)\\ &=\sum_{x_3\leq x_4}z^{x_1+2x_2+3x_3+x_4}&(\text{guideline 3: } x_2 \leftarrow x_2+x_3)\\ &=\sum_{x_1,x_2,x_3,x_4\geq 0}z^{x_1+2x_2+4x_3+x_4}&(\text{guideline 3: } x_4 \leftarrow x_4+x_3)\\ &=\frac{1}{(1-z)^2(1-z^2)(1-z^4)} \end{align*}

---

Conclusion:

Analysing the examples with respect to the relationship of constraints of the form

\begin{align*} \mathcal{C}&=[x_i \leq x_j;x_1,\ldots,x_N\geq 0]\tag{7}\\ \mathcal{C^\prime}&=[x_i+\ldots+x_{j-1} \leq x_j+\ldots+x_k;x_1,\ldots,x_N\geq 0]\tag{8}\\ \end{align*} and a corresponding generating function \begin{align*} F_{\mathcal{C}}(z)&=\sum_{x_i \leq x_j}z^{\lambda_1x_1+\ldots+\lambda_Nx_N}&(\lambda_r \geq 1)\\ F_{\mathcal{C^\prime}}(z)&=\sum_{x_i+\ldots+x_{j-1} \leq x_j+\ldots+x_k}z^{\lambda_1x_1+\ldots+\lambda_Nx_N}&(\lambda_r \geq 1)\\ \end{align*}

we observe:

Guideline 3 Removal of constraints of the form $$x_j \leq x_i$$

The transformation

$$x_i \leftarrow x_i+x_j$$

removes the constraint $x_j \leq x_i$ by replacing ${x_i}$ with ${x_i+x_j}$ in the exponent of $z$. If there are some more complex constraints (different from $x_r \geq 0$) each occurrence of $x_i$ has to be substituted with $x_i+x_j$.

\begin{align*} F(z)&=\sum_{{x_i \leq x_j}\atop{x_1,\ldots,x_N\geq 0}}z^{\lambda_1x_1+\ldots+\lambda_ix_i+\ldots+\lambda_jx_j+\ldots+\lambda_Nx_N}\\ &=\sum_{x_1,\ldots,x_N\geq 0}z^{\lambda_1x_1+\ldots+\lambda_ix_i+\ldots+(\lambda_i+\lambda_j)x_j+\ldots+\lambda_Nx_N}\\ \end{align*}

Guideline 4 Removal of one parameter from the left side of a constraint of the form $$\mathcal{C}=[x_i+\ldots+x_{j-1} \leq x_j+\ldots+x_k]$$

We can remove $x_i$ from the constraint by using an additional constraint $$\mathcal{C}_1=[x_j \leq x_i]$$ and split the function $f_{\mathcal{C}}(z)$ accordingly into $$f_{\mathcal{C}}(z)=f_{\mathcal{C}\cup\mathcal{C}_1}(z)+f_{\mathcal{C}\cup\neg\mathcal{C}_1}(z)$$

One parameter ($x_i$ or $x_j$) can then be cancelled by applying Guideline 3.

Note: Technical detail of the negated constrained $\mathcal{C}_1$. Since we always have the situation $x_r\geq 0$ we get assuming $\mathcal{C}_1=[x_j \geq x_i]$

\begin{align*} \neg\mathcal{C}_1&=[x_i < x_j]=[x_i \geq 0] \backslash [x_i = 0]\\ \end{align*} Therefore we calculate $f_{\mathcal{C}\cup\neg\mathcal{C}_1}(z)$ using $$f_{\mathcal{C}\cup\neg\mathcal{C}_1}(z)=f_{\mathcal{C}}(z) - f_{\mathcal{C}\cup[x_i=0]}(z)$$

Note: After repeated applications of guideline 3 and 4 the complex constraint will become a form $$\mathcal{C}=[0\leq x_r+\ldots+x_N;\quad x_1,\ldots,x_N\geq 0]$$ and can then be removed, since then $\mathcal{C}$ is the same as $[x_1,\ldots,x_N\geq 0]$.

---

A refined inspection:

To check what's going on in somewhat more detail we consider the same constraints being one of \begin{align*} \mathcal{C}_\alpha&=[x_1+x_2\leq x_3;\quad x_1,x_2,x_3\geq 0]\\ \mathcal{C}_\beta&=[x_3 \leq x_1+x_2;\quad x_1,x_2,x_3\geq 0]\\ \mathcal{C}_\gamma&=[x_1+x_2\leq x_3+x_4;\quad x_1,x_2,x_3\geq 0]\\ \mathcal{C}_\delta&=[x_2\leq x_1,x_3\leq x_2,x_3\leq x_4;\quad x_1,x_2,x_3,x_4\geq 0] \end{align*} as above, but the more general diophantine equation $$\lambda_1x_1+\ldots\lambda_Nx_N=0\qquad\qquad (\lambda_r \geq 0)$$ and the corresponding generating function $$G_{\mathcal{C}_{\xi}}(z)=\sum_{\mathcal{C_\xi}}z^{\lambda_1x_1+\ldots+\lambda_Nx_N}\qquad\qquad\xi\in\{\alpha,\beta,\gamma,\delta\}$$

Calculation as before gives:

\begin{align*} G_{\mathcal{C}_\alpha}(z)&=\sum_{x_1+x_2\leq x_3}z^{\lambda_1x_1+\lambda_2x_2+\lambda_3x_3}\\ &=\sum_{x_1,x_2,x_3\geq 0}z^{(\lambda_1+\lambda_3)x_1+(\lambda_2+\lambda_3)x_2+\lambda_3x_3}\\ &=\frac{1}{\left(1-z^{\lambda_3}\right)\left(1-z^{\lambda_1+\lambda_3}\right)\left(1-z^{\lambda_2+\lambda_3}\right)}\\ \\ \\ G_{\mathcal{C}_\beta}(z)&=\sum_{x_3\leq x_1+x_2}z^{\lambda_1x_1+\lambda_2x_2+\lambda_3x_3}\\ &=\frac{1-z^{\lambda_1+\lambda_2+\lambda_3}}{\left(1-z^{\lambda_1}\right)\left(1-z^{\lambda_2}\right)\left(1-z^{\lambda_1+\lambda_3}\right)\left(1-z^{\lambda_2+\lambda_3}\right)} \\ \\ G_{\mathcal{C}_\gamma}(z)&=\sum_{x_1+x_2\leq x_3+x_4}z^{\lambda_1x_1+\lambda_2x_2+\lambda_3x_3+\lambda_4x_4}\\ &=\frac{1-z^{\lambda_1+\lambda_3+\lambda_4}-z^{\lambda_2+\lambda_3+\lambda_4}-z^{\lambda_1+\lambda_2+\lambda_3+\lambda_4} \left(1-z^{\lambda_3}-z^{\lambda_4}\right)} {\left(1-z^{\lambda_3}\right)\left(1-z^{\lambda_4}\right) \left(1-z^{\lambda_1+\lambda_3}\right) \left(1-z^{\lambda_1+\lambda_4}\right) \left(1-z^{\lambda_2+\lambda_3}\right) \left(1-z^{\lambda_2+\lambda_4}\right)} \\ \\ G_{\mathcal{C}_\delta}(z)&=\sum_{{x_2 \leq x_1}\atop{{x_3\leq x_2}\atop{x_3\leq x_4}}}z^{\lambda_1+\lambda_2+\lambda_3+\lambda_4}\\ &=\sum_{x_1,x_2,x_3,x_4\geq 0}z^{ \lambda_1x_1 +(\lambda_1+\lambda_2)x_2 +(\lambda_1+\lambda_2+\lambda_3+\lambda_4)x_3 +\lambda_4x_4}\\ &=\frac{1}{\left(1-z^{\lambda_1}\right) \left(1-z^{\lambda_4}\right) \left(1-z^{\lambda_1+\lambda_2}\right) \left(1-z^{\lambda_1+\lambda_2+\lambda_3+\lambda_4}\right) } \end{align*}

Summary: We observe due to the refined view with general $\lambda_r$ the relationship of constraints with the corresponding exponents more easily. But we also see that even when using moderate complex constraints like $x_1+x_2\leq x_3+x_4$ the generating functions are rather complex and cumbersome to develop only based upon analysing the constraints. It's seems more feasible to simply repeat the steps from guideline 3 and 4 as often as necessary in order to derive the generating function.