Distribute n distinct objects into r alike boxes such that, there are at least 2 objects in a box.

Question

The go-to approach for distributing n distinct objects into r alike boxes is S(n,r). (Stirling no. of the second kind).

How do I make sure there are at least 2 objects in a box?

Answer 1

Using combinatorial classes in the notation from Flajolet and Sedgewick we get the class

$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}} \textsc{SET}_{=r}(\textsc{SET}_{\ge 2}(\mathcal{Z}))$$

which gives the EGF

$$F(z) = \frac{1}{r!} (\exp(z)-1-z)^r.$$

Extracting the coefficient for the count we find

$$n! [z^n] \frac{1}{r!} \sum_{q=0}^r {r\choose q} (\exp(z)-1)^q (-1)^{r-q} z^{r-q} \\ = n! \sum_{q=0}^r (-1)^{r-q} \frac{1}{(r-q)!} {n+q-r\brace q} \frac{1}{(n+q-r)!} \\ = \sum_{q=0}^r (-1)^{r-q} {n\choose r-q} {n+q-r\brace q} \\ = \sum_{q=0}^r (-1)^q {n\choose q} {n-q\brace r-q}.$$

Here we obviously require $n\ge 2r.$ We get for three boxes starting at $n=6$ the sequence

$$15, 105, 490, 1918, 6825, 22935, 74316, 235092, \ldots$$

which points us to OEIS A000478 where we learn not surprisingly that what we have here are the Associated Stirling numbers.

This last formula also counts by inclusion-exclusion. We seek distributions having no singleton sets. Here the nodes of the underlying poset (which is ordered by set inclusion) represent sets $Q$ of singletons and count distributions into $r$ alike sets having these singletons or more. The weight on each node is $(-1)^{|Q|}.$ Hence a distribution having exactly the set $P$ of singletons is included in all nodes $Q\subseteq P \neq \emptyset$ for a total weight of

$$\sum_{Q\subseteq P} (-1)^{|Q|} = \sum_{q=0}^{|P|} {|P|\choose q} (-1)^q = 0.$$

The distributions having no singletons are only included in the node $Q=\emptyset$ and hence have a weight of one. These are precisely what we wish to count. On the other hand summing all weights of the represented distributions over the nodes $Q$ yields

$$\sum_{Q\subseteq [n]} (-1)^{|Q|} {n-|Q|\brace r-|Q|} = \sum_{q=0}^r {n\choose q} (-1)^q {n-q\brace r-q}.$$

We select the singletons corresponding to $Q$ and distribute the rest without any further constraints into the remaining boxes. Here we have taken into account that nodes $Q$ where $|Q|\gt r$ do not represent any distributions because they would have more than $r$ singletons which is not possible with a maximum of $r$ sets.

Answer 2

I think that the mıst suitable way for this problem is to use exponential generating functions. First of all , remember that when we distribute distinct objects into distinct boxes , we can use exponential genarating fucntions. If you do not about generating functions , then firstly you should work over it to understand my solution. Now , lets think that we distributing $n$ distinct objects into $r$ distinct boxes where each boxes have at least two elements in it. Then , the exponential generating function form for each boxes is equal to $$\bigg(\frac{x^2}{2!}+ \frac{x^3}{3!} + \frac{x^4}{4!} + ...\bigg)$$ You can also write it like $(e^x - 1 - x)$ , you can remember these identities form your calculus years. They were called Taylor expansions. Anyway, because of there are $r$ boxes , we should find the coefficent of $[x^{n}]$ in the expansion of $$\bigg(\frac{x^2}{2!}+ \frac{x^3}{3!} + \frac{x^4}{4!} + ...\bigg)^r$$ and multiply it by $n!$ or just find the coeffient of $ \frac{x^n}{n!} $ in this expansion. For example , lets say that $n=12$ , $r=4$ ,then we can distribute these $10$ distinct objects into $4$ distinct boxes where each boxes have at leat $2$ objects by $10! \times \frac{1}{16}$ ways.You can see it in Calculation by wolfram In this example , we restricted it at $\frac{x^4}{4!}$ , because if each boxes have at least $2$ objects then a box can have at most $4$ objects , right ?

Now , lets turn our main question , it is said that the objects are distinct and the boxes are identical.To satify this rule , we dhould divide our result which obtained form distributing distinct objects into distinct boxes by $r!$ ,i.e, the result of factorial of the number of boxes.Because when we divide by $r!$ , we convert the exponential generting functions for each boxes from distinct to identical.

For our example given by me , the answer would be $$\frac{10! \times \frac{1}{16}}{4!}$$

For generalization $$\frac{[x^n]\bigg(\frac{x^2}{2!}+ \frac{x^3}{3!} + \frac{x^4}{4!} + ...\bigg)^r}{r!}$$

However, note that making use of generating function is valid only for the cases where each boxes have at least one element.

I want to thank to @Math Lover for this beneficial knowledge . I hope this help you !!