Sign up ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|cite|improve this question
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. – André Nicolas May 26 '12 at 6:55
$\binom{k}{k'} \sum_{j=0}^{k'} (-1)^j \binom{k'}{j} (k'-j)^i$. – copper.hat May 26 '12 at 7:11
I agree with @AndreNicolas. The challenge is to calculate the ways of painting given the $k'$ colors for the $i$ balls... – asksw0rder May 26 '12 at 7:11
Number of surjective functions from $\{1,...,i\}$ to $\{1,...,k'\}$. – copper.hat May 26 '12 at 7:12
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. – copper.hat May 26 '12 at 7:39

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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