1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Dec 20, 2012 #1
    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.
     
  2. jcsd
  3. Dec 20, 2012 #2

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    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.)
     
  4. Dec 20, 2012 #3
    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?
     
  5. Dec 20, 2012 #4

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  6. Dec 20, 2012 #5

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    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.
     
  7. Dec 20, 2012 #6

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook