[Math] How many compositions of n are there in which each part is an even number

combinatorics

I need to find out how many compositions of n there are in which each part is an even number.

I think I have the correct generating function by doing the following:

$$S = ∪_{k\geq0}N_{even}^k$$

where $k=0$ is the empty composition and $N_{even}=\{2,4,6,…\}$ so,

$$\Phi_S(x) = \Phi_{∪_{k\geq0}N_{even}^k}(x)$$

$$\Phi_S(x) = \sum\limits_{k\geq0}^{} \Phi_{N_{even}^k}(x)$$

$$\Phi_S(x) = \sum\limits_{k\geq0}^{} (\sum\limits_{i\geq0}^{}x^{2i+2})^k$$

$$\Phi_S(x) = \sum\limits_{k\geq0}^{} (x^2(1-x^2)^{-1})^k$$

$$\Phi_S(x) = \dfrac{1}{1-(x^2(1-x^2)^{-1})}$$

$$\Phi_S(x) = \dfrac{1-x^2}{1-2x^2}$$

and the number of compositions would be
$$[x^n](\dfrac{1-x^2}{1-2x^2})$$

Simplifying this to find the number of compositions is where I get stuck. Any help would be appreciated!

Best Answer

How about finding the number of compositions of $\frac n2$ and then doubling all the parts? Since there are $2^{\frac n2-1}$ of them, that is the number of compositions of $n$ into even parts.

Related Solutions

[Math] Generating Series for the set of all compositions which have an even number of parts.

The number of compositions of $n$ with exactly $k$ parts is $\dbinom{n-1}{k-1}$, so the generating function for the number of compositions with an even number of parts is

$$g(x)=\sum_{n\ge 0}\left(\sum_{k\ge 0}\binom{n-1}{2k-1}\right)x^n\;.\tag{1}$$

$\displaystyle\sum_{k\ge 0}\binom{n-1}{2k-1}$ is simply the number of subsets of $\{1,\dots,n-1\}$ with an odd number of elements. For $n\le 1$ that’s clearly $0$, so we can rewrite $(1)$ as

$$g(x)=\sum_{n\ge 2}\left(\sum_{k\ge 0}\binom{n-1}{2k-1}\right)x^n=x^2\sum_{n\ge 2}\left(\sum_{k\ge 0}\binom{n-1}{2k-1}\right)x^{n-2}=x^2\sum_{n\ge 0}\left(\sum_{k\ge 0}\binom{n+1}{2k-1}\right)x^n\;.$$

Now $\displaystyle\sum_{k\ge 0}\binom{n+1}{2k-1}$ is the number of subsets of $\{1,\dots,n+1\}$ having an odd number of elements, and since $n+1\ge 1$, this has a simple closed form that you should know. Let’s say that that closed form is $f(n)$. Then you have

$$g(x)=x^2\sum_{n\ge 0}f(n)x^n\;,$$

where you should be able to recognize the generating function for $\displaystyle\sum_{n\ge 0}f(n)x^n$ fairly easily.

Added: If you follow the convention that $0$ has one composition, of size $0$, then $g(x)$ should have a constant term $1$ in addition to the terms given by $(1)$.

[Math] How many compositions of n with k parts are there in which each part is a even number except that a 1 may occur as a part at most once

Method 1 (counting).

The number of compositions of $n$ is $2^{n-1}$, via standard stars and bars: a composition corresponds to lining up $n$ stars in a row, and inserting bars in any subset of the $n-1$ gaps.

Similarly, the number of compositions of $n$ into $k$ parts is $\binom{n-1}{k-1}$: choose $k-1$ of the $n-1$ gaps to insert bars in.

The compositions we care about for this question are those that either

