Joining points 2

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 line segments. How many ways can these line segments be drawn such that at least two pairs of the line segments intersect?


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


The answer is 783.

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
Jan 4, 2018

The number of configurations with zero intersection is the Catalan number C n . C_n. The number of configurations with one intersection is ( 2 n n 2 ) , \binom{2n}{n-2}, as in your previous problem . The total number of configurations is ( 2 n 2 ) ( 2 n 2 2 ) ( 2 2 ) n ! = ( 2 n ) ! 2 n n ! , \frac{\binom{2n}2 \binom{2n-2}2 \cdots \binom{2}{2}}{n!} = \frac{(2n)!}{2^n n!}, because the numerator of the left side is the number of ways to sequentially pick pairs of points to connect, and the denominator is the number of ways to pick a given set of pairs. So the answer to the question is ( 2 n ) ! 2 n n ! C n ( 2 n n 2 ) , \frac{(2n)!}{2^n n!} - C_n - \binom{2n}{n-2}, which for n = 5 n=5 gives 945 42 120 = 783 . 945-42-120 = \fbox{783}.

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...