Given 2n points on a circle.find the number of ways to draw n non intersecting chords.

### Comments (10) -

Add comment

biuquote

- Comment
- Preview

Given 2n points on a circle.find the number of ways to draw n non intersecting chords.

Add comment

biuquote

- Comment
- Preview

(It appears my first comment disappeared, so I'm posting again.)

A chord from P1 to P2i, halves the rest of the space causing two half-circles with 2(i-1) and 2(n-i) points. For each half circle the same problem can be defined. Let T(x) denote the number of ways to draw x non-intersecting chords between 2x points. We have:

T(n)=\sum_{i=1}^n T(i-1) T(n-i)

or

T(n+1)=\sum_{i=0}^n T(i) T(n-i)

which leads to the Catalan number.

The answer is binom{2n}{n} / (n - 1

You can find it on http://en.wikipedia.org/wiki/Catalan_number (Applications in combinatorics)