0
$\begingroup$

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

  • 0
    I guess the title got edited. Originally it was just "a generating function".2011-11-09

2 Answers 2

3

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, 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.$

1

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.