Arranging 120 students into 6 different groups so that the largest and smallest group differ by 2 me

minwaardekn

minwaardekn

Answered question

2022-06-26

Arranging 120 students into 6 different groups so that the largest and smallest group differ by 2 members
In how many different ways can we arrange 120 students into 6 groups for 6 different classes so that the largest group has at most 2 members more than the smallest group?
My initial plan was to use a generating function, but I stumbled across a problem. Let's mark the groups with numbers 1 to 6 and let n i , i { 1 , , 6 } denote the number of members of the i-th group in some arrangment. To see where this would lead me, for a moment, I assumed n 1 n 2 n 6 n 1 + 2 in hope to find some range { m , M } for n i 's and use a generating function f ( x ) = ( x m + + x M ) 6 and find x 120 the coefficient in front of x 120 , however students are distinct entities and m and M still remained misterious. I then tried figuring out if I was on the somewhat right track by, again taking m = min { n 1 , , n 6 } and write n i = m + j i , j i { 0 , 1 , 2 } .. I believe, an arrangement with 2 groups of 19,2 groups of 20 and 2 groups of 21 people suggests there should be at least 19 people in each group.

Answer & Explanation

Paxton James

Paxton James

Beginner2022-06-27Added 25 answers

Step 1
For an another approach : When we check over the question , we see that it is distributing distingusiable objects into distinguishable boxes question. By that reason , using exponential generating function is more suitable than using ordinary generating functions.
It is given that the largest class can have at most 2 more students than the smallest. Then we see that a group can have at least 19 and at most 21 students. Then if the groups will be distingusihable then our exponential generating function of each group will be ( x 19 19 ! + x 20 20 ! + x 21 21 ! )
Then ,we should find the coefficient of x 120 120 ! or find the coefficient of x 120 and multiply it by 120! in the expansion of ( x 19 19 ! + x 20 20 ! + x 21 21 ! ) 6 .
Step 2
However , if the groups will be indistinguishable , then multiply the result of [ x 120 ] ( x 19 19 ! + x 20 20 ! + x 21 21 ! ) 6
by 1 6 ! .
Then , the result is 1 6 ! × [ x 120 ] ( x 19 19 ! + x 20 20 ! + x 21 21 ! ) 6
When we calculate the result using given coefficient in the link , the answer is 5.756410166785662 e + 87
landdenaw

landdenaw

Beginner2022-06-28Added 8 answers

Step 1
You can do this a smidgen more simply (at least, it's simpler to me).
First, the average size of a group is 20. If any group is smaller than average, then some other group must be larger than average, which means that there must be a group of size at least 21. Thus, the smallest group must have size at least 19.
Distribute 19 people into each group. This can be done in x = ( 114 19 , 19 , 19 , 19 , 19 , 19 ) ways.
Now count the ways to distribute the remaining 6 people across the groups with the constraint that no more than 2 of these people can go into any group and multiply the result by x. The unconstrained number of solutions of x 1 + + x 6 = 6 is ( 11 6 ) . Using the principal of inclusion and exclusion, you must subtract the number of solutions where x i 3. For any i, there are ( 8 3 ) such solutions, so you must subtract 6 ( 8 3 ) . But you also must add back the double-counted solutions where x i , x j 3, of which there are ( 6 2 ) .
So the answer is: ( ( 11 6 ) 6 ( 8 3 ) + ( 6 2 ) ) x .

Do you have a similar question?

Recalculate according to your conditions!

New Questions in Discrete math

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?