Counting problem: generating function using partitions of odd numbers and permuting them

Question

We have building blocks of the following lengths: $3, 5, 7, 9, 11$ and so on, including all other odd numbers other than $1$. Each length is available in two colors, red and blue. For a given number $n$, how many ways can we combine blocks in a unique order (with respect to colors and lengths used) that have a total length of $n$?

Example: $n=9$ has $10$ total ways. We see that we can use a sequence of $3$ blocks of length $3$, each with $2$ color choices, so that makes $2^3=8$ ways. We also can use a $1$ block of $9$ in red or blue. Therefore the total is $10$.

Eventually we may use generating functions to find the number of combinations for any $n$, and I have been looking at the generating function for partitions using odd numbers. There are a few ways this problem differs from the problem of finding how many ways we can use odd numbers to sum to a given $n$. First, we are looking at permutations of these blocks, not just combinations. Second, each block has two colors to choose from, so a combination of $5$ blocks has $2^5$ ways to assign these colors.

Any advice on how to approach this using generating functions or just in general?

Answer 1

Given $n$, let $f_n$ denote the required number of block arrangements.

If we consider the possibilities for the first block for such arrangements, we see that, since the first block can be red or blue and have length one of $3$, $5$, $7$, etc,

\begin{eqnarray*} f_n &=& 2(f_{n-3} + f_{n-5} + f_{n-7} + \cdots + f_k) \\ && \\ && \mbox{where } k = \begin{cases} 0 & \text{if $n$ is odd} \\ 1 & \text{if $n$ is even.} \end{cases} \end{eqnarray*}

Similarly,

\begin{eqnarray*} f_{n+2} &=& 2(f_{n-1} + f_{n-3} + f_{n-5} + \cdots + f_k). \end{eqnarray*}

Combining these two equations we get

$$f_{n+2} - f_n- 2f_{n-1} = 0.$$

This is a third-order linear homogeneous recurrence relation. Its characteristic equation is

$$x^3 - x - 2 = 0.$$

Unfortunately, its roots (one real and a pair of complex conjugates) are complicated in exact form. Here is the solution from Wolfram Alpha, both exact and numerical approximation.

For now, we'll label these roots:$\quad a\quad $ and $\quad b \pm ic$.

For such recurrence relations, the general solution is known to be:

$$\mathbf{f_n = Aa^n + r^n\left(B \cos(n\theta) + C \sin(n\theta)\right)}\qquad\qquad\qquad\qquad\mbox{(*)}$$

for some constants $A,B,C$ and with $r = \sqrt{b^2+c^2}$ and $\theta = \tan^{-1}\left(\frac{c}{b}\right)$, these being the modulus and argument of $b+ic$.

To find $A,B,C$ we have the initial cases:

\begin{eqnarray*} f_0 &=& 1 \\ f_1 &=& 0 \\ f_2 &=& 0. \\ &&\\ \end{eqnarray*} \begin{eqnarray*} 1 = f_0 &=& Aa^0 + r^0\left(B \cos(0) + C \sin(0)\right) \\ &=& A + B \\ \therefore B &=& 1-A.\\ &&\\ 0 = f_1 &=& Aa + r\left(B \cos(\theta) + C \sin(\theta)\right) \\ &=& Aa + r\left(B \frac{b}{r} + C \frac{c}{r}\right) \\ &&\qquad\qquad\mbox{(since $\cos(\tan^{-1}\left(\frac{c}{b}\right))=\frac{b}{r}$ and $\sin(\tan^{-1}\left(\frac{c}{b}\right))=\frac{c}{r}$)} \\ &=& Aa + Bb + Cc \\ &=& Aa -Ab + b + Cc \qquad\mbox{(using $B = 1-A$).} \\ && \\ 0 = f_2 &=& Aa^2 + r^2\left(B \cos(2\theta) + C \sin(2\theta)\right) \\ &=& Aa^2 + r^2\left(B -2B\sin^2\theta + 2C \cos\theta\,\sin\theta\right) \qquad\mbox{(using double-angle formulae)} \\ &=& Aa^2 + r^2\left(B -2B\frac{c^2}{r^2} + 2C \frac{bc}{r^2}\right) \\ &=& Aa^2 + Br^2 -2Bc^2 + 2Cbc \\ &=& Aa^2 + r^2 - Ar^2 -2c^2 + 2Ac^2 + 2b(Ab - Aa - b) \\ && \qquad\qquad\mbox{(using $B=1-A$ and $Cc=Ab - Aa - b$)} \\ &=& A(a^2 - r^2 + 2b^2 + 2c^2 -2ab) + r^2 -2b^2 - 2c^2 \\ &=& A(a^2 + b^2 + c^2 -2ab) -b^2 - c^2. \\ &&\\ \therefore A &=& \dfrac{b^2 + c^2}{a^2 + b^2 + c^2 -2ab}. \\ &&\\ \therefore B &=& 1-A = \dfrac{a^2 - 2ab}{a^2 + b^2 + c^2 -2ab}. \\ &&\\ \therefore C &=& \dfrac{A(b-a) - b}{c} = \dfrac{b^3 + bc^2 - ab^2 - ac^2 - b}{c(a^2 + b^2 + c^2 -2ab)}. \\ \end{eqnarray*}

