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

  • 2
    $\begingroup$ The answer is $\binom{k}{k'}$ times the number of ways to paint using all of a fixed set of $k'$ colours, so that each colour is used. But finding this is not fully pleasant. $\endgroup$ – André Nicolas May 26 '12 at 6:55
  • $\begingroup$ $\binom{k}{k'} \sum_{j=0}^{k'} (-1)^j \binom{k'}{j} (k'-j)^i$. $\endgroup$ – copper.hat May 26 '12 at 7:11
  • $\begingroup$ I agree with @AndreNicolas. The challenge is to calculate the ways of painting given the $k'$ colors for the $i$ balls... $\endgroup$ – asksw0rder May 26 '12 at 7:11
  • 2
    $\begingroup$ Number of surjective functions from $\{1,...,i\}$ to $\{1,...,k'\}$. $\endgroup$ – copper.hat May 26 '12 at 7:12
  • 1
    $\begingroup$ 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. $\endgroup$ – copper.hat May 26 '12 at 7:39

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')$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.