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?

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ My formula gives 3-1=2 which is how many disjoint chord-pairs there are for $n=4$. BTW, thank you for simplifying it! Edit- I get 15-5=10 for $n=5$. $\endgroup$ – sasha Nov 8 '11 at 19:33
  • $\begingroup$ It looks as if I did not understand your formula. For $n=4$ it looked as if there was a term $1(4-3)$ and also at the end a term $(4-3)1$. $\endgroup$ – André Nicolas Nov 8 '11 at 19:44
  • $\begingroup$ I have deleted my answer as I misunderstood the question. $\endgroup$ – Tapu Nov 8 '11 at 19:45
  • 1
    $\begingroup$ @Sasha: Maybe the subtracted term could be described in summation notation. Usually I prefer $\dots$, but summation would help clear ambiguities. Then the term can be given closed form. $\endgroup$ – André Nicolas Nov 8 '11 at 21:25
  • 1
    $\begingroup$ @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!$. $\endgroup$ – André Nicolas Nov 8 '11 at 23:37

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.