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.


marked as duplicate by Hanul Jeon, Davide Giraudo, Johannes Kloos, Dennis Gulko, azimut Nov 17 '13 at 10:55

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Do you already know how many permutations there are of $m$ A’s and exactly $n$ B’s? $\endgroup$ – Brian M. Scott Sep 20 '11 at 1:51
  • $\begingroup$ m+n spots, so (m+n) choose (m) ways to place A. $\endgroup$ – Gbean Sep 20 '11 at 2:08
  • $\begingroup$ Good: that’s all that you really need in order to follow Thijs’s solution. $\endgroup$ – Brian M. Scott Sep 20 '11 at 2:18
  • $\begingroup$ Srivatsan’s argument is very elegant, but the identity at the end of Thijs’s solution is well worth knowing, as is its ‘dual’ $\sum_{i=m}^n \binom{m+i}{m} = \binom{m+n+1}{m+1}$. $\endgroup$ – Brian M. Scott Sep 20 '11 at 7:15
  • $\begingroup$ A question from Sep 2011 marked as duplicate of one of Apr 2013; the mention "This question has been asked before..." would seem somewhat unjustified. $\endgroup$ – Marc van Leeuwen Nov 18 '13 at 4:48

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$$


Not the answer you're looking for? Browse other questions tagged or ask your own question.