I'm currently learning combinatorics and I'm using Richard A Brualdi's book. I was doing the exercises when I came across the question - Prove that the number of permutations of at most $m$ A's and at most $n$ B's equals ${m + n + 2 \choose m + 1} - 1$.
A previously similar question was for exactly $m$ A's and at most $n$ B's. For that, I just added up each of the permutation with 0 B's, 1 B, and so on up to $n$ B's. But for this question I'm a little confused.
On
The answer can simply be given by $$\sum_{i=0}^m\sum_{j=0}^n \binom {i+j}{i}$$ By hockey stick identity we get $$=\sum_{i=0}^m\sum_{j=0}^n \binom {i+j}{i}$$ $$\sum_{i=0}^m \binom {i+n+1}{i+1}=\sum_{i=0}^m \binom {i+n+1}{n}$$ $$=\sum_{i=0}^m \binom {i+n+1}{n}+\binom {n}{n}-\binom {n}{n}$$
Again by hockey stick identity
$$=\binom {m+n+2}{n+1}-1$$
You just need to do the same thing that you did for the previous question - all over again!
First of all, with exactly $m$ $A$'s:
$$\binom{m}{m}+\binom{m+1}{m}+\cdots\binom{m+n}{m}=\binom{m+n+1}{m+1}=\binom{m+n+1}{n}$$
(Hockey-stick identity). Now add all of those for varying $m$:
$$\binom{n+1}{n}+\binom{n+2}{n}+\cdots+\binom{m+n+1}{n}=\binom{n}{n}+\binom{n+1}{n}+\binom{n+2}{n}+\cdots+\binom{m+n+1}{n}-1=\binom{m+n+2}{n+1}-1=\binom{m+n+2}{m+1}-1$$
(by applying the same Hockey-stick identity again and at a convenient point adding and subtracting $\binom{n}{n}=1$).