Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am studying a problem that I have worked out is equivalent to the following:

Problem Description

Given N distinct points on the border of a circle, there are $B_N$ ways to partition them - where $B_i$ is the $i$th bell number.

http://en.wikipedia.org/wiki/Bell_number

For a given partitioning connect all members of the same partition with a solid polygon using the points as verticies (for partitions of size 1, a "1-polygon" is a point. For partitions of size 2, a "2-polygon" is a line segment).

We say a partitioning is exclusive if no pair of polygons intersect. For N points how many exclusive partitionings are there? Let this be $T_N$

Inductive Definition of $T_N$

(Aside: If we limit the partition size to a maximum of 2, I worked out yesterday that the answer is the Motzkins numbers: Efficiently evaluating the Motzkin numbers)

$T_N$ Base Case

It can be easily seen that $T_0 = T_1 = 1$

$T_N$ Recurrence

For the recurrence I broke it down as follows:

Assign one of the N points the origin. There are three cases:

Case 1

The origin is part of a partition of size 1. In that case the remaining $N-1$ points have $T_{N-1}$ exclusive partitionings.

Case 2

The origin is part of a partition of size 2. Let the point it is connected to be clockwise $k$ points away from it. The line segment cuts the remaining $N-2$ points into two smaller independent exclusive partitionings. One of size $k-1$, the other of size $N-2 - (k-1) = N-k-1$. So the total number of exclusive partitionings in case 2 is:

$$\sum_{k=1}^{N-1}{T_{k-1}T_{N-1-k}}$$

Case 3

The origin is part of a partition of size $>2$. Let the first point clockwise of the origin that it is in a partition with be $k$ points away from it. As for case 2 we can see that the $k-1$ points clockwise of the origin have $T_{k-1}$ exclusive partitionings. On the otherside we have $N-1-k$ points, and at least one of them is in the partition with the origin and point $k$. Let the number of valid configurations of these $N-1-k$ points be given by $S_{N-1-k}$.

Defining $S_X$

We can imagine $S_X$ as $X$ points on the border of a circle all on one side of a line segment. Denote the two endpoints of the line segment C (clockwise end) and A (anticlockwise end) We must form a polygon with the line segment and 1 or more of the $X$ points.

Let the first point clockwise of point C that the polygon is formed with be $j$ points away from C. We can see that the $j-1$ points clockwise of the line segment form $T_{j-1}$ exclusive partitionings. For the otherside, there are two subcases. The first is that we close the polygon CjA, in which case the remaining $X-j$ points have $T_{X-j}$ exclusive partitionings. The second is that we use 1 or more points of the remaining $X-j$ points to form a larger polygon. In this subcase there are $S_{X-j}$ configurations.

So for $S_X$ we have:

$$S_0 = 0$$ $$S_1 = 1$$

$$S_X = \sum_{j=1}^{X}T_{j-1}(T_{X-j}+S_{X-j})$$

and overall for case 3 we then have:

$$\sum_{k=1}^{N-1}T_{k-1}S_{N-k-1}$$

$T_N$ Conclusion

and so summing the three cases we have:

$$T_N = T_{N-1} + \sum_{k=1}^{N-1}{T_{k-1}T_{N-1-k}} + \sum_{k=1}^{N-1}T_{k-1}S_{N-k-1}$$

Question

Any clues how I can simplify the two recurrences into one and put them into a closed form for efficient calculation?

share|improve this question
    
I don't know. What I would is, I'd calculate the answers for $n=1,2,3,4,5$, say, and then see what the Online Encyclopedia of Integer Sequences knows. –  Gerry Myerson Aug 3 '12 at 0:28
    
Do you ever get the feeling that its all been done before. These are the Catalan numbers. en.wikipedia.org/wiki/Catalan_number, and the problem I describe is the Noncrossing Partition en.wikipedia.org/wiki/Noncrossing_partition –  Andrew Tomazos Aug 3 '12 at 3:55
    
You could write up an answer now, and then accept it after a couple of days. –  Gerry Myerson Aug 3 '12 at 4:07

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.