Waiting For The Bathroom

After careful analysis and trying many different ways of calculating this number, I've derived a formula for the number of ways to fill a set of size $d$ with the numbers from $1$ to $m$ such that the elements of the set sum to $n$ :

$S(d,m,n)=\large\displaystyle\sum_{k=0}^{\lfloor\frac{n-d}{m}\rfloor}(-1)^k{d\choose k}{n-mk-1\choose d-1}$

Plugging in $d=10$ , $m=5$ and $n=35$ we get:

$S(10,5,35)=\large\displaystyle\sum_{k=0}^5(-1)^k{10\choose k}{35-5k-1\choose 9} = \boxed{473694}$

The number of orders is the coefficient of $x^{35}$ in the series expansion of $(x+x^2+x^3+x^4+x^5)^{10} \; = \; x^{10}(1 - x^5)^{10}(1-x)^{-10} \; =\; x^{10} \left(\sum_{j=0}^{10} (-1)^j {10 \choose j} x^{5j}\right)\left(\sum_{j=0}^\infty {j+9 \choose 9}x^j \right)$ and hence is equal to $\sum_{j=0}^5 (-1)^j {10 \choose j}{34-5j \choose 9} \; = \; \boxed{473694}\;.$

This problem is a perfect example of where generating functions can be used. The number of ways of choosing 10 numbers, each from the set {1, 2, 3, 4, 5} that add up to 35 is equal to the coefficient of $x^{35}$ in the expansion of $(x^1 + x^2 + x^3 + x^4 + x^5)^{10}$ . Obviously, the problem with this method is that this then has to be multiplied out to find the coefficient of $x^{35}$ which takes a long time or requires the use of Wolfram Alpha but when multiplied out, the coefficient of $x^{35}$ is $\boxed{473694}$ which is the answer.

Solve

$x_{1} + x_{2} + x_{3} + x_{4} + x_{5} + x_{6} + x_{7} + x_{8} + x_{9} + x_{10} = 35$

for $1 \leq x_{i} \leq 5$ , $i = 1, 2, 3, 4, 5, \ldots , 10$

Which is equal to

$y_{1} + y_{2} + y_{3} + y_{4} + y_{5} + y_{6} + y_{7} + y_{8} + y_{9} + y_{10} = 25$

for $0 \leq y_{i} \leq 5$ , $i = 1, 2, 3, 4, 5, \ldots , 10$

Let $n(S)$ the number of non negative integral solutions of $y_{1} + y_{2} + y_{3} + y_{4} + y_{5} + y_{6} + y_{7} + y_{8} + y_{9} + y_{10} = 25$

$n(S) = {10 + 25 - 1 \choose 25} = 52451256$

Let $A_{i}$ the number of solutions for $y_{i} \geq 5$

Here we will use Principle of Inclusion and Exclusion - Multiple Sets

Let $B_{i}$ be the number of solutions of $\displaystyle \sum_{1 \leq c \leq d \leq \ldots \leq i} |A_{c} \cap A_{d} \cap \ldots \cap A_{i}|$

$|A_{1} \cap A_{2} \cap A_{3} \cap A_{4} \cap \ldots A_{9} \cap A_{10}| = 0$ $\triangleleft$ $10 \times 5 \geq 25$

$\rightarrow$ $B_{10} = 0$

$|A_{1} \cap A_{2} \cap A_{3} \cap A_{4} \cap \ldots A_{8} \cap A_{9}| = |A_{2} \cap A_{3} \cap A_{4} \cap \ldots A_{9} \cap A_{10}| = 0$ $\triangleleft$ $9 \times 5 \geq 25$

$\rightarrow$ $B_{9} = 0$

$|A_{1} \cap A_{2} \cap \ldots A_{7} \cap A_{8}| = |A_{2} \cap A_{3} \cap \ldots A_{8} \cap A_{9}|\\= |A_{3} \cap A_{4} \cap \ldots A_{9} \cap A_{10}|= 0$ $\triangleleft$ $8 \times 5 \geq 25$

$\rightarrow$ $B_{8} = 0$

$|A_{1} \cap A_{2} \cap \ldots A_{6} \cap A_{7}| = |A_{1} \cap A_{2} \cap \ldots A_{6} \cap A_{8}| \\= |A_{1} \cap A_{2} \cap \ldots A_{6} \cap A_{9}| = |A_{1} \cap A_{2} \cap\ldots A_{6} \cap A_{10}| = \ldots \\= |A_{2} \cap A_{3} \cap \ldots A_{7} \cap A_{8}| = \ldots = |A_{4} \cap A_{5} \cap \ldots A_{9} \cap A_{10}|= 0$

$\triangleleft$ $7 \times 5 \geq 25$

$\rightarrow$ $B_{7} = 0$

