4
$\begingroup$

Is it possible to prove the following identity using combinatorial argument :

$$\left[\sum _{k=0}^{n} {n \choose k}\right] ^ 2 = \sum_{k=0}^{2n}{2n \choose k}$$

$\endgroup$
6
$\begingroup$

Suppose that you have a group of $n$ mixed couples. The lefthand side is the number of ways to choose a set of $k$ men and a set of $\ell$ women for some $k,\ell\in\{0,\dots,n\}$; the righthand side is the number of ways to choose an arbitrary subset of the group. Clearly these are the same.

$\endgroup$
2
$\begingroup$

One can easily give a combinatorial argument for that identity, but the understanding of the situation is not complete without observing that the identity is immediate from the auxiliary formulas $$ \sum_{k=0}^m \binom mk = 2^m \quad\text{for all $m\in\mathbf N$, and}\qquad (2^n)^2 = 2^{2n}, $$ both of which are obvious and have obvious combinatorial proofs, via $$ \left[\sum_{k=0}^n \binom nk\right]^2=(2^n)^2 = 2^{2n} =\sum_{k=0}^{2n} \binom {2n}k. $$ If you compose the bijection corresponding to the first identity above for $m=n$ (which involves double counting of the subsets of an $n$-set), with the one for $(2^n)^2 = 2^{2n}$ (which involves double counting of the subsets of the disjoint union of two $n$-sets), and then again with the bijection for the first identity but for $m=2n$ and in the opposite direction, then you get a bijection for the outer identity given in the question. Indeed this is exactly the bijection described in the answers by Brian Scott and anon.

$\endgroup$
1
$\begingroup$

Sure. Let $\displaystyle{X\choose k}$ denote the $k$-subsets of a set $X$. Then, supposing $|X|=n=|Y|$, we have

$$\begin{array}{cl} \left[\bigsqcup_{k=0}^n{X\choose k}\right]\times\left[\bigsqcup_{\ell=0}^n{Y\choose \ell}\right] & \cong\bigsqcup_{k=0}^n\bigsqcup_{\ell=0}^n\left[{X\choose k}\times{Y\choose\ell}\right] \\ & \cong\bigsqcup_{m=0}^{2n}\left[\bigsqcup_{k=0}^m{X\choose k}\times{Y\choose m-k}\right] \\ & \cong \bigsqcup_{m=0}^{2n}{X\sqcup Y\choose m}.\end{array}$$

Combinatorial arguments come in the form of counting pieces of some structure, then rearranging or reinterpreting the structure (bijecting it with a different structure, if only superficially different) in a manner that retains the number of pieces, then counting the total again. Since the counting was done in two different ways, generally two different expressions result, and equating them yields a combinatorial identity of expressions involving combinatorial data.

The purest kind of structure is arguably just a set. The operations we have on sets include union, intersection, disjoint union, Cartesian product, power sets, $k$-subsets, and so forth. A combinatorial argument is a way of making an algebraic identity into a set-theoretic theorem, and this is possible thanks to the conspiracy of the following facts that mirror elementary algebra rules:

  • $\displaystyle\left|{X\choose k}\right|={|X|\choose k}$.
  • $|A\sqcup B|=|A|+|B|$
  • $|A\times B|=|A|\times|B|$
  • $\sqcup$ and $\times$ are associative, commutative
  • $\times$ distributes over $\sqcup$

The latter two are intended to be understood in an 'up to isomorphism' sense. Since the basic rules for sets and for counting values are mirrors of each other, it's no surprise that a combinatorial argument, put into symbolic form, would perfectly mirror a similar calculation done directly with numbers (indeed, Vandermonde's identity is tacitly used here; the identity is relatively clear for sets where it might not have been so for mere numbers).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.