Finding the number of ways in which a group can take exams?

[khurram usman]

A group of 45 Computer Science students at a particular University had to
take their first Discrete Mathematics course in the Autumn, Winter or
Spring quarter of their Freshman year. How many possible ways were
there for this group to meet this requirement?

i came across this question on the web while preparing for my exam. how do i approach this ?
also is there any good resource of solved problems for discrete mathematics problems on counting,set theory etc.?
any help is appreciated.

 

[Ray Vickson]

A group of 45 Computer Science students at a particular University had to
take their first Discrete Mathematics course in the Autumn, Winter or
Spring quarter of their Freshman year. How many possible ways were
there for this group to meet this requirement?

i came across this question on the web while preparing for my exam. how do i approach this ?
also is there any good resource of solved problems for discrete mathematics problems on counting,set theory etc.?
any help is appreciated.

The question is not well-defined. For example, one can have 15 students in the course in each term. Does that count as ONE way, or many, many ways, depending on how the 45 individual names are assigned to the three terms---that would be 53494979785374631680 different ways! Which interpretation is meant? (You could, of course, try to solve both versions.)

 

[khurram usman]

i think that the second version is wanted. how did you get this huge number?
i was thinking that we have 45 objects and we have to divide them into three groups. we have to find the total number of such groups.
so we have 45 objects and we have to insert 2 sticks in between essentially dividing them into 3 groups. so the total number should be (45+2)C(2) that is 47C2.
this comes out to be 1081
is this approach wrong?

 

[Ray Vickson]

i think that the second version is wanted. how did you get this huge number?
i was thinking that we have 45 objects and we have to divide them into three groups. we have to find the total number of such groups.
so we have 45 objects and we have to insert 2 sticks in between essentially dividing them into 3 groups. so the total number should be (45+2)C(2) that is 47C2.
this comes out to be 1081
is this approach wrong?

The number of distinct ways of splitting a group of N distinguishable items into three groups of sizes n1, n2, n3 (with n1 + n2 + n3 = N) is N!/(n1! * n2! * n3!). So, a group of 45 individuals can be assigned to three groups of 15 each in 45!/(15!)^3 ways.

This is quite easy to see. The number of distinct first groups is N!/(n1! * (N-n1)!) = binomial coefficient C(N,n1). Now, given the N-n1 remaining items not in the first group, the number of ways of putting them into group 2 is C(N-n1,n2) = (N-n1)!/(n2! *(N-n1-n2)!). Therefore, the number of ways of forming the three groups is C(N,n1)*C(N-n1,n2) = the formula I gave before.

 

[haruspex]

i think that the second version is wanted. how did you get this huge number?
i was thinking that we have 45 objects and we have to divide them into three groups. we have to find the total number of such groups.
so we have 45 objects and we have to insert 2 sticks in between essentially dividing them into 3 groups. so the total number should be (45+2)C(2) that is 47C2.
this comes out to be 1081
is this approach wrong?

That gives the number of ordered group sizes. I.e. how many students attend each offering, where you discriminate the offerings but not the students. Thus, attendances (14,15,16) is different from (16,15,14).
Ray's 45!/(15!)^3 is for where the attendances are fixed at (15,15,15) and the students are discriminated. But I don't see anything in the problem statement that fixes that attendance pattern.
If we discriminate students but there are no constraints on attendance pattern, each student can select an offering independently of the others, leading to a much larger number.

 

[Ray Vickson]

i think that the second version is wanted. how did you get this huge number?
i was thinking that we have 45 objects and we have to divide them into three groups. we have to find the total number of such groups.
so we have 45 objects and we have to insert 2 sticks in between essentially dividing them into 3 groups. so the total number should be (45+2)C(2) that is 47C2.
this comes out to be 1081
is this approach wrong?

You say you wanted the second version, but your calculation is for the first version. That is why there is such a huge difference between the two counts.

One way of counting (where you just want to know the class sizes) would be the problem faced by a resource-allocation planner who needs to assign resources to the classes based on enrollment numbers. The number of different resource-allocation packages is equal to the number you tried to calculate above.

Another way of counting would be the problem of determining the different numbers of class-lists, where you not only specify the class sizes but also the individual students in the class. In this problem there are 3^45 = 2954312706550833698643 different possible class lists. This is obtained by summing $N!/(n_1! n_2! n_3!) \; (N = 45)$ over those $n_i \geq 0$ that sum to $N$. You can do the sum by using the trinomial expansion.