Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I know this problem is easy, but it's been a few years since I've touched combinatorics. I was hoping to get some intuition towards a solution :)

Let's say I am picking courses for my upcoming semester. Available to me are 7 math courses, 4 science courses, 4 language courses and 3 history courses. I want to select 3 math courses, 2 science courses, and 1 language or history course. How many ways can I arrange my timetable?

How does this change if I want 3 math courses, 2 science or history courses, and 2 language or history courses?

Thanks for your help!

share|improve this question
add comment

2 Answers

up vote 5 down vote accepted

The number of ways of choosing $k$ objects from $n$ choices is given by $$\binom{n}{k}=\frac{n(n-1)\cdots(n-k+1)}{k(k-1)\cdots2\cdot1},$$ which is known as a binomial coefficient (see also here).

Also, if you have $x$ options for decision #1, and $y$ options for decision #2, and which choice you make in either decision does not affect the other (i.e., they are independent decisions), then there are a total of $xy$ options all together.

So, if you want to pick 3 math courses out of 7, the number of options you have for the math class decision is $$\binom{7}{3}=\frac{7\cdot6\cdot5}{3\cdot 2\cdot1}=35.$$ The number of ways of picking 2 science courses out of 4 is $$\binom{4}{2}=\frac{4\cdot3}{2\cdot1}=6.$$ The number of ways of picking 1 language or history course out of a total of $7=4+3$ language and history courses is $$\binom{7}{1}=\frac{7\cdot6\cdot5\cdot4\cdot3\cdot2}{6\cdot5\cdot4\cdot3\cdot2\cdot1}=7.$$ Now the total number of options you have is simply $$35\cdot 6\cdot 7=1470.$$


The question gets a bit tougher when your choices are not independent, like in your variation (if you choose history courses in your second decision, you might be forced to choose language courses in your third decision). However, it's not exactly clear to me what your variation means; when you say you want "2 science or history courses", does that mean you either want 2 science courses or 2 history courses, or does it mean that you want to choose any 2 courses from the total of 7 science and history courses?

share|improve this answer
    
I don't think ${7 \choose 3}$ is 140. Should be 35. –  Fixee Aug 19 '11 at 1:46
    
Ack, of course (thanks for the catch!). Edited. –  Zev Chonoles Aug 19 '11 at 1:49
    
The variation was meant to be "2 from the science or history courses", not "2 science courses or 2 history courses" –  coffee Aug 20 '11 at 16:36
add comment

You can look at each type of course separately since these choices are (ostensibly) independent. So consider the subproblem of just choosing $k$ courses out of $n$ possibilities: this is denoted ${n \choose k}$ which is defined as $${n \choose k} = \frac{n!}{k!(n-k)!} $$ Here the exclamation mark is "factorial" (look it up if you don't recall the meaning).

Now you can solve your problem: put $n=7$ for 7 math courses, and $k=3$ for the number of math courses you want to pick. $${7 \choose 3}$$ then do the same for the other courses, taking the product as you go: $${7 \choose 3} {4 \choose 2}{4+3 \choose 1} = 35\cdot 6\cdot 7 = 1470$$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.