I was recently doing a homework problem that involved finding the number of lines used to connect a given number of points on a circle. Looking at it logically, I saw that that for the first point, there would be $n-1$ lines you could draw (where $n$ is the number of points on the circle) and the next point would have $n-2$ lines because you're not repeating the line between point $1$ and point $2$. It made sense that this would continue until point $n$, at which point there would be zero lines you can draw.
This meant that if you just add up all of those, you'd get the number.
For example, in the picture below there are $12$ points, so
$11+10+9+8+7+6+5+4+3+2+1 = 66$ lines.
That's all fine, but the weird thing was, when I looked in the back of the book, the answer was given as $\binom{n}{2}$, which also equals $66$. What's the relationship? Why are the two equal?
Answer
$$\sum_{k=0}^n k = \frac{(n+1)n}{2}$$
And
$$\binom nk = \frac{n!}{k!(n-k)!} = \frac{n\cdot(n-1)\cdots(n-k+1)}{k!}$$
In particular
$$\binom n2 = \frac{n(n-1)}{2} = \sum_{k=0}^{n-1} k$$
Another way to see it is by induction. In particular $\binom 1 2 = 0$, and $\binom {n+1}{2} = \binom{n}{1} + \binom{n}{2}$, which probably makes the identity seem a bit less "random".
No comments:
Post a Comment