# How many ways to paint $n$ squares

If I have $n$ squares and want to paint them in $k$ colors and it is not necessary to use all colors. In how many ways I can paint $n$ squares using $k$ colors ? Ways are considered to be different when the number of squares of at least one color differs.

I understand that amount of all possible ways to do it is $k^n$ and we just need to delete simillar ways, so I tried combination with repetition formula but it is not the right answer. What is the right answer to this problem ?

• If there are $n=2$ squares, does painting the first red and the second blue count as the same way as painting the first blue and the second red? Apr 11, 2017 at 11:01
• Let $m_i$ be the number of cubes painted color $i$. Then, you're looking for $m_1+\cdots+m_k=n$, with all nonnegative. This is a stars and bars problem. Apr 11, 2017 at 11:01
• @Henry my mistake, I will edit quesion, Yes, those ways are simillar Apr 11, 2017 at 11:03
• @MichaelBurr yes, thank you, it is what I needed Apr 11, 2017 at 11:12

If we decide to use one of the $k$ colors each time, then we can have $k$ different color combinations among the $n$ squares
If we decide to use two of the $k$ colors each time, then we can have $\displaystyle\binom{k}{2}(n-1)$ different color combinations among the $n$ squares
If we decide to use three of the $k$ colors each time, then we can choose to use the 3rd color once and solve the problem of coloring $n-1$ squares with 2 (among the $k$) colors which would be $\displaystyle \binom{k}{2}(n-2)$ different color combinations of our $n-1$ squares Then we can choose to use the 3rd color twice and solve the problem of coloring $n-2$ squares with 2 (among the $k$) colors which would be $\displaystyle\binom{k}{2}(n-3)$ different color combinations of our $n-1$ squares
Keep going with the 3rd color until you decide to color $n-2$ squares with it
$$\sum_{i=1}^{n-k}\Big(k+\binom{k}{2}(n-i-1)\Big)$$