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

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.
• Shouldn't it be $2\binom{n+2k}{2k}$? I think this follows from the stars and bars method. Jun 2, 2019 at 19:31
• @SmileyCraft Well, for $n=4$ and $k=2$ there appear only to be $2$ options. Essentially, my thinking is that there are $2k$ verticies you label as 'switches', where, if you walk around the graph in a counter-clockwise direction while 'painting' each vertex, you switch colors at these vertices. Jun 2, 2019 at 19:38
• You are correct. I forgot to add the restriction that there needs to be a star to the left of each bar. Your method is more elegant anyways. Jun 2, 2019 at 20:06

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.