The above link to Wolfram Alpha has the approximate values:

\begin{eqnarray*} a &=& 1.52137970680457 \\ b &=& -0.760689853402284 \\ c &=& 0.857873626595179. \end{eqnarray*}

From these we also get: \begin{eqnarray*} r &=& 1.14655842078664 \\ \theta &=& 2.29622326401129 \mbox{ radians}\\ A &=& 0.221171426610117 \\ B &=& 0.778828573389883 \\ C &=& 0.298367108176176. \end{eqnarray*}

Using these values with equation (*) we can calculate actual values for $f_n$:

\begin{eqnarray*} n && f_n \\ \hline 3 && 2 \\ 4 && 0 \\ 5 && 2 \\ 6 && 4 \\ 7 && 2 \\ 8 && 8 \\ 9 && 10 \\ 10 && 12 \\ 11 && 26 \\ 12 && 32 \\ 13 && 50 \\ 14 && 84 \\ 15 && 114 \\ 16 && 184 \\ 17 && 282 \\ 18 && 412 \\ 19 && 650 \\ 20 && 976. \end{eqnarray*}

Answer 2

Assuming you are meaning partitions, the generating function you are looking for is $$ P_{odd,redblue}(z) = \prod_{n=1}^{\infty} \frac{1}{1-2z^{2n+1}}. $$ I don't know yet if the function has a nicer form or what the properties of the function are.
How to get there: You should first be familiar with the multiset construction, from Flajolet's book Analytic Combinatorics, page 29 ff. For a combinatorial class $\mathcal B$ (with $\mathcal B_0 = \emptyset$), the multiset construction is defined as $$ \mathrm{MSET}(\mathcal B) = \prod_{ \beta \in \mathcal B} \mathrm{SEQ}( \{ \beta \}). $$The generating function of the "normal" partitions is $$ P(z) = \prod_{n=1}^{\infty} \frac{1}{1-z^n}. $$ If we may only use odd integers larger than one, we get correspondingly: $$ P_{odd}(z) = \prod_{n=1}^{\infty} \frac{1}{1-z^{2n+1}}. $$ Now we have two possibilities for each odd number, so we simply double the coefficient of $z$: $$ P_{odd,redblue}(z) = \prod_{n=1}^{\infty} \frac{1}{(1-z^{2n+1})^2}. $$ The coefficients of $n=8..12$ are $4,6,7,8,13$, respectively.

Answer 3

Note: This is really a nice question since it provides a good opportunity to consider similar but different concepts in a non-trivial but manageable way!

But first some clarification: The example with $n=9$ in the question above giving a result of $10$ means the number of different compositions of $9$ is $10$. Later on a generating function for partitions is asked for. These are different concepts. So, let's clarify these terms.

Compositions vs. Partitions of an integer ($\geq 1$)

• Informal description:

Compositions of an integer are representations by summands where the order matters. e.g. $8=3+5=5+3$ gives two different compositions of $8$.

Partitions of an integer are representations by summands where the order does not matter. So $8=3+5=5+3$ is regarded as only one partition of $8$.

The following definition is from Analytic Combinatorics from Flajolet and Sedgewick (Def. I.9)

• Precise description:

A composition of an integer $n$ is a sequence $(x_1,x_2,\ldots,x_k)$ of integers (for some $k$) such that $$n=x_1+x_2+\ldots+x_k,\qquad\qquad x_j\geq 1$$

A partition of an integer $n$ is a sequence $(x_1,x_2,\ldots,x_k)$ of integers (for some $k$) such that $$n=x_1+x_2+\ldots+x_k \qquad\text{and} \qquad\qquad x_1\geq x_2\geq \ldots \geq x_k\geq 1$$

---

The answer is divided in four steps:

• First step: We state the generating functions for compositions as well as for partitions of two-colored, odd integers $> 1$

• Second step: Examples with small numbers (plausibility check)

• Third step: Proof of the generating function for compositions

• Fourth step: Proof of the generating function for partitions

---

First step: Generating functions

The following is valid:

The generating function $C(z)$ for the number of compositions of two-colored, odd integers $>1$ is

\begin{align*} C(z)&=\frac{1-z^2}{1-z^2-2z^3}\\ \\ &=1+2z^3+2z^5+4z^6+2z^7+8z^8+10z^9+12z^{10}+\ldots\tag{1}\\ \\ \end{align*}

The generating function $P(z)$ for the number of partitions of two-colored, odd integers $>1$ is

\begin{align*} P(z)&=\prod_{n=1}^{\infty}\left(\frac{1}{1-z^{2n+1}}\right)^2\\ \\ &=\left(\frac{1}{1-z^{3}}\right)^2\left(\frac{1}{1-z^{5}}\right)^2\left(\frac{1}{1-z^{7}}\right)^2\cdot\ldots\\ \\ &=1+2z^3+2z^5+3z^6+2z^7+4z^8+6z^9+7z^{10}+\ldots\tag{2}\\ \\ \end{align*}

Let's color the integers by labeling the blue integers with b and the red integers with r. We see e.g. that the coefficient of $z^6$ in the generating functions for compositions is $4$ and for partitions is $3$: \begin{align*} [z^6]C(z)=4&\qquad\longrightarrow\qquad 6 = 3_b+3_b=3_b+3_r=3_r+3_b=3_r+3_r\\ [z^6]P(z)=3&\qquad\longrightarrow\qquad 6 = 3_b+3_b=3_b+3_r=3_r+3_r \end{align*} We observe, that $C(z)$ respects the order of $3_b+3_r$ and $3_r+3_b$ while $P(z)$ does not distinguish between these and so it's counted only once. The first summand $1=z^0$ in $C(z)$ and $P(z)$ is simply for convenience denoting that there is one possibility for the empty composition resp. the empty partition. By the way the coefficients in (1) and (2) were calculated from the generating functions with the help of Wolfram Alpha.

---

Second step: Compositions and Partitions of small numbers

This is simply a plausibility check of (1) and (2) and also a way to become familiar with the difference between compositions and partitions

We start with the number of compositions of $3$ up to $10$

Compositions: \begin{array}{lll} \text{n}&\text{compositions}&\text{nr of comp.}\\ \hline 3\qquad&3_b,3_r&\qquad2\\ 4\qquad&-&\qquad0\\ 5\qquad&5_b,5_r&\qquad2\\ 6\qquad&3_b+3_b,3_b+3_r,3_r+3_b,3_r+3_r&\qquad4\\ 7\qquad&7_b,7_r&\qquad2\\ 8\qquad&3_b+5_b,3_b+5_r,3_r+5_b,3_r+5_r&\qquad8\\ &5_b+3_b,5_b+3_r,5_r+3_b,5_r+3_r&\\ 9\qquad&3_b+3_b+3_b&\qquad10\\ &3_b+3_b+3_r,3_b+3_r+3_b,3_r+3_b+3_b,&\\ &3_b+3_r+3_r,3_r+3_b+3_r,3_r+3_r+3_b,&\\ &3_r+3_r+3_r&\\ &9_b,9_r&\\ 10\qquad&3_b+7_b,\ldots,7_b+3_b&\qquad12(=8+4)\\ &5_b+5_b,\ldots,5_r+5_r&\\ \end{array}

