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
exponential generating function for distinct objects into distinct boxes
-
0I guess the title got edited. Originally it was just "a generating function". – 2011-11-09
2 Answers
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
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.