Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

$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?

share|improve this question

1 Answer 1

up vote 1 down vote accepted

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

share|improve this answer
    
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$. –  sasha Nov 8 '11 at 19:33
    
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$. –  André Nicolas Nov 8 '11 at 19:44
    
I have deleted my answer as I misunderstood the question. –  Tapu Nov 8 '11 at 19:45
1  
@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. –  André Nicolas Nov 8 '11 at 21:25
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!$. –  André Nicolas Nov 8 '11 at 23:37

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.