10
$\begingroup$

How do you distinguish combination and permutation question?

An example of a combination question:

Example: How many different committees of 4 students can be chosen from a group of 15?

Answer: There are possible combinations of 4 students from a set of 15.

There are 1365 different committees.

An example of a permutation question:

Example: How many ways can 4 students from a group of 15 be lined up for a photograph?

Answer: There are 15P4 possible permutations of 4 students from a group of 15. These are different lineups.

How to know in which case to use $nCm$ and in which $nPm$?

$\endgroup$
  • $\begingroup$ this is the real specific question. $\endgroup$ – guest11 Nov 7 '15 at 5:30
  • 3
    $\begingroup$ Maybe don't read this. How many strings of $0$'s and/or $1$'s of length $10$ have exactly three $0$'s? Order in the string matters, but we solve the problem using combinations. The number of strings is the number of ways to choose where the $0$'s will go. There are ${}_{10}C_3$ ways to do it. $\endgroup$ – André Nicolas Nov 7 '15 at 5:53
  • $\begingroup$ If you are making selection of things then it is permutation while if you are making arrangments then it is combination. Does this make sense . $\endgroup$ – Archis Welankar Nov 7 '15 at 6:16
  • $\begingroup$ yes it makes sense. Thank you ^^ $\endgroup$ – guest11 Nov 7 '15 at 6:27
7
$\begingroup$

Example: How many different committees of 4 students can be chosen from a group of 15? Answer: There are possible combinations of 4 students from a set of 15.

In your first example you are choosing slots for each student to occupy, but you don't care which order the students make in each slot. You only care about the combination.

Example: How many ways can 4 students from a group of 15 be lined up for a photograph? Answer: There are 15P4 possible permutations of 4 students from a group of 15.

In permutations the order of the objects matters. If the objects are indistinguishable then it is a combinations problem.

In your second example you can distinguish one student from another; therefore it is permutations problem, so switching the order of the students in the line will affect the way the photograph looks.

To tell the difference you look at the 'object' in question and ask yourself is it distinguishable or not in the context of the question.

$\endgroup$
7
+100
$\begingroup$

${}_nC_r$ is the number of ways of selecting $r$ items from a set of $n$ items.

${}_nP_r$ is the number of ways of selecting $r$ items from a set of $n$ items and arranging the $r$ selected items in all possible orders.

In brief, combinations are used when you are selecting only; permutations are used when you are selecting and arranging.

It is often said that combinations are used when order doesn't matter and that permutations are used when order matters, but this can be misleading. By "order matters", people probably mean that different orders are distinguishable, which is important, but not the only issue. The other important issue is whether all possible orders are allowed.

If, in selecting $r$ items from $n$, different orders are distinguishable and all possible orders are allowed, then ${}_nP_r$ is appropriate. If, in selecting $r$ items from $n$, either different orders are not distinguishable or only only one order is allowed, then ${}_nC_r$ would be appropriate.

Here are some examples.

  1. How many ways can 4 students from a group of 15 be lined up for a photograph? Answer: to find all possible lineups, you have to find all possible selections, and for each selection, you have to find all possible ways of lining up the selected students. Different lineups are distinguishable and all possible lineups can occur. So there are ${}_{15}P_4$ lineups.
  2. How many ways can 4 students from a group of 15 be lined up for a photograph in order by age, with oldest on the left and youngest on the right? Answer: to find all possible lineups, you have to find all possible selections. Different lineups are distinguishable, but only one lineup is allowed. Once you determine the selection selection, the lineup is forced, since it is according to age. Hence there are ${}_{15}C_4$ lineups.
  3. How many different committees of four students can be chosen from a group of 15? Answer: committees are defined only by their membership, so different orders of the selected committee members are not distinguishable. Hence there are ${}_{15}C_4$ committees.
  4. There are three E Scrabble tiles and four S Scrabble tiles. In how many ways can all of the tiles be placed side-by-side along a straight line? Answer: physical pieces of wood are distinguishable, and so different placements of them are distinguishable. Futhermore all possible placements are possible. Hence there are ${}_7P_7=7!$ placements.
  5. How many different "words" can be spelled using the letter E three times and the letter S four times, where any sequence of letters counts as a word? Answer: a word is distinguished by the sequence of letters, that is, the order, but is not tied to the placement of any physical artifacts. Different sequences of Es and Ss are distinguishable, but the result of permuting only the Es or only the Ss in a particular sequence does not give a distinguishable result. So different orders within the subsequence of Es or within the subsequence of Ss are not distinguishable. Hence there are $$\frac{{}_7P_7}{{}_3P_3\,{}_4P_4}=\frac{7!}{3!\,4!}$$ words. This answer equals ${}_7C_4$, which can be understood as follows: to specify a word, you need only state which four letter positions among the 7 contain Ss, with the understanding that every other position contains an E. A set of four letter positions is distinguished only by its elements, and not by the order in which they are listed. So having Ss in positions 2, 3, 5, and 7 is indistinguishable from having Ss in positions 5, 3, 7, and 2. In other words, different orders of the four S positions are not distinguishable. Hence there are ${}_7C_4$ words.
$\endgroup$
  • 1
    $\begingroup$ Did you mean ${}_7C_4$, which equals 35, or ${}_7C_7$, which equals 1? I will assume you meant ${}_7C_4$, which is the same as the answer to my fifth example. If you were to ask for the number of words that could be spelled with the seven Scrabble tiles, then examples 4 and 5 would be asking the same thing, and would have the same answer. But I was assuming in example 4 that the question was concerned with the arrangement of physical pieces of wood, which are distinguishable no matter whether they have the same letter written on them or not. $\endgroup$ – Will Orrick Nov 23 '15 at 11:34
  • 1
    $\begingroup$ This physical distinguishability can make a difference in applications. Consider this example: you have 100 Scrabble tiles, 2 with the letter E and 98 with the letter S. The number of two-letter words that can be spelled with these tiles is $2^2=4$, but the number of ways of lining up two of the tiles is ${}_{100}P_2=9900$. If two tiles are selected at random and placed side-by-side,the probability that they spell EE is ${}_2P_2/{}_{100}P_2=1/4950$. If instead, there... $\endgroup$ – Will Orrick Nov 23 '15 at 12:00
  • 1
    $\begingroup$ ...are 4 tiles, 2 with E and 2 with S, then there are still $2^2=4$ words that can be spelled, but now there are ${}_4P_2=12$ ways to line up 2 tiles, and the probability that the tiles spell EE is now ${}_2P_2/{}_4P_2=1/6$. $\endgroup$ – Will Orrick Nov 23 '15 at 12:01
  • 1
    $\begingroup$ Indistinguishability does occur in the physical world, in the realm of quantum mechanics. Its effects are profound and, at first sight, strange. The phenomenon of Bose-Einstein condensation is a consequence of indistinguishability. See the Wikipedia article. $\endgroup$ – Will Orrick Nov 23 '15 at 12:51
  • 1
    $\begingroup$ @BLAZE: I downvoted all the answers in this thread that attempt to prescribe a not completely mathematically correct way to determine whether to use P or C. That included one of your answers but not the other one. I strongly disagree with prescribing what to do, since it does not in any way foster understanding. $\endgroup$ – user21820 Nov 27 '15 at 10:14
5
$\begingroup$

In general whenever the position matters, the question is a permutation question. For example when (A,B) and (B,A) are different, it is a permutation question.

And whenever the position does not matter, it is a combination question. For example (A,B) is the same as (B,A).

Example :

1) In how many ways can we select 2 students from three students A,B,C?

Answer = $^3C_2 = \frac{3!}{2!\times(3-2)!} = 3$

This is a combination question because we can select in three ways as follows : (A,B) , (B,C) , (C,A). See here, when (A,B) is selected , it is the same as (B,A).

2) In how many ways can 2 students be lined in a row, out of a total of 3 students A,B,C ?

Answer = $^3 P_2 = \frac{3!}{(3-2)!} = 6$

This is a permutation question because there are six ways as follows: (A,B) , (B,A) , (B,C) , (C,B) , (A,C) , (C,A). Note that now (A,B) and (B,A) are different as in (A,B) , A gets the first position in the row and B gets the second position in the row. While in (B,A) , B gets the first position in the row and A gets the second position. Hence we have to count them as separate possibilities, unlike in the previous example.

$\endgroup$
  • $\begingroup$ thank you! this makes it clear! :) $\endgroup$ – guest11 Nov 7 '15 at 6:24
  • $\begingroup$ but the first question how many ways you will get? why do I get 1 when I use the fomula? $\endgroup$ – guest11 Nov 7 '15 at 6:26
  • $\begingroup$ Please be specific , for which question do you get 1 as the answer ? $\endgroup$ – user180000 Nov 7 '15 at 8:09
  • $\begingroup$ C(3,2) and follow by the formula ... $\endgroup$ – guest11 Nov 7 '15 at 8:50
4
$\begingroup$

Permutations are used when order matters.

Combinations are used when order doesn't matter.

$\endgroup$
  • $\begingroup$ but the question did not ask directly? how do I know? will there questions ever ask directly? $\endgroup$ – guest11 Nov 7 '15 at 5:36
  • 1
    $\begingroup$ It won't tell you directly to use a permutation or combination. You have to determine whether order is relevant in your problem. For example, if you are looking for "combinations" to a lock, this is in fact a misnomer! You are actually looking for permutations since the order of the numbers matters to open up the "combination lock". $\endgroup$ – Levonne Daruiche Nov 7 '15 at 5:38
1
$\begingroup$

Here is another interpretation for the difference between combinations (choosing) and permutations (arrangements):

Suppose you were asked to arrange $3$ books from $5$ different books in a line:

So you first $\color{red}{\mathrm{choose}}$ $3$ books from the possible $5$ and then you $\color{blue}{\mathrm{arrange}}$ them.

Therefore; the distinction goes as follows:

A Permutation is choosing the objects and then arranging them.

A Combination is choosing the objects and not arranging them.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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