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.
  • $\begingroup$ Shouldn't it be $2\binom{n+2k}{2k}$? I think this follows from the stars and bars method. $\endgroup$ Jun 2, 2019 at 19:31
  • $\begingroup$ @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. $\endgroup$
    – Mastrem
    Jun 2, 2019 at 19:38
  • $\begingroup$ 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. $\endgroup$ Jun 2, 2019 at 20:06

1 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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .