bijections between sets

78 Views Asked by At

Let $P_n$ be the set of compositions of $n$ where each part is at least $2, Q_n$ be the set of compositions of $n$ where each part is odd, and $R_n$ be the set of compositions where each part is $1$ or $2.$ Prove using bijections that $|P_n| = |Q_{n-1}| = |R_{n-2}|.$

I can prove the result using generating series but it seems much harder to find the stated bijection. The generating series for $P^*, Q^*,$ and $R^*,$ where $S^*$ is the set of all compositions that are in $S^k$ for some $k\geq 0$ (e.g. $() \in P^0 \subseteq P^*, (2) \in P^1 \subseteq P^*,$ etc. ) are, respectively, $1 + \dfrac{x^2}{1-x-x^2}, 1 + \dfrac{x}{1-x-x^2}, \dfrac{1}{1-x-x^2}$. These are clearly very similar, but I'm not sure how to make use of that through a bijection. I was thinking of considering $0$'s and $1$'s or some other kind of encoding, but I can't find one that'll work.

1

There are 1 best solutions below

1
On BEST ANSWER

Small hints:

  • Do not worry about the generating functions, I do not think they lead to the bijections easily.

  • It is easiest to prove $R_{n-2}\cong P_n$ and $R_{n-2}\cong Q_{n-1}$ (or equivalently, $R_{n-1}\cong Q_n$).

  • Here is a hint for proving $R_{n-1}\cong Q_n$. Given a composition in $R_{n-1}$, meaning a sum of $1$'s and $2$'s, try to group certain summands together to make a composition in $Q_n$.