Solving combinatorial problems with symbolic method and generating functions

analytic-combinatoricscombinatorial-proofscombinatoricsgenerating-functionsinteger-partitions

I am trying to solve the following problems:

a) Let $\mathcal{F}$ be the family of all finite 0-1-sequences that have no 1s directly behind each other. Let the weight of each sequence be its length.
How can $\mathcal{F}$ be constructed with simpler objects? How does the generating function look like?

b) Show with generating functions: The number of partitions of n into different summands equals the number of partitions of n into odd summands.

c) Show with generating functions: The number of compositions of n into summands being 1 or 2 equals the number of compositions of n+2 into summands greater than or equal 2.

My solutions:

a) I have no idea here.

b) Let $\mathcal{P}$ be the partition in different summands. Then $\mathcal{P} = (\{\epsilon\}+\{1\}) \times (\{\epsilon\}+\{2\})\times (\{\epsilon\}+\{3\})\times …$

$\Rightarrow P(z) = (1+z)\cdot (1+z^2) \cdot (1+z^3) \cdot \dotsc = \frac{1}{(1-z)\cdot(1-z^3)\cdot(1-z^5)\cdot \dotsc}$

Now let $\tilde{\mathcal{P}}$ be the partition in odd summands. Then $\tilde{\mathcal{P}} = \{1\}^{\ast}\times\{3\}^{\ast}\times\{5\}^{\ast}\times\dotsc$

$\Rightarrow \tilde{P(z)} = \frac{1}{1-z}\cdot\frac{1}{1-z^3}\cdot\frac{1}{1-z^5}\cdot \dotsc$.

Therefore $P(z) = \tilde{P}(z)$ and so $[z^n]P(z) = [z^n]\tilde{P}(z)$, which proofs that the numbers of partitions of n are the same.

c) Let $\mathcal{K}$ be the number of compositions of n into 1s and 2s.
Then $\mathcal{K} = \{1,2\}^{\ast}$ and so $K(z) = \frac{1}{1-(z+z^2)}$.

Let $\tilde{\mathcal{K}}$ be the number of compositions of n+2 into 2,3,4,5,6,7,… Then $\tilde{\mathcal{K}} = \{2,3,4,5,6,…\}^{\ast}$ and therefore $\tilde{K}(z) = \frac{1}{1-(z^2+z^3+z^4+z^5+…)}$.

I am not sure if I have determined $\mathcal{K}, \tilde{\mathcal{K}}, K(z)$ and $\tilde{K}(z)$ correctly and if so, I don't know how to show that $[z^n]K(z) = [z^{n+2}]\tilde{K}(z)$.

So I'd very much appreciate your help on a) and c). Thanks in advance!

Best Answer

Ad c.)

Your approach is fine. With ${\mathcal{K}} = \{1,2\}^{\ast}$ we obtain \begin{align*} K(z) &= \frac{1}{1-\left(z+z^2\right)}\\ &=\frac{1}{1-z-z^2}\tag{1} \end{align*}

and with $\tilde{\mathcal{K}} = \{2,3,4,5,6,...\}^{\ast}$ we obtain \begin{align*} \tilde{K}(z) &= \frac{1}{1-(z^2+z^3+z^4+z^5+\cdots)}\\ &=\frac{1}{1-\frac{z^2}{1-z}}\tag{2}\\ &=\frac{1-z}{1-z-z^2}\\ &=1+\frac{z^2}{1-z-z^2}\tag{3} \end{align*}

Comment:

In (2) we use the geometric series expansion.

We obtain from (1) and (3) for $n\geq 1$

\begin{align*} \color{blue}{[z^{n+2}]\tilde{K}(z)} &=[z^{n+2}]\left(1+\frac{z^2}{1-z-z^2}\right)\\ &=[z^{n+2}]\frac{z^2}{1-z-z^2}\tag{4}\\ &=[z^n]\frac{1}{1-z-z^2}\tag{5}\\ &\,\,\color{blue}{=[z^n]K(z)} \end{align*}

and the claim follows.

Comment:

In (4) we skip the term $1$ which does not contribute to the coefficient of $z^{n+2}$ since $n\geq 1$.
In (5) we apply the rule $[z^{p-q}]A(z)=[z^p]z^qA(z)$.

Note the coefficients of \begin{align*} K(z)&=\frac{1}{1-z-z^2}\\ &=\color{blue}{1}+\color{blue}{1}z+\color{blue}{2}z^2+\color{blue}{3}z^3+\color{blue}{5}z^4+\color{blue}{8}z^5+\cdots \end{align*} are the Fibonacci numbers.

ad a.)

We start with binary sequences with no consecutive equal characters at all. See example III.24 Smirnov words from Analytic Combinatorics by P. Flajolet and R. Sedgewick for more information.

A generating function for the number of Smirnov words over a binary alphabet is given by \begin{align*} \left.\left(1-\frac{u}{1+u}-\frac{w}{1+w}\right)^{-1}\right|_{u=w=z}\tag{6} \end{align*}

where $u$ represents occurrences of $0$ and $w$ occurrences of $1$. Since there are no restrictions stated for zeros we replace occurrences of $0$ in a Smirnov word by one or more zeros. \begin{align*}\ u\longrightarrow u+u^2+u^3+\cdots=\frac{u}{1-u}\tag{7} \end{align*}

We substitute (7) in (6) evaluate at $z$ and obtain

\begin{align*} \left(1-\frac{\frac{z}{1-z}}{1+\frac{z}{1-z}}-\frac{z}{1+z}\right)^{-1} &=\left(1-z-\frac{z}{1+z}\right)^{-1}\\ &=\frac{1+z}{1-z-z^2}\\ &=1+2z+3z^2+5z^3+8z^4+\cdots \end{align*}

which is again a generating function of (shifted) Fibonacci numbers.

Related Solutions

[Math] Generating Functions and Linear Diophantine Inequalities

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.

Generating functions for unimodal sequences

You’ve basically already correctly described how this generating function is derived. I would suggest to use different summation indices on the two sides of the equation, as they have different roles. On the left, $n$ is the number being composed. On the right, $n+1$ is the largest part of the strictly unimodal composition: the peak. This accounts for the factor $q^{n+1}$, and $(-q;q)_n=\prod_{k=1}^n\left(1+q^k\right)$ is the generating function for partitions with distinct parts of size at most $n$. Every strictly unimodal composition with peak $n+1$ can be uniquely split into a strictly increasing composition with parts of size at most $n$, the peak, and a strictly decreasing composition with parts of size at most $n$. Both strictly increasing compositions and strictly decreasing compositions are in bijection with partitions.

Best Answer

Related Solutions

[Math] Generating Functions and Linear Diophantine Inequalities

Generating functions for unimodal sequences

Related Question