0
$\begingroup$

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?

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

3 Answers 3

1
$\begingroup$

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$

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

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

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Steve Kass
    Feb 17, 2014 at 3:25
  • 1
    $\begingroup$ Yes that's what I meant. THANK YOU for clarifying. $\endgroup$
    – lwang456
    Feb 17, 2014 at 3:27
0
$\begingroup$

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})$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .