This problem is from Stanley’s “Enumerative Combinatorics Vol. I”, more precisely problem 12 from Chapter 1 (sadly, no solution is provided there.)

Consider points arranged in the unit circumference and draw all chords connecting two of the points. Assume that the points are laid out in such a way no three chords intersect in a single point (that is, there are no triple intersections). Into how many regions will the interior of the circle by divided? Stanley says: “Try to give an elegant proof avoiding induction, finite differences, generating functions, summations, and the like.” One can do such a thing.

There’s another problem that involves placing points in the circle. Place points in the circle, and label of them with a , and the remaining with a . Prove we can trace the circle, starting from on of this points, in such a way that the partial sums of the values of the points is always positive, and this can be done both clockwise and anticlockwise. Can you generalize this to a continuous (as opposed to discrete) setting?

### Like this:

Like Loading...

First problem: forgetting about the exterior faces we obtain a planar graph with say vertices, faces, and edges. We’re trying to find . The construction ensures there are vertices of degree four, and vertices of degree . Thus , or what is the same, . I claim there are vertices of degree four. Indeed, any such vertex determines four distinct points in the circle, corresponding to a unique -subset of , and viceversa. Note that when , there are no such intersections, and the binomial is indeed zero. Euler’s formula now gives

which is the same as .

LikeLike

Second problem: Pick an arbitrary point and consider the function that moves clockwise steps, performing the sum of the values of the points traced. Thus . This functions then achieves a minimum at some , and the shifted function is our solution. The continuous analogue is the following: pick a function that integrates to . There is then a point such that remains nonzero.

LikeLike