$|A_{1} \cap A_{2} \cap \ldots A_{5} \cap A_{6}| = |A_{1} \cap A_{2} \cap \ldots A_{5} \cap A_{7}| \\= |A_{1} \cap A_{2} \cap \ldots A_{5} \cap A_{8}| = |A_{1} \cap A_{2} \cap\ldots A_{5} \cap A_{9}| = \ldots \\= |A_{2} \cap A_{3} \cap \ldots A_{6} \cap A_{7}| = \ldots = |A_{5} \cap A_{6} \cap \ldots A_{9} \cap A_{10}|= 0$

$\triangleleft$ $6 \times 5 \geq 25$

$\rightarrow$ $B_{6} = 0$

$|A_{1} \cap A_{2} \cap A_{3} \cap A_{4} \cap A_{5}| = |A_{1} \cap A_{2} \cap A_{3} \cap A_{4} \cap A_{6}| \\= \dots = |A_{2} \cap A_{3} \cap A_{4} \cap A_{5} \cap A_{6}| =\ldots = |A_{6} \cap A_{7} \cap A_{8} \cap A_{9} \cap A_{10}| = 1$

$\triangleleft$ $25 - 5 \times 5=0$ $\triangleleft$ $\triangleleft$ ${10+0-1 \choose 0} = 1$

$\rightarrow$ $B_{5} = {10 \choose 5} \times 1 = 252$

$|A_{1} \cap A_{2} \cap A_{3} \cap A_{4}| = |A_{1} \cap A_{2} \cap A_{3} \cap A_{5}| \\= \dots = |A_{2} \cap A_{3} \cap A_{4} \cap A_{5}| =\ldots \\= | A_{7} \cap A_{8} \cap A_{9} \cap A_{10}| = 2002$

$\triangleleft$ $25 - 4 \times 5=5$ $\triangleleft$ $\triangleleft$ ${10+5-1 \choose 5} = 2002$

$\rightarrow$ $B_{4} = {10 \choose 4} \times 2002 = 420420$

$|A_{1} \cap A_{2} \cap A_{3}| = |A_{1} \cap A_{2} \cap A_{4}| = \dots = |A_{2} \cap A_{3} \cap A_{4}| =\ldots \\= |A_{3} \cap A_{4} \cap A_{5}| = \ldots |A_{8} \cap A_{9} \cap A_{10}| = 92378$

$\triangleleft$ $25 - 3 \times 5=10$ $\triangleleft$ $\triangleleft$ ${10+10-1 \choose 10} = 92378$

$\rightarrow$ $B_{3} = {10 \choose 3} \times 92378 = 11085360$

$|A_{1} \cap A_{2} | = |A_{1} \cap A_{3} | = \dots = |A_{2} \cap A_{3}| \\=\ldots = |A_{3} \cap A_{4}| = \ldots |A_{7} \cap A_{9} = |A_{7} \cap A_{10}| \\=|A_{8} \cap A_{9}|=\ldots |A_{9} \cap A_{10}|=1307504$

$\triangleleft$ $25 - 2 \times 5=15$ $\triangleleft$ $\triangleleft$ ${10+15-1 \choose 15} = 1307504$

$\rightarrow$ $B_{2} = {10 \choose 2} \times 1307504 = 58837680$

$|A_{1}| = |A_{2}| = |A_{3}| = \ldots = |A_{10}| = 10015005$ $\triangleleft$ $25 - 1 \times 5=20$ $\triangleleft$ $\triangleleft$ ${10+20-1 \choose 20} = 10015005$

$\rightarrow$ $B_{1} = {10 \choose 1} \times 10015005 = 100150050$

$\displaystyle \left|\bigcup_{i=1}^n A_i\right| = \sum_{i=1}^n\left|A_i\right|-\sum_{ 1 \leq i < j \leq n }\left|A_i\cap A_j\right| + \sum_{ 1\leq i< j < k \leq n}\left|A_i\cap A_j\cap A_k\right| \\-\ \cdots\ + \left(-1\right)^{n-1} \left|A_1 \cap\cdots\cap A_10 \right|$

$\displaystyle \left|\bigcup_{i=1}^{10} A_i\right| = B_{1} - B_{2} + B_{3} - B_{4} + B_{5} - B_{6} + B_{7} - B_{8} + B_{9} - B_{10}$

$\displaystyle \left|\bigcup_{i=1}^{10} A_i\right| = 100150050 - 58837680 + 11085360 - 420420 + 252 - 0 +0 - 0 + 0$

$\displaystyle \left|\bigcup_{i=1}^{10} A_i\right| = 51977562$

$n\overline{\left(\bigcup_{i=1}^{10} A_i\right)} = n(S) - n\left(\bigcup_{i=1}^{10} A_i\right)$

$n\overline{\left(\bigcup_{i=1}^{10} A_i\right)} = 52451256 - 51977562$

$n\overline{\left(\bigcup_{i=1}^{10} A_i\right)} = \boxed{473694}$