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:
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: