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

  • 2
    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.2012-05-26
  • 0
    $\binom{k}{k'} \sum_{j=0}^{k'} (-1)^j \binom{k'}{j} (k'-j)^i$.2012-05-26
  • 0
    I agree with @AndreNicolas. The challenge is to calculate the ways of painting given the $k'$ colors for the $i$ balls...2012-05-26
  • 2
    Number of surjective functions from $\{1,...,i\}$ to $\{1,...,k'\}$.2012-05-26
  • 0
    @copper.hat does the $(-1)^j$ mean to eliminate the duplications? My understanding on your solution is that if considering all cases using $(k'-j)$ colors, all cases using $(k'-j-1)$ will also be counted, right?2012-05-26
  • 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