Splitting Up For Study

8 students are planning on splitting up into 3 (non-empty) study groups. How many ways can they split up into these study groups?

Note : It is possible that a study group contains only 1 person.


The answer is 966.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Using inclusion -exclusion principle,the total number of ways of splitting the students into three groups is 3 8 3 ( 2 8 ) + 3 ( 1 8 ) 3^8-3(2^8)+3(1^8) .However,since the three groups are identical we need to divide by 3 ! 3! . Hence we get the answer as 966 966

Very nice interpretation! Make it very simple to approach!

Calvin Lin Staff - 5 years ago

Can you explain what the numbers in the expression mean?

e r - 2 years, 11 months ago

How can groups be anything other than identical? By assigning them numbers?

Akash Tyagi - 2 years, 1 month ago
Andy Hayes
May 10, 2016

Relevant wiki: Distinct Objects into Identical Bins

This problem is modeled as distinct objects (students) into identical non-empty bins (study groups).

This can be accomplished using Stirling numbers of the second kind .

In particular, we are trying to find S ( 8 , 3 ) S(8,3) .

Begin with the identity, S ( n , r ) = r S ( n 1 , r ) + S ( n 1 , r 1 ) S (n,r) = r S(n-1, r) + S(n-1, r-1) Use recurrence relations and the basic cases of Stirling numbers of the second kind to find the value of S ( 8 , 3 ) S(8,3) .

S ( 8 , 3 ) = 3 S ( 7 , 3 ) + S ( 7 , 2 ) = 3 S ( 7 , 3 ) + 2 6 1 = 3 S ( 7 , 3 ) + 63 S(8,3)=3S(7,3)+S(7,2)=3S(7,3)+2^6-1=3S(7,3)+63 S ( 7 , 3 ) = 3 S ( 6 , 3 ) + S ( 6 , 2 ) = 3 S ( 6 , 3 ) + 2 5 1 = 3 S ( 6 , 3 ) + 31 S(7,3)=3S(6,3)+S(6,2)=3S(6,3)+2^5-1=3S(6,3)+31 S ( 6 , 3 ) = 3 S ( 5 , 3 ) + S ( 5 , 2 ) = 3 S ( 5 , 3 ) + 2 4 1 = 3 S ( 5 , 3 ) + 15 S(6,3)=3S(5,3)+S(5,2)=3S(5,3)+2^4-1=3S(5,3)+15 S ( 5 , 3 ) = ( 5 3 ) + 3 ( 5 4 ) = 10 + 3 × 5 = 25 S(5,3)={5\choose 3} + 3{5\choose 4}=10+3\times 5=25

Now working backwards to S ( 8 , 3 ) S(8,3) :

S ( 6 , 3 ) = 3 S ( 5 , 3 ) + 15 = 3 × 25 + 15 = 90 S(6,3)=3S(5,3)+15=3\times 25+15=90 S ( 7 , 3 ) = 3 S ( 6 , 3 ) + 31 = 3 × 90 + 31 = 301 S(7,3)=3S(6,3)+31=3\times 90+31=301 S ( 8 , 3 ) = 3 S ( 7 , 3 ) + 63 = 3 × 301 + 63 = 966 S(8,3)=3S(7,3)+63=3\times 301+63=966

Thus, there are 966 \boxed{966} ways to form the study groups.

Good. But i wonder is there a nice and easy way to do that?

Shashank Rustagi - 9 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...