5
$\begingroup$

If we were to put $m$ distinct balls to $n$ identical boxes with no empty boxes, there would be $S(m,n)$ ways to do it where $S(m,n)$ is the Stirling number of the second kind.

But when it comes to the case where we should put the balls with each box has at least $2$ balls, I am stuck here because this is not an ordinary surjection anymore. What I tried so far was trying to examine the problem case by case.

Let $\sigma(m,n)$ be the number of ways of putting $m$ distinct balls to $n$ identical boxes with each box has at least $2$ balls. For the case $m < 2n$, we have $0$ way to do this, obviously. For the case $m = 2n$, I think the number of ways $$\sigma(m,n) = \sigma(2n,n) = \frac{1}{n!} \prod_{\scriptstyle i = 0\atop\scriptstyle i \ even}^{2n-2} \binom{2n-i}{2}$$ because we are partioning $2n$ as $2+2+...+2$ where there are $n$ many $2$'s and since the boxes are identical, we are dividing it by $n!$ in order to avoid overcounting. It is also obvious that for $m \ge 2$ and $n = 1$, $\sigma(m,n) = \sigma(m,1) = 1$. But for other cases, I cannot find any way to find a closed form expression or a recurrence relation for $\sigma(m,n)$ because I think I need to consider both number of ways of partioning $m$ into $n$ classes and number of ways of seperating balls for each partioning in order to find a closed form expression. And in order to find a recurrence relation, I have to proceed as deriving a recurrence relation for Stirling numbers of the second kind but here there are not two cases as in the Stirling numbers $\bigg(S(m,n) = S(m-1,n-1) + nS(m-1,n)$, here the two cases are "when we put $m-1$ balls into $n-1$ boxes" and "when we put $m-1$ balls into $n$ boxes" $\bigg)$. If I could find a way to divide the problem into some disjoint cases, I would have found a recurrence relation but no luck there so any suggestion will be appreciated.

$\endgroup$
3
$\begingroup$

We get for the combinatorial class of set partitions into non-empty parts and hence Stirling numbers the specifiaction

$$\mathfrak{P}_{=k}(\mathfrak{P}_{\ge 1}(\mathcal{Z}))$$

and thus the generating function

$$\sum_{n\ge 0} {n\brace k} \frac{z^n}{n!} = \frac{(\exp(z)-1)^k}{k!}.$$

This will start producing non-zero terms when $n\ge k.$ Using the same construction we get for set partitions with at least two balls

$$\mathfrak{P}_{=k}(\mathfrak{P}_{\ge 2}(\mathcal{Z}))$$

and thus the generating function

$$\sum_{n\ge 0} {n\brace k}_{\ge 2} \frac{z^n}{n!} = \frac{(\exp(z)-z-1)^k}{k!}.$$

Extracting coefficients from this we find

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

This yields

$$\bbox[5px,border:2px solid #00A000]{ {n\brace k}_{\ge 2} = \sum_{q=0}^k {n\choose k-q} (-1)^{k-q} {n+q-k\brace q}.}$$

For example with $k=3$ we get the sequence starting at six

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

which is OEIS A000478 where the preceding calculation is confirmed. With $k=4$ we find starting at eight,

$$105, 1260, 9450, 56980, 302995, 1487200, 6914908, \ldots$$

which is OEIS A058844 which once more confirms these data.

$\endgroup$
1
$\begingroup$

Are you familiar with cycle notation for permutations? Two permutations are conjugate if and only if they have the same cycle type. All permutations with the same cycle type belong to the same conjugacy class. There is a bijection between $\text{Par}(m)$ and the conjugacy classes of $\text{Sym}(m)$ (the $m!$ permutations).

Now let $\mu = (\mu_{1}^{a_{1}}, \ldots, \mu_{k}^{a_{k}}) \in \text{Par}(m)$, where exponent denotes multiplicity. The size of a conjugacy class is given by:

$$\frac{m!}{\prod_{i=1}^{k} (\mu_{i}^{a_{i}} \cdot a_{i}!)}$$

Let $\text{Par}_{2, n}(m)$ be the set of partitions of $m$ with $n$ parts, and each part is at least $2$. You are interested in permutations with cycle type $\mu \in \text{Par}_{2,n}(m)$.

$\endgroup$
  • $\begingroup$ Actually I am not used to the group theory concepts and I have never heard of the notation you mentioned. But thank you very much for a different approach, I will try to understand the cycle notation and its application. $\endgroup$ – ArsenBerk Dec 20 '17 at 3:19
1
$\begingroup$

is it $\sigma(m,n) = (m-1) * \sigma(m-2,n-1) + n * \sigma (m-1,n)$ ?

$\endgroup$
  • $\begingroup$ This seems correct and I understood the second case ($n \sigma(m-1,n)$) but in the first case, where does $m-1$ come from? $\endgroup$ – ArsenBerk Dec 22 '17 at 0:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.