How many ways are there to distribute $19$ distinct objects into $3$ distinct boxes such that no two boxes contain same number of element

Question

How many ways are there to distribute $19$ distinct objects into $3$ distinct boxes such that no two boxes contain same number of element,i.e, each boxes have distinct number of elements. No empty boxes allowed.

My work: I chose using principle of inclusion exclusion principle and generating functions , so

• All - at least two boxes have same number of element

• All : Stirling number of second kind $3! \times S(19,3)=3! \times193448101$ or $\bigg[\frac{x^{19}}{19!}\bigg](e^x-1)^3$ by generating functions.

• Now, lets calculate two boxes have same number of element. Firstly, select which ones they are by $\binom{3}{2}$.Because of these two boxes have same number of elements, they can take $(1,1),(2,2),(3,3),..,$. So, if we select the elements for these two boxes at the same time, and after the selection we disperse selected elements between them equally. So, our E.G.F is equal to $$\binom{2}{1}\frac{x^2}{2!}+\binom{4}{2}\frac{x^4}{4!}+\binom{6}{3}\frac{x^6}{6!}+...+ =\sum_{n \geq1}\frac{x^{2n}}{(n!)^2}$$ So $$\binom{3}{2}\bigg[\frac{x^{19}}{19!}\bigg]\bigg(\sum_{n \geq1}\frac{x^{2n}}{(n!)^2}\bigg)e^x$$ where $e^x$ is for the rest box.

• Now, lets calculate three boxes have same number of elements using the same way.

$$\binom{3}{3}\bigg[\frac{x^{19}}{19!}\bigg]\bigg(\sum_{n \geq1}\frac{x^{3n}}{(n!)^3}\bigg)$$

Then, the answer is $$\bigg[\frac{x^{19}}{19!}\bigg]\bigg[(e^x-1)^3-\binom{3}{2}\bigg(\sum_{n \geq1}\frac{x^{2n}}{(n!)^2}\bigg)e^x+\binom{3}{3}\bigg(\sum_{n \geq1}\frac{x^{3n}}{(n!)^3}\bigg)\bigg]$$

First of all I want you to check my method whether it is correct or not. Secondly,I want to simplify my generating functions into more closed form. I assume that $\bigg(\sum_{n \geq1}\frac{x^{3n}}{(n!)^3}\bigg)$ or $\bigg(\sum_{n \geq1}\frac{x^{2n}}{(n!)^2}\bigg)$ can be represented more closed form such as trigonometric , logarithmic or any others forms.

Note: Any other easier methods are accepted, please make contribution to find more practical methods.

$\color{red}{NOTE 2}$: It would be nice to see generalized solution for n distinct balls into r distinct bins such that no bins contain same number of elemnt

Answer 1

You are free to place 18 balls anywhere you like, and almost free to place the last ball except when it makes a count match. And except when it leaves an empty box. So the answer is between $3^{18}$ and $3^{19}$.

The exact answer is $$\sum_{a + b + c = 19 \\ a,b,c\text{ distinct} \\ a,b,c \text{ positive}} {19 \choose a} {19 - a \choose b} $$

which is $773,698,050 \approx 3^{18} \times 1.997$. You could try lifting the $\ne$ branch out of the sums to make a finite set of combination sums, but not sure it is worth the effort.

Answer 2

Obviously, all three boxes can't have the same number of items.

So, PIE is very easy, and we get $\color{green}{3^{19} - 3\cdot2^{19}+ 3}$ without any restrictions. Now, suppose 2 boxes have the same no. of elements. There are $\color{red}3$ ways to select the pairs.

Once you have the pair, suppose both have $k$ objects, $1\le k \le 9$. Now, this can be done in $$\binom{19}{2k}\binom{2k}{k}$$ways. Other objects must go into the remaining box (and it can't be empty, due to parity of 19). Summing, $$\sum_{k=1}^{9} \binom{19}{2k}\binom{2k}{k}$$

I don't see any useful trick to calculate this, other than brute forcing it.

You should get $\color{red}{128996852}$, hence the final answer is $$\boxed{\color{green}{3^{19} - 3\cdot2^{19}+ 3} - \color{red}{3\cdot 128996852}}$$ This is $773698050$.