1

There was a question that was asked as below. How many different ways can you distribute m distinct objects into n distinct bins such that there are no bins with exactly one object.

To solve this I made an attempt but do not know how to finish it off in terms of know expressions.

Using exponential generating function, we have

$ G_e(x) = (1+x^2/2! + x^3/3!+..)^m$

I write this now as $(e^x-x)^m = \sum_{h=0}^{m}{m\choose h} (-x)^h \sum_{n=0}^{\infty} \dfrac{(m-h)^n x^n}{n!}$

I do not know how I can get it in the form of know expression such as S(n,m)

Could someone help me in manipulating the above expression and simplifying it further.

Satish Ramanathan
  • 11,984

1 Answers1

1

For $n$ distinct bins with no singletons in the bins we get the combinatorial class

$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}} \textsc{SEQ}_{=n}(\textsc{SET}_{\ne 1}(\mathcal{Z})).$$

This yields per EGF

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

This is

$$\bbox[5px,border:2px solid #00A000]{ m! \sum_{q=0}^n \frac{n!}{(n-q)!} \sum_{p=q}^m \frac{1}{p!} {p\brace q} (-1)^{m-p} {n-q\choose m-p}.}$$

For the case of $m\le n$ we can further simplify to get

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

Marko Riedel
  • 61,317