1
$\begingroup$

How many ways are there to distribute 12 books to 4 people under the conditions that all the books are distributed and that one person is allowed to take zero books?

I thought that from all the possible distributions (4^{12}) I should subtract those which do not satisfy both the conditions. That is, I must subtract the number of ways in which at least $2$ people get no books. I can choose the $2$ people that get $0$ books with ${4 \choose 2}$ ways, and then all the possible distributions turn out to be $${4 \choose 2}\cdot (2^{12}-12+1).$$ So, the answer would be $$4^{12}-{4 \choose 2}\cdot 2^{12}+{4 \choose 2} \cdot 12-{4 \choose 2}.$$

Is that correct?

$\endgroup$
8
  • 2
    $\begingroup$ Exactly one person is allowed to take zero books? $\endgroup$
    – eMathHelp
    Commented Sep 12, 2022 at 20:37
  • $\begingroup$ Yes, which means that at most one person gets zero books. The case that each person gets a book is allowed. $\endgroup$
    – User
    Commented Sep 12, 2022 at 21:16
  • $\begingroup$ Are the books distinguishable? I gave my answer below but I treated books as indistinguishable like red balls, for example. Are you considering that book one is different than book two? $\endgroup$
    – John Douma
    Commented Sep 12, 2022 at 22:26
  • $\begingroup$ I think $${4 \choose 2}\cdot (2^{12}-12+1)$$ should be replaced by $$2^{12} \cdot{4 \choose 2}-8$$ $\endgroup$
    – WW1
    Commented Sep 12, 2022 at 23:22
  • $\begingroup$ Yes, the books are distinguishable. And so are the people of course. $\endgroup$
    – User
    Commented Sep 13, 2022 at 6:29

3 Answers 3

1
$\begingroup$

A solution in terms of Stirling numbers of the second time is concise. Another method is to use the generalized principle of inclusion and exclusion.

What we want is the number of functions from $[1..12]$ to $[1..4]$ which omit at most one number in the range $[1..4]$. In general, the number of surjections from $[1..n]$ to $[1..k]$ is $k! S(n,k)$ where $S(n,k)$ is a Stirling number of the second kind. So the number of surjections from $[1..12]$ to $[1..4]$ is $4! S(12,4)$. For the number of functions which omit exactly one number in the range, there are $4$ choices of the omitted number and $3! S(12,3)$ surjections from $[1..12]$ to the remaining set of three numbers. So all together there are $$4! S(12,4) + 4! S(12,3) = 24 \times 611501 + 6 \times 86526 = 16752648$$ acceptable functions. This method assumes, of course, that you have some way of finding the values of the Stirling numbers, whether by tables, software, or computation. One suitable set of tables is the Handbook of Mathematical Functions (AMS55) by Abramowitz and Stegun, available on-line: Handbook of Mathematical Functions.

For the inclusion / exclusion approach, let's say a function $f:[1..12] \to [1..4]$ has "property $i$" if $i$ is not a value of $f(x)$ for $1 \le i \le 4$, and define $S_j$ as the number of functions which have $j$ of the properties, for $1 \le j \le 3$. Then $$S_j = \binom{4}{j} (4-j)^{12}$$ The extended principle of inclusion / exclusion says, in general, that the number of functions with at least $j$ of the properties is $$a_j = S_j - \binom{j}{1} S_{j+1} + \binom{j+1}{2} S_{j+2} - \dots + \binom{m}{m-1}S_m$$ We would like to compute the number of functions that have at least $2$ of the properties, since these are the functions which are unacceptable. $$a_2 = S_2 - \binom{2}{1} S_3 = 24568$$ We subtract these from the total number of functions to find the number which are acceptable: $$4^12-a_2 = 16752648$$ which agrees with the number computed via Stirling numbers.

Two references for the generalized inclusion / exclusion principle as used above:

(1) Schaums's Theory and Problems of Combinatorics by V.K. Balakrishnan, p.68.

(2) An Introduction to Probability Theory and Its Applications by William Feller, Volume I, Third Edition, p. 109.

$\endgroup$
0
$\begingroup$

I think that there is no simple formula, but there is some recurrence.

Let $F(n,m)$ is the number of ways to distribute $n$ distinguishable books to $m$ distinguishable people, such that each person gets at least one book.

Note, that $F(n, 1)=1$ and $F(n, n)=n!$.

Thus, $F(n,m)=\sum_{k=1}^{n-m+1}C(n,k)F(n-k, m-1)$.

We need to find $F(12,4)$.

Also, since we allow exactly one person to get zero books, fix any person and distribute 12 books to 3 other people.

The final answer is $F(12,4)+4F(12,3)$.

By writing a simple program I got the answer $16752648$.

Also, checked a simpler case of distributing 4 books to 2 people: $F(4,2)+2F(4,1)=16$:

$$\{1\},\{2,3,4\}$$ $$\{2\},\{1,3,4\}$$ $$\{3\},\{1,2,4\}$$ $$\{4\},\{1,2,3\}$$ $$\{1,2\},\{3,4\}$$ $$\{1,3\},\{2,4\}$$ $$\{1,4\},\{2,3\}$$ $$\{2,3\},\{1,4\}$$ $$\{2,4\},\{1,3\}$$ $$\{3,4\},\{1,2\}$$ $$\{1,2,3\},\{4\}$$ $$\{1,2,4\},\{3\}$$ $$\{1,3,4\},\{2\}$$ $$\{2,3,4\},\{1\}$$ $$\{\},\{1,2,3,4\}$$ $$\{1,2,3,4\},\{\}$$

$\endgroup$
0
$\begingroup$

This amounts to finding
$[All\; Ways]\, -\,[Ways\; with\; at\; least\; 2\;people\; deprived]$

$= 4^{12} \,-\binom42\cdot 2^{12} \,+\binom21\binom43 \cdot 1^{12} \,= 16752648$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .