Recently in a combinatorics problem I am trying to do, I need to find a way to partition 10 (distinct) people into 5 groups, with each group having a maximum size of 4 people. So a valid partition might be
$$ * | *** | **** | * | ** $$
I'm know that there are the the Stirling numbers of the second kind which give the number of ways to order $n$ elements into $k$ subsets, but I can't seem to find a way to use this in my problem. I also am wondering if there is a way to generalize my problem?
Any help is appreciated!
Best Answer
I do not understand why you are having a difficulty when you are aware of Stirling numbers of the second kind.
If you examine the problem, the upper limit plays no role since all groups are to be non-empty, thus simply
$5!*S2(10,5)$
Or (if you don't have recourse to a table of Stirling numbers), just apply inclusion-exclusion, thus
$5^{10} - \binom51*4^{10}+\binom52*3^{10} -\binom53*2^{10} +\binom54*1^{10}$
PS:
If you are actually having a problem with an upper bound, here is a general formula using stars and bars with upper bound
The general formula for $N$ objects, $K$ boxes and a max of $M$ in each box would be
$$ \sum_{j=0}^{\lfloor\frac{N}{M+1}\;\,\rfloor}(-1)^j\binom Nj\binom{N-j(M+1)+K-1}{K-1}\; $$
For the example you gave, $\lfloor\frac{N}{M+1}\rfloor=\lfloor\frac{10}{5}\rfloor = 2$
This would give the number of patterns of identical objects into distinct boxes, and you would need to multiply by $10!$ to get the desired answer
Or, if you are comfortable with generating functions, you could go by that route, as in the other answer by @Arun Madhav