7
$\begingroup$

This identity was posted a while back but the question had been closed; the question wasn't asked elaborately, though the proof of the identity is a nice application of combinatorics and a good example for future reference.

Also, there was just a flat-out wrong answer which had a couple of upvotes, so I thought to give my own possible proof and sort of 'reopen' the question that was left. Hopefully this time the question will have enough context to stay alive.

As a side note: the given right side does not appear symmetric between $k$ and $n$. However, when $\binom{m}{2}=m(m-1)/2$ is inserted and the products expanded, only symmetric terms remain uncancelled. Rendering the right side as $k^2\binom{n}{2}+n\binom{k}{2}$ would give the same cancellations and the same net value.

Proof

Suppose you have a grid of $n\times k$ dots. Firstly, the amount of ways to connect any two dots is $\binom{nk}{2}$. Now consider the right-hand side. We can split the cases for which the connected dots are on the same column, row, or are in both different columns and rows.

If the two connected dots are in the same column, we can choose two points from any two different rows in $\binom{n}{2}$ ways, and we have $k$ columns for which the two points can be on the same column, which gives a total of $k\binom{n}{2}$ options. The same argument holds for constant rows: $n\binom{k}{2}$.

Now if neither the row nor the column can stay constant, we can pick any point in $nk$ ways, and choose the second point from the remaining $(n-1)(k-1)$ points; one column and one row will be unavailable. This gives us $\frac{nk(n-1)(k-1)}{2}$ options, as we have to rule out the double counting.

We will now show (algebraically) that $n\binom{k}{2}+\frac{nk(n-1)(k-1)}{2}=n^2\binom{k}{2}$. We have that $\binom{k}{2}=\frac{k(k-1)}{2} =\frac{nk(n-1)(k-1)}{2n(n-1)} \iff n(n-1)\binom{k}{2}=\frac{nk(n-1)(k-1)}{2}=n^2\binom{k}{2}-n\binom{k}{2}$ which leads to the equation above.

Combining these cases gives $\binom{nk}{2}=k\binom{n}{2}+n\binom{k}{2}+\frac{nk(n-1)(k-1)}{2} = k\binom{n}{2}+n^2\binom{k}{2}$

If there are any mistakes or improvements on the arguments, please feel free to point them out.

$\endgroup$
  • $\begingroup$ Uh ... How is the left side symmetric when $n$ and $k$ are interchanged and the right side isn't? $\endgroup$ – Oscar Lanzi Mar 30 at 22:28
  • $\begingroup$ @OscarLanzi The right side is symmetric too, just not obviously so. $\endgroup$ – Michael Biro Mar 30 at 22:32
  • 1
    $\begingroup$ I have now explained it. Feel free to roll back the edit if you feel it is inappropriate. $\endgroup$ – Oscar Lanzi Mar 30 at 23:11
5
$\begingroup$

I don't think you need as many cases, which saves a little algebra. We have $k$ groups of $n$ dots each, so choosing two of them can be done in $\binom{nk}{2}$ ways.

Alternatively, both are in the same group of $n$ which has $\binom{k}{1} \cdot \binom{n}{2}$ possibilities, or they are in different groups of $n$, which has $\binom{k}{2} \binom{n}{1}^2$ possibilities.

Therefore, $\binom{nk}{2} = k \binom{n}{2} + n^2 \binom{k}{2}$

$\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.