Joining points

Ten points P 1 , P 2 , , P 10 P_1,P_2,\ldots ,P_{10} are equally spaced around a circle. They are connected in separate pairs by 5 5 line segments. How many ways can such line segments be drawn so that only one pair of line segments intersect?

Bonus: Generalise for 2 n 2n equally spaced points.


The answer is 120.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Patrick Corn
Oct 3, 2017

So I get ( 2 n n 2 ) \binom{2n}{n-2} for a general answer, but I get it in a weird way, by using Catalan numbers and then getting a bunch of cancellation. There must be some direct combinatorial argument, but I haven't thought too hard about it...

My argument starts by using the fact that the number of ways to draw chords with zero crossings is the n n th Catalan number. Then the idea is: pick a point A , A, and then go around clockwise and pick the other three points B , C , D B,C,D that the crossing lines are going to hit (the segments will be A C AC and B D BD ). So we've got 2 n 2n choices for the point (say A A ), then we pick a number 2 a 2a of points in between A A and B B where we have C a C_a ways to draw non-intersecting chords, then we've got the next point B , B, then 2 b 2b more points, then C , C, then 2 c 2c more points, then D , D, then 2 d 2d more points. So the total number of ways is 2 n 4 a + b + c + d = n 2 C a C b C c C d , \frac{2n}4 \sum_{a+b+c+d=n-2} C_aC_bC_cC_d, where we've divided by 4 4 because we could have started at B , C , B,C, or D D and gotten the same configuration.

Now the recursive formula C m + 1 = C 0 C m + C 1 C m 1 + + C m C 0 C_{m+1} = C_0C_m + C_1C_{m-1} + \cdots + C_mC_0 for the Catalan numbers allows us to chop up the sum: if a + b = k , a+b=k, 2 n 4 a + b + c + d = n 2 C a C b C c C d = n 2 k = 0 n 2 ( a = 0 k C a C k a ) ( c = 0 n k 2 C c C n k 2 c ) = n 2 k = 0 n 2 C k + 1 C n k 1 = n 2 j = 1 n 1 C j C n j = n 2 ( C 0 C n + C n C 0 + j = 0 n C j C n j ) = n 2 ( C n + 1 2 C n ) . \begin{aligned} \frac{2n}4 \sum_{a+b+c+d=n-2} C_aC_bC_cC_d &= \frac{n}2 \sum_{k=0}^{n-2} \left( \sum_{a=0}^k C_a C_{k-a} \right) \left( \sum_{c=0}^{n-k-2} C_c C_{n-k-2-c} \right) \\ &= \frac{n}2 \sum_{k=0}^{n-2} C_{k+1} C_{n-k-1} \\ &= \frac{n}2 \sum_{j=1}^{n-1} C_jC_{n-j} \\ &= \frac{n}2 \left( -C_0C_n + -C_nC_0 + \sum_{j=0}^n C_j C_{n-j} \right) \\ &= \frac{n}2 (C_{n+1}-2C_n). \end{aligned}

The explicit formula C n = 1 n + 1 ( 2 n n ) C_n = \frac1{n+1} \binom{2n}{n} plus some algebra lets us simplify that expression to ( 2 n n 2 ) . \binom{2n}{n-2}. For n = 5 , n=5, this is ( 10 3 ) = 120 . \binom{10}3 = \fbox{120}.

Great solution! Better than my guessing the generalisation through pattern-spotting...

Miles Koumouris - 3 years, 8 months ago

Log in to reply

I found this paper that gives a general formula for f ( n , m ) f(n,m) where m m is a certain number associated with the configuration of chords, and f f counts the total number of such configurations. When m = n m=n there are no intersections and when m = n 1 m=n-1 there is exactly one intersection. (But in general I don't believe that m m is equal to n n minus the number of intersections.)

Anyway, I can recover ( 2 n n 2 ) \binom{2n}{n-2} by plugging in m = n 1 m=n-1 to the formula in that paper. But I still don't see an easy combinatorial argument anywhere.

Patrick Corn - 3 years, 8 months ago

Log in to reply

Thank you - I'll have a look at it.

Miles Koumouris - 3 years, 8 months ago

Regarding the paper; if we let i i be the number of pairs of chords that intersect, I think that when m n m\leq n , m m does indeed equal n i n-i . This is pretty easy to see, since the number of trees decreases by one each time you add an edge, regardless of whether the edge is added to form or lengthen a cycle, or whether it is used to join two vertices (priorly trees) to form one tree, etc. I believe the problem arises when i > n i>n , since 0 i n ( n 1 ) 2 0\leq i\leq \dfrac{n(n-1)}{2} may exceed n n . Clearly m = 0 m=0 when n i n ( n 1 ) 2 n\leq i\leq \dfrac{n(n-1)}{2} , but the domain in his formula doesn't allow this. I wonder if there would there exist a way to determine values outside the 'allowed' domain?

Miles Koumouris - 3 years, 8 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...