Number of compositions of n

Question

Prove that for $n\ge2$, the number of compositions of $n$ where the first part is 1 is equal to the number of compositions of $n$ where the first part is greater than 1.

This is what I am stuck on. I got that the number of compositions of $n$ where the first part is 1 is $$[x^{n-1}] \frac{1-x}{1-2x}$$ and the number of compositions where the first part is greater than 1 is $$[x^n] \frac{1-x}{1-x-x^2}$$ but I don't know how to show that they are equal to each other.

Can someone help me please?

Answer 1

Different approach: Biject between $1+a_1+a_2+\cdots+a_k$ and $(1+a_1)+a_2+\cdots+a_k$.

Answer 2

We have $n$ copies of X in a row, like this: $$ \text{X}\quad\text{X}\quad\text{X}\quad\text{X}\quad\text{X}\quad\text{X}\quad\text{X}\quad\text{X}\quad\text{X}\quad\text{X}\quad\text{X}\quad\text{X}\quad\text{X}\quad\text{X}$$

This determines $n-1$ "gaps." We choose any number of these gaps, possibly $0$, to put a separator into. So there are just as many compositions of $n$ as there are subsets of an $n-1$-element set, namely $2^{n-1}$.

Now consider the choices where we put a separator immediately after the leftmost X. So now we are choosing any number of gaps from the remaining $n-2$. There are $2^{n-2}$ ways to do this.

That is half the total number of compositions. Thus there are $2^{n-2}$ compositions that start with a number bigger than $1$.

Remark: The generating function mentioned in the OP for the number of compositions with first element greater than $1$ is not correct.

Answer 3

I've upvoted vadim123's bijective answer (which I think is the best way of seeing this), but if you want to do it via your original approach of generating functions, note that the second one you wrote is not correct.

A composition where the first part is $1$, or in other words something that has the form "$1$" followed by a sequence of positive integers, can be denoted (following the notation of the book Analytic Combinatorics) as $\mathcal{Z} \times \operatorname{S\scriptsize EQ}(\mathcal{I})$ where $\mathcal{I}$ denotes the class of positive integers $\{1, 2, 3, \dots\}$ (with the "size" of an integer being that integer itself). In other words $\mathcal{I} = \operatorname{S\scriptsize EQ}_{\ge 1}(\mathcal{Z})$ and it has generating function $\frac{z}{1-z}$, which means that the GF for compositions with first part $1$ is $$z \frac{1}{1-\frac{z}{1-z}} = \frac{z(1-z)}{1-2z},$$ as you got.

The class of compositions where the first part is greater than $1$, and therefore at least $2$, is $$\operatorname{S\scriptsize EQ}_{\ge 2}(\mathcal{Z}) \times \operatorname{S\scriptsize EQ}(\mathcal{I}) \\ = \operatorname{S\scriptsize EQ}_{\ge 2}(\mathcal{Z}) \times \operatorname{S\scriptsize EQ}(\operatorname{S\scriptsize EQ}_{\ge 1}(\mathcal{Z})) $$ and therefore has generating function $$\frac{z^2}{1-z} \frac{1}{1-\frac{z}{1-z}} = \frac{z^2}{1-2z}, $$ different from what you got.

These are different expressions, but if we denote $T_n = [z^n]\frac{1}{1-2z}$, then the coefficient of $z^n$ in the first GF is $T_{n-1} - T_{n-2}$, and in the second GF is $T_{n-2}$, which happen to both be equal to $2^{n-2}$ as $T_n = 2^n$ for all $n$.