Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

Help with combinatorial proof of binomial identity: $\sum\limits_{k=1}^nk^2{n\choose k}^2 = n^2{2n-2\choose n-1}$. (Similar)

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.

share|improve this question

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.