Another ball-painting problem: assume that we have $i$ balls (with numbered labels, so order is sensitive), and $k$ different colors. Now we need to paint these balls using these colors so that exactly $k'$ colors ($k' < k$) should be used. The question is how many different ways there are to paint these balls?
I somehow think about a solution as
$P^{k}_{k'}*C^{k'}_{i-k'}*(P^{k'}_{i-k'} + P^{k'}_{i-k'-1} + ... + P^{k'}_{1})$
The basic idea is that we first choose $k'$ colors, and paint $k'$ balls. For the $(i-k')$ balls left, we choose some colors from the used $k'$ colors, and paint them, and put them back to the $k'$ balls already painted.
However I don't think my solution is correct since there may be the case that when putting back the repeated color balls, some cases may be duplicated. So the correct should be less than the one I give.
Any ideas? Let me know if the problem is not clear to you...