8
$\begingroup$

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.

$\endgroup$
3
+100
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for the long response, but this is all information I already knew from the reading. And the two examples you chose have been examined, and both (as I have said) yield a neat and tidy combinatorial interpretation. Thus my remaining question is: "how do I interpret the results of the second and third problems?" $\endgroup$ – A.E Sep 4 '14 at 14:56
  • $\begingroup$ @A.E: Oh, yes! When I was reading your question, I thought you first of all wanted support in applying the symbolic method to the problem. But now I see your point. I'm thinking about it ... $\endgroup$ – Markus Scheuer Sep 4 '14 at 16:52
  • $\begingroup$ Your computation of $A(z)$ after (3) is false. Your problem is that you forget some of the variables. For any $(x_1,x_2,y_{34})$ there will be several values of $(x_3,x_4)$ satisfying the equations. $\endgroup$ – Ewan Delanoy Sep 5 '14 at 9:18
  • $\begingroup$ @EwanDelanoy: Yes, you're right. Thanks for the hint. I've already detected it and I'll correct it soon. In the meanwhile I've found a paper which systematically treats the inequality constraints. Hmm, maybe it's better to simply post a reference to the paper to quickly remove the inconsistency of my answer. Thanks again and regards, $\endgroup$ – Markus Scheuer Sep 5 '14 at 9:41
  • $\begingroup$ @A.E: Thanks for accepting the answer and granting the bounty. Best regards, $\endgroup$ – Markus Scheuer Sep 10 '14 at 6:20
4
$\begingroup$

I am not exactly sure what it means to do the symbolic method, but I'll explain the method I would use for computing generating functions of this type by example.

Say we wanted the one for $\{x_1+x_2\leq x_3\}$. We can introduce $\xi\geq0$ and write $x_3=x_1+x_2+\xi$, so we have as the generating function \begin{align*} \sum_{x_1+x_2\leq x_3} z^{x_1+x_2+x_3} &= \sum_{x_1}\sum_{x_2}\sum_{\xi} z^{2x_1+2x_2+\xi}\\ &=\sum_{x_1}z^{2x_1}\sum_{x_2}z^{2x_2}\sum_{\xi}z^\xi\\ &=\frac{1}{(1-z)(1-z^2)^2}. \end{align*} Combinatorially, we could have noticed that this introduced variable shows what we are wanting to do is count partitions of $n$ in the form $n=x_1+x_2+x_3=2x_1+2x_2+\xi$, which is to say as a sum of a non-negative integer and two even non-negative integers. Hence we multiply $1/(1-z)$ (a generating function for the number of ways of partitioning a number as a single non-negative integer) and $1/(1-z^2)$ twice (a generating function for the number of ways of partitioning a number as a single even non-negative integer).

And for $\{x_1+x_2\geq x_3\}$, we similarly introduce $\xi\geq0$ and write $x_1+x_2=x_3+\xi$ to compute \begin{align*} \sum_{x_1+x_2\geq x_3} z^{x_1+x_2+x_3} &= \sum_{x_3}\sum_{\xi}\sum_{x_1+x_2=\xi+x_3} z^{2x_3+\xi}\\ &= \sum_{x_3}\left(z^{2x_3}\sum_{\xi}\sum_{x_1+x_2=x_3+\xi}z^\xi\right)\\ &= \sum_{x_3}z^{2x_3}\sum_\xi(x_3+\xi+1)z^\xi\\ &= \sum_{x_3}z^{2x_3}\left(\sum_\xi x_3z^\xi + \sum_\xi (\xi+1)z^\xi\right)\\ &= \sum_{x_3}z^{2x_3}\left(\frac{x_3}{1-z}+\frac{1}{(1-z)^2}\right)\\ &= \frac{1}{1-z}\cdot\frac{z}{(1-z^2)^2} + \frac{1}{(1-z)^2}\cdot\frac{1}{1-z^2}\\ &= \frac{1+z+z^2}{(1-z)(1-z^2)^2}. \end{align*} Unfortunately, I'm having a hard time producing a combinatorial description for this one.

$\endgroup$
  • $\begingroup$ Kyle, thanks for your response. I am sure I will find this technique useful in the future. However, I am going to leave the question open to see if anyone has a combinatorial description of the second (and third and fourth) problems. $\endgroup$ – A.E Sep 2 '14 at 17:15
3
$\begingroup$

For a set $A\subseteq {\mathbb N}^4$, we put $G(A)=\sum_{(x_1,x_2,x_3,x_4)\in A} z^{x_1+x_2+x_3+x_4}$. Then

$$ \begin{array}{lcl} G(\lbrace x_1+x_2\leq x_3+x_4 \rbrace) &=& \frac{1}{2}.\bigg(G({\mathbb Z}^4)+G(\lbrace x_1+x_2= x_3+x_4 \rbrace) \bigg) \ \text{(symmetry argument)} \\ &=& \frac{1}{2}.\bigg(\frac{1}{(1-z)^4}+\sum_{t}\sum_{x_1+x_2=t}z^{x_1+x_2} \sum_{x_3+x_4=t}z^{x_3+x_4} \bigg)\\ &=& \frac{1}{2}.\Bigg(\frac{1}{(1-z)^4}+\sum_{t}\bigg(\sum_{x_1+x_2=t}z^{x_1+x_2} \bigg)^2 \Bigg)\\ &=& \frac{1}{2}.\Bigg(\frac{1}{(1-z)^4}+\sum_{t}(t+1)^2z^{2t} \Bigg)\\ &=& \frac{1}{2}.\Bigg(\frac{1}{(1-z)^4}+\sum_{t}\big(2\frac{t^2+3t+2}{2}-(t+1)\big)z^{2t} \Bigg)\\ &=& \frac{1}{2}.\Bigg(\frac{1}{(1-z)^4}+\sum_{t}\big(2\binom{t+2}{2}-\binom{t+1}{1}\big)z^{2t} \Bigg)\\ &=& \frac{1}{2}.\Bigg(\frac{1}{(1-z)^4}+\frac{2}{(1-z^2)^3}-\frac{1}{(1-z^2)^2} \Bigg)\\ &=& \frac{1 - 2z + 2z^2 - 4z^3 + 5z^4 - 2z^5}{(1-z)^4(1-z^2)^3}\\ \end{array} $$

For the last one, we can use the same ideas as in Kyle Miller’s answer : putting $t_4=x_4-x_3,t_2=x_2-x_3,t_1=x_1-x_2$, we have

$$ \lbrace x_1 \ge x_2, x_2 \ge x_3,x_3 \le x_4 \rbrace= \lbrace (x_3+t_1+t_2,x_3+t_2,x_3+t_4) | (t_1,t_2,t_3,t_4)\in {\mathbb N}^4 \rbrace $$

and hence

$$ \begin{array}{lcl} G(\lbrace x_1 \ge x_2, x_2 \ge x_3,x_3 \le x_4 \rbrace) &=& \sum_{t_1,t_2,x_3,t_4}z^{t_1+2t_2+4x_3+t_4} \\ &=& \frac{1}{(1-z)^2(1-z^2)(1-z^4)}\\ \end{array} $$

$\endgroup$
  • $\begingroup$ Thanks! Before I accept your answer, I was wondering if there is a combinatorial interpretation of the resulting generating functions for the second and third ones I listed. In Sedgewick's book, he sets out to create a formal calculus for deriving generating functions from algebraic "combinatorial" operations, such as Cartesian product (product of generating functions) and disjoint union (sum of generating functions). I understand the interpretation of the first and last, but I have no intuitive explanation for the numerators in the middle two. $\endgroup$ – A.E Sep 3 '14 at 16:18
  • $\begingroup$ @A.E Well, each and every one of the steps in my computation can be translated as one of the "combinatorial" operations you enumerate, but writing it would only make the presentation more complicated. It is worth knowing that such a correspondence exists, but it is uninteresting to write the details in more complicated examples, at least in my view. I can write the (ugly,complicated) "combinatorial" explanation if you insist. $\endgroup$ – Ewan Delanoy Sep 3 '14 at 17:16
  • $\begingroup$ No, I am not seeking the correspondence at the derivation level, I am seeking it at the end result. For example: $G(\{x_1 \ge x_2, x_2 \ge x_3, x_3 \le x_4\}) = \dfrac{1}{(1-z)^2(1-z^2)(1-z^4)}$ can be seen as the product of generating functions for the combinatorial classes two positive integers, a multiple of $2$, and a multiple of $4$. However, for the first one you solved and the second one Kyle Miller solved, I do not see such a simple interpretation. Perhaps there is only an unenlightening interpretation, and perhaps it cannot be disentangled from the derivation. $\endgroup$ – A.E Sep 3 '14 at 17:40
  • $\begingroup$ The result of your first calculation corresponds with the result of my example 3. You could simplify it by cancelling $(1-z)^3$ if you like. Regards. $\endgroup$ – Markus Scheuer Sep 6 '14 at 12:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.