2
$\begingroup$

Let $m$ be a positive integer. The numbers $1,2, \cdots , m$ are evenly spaced around a circle. A red marble is placed next to each number. The marbles are indistinguishable. Adrian wants to choose $k$ marbles ($k \le \frac m2$), colour them blue, and place them back in their original positions in such a way that there are no neighbouring blue marbles in the resulting configuration. In how many ways can he do this ?

My solution is $\frac{m}{m-k} \binom{m-k}{k}$. Is it true ?

$\endgroup$
1
$\begingroup$

The resulting configuration is a binary word of length $m$, containing $k$ ones (for blue) and $m-k$ zeros (for red). No two ones may be next to each other, and it is also forbidden that the first and the last letter both are ones.

In order to create all such words we first write the $m-k$ zeros, leaving $m-k+1$ slots between them and at the ends. We then can choose $k$ of these slots to write a one therein. From the ${m-k+1\choose k}$ words so generated we have to remove the ${m-k-1\choose k-2}$ words having a one at both ends, so that the total number $N$ of admissible words comes to $$N={m-k+1\choose k}-{m-k-1\choose k-2}={m\over m-k}{m-k\choose k}\ .$$

$\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.