Tags: | Posted by Admin on 2/23/2012 10:35 AM | Comments (10)

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

Comments (10) -

kaushik United States on 3/7/2012 12:48 AM n ways we can draw.
kaushik United States on 3/7/2012 12:49 AM n ways.
Admin United States on 3/7/2012 12:46 PM @kaushik  why do you think so?
David United States on 3/21/2012 11:31 AM According to the Internet, the answer is the nth Catalan number or (2n choose n)/(n-1). Whenever I count them, this works but I have not yet figured out why.
Ben United States on 3/22/2012 6:53 PM Definitely not n. The answer should be the nth catalan number, or 1/(n+1) * \binom{2n}{n}.
Ben United States on 3/23/2012 7:52 PM Definitely not n. Just check it for small numbers (n=3) to see this is wrong. I believe the answer is the nth Catalan number, or 1/(n+1) * \binom{2n}{n}. You can prove this by coming up with a recurrence relation.

(It appears my first comment disappeared, so I'm posting again.)
hadi Canada on 4/7/2012 3:07 PM Let's name the points in order by Pi for i=1 to 2n. Choose a point, say P1. For point P1, there is n ways to draw an acceptable chord, i.e., a chord that leads to a non-intersecting set of other chords; such a chord needs to be drawn from P1 to P2i where i=1 to n.

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)
T(n+1)=\sum_{i=0}^n T(i) T(n-i)
which leads to the Catalan number.
sjr celestia United States on 4/10/2012 4:02 AM ask a useful one...........
Ruslan Russia on 4/16/2012 2:35 AM This is one of definitions of Catalan numbers.
The answer is binom{2n}{n} / (n - 1

You can find it on http://en.wikipedia.org/wiki/Catalan_number (Applications in combinatorics)
SpotZup France on 11/19/2012 2:03 PM I can't find the Catalan number as most of you do. Take n=2, so we have a circle with 2n=4 points. Well, there is at least 10 ways to draw n=2 non-intersecting chords. The four L-shaped ways, the four 7-chaped ways, and two extra ways with 2 parallels chords. That is much more than the second Catalan number, where am I wrong ?

Add comment

  Country flag
  • Comment
  • Preview