Combinatorics-number of permutations of $m$ A's and at most $n$ B's 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.
 A: 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$$
A: 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}$. 
