# How to Devise Combinatorial Arguments for Proving Identities

What are some strategies or tips for contriving/devising combinatorial arguments?

Combinatorial proof for $\binom{n}{a}\binom{a}{k}\binom{n-a}{b-k} = \binom{n}{b}\binom{b}{k}\binom{n-b}{a-k}$?

I might divine that $\{a\}, \{b\} \subseteq \{n\}$, but how and why would you realise :

LHS = # of ways to pick either team $\times$ # of ways to pick all leaders for both teams
RHS = $\times$ # of ways to pick all leaders for both teams $\times$ # of ways to pick either team

RHS: The $2n - 2$ suggest that out of the $2n$ things, the $2$ subtracted may be special roles. Then?

LHS: How would $k^2\binom{n}{k}^2$ divulge: For each of the $1 \le k \le n$ women,
$LHS =$ the # of ways to select women $\times$ the # of ways to select the female cocaptain
$\times$ the # of ways to select the male cocaptain $\times$ the # of ways to select the male players?

P18, Ex 1.12(c), A 1st Course in Pr, Ross: $\sum_{k=0}^n {k^3 {n \choose k}} = n^2(2n + 3)2^{n - 3}$

The RHS has no binomial coefficients, so how would you divine/previse to consider all 5 cases of: the total # of ways of forming a committee of $n$ people with a chair, secretary:

$1.$ Chair = Secretary = Treasurer.
$2.$ Chair = Secretary, $\qquad 3.$ Secretary = Treasurer, $\qquad 4.$ Chair = Treasurer.
$5.$ Chair $\neq$ Secretary $\neq$ Treasurer.

With alternating signs, this question requiring a wily change of variable is still more intricate.

-