0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ $$\sum_{i=0}^m\sum_{j=0}^n \frac {(i+j)!}{i!j!}$$=$$\sum_{i=0}^m\sum_{j=0}^n \binom {i+j}{j}$$ $\endgroup$ Feb 13, 2018 at 6:15

2 Answers 2

2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Thanks, great answer. +1. $\endgroup$
    – vs_292
    Feb 13, 2018 at 6:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .