# exponential generating function for distinct objects into distinct boxes

I have to find the exponential generating function for placing distinct objects into $k$ distinct boxes with at least $m$ object per box, indexed by the number of objects. Could you help me please? Also with some hints

• Homework ? If so, see this relevant meta post. – Sasha Nov 1 '11 at 22:54
• Can you do it for $k=1$ and $k=2$? – Phira Nov 1 '11 at 23:56
• Please make your title a question or statement that describes your problem; "a generating function" gives very little information. – Dan Drake Nov 7 '11 at 0:40
• @Dan, howzat?${}$ – Gerry Myerson Nov 7 '11 at 0:52
• I guess the title got edited. Originally it was just "a generating function". – Dan Drake Nov 9 '11 at 13:22

Let $a_k(m,n)$ be the number of ways of placing $n$ distinct objects in $k$ distinct boxes if there must be at least $m$ objects in each box. Suppose first that $k=1$. Clearly $a_1(m,n)=0$ if $n<m$, and $a_1(m,n)=1$ if $m\ge n$, so the exponential generating function for the $a_1(m,n)$ is $$A_1(x)=\sum_{n\ge 0}a_1(m,n)\frac{x^n}{n!}=\sum_{n\ge m}\frac{x^n}{n!}=e^x-\sum_{n=0}^{m-1}\frac{x^n}{n!}.$$
Suppose now that you know $A_k(x)$ for some $k\ge 1$. To distribute $n$ objects amongst $k+1$ boxes you must first choose some of them to go into box $k+1$ and then distribute the remainder amongst the first $k$ boxes. Suppose that you put $r$ objects into box $k+1$. You can choose these $r$ objects in $\binom{n}r$ ways, and there are then $a_1(m,r)$ ways to ‘distribute’ them to box $k+1$ and $a_k(m,n-r)$ ways to distribute the remainder amongst the other $k$ boxes. Summing over the possible values of $r$, we find that $$a_{k+1}(m,n) = \sum_{r=0}^n\binom{n}r a_1(m,r)a_k(m,n-r)\;,$$ which is exactly what is needed to give us $A_{k+1}(x)=A_1(x)A_k(x)$. By induction, then, $$A_k(x)=A_1(x)^k=\left(e^x-\sum_{n=0}^{m-1}\frac{x^n}{n!}\right)^k\tag{1}.$$ If we set $$p_m(x)=\sum_{n=0}^{m-1}\frac{x^n}{n!},$$ the Taylor polynomial of order $m-1$ for the exponential function, $(1)$ can be written simply $$A_k(x) = \big(e^x-p_m(x)\big)^k.$$
It is easy to do for $k=1$. For general $k$, one can use the correspondence between disjoint union of labelled combinatorial objects and products of exponential generating functions.