The question is in the title. I have no idea how to do this one. I was trying to rewrite $n^2$ as $\binom {n}{1} \times \binom {n}{1}$. I was going to say the story is, suppose there are $n$ boys and $n$ girls. How many ways there are to pick $1$ boy and $1$ girl, which is the LHS. But then I don't have any idea how to prove the RHS.

  • 2
    $\begingroup$ I see it geometrical: are of square equals sum of areas of two rectangles $n\cdot (n-1)$ and $n\cdot 1$. $\endgroup$
    – zkutch
    Oct 18 at 23:50
  • $\begingroup$ I note $n(n-1) = 2 \binom{n}{2}$. $\endgroup$ Oct 18 at 23:53
  • $\begingroup$ @zkutch omg that's so clever! $\endgroup$ Oct 19 at 0:26

One idea: consider counting ordered pairs of integers $(a, b)$ in the range $\{1, \ldots, n\}$. Count the cases $a = b$ and $a \neq b$ separately.


If we have two people that need to choose from $n$ items (not necessarily distinct),

then there are $n \cdot n = n^{2}$ possibilities.

If we instead count the distinct possibilities first we subtract one for the second person's choice, which gives $n(n-1)$.

Note that since we have $n$ items, there are exactly $n$ possibilities where they do choose the same item.

These are independent choices with the union being the first counting method:

i.e. Distinct + Not distinct = Not necessarily distinct.

Hence we add them and get $n^{2}=n(n-1)+n$.

  • $\begingroup$ thank you! I has this thought at first but I denied it for some reason. $\endgroup$ Oct 19 at 0:24

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.