100 books in 10 identical bags

Question

Show that the number of ways of distributing 100 identical books into 10 indistinguishable bags so that no two bags contain the same of number of books and no bag is empty, is the same as the number of ways of distributing 55 identical objects into 10 bags so that no bag is empty.

I think I have solved the second part of the question correctly as:

$x_1+ x_2+.....+x_{10}= 45$ (Technique: Stars and Bars)

This has$\dbinom {55}{45}$ solutions.

Now how do I solve the first part?

Progress till now:

We need solutions of

$x_1+x_2....+x_{10} = 90$

This has $\dbinom{99}{90}$ solutions. Now from this how do I eliminate the solutions when any two bags contain same number of books? It seems to be really tough. Also, the bags are identical which adds to the trouble.

Answer 1

You are looking for the number of distinct partitions of $100$ items into $10$ non-equal parts.

As partitions are unordered (because the bags are indistinguishable), we can choose to have them in ascending order. Then since we are aware that each bag's book count is strict bigger than the previous bag, we can subtract off $0,1,2,\ldots$ books from the successive bags to leave a partition which is still ordered, still nonzero books in each bag, but now the adjacent bags may have identical book counts. Here we have removed a total of $45$ books for a $10$-way partition over $55$ remaining books without the requirement for all-different book counts.

---

Using the recursive definition of $p_k(n)$, the number of distinct partitions of $n$ items into exactly $k$ non-zero parts, that

$p_k(n) = p_k(n-k) + p_{k-1}(n-1)$

with $p_k(n) = 0$ when $n<k$ and $p_1(n) =1$, we can get the exact value of $p_{10}(55)$ in a spreadsheet calculation, which happily agrees with Jack D'Aurizio's result:

