2
$\begingroup$

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

  • 1
    A tedious application of the inclusion-exclusion formula for probabilities to count the set of surjective functions. Basically all functions less the union of those that exclude a particular color. Since they overlap, we need the sieve principle.2012-05-26

1 Answers 1

1

First, reduce the problem to painting with $k'$ colours by including a factor $\dbinom{k}{k'}$.

Now, as copper.hat mentioned in the comments, we need to know how many surjective functions $\{1 \ldots i\} \to \{1\ldots k'\}$ there are.

By definition, this problem is solved by the Stirling numbers of the second kind (Wikipedia); in this case $S(i, k')$, so that our solution becomes $\dbinom{k}{k'} S(i,k')$.