Prove that the number of permutations of $m$ A's and at most $n$ B's equals $\dbinom{m+n+1}{m+1}$.
I'm not sure how to even start this problem.
Tell me more
×
Mathematics Stack Exchange is a question and answer site for
people studying math at any level and professionals in related fields. It's 100% free, no registration required.
|
|
|||||||||
|
|
Here's a combinatorial solution. Take a string $\alpha$ containing exactly $m+1$ A's and $n$ B's. Identify the final occurrence of $A$ in $\alpha$. Form the string $\beta$ by deleting this final occurrence of $A$ and all the characters that follow it (the characters following it must all be $B$). It is clear that $\beta$ contains exactly $m$ A's and at most $n$ B's. Further, the strings $\alpha$ and $\beta$ are in one-to-one correspondence with each other. (We already described how to obtain $\beta$ from $\alpha$. To write down $\alpha$ given $\beta$, concatenate $\beta$ with an $A$ followed by enough $B$'s to make the total number of $B$'s exactly equal to $n$.) Thus the number of permutations with $m$ A's and at most $n$ B's is equal to the number of permutations with exactly $m+1$ A's and exactly $n$ B's, which is clearly $\binom{m+n+1}{m+1}$. |
|||
|
|
|
By summing all possibilities of $n$, we get that the number of permutations $P_n$ satisfies $$P_n = \binom{m+n}{n} + \binom{m+(n-1)}{(n-1)} + \ldots + \binom{m+0}{0} = \sum_{i=0}^n \binom{m + i}{i}$$ Note that $$\binom{a}{b} = \binom{a-1}{b} + \binom{a-1}{b-1}$$ Repeatedly applying this to the last term, we get $$\begin{array}{rcl} \binom{a}{b} &=& \binom{a-1}{b} + \binom{a-1}{b-1} \\ &=& \binom{a-1}{b} + \binom{a-2}{b-1} + \binom{a-2}{b-2} \\ &=& \binom{a-1}{b} + \binom{a-2}{b-1} + \binom{a-3}{b-2} + \binom{a-3}{b-3} \\ &=& \binom{a-1}{b} + \binom{a-2}{b-1} + \binom{a-3}{b-2} + \binom{a-4}{b-3} + \ldots \\ &=& \binom{a-1}{b} + \binom{a-2}{b-1} + \binom{a-3}{b-2} + \binom{a-4}{b-3} + \ldots + \binom{a-b-1}{0} \\ &=& \sum_{i=0}^b \binom{a-b-1+i}{i} \end{array}$$ Substituting $b$ by $a-b$ we similarly get $$\binom{a}{a-b} = \sum_{i=0}^{a-b} \binom{b-1+i}{i}$$ Replacing $b = m + 1$ and $a = n + m + 1$ we thus get $$\binom{n + m + 1}{n} = \sum_{i=0}^{n} \binom{m+i}{i} = P_n$$ |
|||
|
|
