In how many ways one can color n lined up bins in m colors with a constraint that colored bins are not allowed to be neighbors? Any number of bins can be left uncolored. any number of colors <= m can be used.

possibly a hint: I was going first to find all the combinations with one color and than allow each colored bin to have any color out of m for each combination.


closed as off-topic by 3SAT, John B, Rory Daulton, hardmath, user26857 Feb 20 '16 at 21:25

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – 3SAT, John B, Rory Daulton, hardmath, user26857
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Are you required to use all $m$ colors? $\endgroup$ – Brian M. Scott Feb 20 '16 at 20:26
  • 1
    $\begingroup$ Welcome to MathSE! You are more likely to get a good answer to your question if you follow a few guidelines. In particular, what have you tried so far, and just where are you stuck? This is not a homework-answering site: we want to see that you have put significant work into the problem. $\endgroup$ – Rory Daulton Feb 20 '16 at 20:45
  • $\begingroup$ no, you can use any number of colors <= m $\endgroup$ – D.Luchinsky Feb 22 '16 at 1:02

There might be a much easier way, but I see it this way:

Let $f(n, m)$ be the number of ways to color $n$ bins with $m$ colors and satisfy your condition.

$$f(n, m) = \overbrace{m \cdot f(n - 2, m)}^{\text{color the $n^{\text{th}}$ one, and skip one}} + \overbrace{f(n - 1, m)}^{\text{don't color the $n^{\text{th}}$ one}}$$

This order $2$ recurrence relation will require us to define $2$ base cases: $$f(1, m) = m + 1$$ $$f(2, m) = 2m + 1$$

Now since your $m$ is fixed, you can solve the following linear recurrence relation: $$f_n = m\cdot f_{n-2} + f_{n-1}$$


Hint: You may consider that maximal number of bins to be colored is (n-1)/2 because if the number exceeds this two colored adjacent bins can occur

Hint2: For any subcase consider that the "moving" colored bin can have space relatively of how much do unclored=N/colored=C bins exist.

  • Example with colored C=(n-1)/2 there is no space for colored bins to move:

$NCNCNC...N$ so available moves for colored bins $C$ over non-colored $N$ are $0$ anywhere. $0000...$($(n-1)/2$ times)


  • Example with colored $C=(n-2)/2$ there is one bin space for each colored bin to move:

NCNNCNC...N ,or, NNCNCNNC...N the solution can be interpreted numerically as $010000...$ or $1000000...$ where $1$ means the bin is moved to right

NCNNCNC...N ,or, NCNCNNC...N this solution can be interpreted numerically as $010000...$ or $0010000...$

So on, ...we have one allowable move to either left or right for egding bins and 2 moves for the rest, in addition to the actual position, the formula for this case is written as $S_1=(1+1+2((n-2)/2-2)+1)*m^{(n-2)/2}$

...following this logic one can move on to $S_2$: $2000...$,$1100...$,$0200...$,$01010...$, ...etc

Hint3: From the numerical translation of the problem, we can extrapolate a general rule of $S_k$

$Sequence_k=x_1x_2....x_{(n-k-1)/2}$ where sum of $x$'s is $k$ and $x$ is between $0$ and $k$ inclusive.

The solution is the sum of all $S$'s


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