$$\small\begin{array}{|c|c|} \hline n \downarrow \quad k \to & \;\;1\;\; & \;\;2\;\; & \;\;3\;\; & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline 2 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline 3 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline 4 & 1 & 2 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline 5 & 1 & 2 & 2 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ \hline 6 & 1 & 3 & 3 & 2 & 1 & 1 & 0 & 0 & 0 & 0 \\ \hline 7 & 1 & 3 & 4 & 3 & 2 & 1 & 1 & 0 & 0 & 0 \\ \hline 8 & 1 & 4 & 5 & 5 & 3 & 2 & 1 & 1 & 0 & 0 \\ \hline 9 & 1 & 4 & 7 & 6 & 5 & 3 & 2 & 1 & 1 & 0 \\ \hline 10 & 1 & 5 & 8 & 9 & 7 & 5 & 3 & 2 & 1 & 1 \\ \hline 11 & 1 & 5 & 10 & 11 & 10 & 7 & 5 & 3 & 2 & 1 \\ \hline 12 & 1 & 6 & 12 & 15 & 13 & 11 & 7 & 5 & 3 & 2 \\ \hline 13 & 1 & 6 & 14 & 18 & 18 & 14 & 11 & 7 & 5 & 3 \\ \hline 14 & 1 & 7 & 16 & 23 & 23 & 20 & 15 & 11 & 7 & 5 \\ \hline 15 & 1 & 7 & 19 & 27 & 30 & 26 & 21 & 15 & 11 & 7 \\ \hline 16 & 1 & 8 & 21 & 34 & 37 & 35 & 28 & 22 & 15 & 11 \\ \hline 17 & 1 & 8 & 24 & 39 & 47 & 44 & 38 & 29 & 22 & 15 \\ \hline 18 & 1 & 9 & 27 & 47 & 57 & 58 & 49 & 40 & 30 & 22 \\ \hline 19 & 1 & 9 & 30 & 54 & 70 & 71 & 65 & 52 & 41 & 30 \\ \hline 20 & 1 & 10 & 33 & 64 & 84 & 90 & 82 & 70 & 54 & 42 \\ \hline 21 & 1 & 10 & 37 & 72 & 101 & 110 & 105 & 89 & 73 & 55 \\ \hline 22 & 1 & 11 & 40 & 84 & 119 & 136 & 131 & 116 & 94 & 75 \\ \hline 23 & 1 & 11 & 44 & 94 & 141 & 163 & 164 & 146 & 123 & 97 \\ \hline 24 & 1 & 12 & 48 & 108 & 164 & 199 & 201 & 186 & 157 & 128 \\ \hline 25 & 1 & 12 & 52 & 120 & 192 & 235 & 248 & 230 & 201 & 164 \\ \hline 26 & 1 & 13 & 56 & 136 & 221 & 282 & 300 & 288 & 252 & 212 \\ \hline 27 & 1 & 13 & 61 & 150 & 255 & 331 & 364 & 352 & 318 & 267 \\ \hline 28 & 1 & 14 & 65 & 169 & 291 & 391 & 436 & 434 & 393 & 340 \\ \hline 29 & 1 & 14 & 70 & 185 & 333 & 454 & 522 & 525 & 488 & 423 \\ \hline 30 & 1 & 15 & 75 & 206 & 377 & 532 & 618 & 638 & 598 & 530 \\ \hline 31 & 1 & 15 & 80 & 225 & 427 & 612 & 733 & 764 & 732 & 653 \\ \hline 32 & 1 & 16 & 85 & 249 & 480 & 709 & 860 & 919 & 887 & 807 \\ \hline 33 & 1 & 16 & 91 & 270 & 540 & 811 & 1009 & 1090 & 1076 & 984 \\ \hline 34 & 1 & 17 & 96 & 297 & 603 & 931 & 1175 & 1297 & 1291 & 1204 \\ \hline 35 & 1 & 17 & 102 & 321 & 674 & 1057 & 1367 & 1527 & 1549 & 1455 \\ \hline 36 & 1 & 18 & 108 & 351 & 748 & 1206 & 1579 & 1801 & 1845 & 1761 \\ \hline 37 & 1 & 18 & 114 & 378 & 831 & 1360 & 1824 & 2104 & 2194 & 2112 \\ \hline 38 & 1 & 19 & 120 & 411 & 918 & 1540 & 2093 & 2462 & 2592 & 2534 \\ \hline 39 & 1 & 19 & 127 & 441 & 1014 & 1729 & 2400 & 2857 & 3060 & 3015 \\ \hline 40 & 1 & 20 & 133 & 478 & 1115 & 1945 & 2738 & 3319 & 3589 & 3590 \\ \hline 41 & 1 & 20 & 140 & 511 & 1226 & 2172 & 3120 & 3828 & 4206 & 4242 \\ \hline 42 & 1 & 21 & 147 & 551 & 1342 & 2432 & 3539 & 4417 & 4904 & 5013 \\ \hline 43 & 1 & 21 & 154 & 588 & 1469 & 2702 & 4011 & 5066 & 5708 & 5888 \\ \hline 44 & 1 & 22 & 161 & 632 & 1602 & 3009 & 4526 & 5812 & 6615 & 6912 \\ \hline 45 & 1 & 22 & 169 & 672 & 1747 & 3331 & 5102 & 6630 & 7657 & 8070 \\ \hline 46 & 1 & 23 & 176 & 720 & 1898 & 3692 & 5731 & 7564 & 8824 & 9418 \\ \hline 47 & 1 & 23 & 184 & 764 & 2062 & 4070 & 6430 & 8588 & 10156 & 10936 \\ \hline 48 & 1 & 24 & 192 & 816 & 2233 & 4494 & 7190 & 9749 & 11648 & 12690 \\ \hline 49 & 1 & 24 & 200 & 864 & 2418 & 4935 & 8033 & 11018 & 13338 & 14663 \\ \hline 50 & 1 & 25 & 208 & 920 & 2611 & 5427 & 8946 & 12450 & 15224 & 16928 \\ \hline 51 & 1 & 25 & 217 & 972 & 2818 & 5942 & 9953 & 14012 & 17354 & 19466 \\ \hline 52 & 1 & 26 & 225 & 1033 & 3034 & 6510 & 11044 & 15765 & 19720 & 22367 \\ \hline 53 & 1 & 26 & 234 & 1089 & 3266 & 7104 & 12241 & 17674 & 22380 & 25608 \\ \hline 54 & 1 & 27 & 243 & 1154 & 3507 & 7760 & 13534 & 19805 & 25331 & 29292 \\ \hline 55 & 1 & 27 & 252 & 1215 & 3765 & 8442 & 14950 & 22122 & 28629 & \color{red}{33401} \\ \hline \hline \end{array}$$

Answer 2

The number of partitions of $100$ into $10$ unequal parts is given by the coefficient of $y^{10} x^{100}$ in

$$ \prod_{n\geq 1}\left(1+y x^{n}\right) $$ which by Joffan's remark is given by the number of partitions of $100-45=55$ into $10$ parts, i.e. by the coefficient of $y^{10}x^{55}$ in $$ \prod_{n\geq 1}\left(1+yx^{n}+y^2x^{2n}+\ldots\right) = \prod_{n\geq 1}\frac{1}{1-yx^n}=\frac{1-y}{(y;x)_{\infty}}$$ in terms of q-Pochhammer symbols. This also is the coefficient of $x^{55}$ in $\frac{x^{10}}{t(x)}$, where $t(x)$ is a polynomial with degree $55$ and coefficients in $\{-2,-1,0,1,2\}$, which can be factored as

$$t(x)=(x-1)^{10}(x+1)^5 \Phi_3(x)^2\Phi_4(x)^2 \Phi_5(x)^2\Phi_6(x)\Phi_7(x)\Phi_8(x)\Phi_9(x)\Phi_{10}(x).$$ By partial fraction decomposition and lengthy computations we have that the final outcome should be $\color{red}{33401}$.