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

  • 1
    Homework ? If so, see this relevant [meta post](http://meta.math.stackexchange.com/questions/1803/how-to-ask-a-homework-question).2011-11-01
  • 0
    Can you do it for $k=1$ and $k=2$?2011-11-01
  • 0
    Please make your title a question or statement that describes your problem; "a generating function" gives very little information.2011-11-07
  • 0
    @Dan, howzat?${}$2011-11-07
  • 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$$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.