and go on with the number of partitions of $3$ up to $10$

Partitions:

\begin{array}{lll} \text{n}&\text{partitions}&\text{nr of part.}\\ \hline 3\qquad&3_b,3_r&\qquad2\\ 4\qquad&-&\qquad0\\ 5\qquad&5_b,5_r&\qquad2\\ 6\qquad&3_b+3_b,3_b+3_r,3_r+3_r&\qquad3\\ 7\qquad&7_b,7_r&\qquad2\\ 8\qquad&3_b+5_b,3_b+5_r,3_r+5_b,3_r+5_r&\qquad4\\ 9\qquad&3_b+3_b+3_b,3_b+3_b+3_r&\qquad 6\\ &3_b+3_r+3_r,3_r+3_r+3_r&\\ &9_b,9_r&\\ 10\qquad&3_b+7_b,3_b+7_r,3_r+7_b,3_r+7_r&\qquad7(=4+3)\\ &5_b+5_b,5_b+5_r,5_r+5_r&\\ \end{array}

We observe the columns number of compositions and number of partitions coincide with the stated coefficients of $C(z)$ and $P(z)$ in (1) and (2).

---

Note: We now follow Flajolet (section I.3) very closely. We build so called constructions. These are certain sets containing symbolic objects corresponding to compositions resp. partitions which we want to count. And the clou is that there is also a powerful translation mechanism from these constructions into generating functions. That's all ... :-)

Third step: Generating function $C(z)$ of compositions

We start with defining a set for the blue, odd integers $> 1$ and the red, odd integers $>1$.

Let \begin{align*} \mathcal{B}_b&=\{3_b,5_b,7_b,\ldots\}\cong\{\bullet\bullet\bullet,\bullet\bullet\bullet\bullet\bullet,\ldots\}=\text{SEQ}_{(odd,>1)}\{\bullet\}\tag{3}\\ \mathcal{B}_r&=\{3_r,5_r,7_r,\ldots\}\cong\{\circ\circ\circ,\circ\circ\circ\circ\circ,\ldots\}=\text{SEQ}_{(odd,>1)}\{\circ\}\tag{4}\\ \end{align*}

Next we consider the disjoint union $\mathcal{B}_{(b,r)}$ of $\mathcal{B}_b$ and $\mathcal{B}_r$.

Let \begin{align*} \mathcal{B}_{(b,r)}&=\mathcal{B}_b+\mathcal{B}_r\\ &=\{3_b,3_r,5_b,5_r,7_b,7_r\ldots\}\\ &\cong\{\bullet\bullet\bullet,\circ\circ\circ,\bullet\bullet\bullet\bullet\bullet,\circ\circ\circ\circ\circ,\ldots\}\\ &=\text{SEQ}_{(odd,>1)}\{\bullet,\circ\}\\ \end{align*}

Observe, that $\text{SEQ}_{(odd,>1)}\{\bullet\}$ is only a shorthand notation for the set $\{\bullet\bullet\bullet,\bullet\bullet\bullet\bullet\bullet,\ldots\}$ which is simply $\mathcal{B}_b =\{3_b,5_b,7_b,\ldots\}$ in unary notation.

The generating function $B_b(z)$ for the construction $\mathcal{B}_b$ can be easily derived:

