Help finding a combinatorial proof of ${kn \choose 2}= k{n \choose 2}+n^2{k \choose 2}$

Question

Hi I have been trying to find a way to find a combinatorial proof for ${kn \choose 2}= k{n \choose 2}+n^2{k \choose 2}$.

Answer 1

Hint: You want to pick $2$ elements out of $k$ buckets of $n$ elements each. You have two possible ways to do it: either you pick a bucket, and then you take $2$ elements from this bucket, or you pick $2$ buckets and then you choose one element from each of those $2$ buckets.

Answer 2

Consider a set of $k\cdot n$ elements allocated in a grid with $n$ rows and $k$ columns then

• on the LHS we have the ways to choose $2$ elements among all of them
• on the RHS we have the cases with 2 elements choseen from a same row $k{n \choose 2}$ and the cases 2 elements choseen from a same column $n{k \choose 2}$ and the orther cases with $2$ elements chosen form different columns and rows $nk+(n-1)(k-1)$, indeed

$$k{n \choose 2}+n{k \choose 2}+nk+(n-1)(k-1)=k{n \choose 2}+n^2{k \choose 2}$$

Answer 3

As an addendum to Daniel Robert-Nicoud’s excellent hint, I find it helpful to rewrite the equality in the following way:

$$\binom{kn}{2} = \binom{k}{1}\binom{n}{2} + \binom{k}{2}\binom{n}{1}\binom{n}{1}.$$

By reading multiplication as “and then,” and addition as “or,” try to recover Daniel’s narrative by reading off the right-hand side.

---

With this thought process in mind, try to come up with a formula for $\binom{nk}{3}$. Can you generalize this pattern?