have all parts even: $n = 2a_1 + 2a_2 + \dots + 2a_k$, which corresponds via the observation that $n/2 = a_1 + a_2 + \dots + a_k$ to an arbitrary composition of $n/2$ into $k$ parts, whose number is $2^{n/2 - 1}$ (if $n$ is even, and $0$ otherwise).
have exactly one part equal to $1$, and the other parts even: this can be either the first part ($n = 1 + 2a_1 + 2a_2 + \dots + 2a_{k-1}$) or the second part ($n = 2a_1 + 1 + 2a_2 + \dots + 2a_{k-1}$)... or any part up to the $k$th part ($n = 2a_1 + 2a_2 + \dots + 2a_{k-1} + 1$). Note that all these compositions are distinct. In each case, any such composition corresponds via the observation that $\frac{n - 1}{2} = a_1 + a_2 + \dots + a_{k-1}$ to an arbitrary partition of $\frac{n-1}{2}$ into $k-1$ parts, whose number is $\binom{(n-1)/2-1}{k-1}$ (if $n$ is odd, and $0$ otherwise).

So the answer is

$$\binom{n/2 - 1}{k-1}[n\text{ is even}] + k\binom{(n-1)/2 - 1}{k-1}[n\text{ is odd}].$$

Method 2 (generating functions).

Let $\mathcal{E}$ denote the class of all positive even numbers. We have a specification and consequent generating function for $\mathcal{E}$ as $$\mathcal{E} = \operatorname{S\scriptsize EQ}_{\ge 1}(\mathcal{Z}\times\mathcal{Z})$$ $$E(z) = \frac{z^2}{1-z^2}$$ (Check that $E(z) = z^2 + z^4 + z^6 + \dots$ as expected.)

Let $\mathcal{C}$ denote the class of compositions of the kind we want. A specification for $\mathcal{C}$ is, considering the compositions with all parts even, and then with first part $1$, second part $1$, and so on: $$ \mathcal{C} = (\mathcal{E}\times\cdots\times\mathcal{E}) + (\mathcal{Z}\times\mathcal{E}\times\cdots\times\mathcal{E}) + (\mathcal{E}\times\mathcal{Z}\times\cdots\times\mathcal{E}) + \dots + (\mathcal{E}\times\cdots\times\mathcal{E}\times\mathcal{Z}) $$ which in simpler notation is $$\mathcal{C} = (\mathcal{E}^k) + k(\mathcal{Z}\times\mathcal{E}^{k-1})$$ giving the generating function $$C(z) = E(z)^k + kzE(z)^{k-1}$$ which with our previously found generating function $E(z)$ is $$C(z) = \left(\frac{z^2}{1-z^2}\right)^k + kz\left(\frac{z^2}{1-z^2}\right)^{k-1}.$$

Note: it is possible to derive the coefficients from the generating function, or the generating function from the coefficients, but depending on what you're after (closed forms or asymptotics), it may not be worth going that route.

For example, from $C(z)$ we can get $C_n = [z^n]C(z)$ by calculating coefficients. $$[z^n]\left(\frac{z^2}{1-z^2}\right)^k = [z^{n-2k}](1-z^2)^{-k} = [z^{n/2-k}](1-z)^{-k}[n\text{ is even}] = (-1)^{n/2-k}\binom{-k}{n/2-k}[n\text{ is even}] = \binom{n/2-1}{n/2-k}[n\text{ is even}] = \binom{n/2-1}{k-1}[n\text{ is even}]$$ (would be a bit faster if you know beforehand that $[z^n]\left(\frac{z}{1-z}\right)^r = \binom{n-1}{r-1}$) and similarly $$[z^n]\left(kz(\frac{z^2}{1-z^2})^{k-1}\right)=k[z^{(n-1)/2}](\frac{z}{1-z})^{k-1}[n\text{ is odd}] = k\binom{(n-1)/2 - 1}{k-1}[n\text{ is odd}].$$

Best Answer

Related Solutions

[Math] Generating Series for the set of all compositions which have an even number of parts.

[Math] How many compositions of n with k parts are there in which each part is a even number except that a 1 may occur as a part at most once

Related Question