2
$\begingroup$

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.