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.

So I'm trying to come up with a recursive formula $f(n)$ which counts the number of all partitions of $[n]$ into $k$ identical blocks, where the number of elements in each box is more than 1.

What i've tried to do is look at the $n$-th element. If I assume that the $n$-th element is in a box of size $n-2i$, then there's $2i$ element's remaining. Should it follow that there are ${n \choose 2i}$ ways to pick these, and then $f(i)$ valid ways to partition them? Giving $$f(n) = \sum_{i=0}^{n-1} {n\choose 2i}f(i)$$

Does this seem right? If no, any hints you can give me?

share|improve this question
    
Your blocks are unlabelled, right? –  Matemáticos Chibchas Jan 28 '13 at 2:15
    
Yes, I forgot to add that, sorry. –  MITjanitor Jan 28 '13 at 2:16

1 Answer 1

up vote 0 down vote accepted

This is a partial answer. First, $f(n)=0$ for $n<2k$ and $$f(2k)=\frac1{k!}\binom{2k}2\binom{2k-2}2\cdots\binom 42\binom 22=\frac{(2k)!}{2^kk!}$$ (you choose $2$ of the $2k$ numbers, then you choose another $2$ of the remaining $2k-2$ numbers, and so on. Finally, you divide by $k!$ since your boxes are identical).

For $n>2k$, suppose that you already put the numbers $1,\dots,n-1$ in the boxes. Then you only can have at most $1$ box with a single element (briefly, a single box), because otherwise the last choice for $n$ would not be enough to avoid single boxes. If none of the box is single, then you can put your number $n$ in any place. If there is a box with a single number, say $j$, then actually you already filled the other $k-1$ boxes with $n-2$ numbers, none of the boxes being single.

The first option contributes $k\cdot f(n-1)$; unfortunately, for the second option I must consider your function $f$, but with $k-1$ instead of $k$. In other words, denoting your function by $f_k$, then the second option contributes $(n-1)\cdot f_{k-1}(n-2)$ (the factor $n-1$ corresponds to the choices for $j$). Consequently the recurrence becomes

$$f_k(n)=kf_k(n-1)+(n-1)f_{k-1}(n-2)\,.$$

I wish to see a solution involving just the function $f_k$,

share|improve this answer

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.