0
$\begingroup$

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 ?

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – Henry
    Apr 11, 2017 at 11:01
  • 4
    $\begingroup$ 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. $\endgroup$ Apr 11, 2017 at 11:01
  • $\begingroup$ @Henry my mistake, I will edit quesion, Yes, those ways are simillar $\endgroup$
    – MRMKR
    Apr 11, 2017 at 11:03
  • $\begingroup$ @MichaelBurr yes, thank you, it is what I needed $\endgroup$
    – MRMKR
    Apr 11, 2017 at 11:12

1 Answer 1

0
$\begingroup$

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

If you can see the pattern here, the answer you are searching is

$$\sum_{i=1}^{n-k}\Big(k+\binom{k}{2}(n-i-1)\Big)$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .