4
$\begingroup$

Consider the vertices of a regular n-gon, numbered 1 through n. (Only the vertices, not the sides). A "configuration" means some of these vertices are joined by edges.

A "good" configuration is one with the following properties:

1) There is at least one edge.

2) There can be multiple edges from a single vertex.

3) If A and B are joined by an edge, then the degree of A equals the degree of B.

4) No two edges must intersect each other, except possibly at the endpoints.

5) The degree of each vertex is at most k. (where $0\leq k \leq n$ )

Find f(n, k), the number of good configurations. For example, f(3, 2) = 4 and f(n, 0) = 0.

  • 1
    And for k=2, one less than the Catalan numbers?2012-08-07

2 Answers 2

2

From the various comments we have

  • $f(n,0) = 0$ since we can have no edges, but need at least one
  • $f(n,1)=M_n-1$ where $M_n$ are the Motzkin numbers, the number of different ways of drawing non-intersecting chords on a circle between $n$ points, and $-1$ because we need at least one edge
  • $f(n,2)=C_n-1$ where $C_n$ are the Catalan numbers, the number of noncrossing partitions on a circle between $n$ points, and $-1$ because we need at least one edge
  • $f(n,k)=f(n,2)$ for $k\gt 2$ as we cannot have degrees greater than $2$ on a convex polygon without intersections

There are many recurrence relations. Two pretty ones are $M_{n+1}=M_n+\sum_{i=0}^{n-1}M_i M_{n-i-1}$ and $C_{n+1}=\sum_{i=0}^{n}C_i\,C_{n-i}$ starting from $M_0=1$ and $C_0=1$.

The Catalan numbers can be written in closed form as $C_n = \frac{1}{n+1}{2n\choose n}$ but there is no similarly simple form for the Motzkin numbers.

2

We can show that vertex degrees $k \le 2$. Suppose for contradiction that $n$ is the size of a minimal counterexample, a convex $n$-gon with some degree $k \gt 2$. By minimality (discarding any vertices not connected to the given one) all vertices in the $n$-gon have degree $k$.

But it is known that the maximum number of nonintersecting diagonals of an $n$-gon is $n-3$. Add in the outer edges of the polygon itself and we'd have at most $2n-3$ nonintersecting edges.

But for $n$ vertices to each have degree $k$ requires $\frac{nk}{2}$ edges. Now an elementary inequality argument:

$ \frac{nk}{2} \le 2n-3 $

$ k \le 4 - \frac{6}{n} $

immediately gives us that $k \le 3$.

To rule out $k = 3$ makes essential use of the convexity of the polygon, in that a nonconvex quadrilateral allows nonintersecting edges with three meeting at each vertex. However in a convex polygon once the maximum number of nonintersecting diagonals are added, the result is a dissection of the polygon into triangles. At least two of these triangles consist of two "external" edges and one diagonal, so that the corresponding vertex opposite the diagonal edge has only degree $2$.


Added: Let's flesh out the reduction of $f(n,k)$ to fewer vertices by consideration of cases: vertex $1$ has (a) no edge, (b) one edge, or (c) two edges (if $k=2$ allows).

If vertex $1$ has no edge, we get a contribution of $f(n-1,k)$ from "good configurations" of the remaining $n-1$ vertices.

If vertex $1$ has just one edge, its other endpoint vertex $p$ must also have only that edge. This induces a contribution summing the "good configurations" of the two sets of vertices on either side of vertex $p$, including possibly empty ones there since we've already satisfied the requirement of at least one edge:

$ \sum_{p=2}^{n} (1 + f(p-2,k)) (1 + f(n-p,k)) $

If vertex $1$ has two edges (as noted, only possible if $k=2$), the contributions are similar but need more bookkeeping. Vertex $1$ belongs to a cycle of $r \gt 2$ edges, and the remaining $n-r$ vertices are partitioned thereby into varying consecutive subsets, each of which has its own "good configuration" (or an empty one).

  • 0
    Does it make it any easier to solve?2012-08-07