Color $m$ vertices of a cyclic graph red such that there are exactly $k$ red segments.

Question

Let $n,m,k$ be positive integers with $$n\ge m\ge k\ge2,\quad n\ge 2k$$ and consider the cyclic graph with $n$ vertices. How many different ways are there to color each vertex either blue or red such that

• A total of $m$ vertices is colored red
• There are $k$ red segments in total

If one coloring can be turned into another by rotating the graph, these two are considered different colorings (except of course when a rotation by $0^\circ$ suffices).

---

Of course counting graphs where just one of these conditions hold isn't hard.

• There are ${n\choose m}$ different ways of coloring the graph such that exactly $m$ vertices are colorered red.
• There are $2{n\choose 2k}$ ways of coloring the graph such that there are exactly $k$ red segments.

Answer 1

Let us consider one extra restriction: vertex $1$ must be blue.

Then we have to distribute $m$ red vertices into $k$ non-empty distinguishable segments. By the stars and bars method we get $k-1$ bars and $m$ stars, but every bar needs a star to its left, and we need to end with a star. This gives $\binom{m-1}{k-1}$ options.

We then need to put the $k$ segments between the $n-m-1$ remaining blue vertices, and between any two segments there needs to be at least one blue vertex. By similar reasoning to the above we get $\binom{n-m}{k}$ options.

In total there are $\binom{m-1}{k-1}\binom{n-m}{k}$ options. By symmetry, the same holds if we pick any other vertex than $1$ to be blue. We can consider every vertex as possibly being blue, and then we have considered every valid colouring exactly $n-m$ times. This means there are $\frac{n}{n-m}\binom{m-1}{k-1}\binom{n-m}{k}$ valid colourings in total.