My Question: 6 different books are to be distributed among three peoples {R/S/G} . Then number of ways of distribution of books such that each person gets atleast one book.

My attempt:

$$\binom{6}{3} 3! 3^3 = 3240$$

because we can choose first three books with $\binom{6}{3}$ and give them to three people with $3!$. Then we can distribute remaining three books with $27$ different ways.

  • 1
    $\begingroup$ Please format your math expressions. $\endgroup$ – John Dec 20 '17 at 17:40
  • 3
    $\begingroup$ Apply inclusion-exclusion to the cases where one or more of the people didn't get any books to arrive at an answer of $3^6-2^6-2^6-2^6+1^6+1^6+1^6-0^6=540$, same as below. $\endgroup$ – JMoravitz Dec 20 '17 at 18:52

This question can be considered as the following:

Let $A$ and $B$ be sets such that $|A| = 6$ and $|B| = 3$. How many surjections $A \rightarrow B$ are there?

When number of surjections is asked, you should use "Stirling numbers of the second kind" in order to solve the problem. Then answer of this question is $$3!S(6,3) = 6*90 = 540$$

Here, the number $S(6,3)$ is the number of ways of distributing $6$ different books to $3$ identical people (I don't know how can something like this be possible but you can consider it this way). Since the people are different, you can change the order with $3!$ so the result follows.

Now the problem with your solution is assume you have books $1,2,3,4,5,6$. Then in the first choose, suppose you choose $1,2,3$ and give it them to $R,S,G$ respectively. Then you are distributing the remaining books, suppose $4,5,6$ to $R,S,G$, respectively, similar to the first distribution. But this is same as choosing the first three books as $4,5,6$ and distributing the remaining three as $1,2,3$, giving each people two books. So you are over-counting the possibilities. I also suggest you to learn the Stirling numbers of the second kind and its relation with number of surjections (It is about Inclusion-Exclusion Principle).


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.