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
    The tags are visible wherever the question appears -- there's no need to repeat "combinatorics" in the title.2012-08-06
  • 1
    Do you need to consider $k\gt 2$?2012-08-06
  • 0
    It seems we can make headway by partitioning the vertices into connected subgraphs, per condition (3), where the degree must be constant in that subgraph. Perhaps this is the point the poster had in mind with tagging "recurrence relations". However condition (4) severely limits the ways in which subgraphs that contain any edges may be selected (no intersecting edges).2012-08-06
  • 0
    Since you arranged the vertices on an $n$-gon, did you intend to consider only those edges that were inside the polygon or on its boundary? For example, with $n=4\text{ and }k=3$ would you consider the complete graph on 4 vertices as "good"?2012-08-06
  • 0
    Well, K4 is not good, because when its vertices are arranged as a regular 4-gon, its edges cross.2012-08-06
  • 0
    So due to the first answer, the question reduces to finding f(n, 1) and f(n, 2).2012-08-06
  • 1
    For k=1 these are one less (because empty set of edges is excluded) than the [Motzkin numbers](http://oeis.org/A001006).2012-08-07
  • 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
    Do you think this question can be reformulated as: Given a regular $n$-gon, how many ways can the $n$ vertices be partitioned using non-intersecting chords on the circumscribing circle, and every partition must contain at least one vertex. (With each partition, draw (a) the $k$-gon if there are $k \ge 3$ vertices, (b) the (only possible) edge if $k = 2$, or (c) do nothing if $k = 1$.)2012-08-07
  • 0
    @ladaghini: Yes, it does seem to be an equivalent formulation. We can probably require the chords' endpoints to be midpoints of the arcs between polygon vertices.2012-08-07
  • 0
    Does it make it any easier to solve?2012-08-07