Combinatorics, Recurrences, Catalan numbers
There are N points along a circle. We've to draw non-intersecting chords on these points. Special property to satisfy is that if there is a chord between points A and B, number of chords incident on A should be same as number of chords incident on B. Also number of chords incident on any point should be no more than K where K is an input parameter. Task is to find out how many ways of drawing chords are there when atleast one chord is drawn.
Answers are same for all K > 2 and K = 2. So now there are three cases :
Firstly, assume that there is no constraint on number of chords incident on a point, or in other words, K is very large (say N). If one tries to draw some cases by hand, it is easy to see that it is impossible to draw a system of non-intersecting chords where 3 or more chords are incident on the same point. If this is true, answers for all K > 2 should be same as answer for K = 2 as in no valid game, would be draw more than 2 chords incident on the same point.
Here is formal proof for the same.
Claim : In any valid system of non-intersecting chords, no point has more than 2 chords incident onto it.
Proof : Consider a game where this is not true. Now consider a graph where all points are vertices and there is an edge between two points if they've a chord between them. Make connected components of this graph. Let C be any arbitrary component. Number of bondings is same for every vertex in a connected component, by definition of game. So if we can prove that there is some vertex of degree 2 in any arbitrarily chosen component, we'd be through.
Say vertices of component are V1, V2 .. Vk in clockwise order along the circle. Add chords (V1, V2) , (V2, V3) .... etc if they don't already exist. They can't intersect with any of the existings chords of this component. Now we've a K sided convex polygon whose vertices are Vi for different i.
Find any diagonal. It separates the polygon into two parts. Take any of the parts. Say the current part is constrained by a diagonal between vertices X and Y and a path between these vertices by the border of the polygon which passes through every vertex between them (there are two possibilities, but we consider any one of them);
Our strategy is to start with some part like this, and then at each stage will we take a part which is inside the previous part.
So repeat the following for i from 0 to infinity:
1) Find any diagonal inside the current part. It separates this part into two smaller parts.
Now this algorithm would stop as every time we're decreasing the number of vertices in our chosen part and there is only finite number of them. When it stops, we've a convex polygon (with atleast 3 vertices) whose all vertices (except 2) are along the circle. Since there is no diagonal (that is why we stopped) in this polygon, vertices on the circle have a degree of atmost 2. Hence proved.
Now let's try to solve the three cases.
Case 1 : K = 0
This is the easiest case. As we can't draw any chord and any valid game must have atleast 1 chord, there are no valid games possible. So the answer for all N is 0.
Case 2 : K = 1
Denote by f(N) the number of different games possible for N points. Let's try to
find out a recurrence relation for this quantity. Label all the points and look
at point number 1. There are two cases:
Hence we get following recurrence:
Note that final answer is f(N) - 1 as empty game is not a valid game.
You can also find a direct linear recurrence for Motzkin number on its wikipedia
Case 3 : K = 2
As stated above K = 2 is as good as K = infinity. So all we need to find is the number of non-intersecting systems of chords with one extra contraint : if there is a chord between A and B, number of chords incident on A should be same as number of chords incident on B.
Let's try to derive a recurrence for it.
Firstly we'd try to get away with the constraint that if there is a chord between A and B, number of chords incident on A should be same as that of B.
Claim : The constraint that all vertices of same component have the same bonding
number and the fact that no vertex is allowed to have more than 2 bondings together
imply that given a connected component, there is only 1 way of creating bonds in
that component and that 1 way is a cycle.
Hence given a connected component, there is exactly 1 way of drawing chords respecting all the constraints of the problem.
Now we can safely forget the constraint that if A and B have bonding, their bonding
numbers should be same. Once we do that, we need to find number of ways of
choosing different connected components.
Let f(N) denote the number of valid games. Let g(N) denote the number of valid games where point 1 and point 2 are always bonded. Now let's look the first point. It may not be involved in any bonding in which case answer is f(N-1). Or it might be involved in some bondings. Look at the leftmost such point (along clockwise order). say it is ith point. Then
About computing g(N) : Now as all we care about is connected components (from the claim) and points 1 and 2 are already connected, we could merge them! So
So we get
As f(0) = 1,
This is exactly same as the famous recurrence for Catalan numbers. In fact thanks to Gennady for pointing out, but the image on Wikipedia page of Catalan numbers itself is of this problem : non-intersecting partitions of N-element set.
So the final answer in this case is Catlana(N) - 1 (Again subtract 1 because empty game is not a valid game). All catalan numbers can also be precomputed in O(N) time by using the following more readily computable form of the recurrence:
One final note regarding the implementation. All answers had to be computed modulo (10^14 + 7) and as many contestants noted as well - this MOD is not a prime. That makes things difficult as divison modulo MOD may not be defined in certain cases. There are two work arounds:
Can be found here.
Can be found here.
This question is marked "community wiki".
asked 12 Aug '12, 00:11
"Beware, as here divison is also involved, for each quantity one would need to maintain the highest powers of each of these primes which divides them as well." Can someone explain how this could help?
answered 14 Aug '12, 16:40