1
$\begingroup$

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?

  • 0
    You could write up an answer now, and then accept it after a couple of days.2012-08-03

0 Answers 0