3
$\begingroup$

$n$ points are given on a circle. I'm looking for a formula for the number of pairs of disjoint chords connecting them. What I have so far:

I count the number of pairs of interior intersecting chords and subtract from the total number of pairs of chords on $n$ points. The latter can be calculated using: $\frac{\binom{n} {2}\binom{n-2}{2}}{2!}$

To count pairs of intersecting chords, I essentially go around the circle quadruple-counting the pairs (once for every point). Every chord determines two sides of the circle (half-planes) in which there are as few as 1 and as many as $n-3$ points for which points on one side can be connected with another point on the other side creating a pair of intersecting chords. In this manner, I get the following overcount:

$n\times(1\cdot(n-3)+2\cdot(n-4)+3\cdot(n-5)+\ldots+(n-3)\cdot1)$

Dividing this by 4 and subtracting from the total is my formula:

$\frac{\binom{n} {2}\binom{n-2}{2}}{2}-\frac{n\times(1\cdot(n-3)+2\cdot(n-4)+3\cdot(n-5)+\ldots+(n-3)\cdot1)}{4}$

Can anyone verify that my argument is valid?

1 Answers 1

1

There is a simple answer to the chord-pair counting problem. Take any $4$ of our points. They determine $2$ pairs of chords that do not meet. So the answer should be something equivalent to $2\binom{n}{4}.$

  • 1
    @Sasha: Your method can be "finished" more quickly. You chose $2$, then chose $2$, then divided by $2!$ to get rid of order. Look at choices that give rise to a particular *set* of $4$. There are $3$ of them. One is bad (inner intersection point) and $2$ are good. So the answer is $(2/3)\binom{n}{2}\binom{n-2}{2}/2!$.2011-11-08