Ten points P 1 , P 2 , … , P 1 0 are equally spaced around a circle. They are connected in separate pairs by 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 equally spaced points.
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.
Great solution! Better than my guessing the generalisation through pattern-spotting...
Log in to reply
I found this paper that gives a general formula for f ( n , m ) where m is a certain number associated with the configuration of chords, and f counts the total number of such configurations. When m = n there are no intersections and when m = n − 1 there is exactly one intersection. (But in general I don't believe that m is equal to n minus the number of intersections.)
Anyway, I can recover ( n − 2 2 n ) by plugging in m = n − 1 to the formula in that paper. But I still don't see an easy combinatorial argument anywhere.
Log in to reply
Thank you - I'll have a look at it.
Regarding the paper; if we let i be the number of pairs of chords that intersect, I think that when m ≤ n , m does indeed equal 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 , since 0 ≤ i ≤ 2 n ( n − 1 ) may exceed n . Clearly m = 0 when n ≤ i ≤ 2 n ( n − 1 ) , 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?
Problem Loading...
Note Loading...
Set Loading...
So I get ( n − 2 2 n ) 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 th Catalan number. Then the idea is: pick a point A , and then go around clockwise and pick the other three points B , C , D that the crossing lines are going to hit (the segments will be A C and B D ). So we've got 2 n choices for the point (say A ), then we pick a number 2 a of points in between A and B where we have C a ways to draw non-intersecting chords, then we've got the next point B , then 2 b more points, then C , then 2 c more points, then D , then 2 d more points. So the total number of ways is 4 2 n a + b + c + d = n − 2 ∑ C a C b C c C d , where we've divided by 4 because we could have started at B , C , or 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 for the Catalan numbers allows us to chop up the sum: if a + b = k , 4 2 n a + b + c + d = n − 2 ∑ C a C b C c C d = 2 n k = 0 ∑ n − 2 ( a = 0 ∑ k C a C k − a ) ( c = 0 ∑ n − k − 2 C c C n − k − 2 − c ) = 2 n k = 0 ∑ n − 2 C k + 1 C n − k − 1 = 2 n j = 1 ∑ n − 1 C j C n − j = 2 n ( − C 0 C n + − C n C 0 + j = 0 ∑ n C j C n − j ) = 2 n ( C n + 1 − 2 C n ) .
The explicit formula C n = n + 1 1 ( n 2 n ) plus some algebra lets us simplify that expression to ( n − 2 2 n ) . For n = 5 , this is ( 3 1 0 ) = 1 2 0 .