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

  • 0
    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$.2011-11-08
  • 0
    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$.2011-11-08
  • 0
    I have deleted my answer as I misunderstood the question.2011-11-08
  • 0
    @Swapan I'd still like to thank you and ask if your misunderstanding came from the way I described or presented the problem? Please be honest, because I'm always looking for ways to improve my mathematical writing.2011-11-08
  • 0
    @AndréNicolas I knew my formula wasn't elegant in any respect when I derived it, but your misunderstanding it makes me want to ask if there is a better way I could have written that sum. (For starters, I see that the formula uses all three notations for multiplication, $\cdot, \times$ and juxtaposition.)2011-11-08
  • 0
    @sasha: There is no problem with your reasoning. I misunderstood the problem--I was thinking of "number of ways", rather than counting the number of individual chords. So please feel no worry about this.2011-11-08
  • 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.2011-11-08
  • 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