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

minwaardekn 2022-06-26 Answered
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.
You can still ask an expert for help

Want to know more about Discrete math?

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

Solve your problem for the price of one coffee

  • Available 24/7
  • Math expert for every subject
  • Pay only if we can solve it
Ask Question

Answers (2)

Paxton James
Answered 2022-06-27 Author has 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
Did you like this example?
Subscribe for all access
landdenaw
Answered 2022-06-28 Author has 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 .
Did you like this example?
Subscribe for all access

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

You might be interested in

asked 2021-08-18

Discrete Mathematics Basics

1) Find out if the relation R is transitive, symmetric, antisymmetric, or reflexive on the set of all web pages.where (a,b)R if and only if 
I)Web page a has been accessed by everyone who has also accessed Web page b.
II) Both Web page a and Web page b lack any shared links.
III) Web pages a and b both have at least one shared link.

asked 2021-07-28

Let A, B, and C be sets. Show that (AB)C=(AC)(BC)
image

asked 2021-08-15
How many elements are in the set { 0, { { 0 } }?
asked 2020-11-09
Use proof by Contradiction to prove that the sum of an irrational number and a rational number is irrational.
asked 2021-02-19
For the following questions you must use the rules of logic (Don’t use truth tables)
a) Show that (pq) and (¬p¬q ) are logically equivalent.
b) Show that not ( pq) and (pq) are logically equivalent.
asked 2022-09-05
Assume that a b mod n and that n∣a. Show that n∣b
Here is what I have.
If a b mod n this implies a = b + x n for some x Z . (1)
Since n∣a we can say a = y n for some y Z . (2)
Combining (1) and (2) we have y n = b + x n (3)
Dividing (3) by n we have that n∣b (4).
Is this correct? Can I divide like this in line (4) in this kind of proof?
asked 2022-07-15
I'm doing a review for my discrete math test on functions and I'm having troubles with a few questions. Can I get some guidance in how to do these questions so I can be more prepared for the test?
1. (b) Show that the 'rule' g : Z 6 Z 9 defined by f ( [ a ] 6 ) = [ 4 a ] 9 is not a well-defined function.
2. Define a function f : N × N N by f ( ( a , b ) ) = gcd ( a , b )
(a) show that f is not one-to-one
(b) show that f is onto
3. Let A, B, C be non-empty sets and let f : A B and g : B C be functions.
(a) Show that it g f is onto, then g is onto
(b) Find an example of functions f and g such that g f is onto but where f is not onto

New questions

Solve your problem for the price of one coffee

  • Available 24/7
  • Math expert for every subject
  • Pay only if we can solve it
Ask Question