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'm having a hard time trying to determine when to use combination and when to use permutation with a problem. Can someone offer a clear and concise explanation or general rules to follow so I don't get tripped up on similar problems?

For example: How many ways are there to select five players from a 10-member tennis team.

My approach would be that there are 10 ways to choose the first spot, 9 for the second, 8 for the third... so the total is 10!/5!; but apparently this is a combination problem.

I'm just having a hard time telling the difference between the two. Are there any questions I can ask myself before I begin to really solidify what the problem is asking for?

Thank you!

EDIT:

Here's another problem I'm confused with:

Suppose that there are 9 faculty members in the mathematics department and 11 in the computer science department. How many ways are there to select a committee to develop a discrete mathematics course at a school if the committee is to consist of three faculty members from the mathematics department and four from the computer science department?

Why is the answer 9!/(3!6!) * 11!/(4!7!) rather than 9!/(3!6!) + 11!/(4!7!)?

share|improve this question
    
Here order of selection doesn't matter, only the overall team. There is no first spot, second spot, $\dots$. If you were lining them up in a row there would be. However, things can get complicated. When we are counting the number of words using $4$ A's and $7$ B's (so order matters), the answer is the "combinations symbol" $\binom{11}{4}$. –  André Nicolas Oct 28 '12 at 22:15
add comment

2 Answers

up vote 3 down vote accepted

Regular rule, Permutation is when order matters. You can memorize it with P ermutation-P osition. Combination on the other hand doesn't care in which order the elements are chosen.

As in your first example, you want to choose $5$ players, but no other information is given so you assume order isn't important.

Note that I the problem stated $5$ player to form a hockey team, then order could have mattered, for say center, Left and right wing, and left and right D player.

For your second example, note that for each subcomitee of $3$ members of math, there are $11!/(4!7!)$ subcomitee of members of CS so you have to multiply them

share|improve this answer
add comment

The fundamental question is: Does the order of my choices matter?

In this problem it does not: it’s the same five players whether you select them in the order A, B, C, D, E, the order A, C, D, E, B, or any of the other $118$ possible order. Your calculation, however, counts the selection A, B, C, D, E as different from the selection A, C, D, E, B. In other words, you’ve counted each permutation of $5$ players as a separate selection, when all that is wanted is the number of distinct sets of $5$ players that can be formed.

If, on the other hand, the problem had been to count the number of ways of selecting $5$ of the digits $0,1,\dots,9$ and writing them down to form a $5$-digit number (possibly with a leading $0$), the order would have mattered: the number $24815$ is different from the number $84512$, even though they contain the same digits. Your calculation would have been correct for this problem.

Your second question is about the multiplication (or Chinese menu) principle of counting. You have two choices to make: you must select the members from the math department, and you must select the members from the computer science department. The numbers here are moderately large, so lets look at a similar problem with smaller numbers. Suppose that the committee is to have just two members, one from each department. Let’s also suppose that the math department has only $3$ members and the computer science department only $4$. Make a little table:

$$\begin{array}{r|cc} &C_1&C_2&C_3&C_4\\ \hline M_1&1&2&3&4\\ M_2&5&6&7&8\\ M_3&9&10&11&12 \end{array}$$

Each number in the body of the table represents one way of picking a committee: number $7$ for instance, is the committee $\{M_2,C_3\}$ consisting of mathematician number $2$ and computer scientist number $3$. Clearly there are $12$ possible committees, simply because there are $12$ slots in the table; and there are $12$ slots in the table because it has $3$ rows and $4$ columns, and $3\cdot4=12$.

Now imagine making a similar table for the bigger problem. It would have $\binom93=\frac{9!}{3!6!}$ rows, one for each of the possible sets of $3$ mathematicians, and it would have $\binom{11}4=\frac{11!}{4!7!}$ columns, one for each of the possible sets of $4$ computer scientists. It would therefore have $\binom93\binom{11}4$ slots, each of which would correspond to matching a particular set of $3$ mathematicians with a particular set of $4$ computer scientists.

The general principle is that if you are making a set of $m$ independent choices, and choice number $k$ can be made in $n_k$ different ways, then the whole task can be carried out in $n_1n_2\dots n_m$ different ways. In my simplified committee problem $m=2$, $n_1=3$, and $n_2=4$; in the original committee problem $m=2$, $n_1=\binom93$, and $n_2=\binom{11}4$.

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.