Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
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
add comment

2 Answers

up vote 3 down vote accepted

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.