Let \begin{align*} B_b(z)&=z^3+z^5+z^7+\ldots\\ &=z^3\left(1+z^2+z^4+\ldots\right)\\ &=\frac{z^3}{1-z^2}\tag{5} \end{align*} Similarly we get \begin{align*} B_r(z)&=\frac{z^3}{1-z^2} \end{align*} We introduce $B_{(b,r)}(z)$, the generating function for $\mathcal{B}_{(b,r)}$. Since $\mathcal{B}_{(b,r)}$ is the combinatorial sum (disjoint union) $\mathcal{B}_b+\mathcal{B}_r$, we observe

\begin{align*} B_{(b,r)}(z)&=B_b(z)+B_r(z)\\ &=\frac{2z^3}{1-z^2}\tag{6} \end{align*}

We now define the construction for all compositions of $\mathcal{B}_{(b,r)}$. Since the compositions do respect the order of its constituents they can be specified as sequence of elements of $\mathcal{B}_{(b,r)}$.

The construction $\mathcal{C}$ of all compositions of $\mathcal{B}_{(b,r)}$ and the corresponding generating function $C(z)$ are given as \begin{align*} \mathcal{C}&=\text{SEQ}(\mathcal{B}_{(b,r)})\\ &=\{\varepsilon\}+\mathcal{B}_{(b,r)}+\mathcal{B}_{(b,r)}\times\mathcal{B}_{(b,r)} +\mathcal{B}_{(b,r)}\times\mathcal{B}_{(b,r)}\times\mathcal{B}_{(b,r)}+\ldots\\ \\ C(z)&=1+B_{(b,r)}(z)+\left(B_{(b,r)}(z)\right)^2+\left(B_{(b,r)}(z)\right)^3+\ldots\\ &=\frac{1}{1-B_{(b,r)}(z)}\\ &=\frac{1}{1-\frac{2z^3}{1-z^2}}\\ &=\frac{1-z^2}{1-z^2-2z^3} \end{align*}

which proves (1).

---

Fourth step: Generating function $P(z)$ of partitions

We use the following constructions and corresponding generating functions from above: \begin{array}{ll} \mathcal{B}_b=\text{SEQ}_{(odd,>1)}\{\bullet\}\qquad&\qquad B_b(z)=\frac{z^3}{1-z^2}\\ \mathcal{B}_r=\text{SEQ}_{(odd,>1)}\{\circ\}\qquad&\qquad B_r(z)=\frac{z^3}{1-z^2}\\ \mathcal{B}_{(b,r)}=\text{SEQ}_{(odd,>1)}\{\bullet,\circ\}\qquad&\qquad B_{(b,r)}(z)=\frac{2z^3}{1-z^2}\\ \end{array}

Observe, that partitions can be considered to be multisets. E.g. the partition $13=3+5+5$ corresponds to the multiset $\{3,5,5\}$. We now refer to Flajolets section of a Multiset construction.

According to the Multiset construction (Flajolet I.2.2, number (24)), the construction $\mathcal{P}$ of all partitions of $\mathcal{B}_{(b,r)}$ and the corresponding generating function $P(z)$ is \begin{align*} \mathcal{P}&=\text{MSET}\left(\mathcal{B}_{(b,r)}\right)\\ &\cong\prod_{\beta\in\mathcal{B}_{(b,r)}}\text{SEQ}\left(\{\beta\}\right)\\ &=\prod_{\beta\in\mathcal{B}_b+\mathcal{B}_r}\text{SEQ}\left(\{\beta\}\right)\\ &=\prod_{\beta\in\mathcal{B}_b}\text{SEQ}\left(\{\beta\}\right) \times \prod_{\beta\in\mathcal{B}_r}\text{SEQ}\left(\{\beta\}\right)\\ \\ P(z)&=\prod_{n=1}^{\infty}\frac{1}{1-z^{2n+1}}\prod_{n=1}^{\infty}\frac{1}{1-z^{2n+1}}\\ &=\prod_{n=1}^{\infty}\left(\frac{1}{1-z^{2n+1}}\right)^2\\ \end{align*}

which proves (2).

---

Hint: Flajolets book is an outstanding classic. Maybe you'd like to have a look at my answer to this question if you are interested in corresponding literature.