# unlimited combination

It's a combination problem. 50 people shall be splitted in groups less than five $(\le5)$ what are the number of all possible combinations?

That means there can exist 1-person groups, 2-people groups, 3,4,5-people groups in one possible situation. The question is asking how many situations could there be?

• Is it necessary that the groups have null intersection?
– Hawk
Feb 17, 2014 at 3:12
• not necessarily... see the comments below Feb 17, 2014 at 3:39
• You agree that it's a problem about partitioning --- that means the groups don't intersect each other. Feb 17, 2014 at 9:26
• Do you have some reason to believe there's a formula, or an efficient way to compute the answer? Feb 17, 2014 at 9:29
• If they have null intersection, then I think, I may not have to think very much to get a solution.
– Hawk
Feb 17, 2014 at 13:32

Let $F(n)$ denotes the number of such partitions for $n$ total people, then $$F(n)=F(n-1) + (n-1)F(n-2)+\frac {1}{2!}(n-1)(n-2)F(n-3)+\frac {1}{3!}(n-1)(n-2)(n-3)F(n-4)+\frac {1}{4!}(n-1)(n-2)(n-3)(n-4)F(n-5)$$ which amounts to picking one person and explicitly putting him alone or in a group of 1,2,3,4 persons.

Of course $F(1)=1$ and $F(a<0)=0$.

I am not aware of an explicit analytic solution to this recurrence relation but a simple script should give you the answer for $n=50$

• Nice idea. But I think you should divide the $(n-1)(n-2)F(n-3)$ term, for example, by 2. Jun 21, 2014 at 13:59
• @Michael Of course I should ; ) Thank you Jun 21, 2014 at 14:01
• In the second idea, don't you miss out 4+4+2=5+5? Jun 21, 2014 at 15:06
• @Michael: Indeed, among other mistakes there is this one yes. Thank you for pointing it out. Jun 21, 2014 at 15:15

$${50 \choose 5} + {50 \choose 4} + {50 \choose 3} + {50 \choose 2} + {50 \choose 1}$$

• I don't think that's what the OP wants. Your answer is the number of different non-empty subgroups of the 50 people of size at most 5. The question is harder: In how many ways can a group of 50 people be partitioned into subgroups where none of the subgroups contains more than 5 people. Feb 17, 2014 at 3:25
• Yes that's what I meant. THANK YOU for clarifying. Feb 17, 2014 at 3:27

From Frederic's recursion, let $F(n)=n!G(n)$, then the recursion for $G(n)$ is $$nG(n)=G(n-1)+\frac{G(n-2)}{2}+\frac{G(n-3)}{6}+\frac{G(n-4)}{24}$$ Let $H(x)$ be the generating function $H(x)=\sum G(n)x^n$, then $$H'(x)=H(x)+xH(x)/2+x^2H(x)/6+x^3H(x)/24\\ H(x)=\exp(x+x^2/4+x^3/18+x^4/96)$$ I expect the dominant term, for large $n$, will be $F(n)\approx n!/((n/4)!96^{n/4})$