I am trying to find a nice way to solve for $$\sum_{a,b,c\ge 1, a+b+c=9}\frac{9!}{a!b!c!}=18150$$ I managed to solved it (and verified by computer) by doing manually (on paper) on $7$ cases and got a "nice" answer of $216+1512+3024+2268+1890+7560+1680=18150=2\cdot 3\cdot5^2 \cdot11^2$.
-
$\begingroup$ This seems like a casework hell kinda problem. I doubt there's an elegant solution to this other than smart grouping of terms, which still won't be nice. Also, you have provided no evidence as to why we should expect there to be a nice way to solve this either. The solution does not look promising at all. $\endgroup$– Rushabh MehtaCommented Dec 28, 2020 at 16:44
-
$\begingroup$ @DonThousand When $9$ is changed to $n$, there may be a nice closed form. $\endgroup$– SpeedingCommented Dec 28, 2020 at 16:46
-
$\begingroup$ @MatthewDaly Yes, there are more. I assumed that and multiply to correct the undercounting. Btw, I have also thought of using PIE. $\endgroup$– SpeedingCommented Dec 28, 2020 at 16:50
2 Answers
Given $a,b,c$, each summand can be thought of as the number of ways to fill $9$ slots with $a$ blue marbles, $b$ red marbles, and $c$ yellow marbles. Therefore, the sum is the total number of ways to fill $9$ slots with blue, red, and yellow marbles assuming at least one of each. You can solve this with the inclusion/exclusion principle as $$3^9-3\cdot2^9+3\cdot1^9=18150$$
This is the number of surjections from a 9-set onto a 3-set. More generally, the number of surjections from an $n$-set onto a $k$-set involves Stirling numbers of the second kind: https://oeis.org/A019538