Counting number of unique combinations

combinatoricsprogramming

I came across a programming challenge recently and I'm wondering if there's a closed-form solution to this.

There is a strip with squares of unit length each. The strip's total length is N (i.e. there are N squares). You have M painters of length K units each. You can paint over the squares with these painters however many times you want. How many unique combinations can you make?

Ex. N = 3, M = 2, K = 2 gives 6 unique combinations
(000 , 111, 011, 100, 001, 110)

I currently have a brute-force algorithm to solve this, but I'm sure there has to be a more elegant solution.

I am not a student and this is not a homework question. I just do these for fun.

Best Answer

The possible combinations are precisely the ones containing $K$ consecutive squares of the same color.

These are the only ones possible, because the last time you paint, you create such a strip. To see that all of them are possible, we can use the following algorithm.

Suppose that we have a sequence of colors $a_1, a_2, \dots, a_N$ with $a_{i+1} = a_{i+2} = \dots = a_{i+K}$ for some $i$. Then:

  1. First, make sure that colors $a_1, a_2, \dots, a_i$ are correct, in that order. To do this, color the interval $[1,K]$ with color $a_1$, then the interval $[2,K+1]$ with color $a_2$, and so on, until you color the interval $[i,i+K-1]$ with color $a_i$.
  2. Second, make sure that colors $a_N, a_{N-1}, \dots, a_{i+K+1}$ are correct, in that order. To do this, color the interval $[N-K+1,N]$ with color $a_N$, then the interval $[N-K,N-1]$ with color $a_{N-1}$, and so on, until you color the interval $[i+1,i+K+1]$ with color $a_{i+K+1}$.
  3. Finally, color the interval $[i+1,I+K]$ with the color that all $K$ of these squares are supposed to have.

This gives us a characterization of the possible combinations; counting them is a bit harder.

There is a recursive formula for impossible combinations. Fix $M,K$ and let $c_N$ be the number of impossible combinations of length $N$. (So, the number we actually want - the number of possible combinations - is $M^N - c_N$.) For $N=1,2,\dots,K-1$, we have $c_N = M^N$. For $N \ge K$, we have $$ c_N = (M-1) \left(c_{N-1} + c_{N-2} + \dots + c_{N-K+1}\right) $$ by breaking it up into cases: some number between $1$ and $K-1$ of the rightmost squares have the same color (but no more than that many), and they have one of the $M-1$ possible colors that are not equal to the color that comes before them.

This generally doesn't have a nice closed form. Some special cases do:

  • When $K=2$, we have $c_1 = M$ and $c_N = (M-1) c_{N-1}$ when $N \ge 2$, so $c_N = M(M-1)^{N-1}$.
  • When $M=2$ and $K=3$, we have $c_1 = 2$, $c_2 = 4$ and $c_N = c_{N-1} + c_{N-2}$ when $N \ge 3$, which is the Fibonacci number recurrence. Here, $c_N = 2F_{N+1}$, where we take the Fibonacci numbers to begin $F_1 = 1, F_2 =1, F_3 = 2, \dots$.
Related Question