12
votes
2answers
327 views

Show $\binom{n}{k}\binom{k}{a} = \binom{n}{a}\binom{n-a}{k-a}$ by block-walking interpretation of Pascal's triangle

A combinatorial proof for the identity $$\binom{n}{k}\binom{k}{a} = \binom{n}{a}\binom{n-a}{k-a}$$ is the following "committee" argument, which seems the most common. There are $\binom{n}{k}$ ...
0
votes
1answer
208 views

Proving Binomial Identities Using Bijections To Lattice Paths

How can I derive a bijection to show that the following equality holds? $2\displaystyle\sum\limits_{j=0}^{n-1} \binom{n-1+j}{j} = \binom{2n}{n}$ In class, we've been deriving bijections using ...
0
votes
1answer
356 views

Lattice Paths Question

You know, how we can have lattice paths, where we can move either one block north, or one block east, and we have the find all the possible ways of reaching the point (x.y) from (0,0). That is ...
4
votes
1answer
219 views

Proving this identity $\sum_k\frac{1}{k}\binom{2k-2}{k-1}\binom{2n-2k+1}{n-k}=\binom{2n}{n-1}$ using lattice paths

How can I prove the identity $\sum_k\frac{1}{k}\binom{2k-2}{k-1}\binom{2n-2k+1}{n-k}=\binom{2n}{n-1}$? I have to prove it using lattice paths, it should be related to Catalan numbers The $n$th ...