0
$\begingroup$

I am new to permutation and combination and am looking for guidance in the following example:

We have 3 people - A, B, C

How many ways are there to arrange them into Rank 1,2,3

Looking at the example, it is clear that No repetitions are allowed and that ordering is not important (in the sense - Rank 1 - A, Rank 2 - B, Rank 3 - C is the same as Rank 2 - B, Rank 3 - C, Rank 1 - A).

So as a permutation problem we have answer as 3! = 6

Where as a variation problem we have the answer as 3!/0! = 3! = 6 (but if ordering is not important then it would be 3^3 = 27)

Please can you help me understand how me decide between Permutation or variation? and whether ordering is important or not?

$\endgroup$
15
  • 3
    $\begingroup$ I don't understand the question. If no repetitions are allowed then it's just $3!$, as you say. $3$ choices for the first rank, then $2$ for the second, and then the third is determined. If you allow repetitions you get a completely different problem. $\endgroup$
    – lulu
    Jul 3, 2019 at 12:59
  • 3
    $\begingroup$ "Where as a variation problem" What is a "variation" problem in this context? $\endgroup$
    – JMoravitz
    Jul 3, 2019 at 13:01
  • 1
    $\begingroup$ I still don't understand. If "No repetitions are allowed and [that ]ordering is not important." then the answer is obviously $1$. $\endgroup$
    – lulu
    Jul 3, 2019 at 13:02
  • 2
    $\begingroup$ Every permutation problem is a variation problem with $p=n$. In fact, there is no need for the term variation (which is why mathematicians who study combinatorics use only the term permutation and do not have a separate term, variation. $\endgroup$ Jul 3, 2019 at 13:07
  • 3
    $\begingroup$ The end result, is that you can choose whatever naming, whatever semantics, and whatever description you like to solve any problem, so long as your choice is consistent and you can adequately and properly describe your problem using those things. A word of advice... completely ignore "permutation problem" and "variation problem" and instead just use the rule of product which is far more fundamental and use binomial coefficients. $\endgroup$
    – JMoravitz
    Jul 3, 2019 at 13:08

2 Answers 2

3
$\begingroup$

To arrange $n$ items in a row (which can be accomplished in $n!$ ways) is equivalent to picking $k$ of $n$ items to arrange in a row (which can be accomplished in $\frac{n!}{(n-k)!}$ ways) in the case that $k=n$.

The only difference between them is semantics and that the formula for "variations" that you refer to is simply for the more generalized case where we might choose to arrange only some of but not all of our items into a row.


It helps to keep an example in the back of your mind on what exactly each of these formula count. For example, given the set $\{a,b,c,d\}$:

  • the calculation $4!$ here can be in reference to the number of arrangements of all letters where order of letters matters and letters may not be repeated, every letter appearing exactly once each. Such an arrangement can be thought of as a permutation. Examples of things being counted here would be abcd, abdc, acbd, acdb, ...

  • the calculation $\frac{4!}{(4-2)!}$ here can be in reference to the number of arrangements of only two of the letters where order of letters matters and letters may not be repeated, each letter appearing at most once each. In your terminology, this would be a "variation." Examples of things being counted here would be ab, ac, ad, ba, bc, ... Note how ab and ba are treated as being different.

  • the calculation $\binom{4}{2}=\frac{4!}{2!(4-2)!}$ here can be in reference to the number of combinations of two of the letters where here order of letters does not matter, letters may not be repeated, each letter appearing at most once each. Perhaps more correctly described, it counts the number of subsets of size two of the set $\{a,b,c,d\}$. Examples of things being counted here would be $\{a,b\}, \{a,c\}, \{b,c\},\dots$. Note here that $\{a,b\}$ is treated as being the same as $\{b,a\}$ since these are equal sets.

$\endgroup$
5
  • $\begingroup$ Please can you also advise how we can know if order is important or not. In my question (ranking problem), is the order important or not? $\endgroup$
    – variable
    Jul 3, 2019 at 13:29
  • 1
    $\begingroup$ @variable it should be readily apparent given the context of the problem. If you have 100 atheletes from different countries competing in the olympics and you ask how many ways you can give out gold, silver, and bronze to the top three atheletes... the outcome where China wins gold, Russia wins Silver and America wins Bronze is obviously a different outcome than the one where America is the one who won Gold, China winning Silver, and Russia winning Bronze. We know it is different because the experience of the athelete changes, coming home with a gold medal is better than with a bronze. $\endgroup$
    – JMoravitz
    Jul 3, 2019 at 13:40
  • $\begingroup$ The way I am thinking is that - the outcome - China wins gold, Russia wins Silver and America wins Bronze - will be the same irrespective of how this ordered. So it is same as - America wins Bronze, China wins gold, Russia wins Silver. Sorry I am new so any information in the right direction will be helpful. $\endgroup$
    – variable
    Jul 3, 2019 at 13:42
  • 1
    $\begingroup$ You are misunderstanding what is being ordered here. To make it clearer... we are filling in the blanks of the following "Winners List." Person who wins gold ________, Person who wins silver ________, Person who wins bronze ________. Our "winners list" will always be written in this order and never in any other order. What actually matters here and what changes is who receives what medal. It doesn't actually matter to us in what order this information is displayed. $\endgroup$
    – JMoravitz
    Jul 3, 2019 at 13:43
  • $\begingroup$ Thanks - I was clear so far that a problem of having group of friends is a combination problem (order is not important) and password is a permutation problem (order is important). I will keep reading your answer over and over again till it makes clear sense. I think I need to understand the context more. $\endgroup$
    – variable
    Jul 3, 2019 at 13:46
2
$\begingroup$

A permutation asks how many ways there are to permute, or order, some number of elements from a larger set of elements. For instance, suppose you're organizing a photo with family members. Only $5$ of them will fit in the photo, but you have $9$ family members present. Then how many ways are there to take this photo, if you care about the order they're in? Well, imagine we're filling the $5$ photo slots from left to right. For the very first slot, we have $9$ options, from all the family members. Now for the second slot, we have $8$ options; the next we have $7$, then $6$, and the last slot has $5$ options to fill with. This means we must have $9\cdot8\cdot7\cdot6\cdot5$ ways to take the picture. In basic combinatorics, this is denoted the permutation, $P(n,k)$, and is the number of ways to permute $k$ objects from a group of $n$:

$$ P(n,k)=n\cdot(n-1)\cdot(n-2)\cdots(n-k+1)=\frac{n!}{(n-k)!} $$

A combination asks how many ways there are to combine elements from a larger group, not including order. For this, we can use our friend, the permutation. Imagine the same situation, lining $k$ of your $n$ family members up for a photo, but this time you don't care about order. There are $P(n,k)$ ways to do it including order; for each group of $k$ family members, there are $k!$ ways to put them in order. Thus, we want to know the muber of ways to choose family members in order divided by the number of ways to order them, which leaves us with simply the number of ways to choose them. This is the combination $C(n,k)$, or more often denoted $n\choose k$:

$$ C(n,k)= {n\choose k} = \frac{P(n,k)}{k!} = \frac{n!}{k!(n-k)!} $$

To return to your initial question: suppose we have people $A,B,C$, and want to arrange them into ranks $1,2,3$. Ordering is actually important here - to see this imagine the ranks are places in an Olympic race. Clearly $A→1,B→2,C→3$ is different from $C→1,A→2,B→3$, as $C$ and their team might argue very strongly! In this case, we have $3$ options for picking rank $1$. We then have $2$ options for rank $2$, and then only $1$ option for the final rank. This gives us $3\cdot2\cdot1=3!$ ways to do it; this is a permutation in disguise, as we are arranging $3$ objects from a pool of $3$, which there is $P(3,3)$ ways to do. And if we check we find that $P(3,3)=\frac{3!}{(3-3)!}=\frac{3!}{0!}=3!$ - exactly the result we were looking for!

The $3^3=27$ answer comes in a slightly different variation which involves neither permutations or combinations. This occurs when you allow replacement of the objects! Imagine you're pulling names from a hat, but every time you pull a name and read it, you put it back. How many ways are there to pull the names? Say we have $3$ names. For the first name we pull, we have $3$ possible names to pull. But since we put it back, on the next draw we also have $3$ possibilities! Thus, if we draw $k$ times, we have $3^k$ ways to pull the names. Applied to your problem, imagine a variation in which instead of ranks we were giving $A,B,$ and $C$ awards. If we can give multiple awards to each person, we have replacement. With $3$ people and $3$ awards, there would be $3^3=27$ ways to give these awards to the people.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .