Combinations and Permutations

What'south the Departure?

In English we use the word "combination" loosely, without thinking if the club of things is important. In other words:

in speech

"My fruit salad is a combination of apples, grapes and bananas" We don't intendance what lodge the fruits are in, they could also exist "bananas, grapes and apples" or "grapes, apples and bananas", its the aforementioned fruit salad.

in speech

"The combination to the safety is 472" . Now nosotros practise intendance about the gild. "724" won't piece of work, nor will "247". Information technology has to be exactly four-7-2.

And then, in Mathematics we apply more than precise language:

  • When the order doesn't thing, it is a Combination.
  • When the society does affair information technology is a Permutation.

permutation lock

And then, nosotros should actually call this a "Permutation Lock"!

In other words:

A Permutation is an ordered Combination.


thought To assistance you lot to remember, call up "Permutation ... Position"

Permutations

There are basically ii types of permutation:

  1. Repetition is Immune: such as the lock above. Information technology could be "333".
  2. No Repetition: for instance the offset 3 people in a running race. You can't exist kickoff and second.

1. Permutations with Repetition

These are the easiest to calculate.

When a thing has n unlike types ... nosotros have n choices each time!

For example: choosing 3 of those things, the permutations are:

n × n × n
(northward multiplied three times)

More generally: choosing r of something that has n different types, the permutations are:

n × n × ... (r times)

(In other words, there are n possibilities for the outset pick, And then there are north possibilites for the 2d choice, and so on, multplying each time.)

Which is easier to write down using an exponent of r:

north × n × ... (r times) = nr

Example: in the lock higher up, there are 10 numbers to choose from (0,i,2,3,4,five,6,7,8,9) and we cull 3 of them:

ten × 10 × ... (three times) = 103 = 1,000 permutations

So, the formula is just:

nr
where due north is the number of things to choose from,
and nosotros cull r of them,
repetition is allowed,
and club matters.

2. Permutations without Repetition

In this instance, we have to reduce the number of available choices each time.

pool balls

Case: what order could 16 pool assurance be in?

After choosing, say, number "14" we can't choose it once more.

So, our starting time choice has 16 possibilites, and our side by side choice has 15 possibilities, then xiv, 13, 12, xi, ... etc. And the total permutations are:

sixteen × 15 × fourteen × xiii × ... = twenty,922,789,888,000

Merely perchance nosotros don't desire to choose them all, but 3 of them, and that is and then:

16 × 15 × 14 = 3,360

In other words, there are 3,360 different ways that three pool balls could be arranged out of 16 balls.

Without repetition our choices become reduced each time.

Just how do nosotros write that mathematically? Answer: we utilise the "factorial function"

!

The factorial office (symbol: ! ) just means to multiply a series of descending natural numbers. Examples:

  • 4! = 4 × 3 × 2 × 1 = 24
  • 7! = seven × half dozen × 5 × 4 × iii × 2 × 1 = 5,040
  • ane! = 1
Annotation: it is generally agreed that 0! = one. It may seem funny that multiplying no numbers together gets united states of america ane, but it helps simplify a lot of equations.

And then, when nosotros want to select all of the billiard assurance the permutations are:

16! = 20,922,789,888,000

But when nosotros desire to select just three we don't desire to multiply after 14. How do nosotros do that? There is a not bad trick: we divide past xiii!

sixteen × 15 × 14 × 13 × 12 × ... 13 × 12 × ...   =  16 × xv × xiv

That was neat: the 13 × 12 × ... etc gets "cancelled out", leaving only 16 × 15 × xiv.

The formula is written:

n! (n − r)!

where n is the number of things to cull from,
and we choose r of them,
no repetitions,
guild matters.

Example Our "order of 3 out of 16 puddle balls example" is:

16! (16−iii)! = sixteen! xiii! = 20,922,789,888,000 6,227,020,800 = 3,360

(which is just the same every bit: 16 × 15 × 14 = 3,360)

Example: How many ways can beginning and second place be awarded to ten people?

10! (10−2)! = 10! 8! = 3,628,800 40,320 = 90

(which is just the same as: x × ix = 90)

Notation

Instead of writing the whole formula, people employ different notations such as these:

P(n,r) = northwardPr = northPr = northward! (due north−r)!

Examples:

  • P(10,2) = 90
  • tenP2 = 90
  • 10Pii = xc

Combinations

There are besides two types of combinations (think the order does not matter at present):

  1. Repetition is Allowed: such as coins in your pocket (5,v,5,x,10)
  2. No Repetition: such as lottery numbers (2,14,15,27,30,33)

ane. Combinations with Repetition

Really, these are the hardest to explicate, and then we volition come back to this later.

2. Combinations without Repetition

This is how lotteries work. The numbers are drawn ane at a fourth dimension, and if nosotros have the lucky numbers (no thing what order) we win!

The easiest way to explain it is to:

  • assume that the guild does thing (ie permutations),
  • and then alter information technology so the order does non thing.

Going dorsum to our puddle ball example, let's say nosotros merely want to know which 3 pool balls are called, not the lodge.

Nosotros already know that 3 out of 16 gave the states 3,360 permutations.

Merely many of those are the same to united states of america now, because nosotros don't care what gild!

For instance, allow u.s. say balls 1, ii and iii are called. These are the possibilites:

Lodge does matter Society doesn't thing
ane 2 3
1 3 ii
2 one 3
2 3 1
3 1 ii
3 2 one		 one two iii

So, the permutations have 6 times every bit many possibilites.

In fact there is an easy way to work out how many means "i ii three" could be placed in order, and nosotros take already talked about it. The answer is:

3! = iii × 2 × i = half-dozen

(Another case: 4 things tin can be placed in 4! = four × 3 × two × 1 = 24 dissimilar ways, try it for yourself!)

So we adjust our permutations formula to reduce it by how many ways the objects could be in order (because we aren't interested in their lodge any more):

n! (n−r)! 10 one r! = n! r!(n−r)!

That formula is and so important it is often only written in big parentheses like this:

n! r!(n−r)! = ( n r )

where n is the number of things to choose from,
and we cull r of them,
no repetition,
order doesn't matter.

It is often called "due north choose r" (such as "xvi choose 3")

And is likewise known as the Binomial Coefficient.

Note

All these notations mean "n choose r":

C(due north,r) = northwardCr = nCr = ( n r ) = n! r!(n−r)!

Only call up the formula:

n! r!(north − r)!

Instance: Puddle Balls (without order)

So, our pool brawl example (now without order) is:

16! 3!(sixteen−3)!

= 16! 3! × thirteen!

= xx,922,789,888,000 half-dozen × 6,227,020,800

= 560

Notice the formula 16! 3! × 13! gives the same answer as xvi! thirteen! × 3!

And so choosing 3 balls out of 16, or choosing xiii assurance out of 16, have the same number of combinations:

16! 3!(16−3)! = sixteen! 13!(16−13)! = 16! 3! × 13! = 560

In fact the formula is nice and symmetrical:

due north! r!(n−r)! = ( n r ) = ( due north n−r )

Also, knowing that 16!/13! reduces to 16×15×14, we can salve lots of calculation past doing it this way:

sixteen×15×14 3×two×one

= 3360 6

= 560

Pascal's Triangle

We can as well employ Pascal's Triangle to find the values. Go downwards to row "northward" (the top row is 0), and then along "r" places and the value in that location is our answer. Here is an extract showing row 16:

ane 14 91 364 ...
1 xv 105 455 1365 ...
1 xvi 120 560 1820 4368 ...

1. Combinations with Repetition

OK, now nosotros can tackle this one ...

ice cream

Permit us say there are five flavors of icecream: assistant, chocolate, lemon, strawberry and vanilla.

We can take three scoops. How many variations will in that location exist?

Permit's use letters for the flavors: {b, c, fifty, southward, v}. Example selections include

  • {c, c, c} (3 scoops of chocolate)
  • {b, l, v} (one each of assistant, lemon and vanilla)
  • {b, five, 5} (ane of banana, 2 of vanilla)

(And just to be clear: There are n=5 things to choose from, we cull r=3 of them,
order does not matter, and nosotros can repeat!)

Now, I tin can't draw direct to you how to summate this, but I tin can prove yous a special technique that lets you work it out.

bclsv

Think nigh the ice cream being in boxes, we could say "movement past the first box, then take 3 scoops, then movement along three more boxes to the finish" and nosotros will have 3 scoops of chocolate!

So information technology is similar we are ordering a robot to get our ice cream, but information technology doesn't change anything, nosotros still go what we desire.

We can write this downwardly as acccaaa (pointer means move, circumvolve means scoop).

In fact the three examples to a higher place can be written like this:

And then instead of worrying about dissimilar flavors, we have a simpler question: "how many unlike ways can we adjust arrows and circles?"

Notice that there are ever 3 circles (3 scoops of ice cream) and 4 arrows (nosotros need to move 4 times to get from the 1st to 5th container).

So (being general here) there are r + (northward−i) positions, and we want to choose r of them to have circles.

This is like saying "we have r + (north−1) pool balls and desire to cull r of them". In other words information technology is now similar the pool balls question, but with slightly changed numbers. And nosotros tin write it like this:

(r + n − 1)! r!(due north − one)! = ( r + n − i r )

where north is the number of things to choose from,
and nosotros choose r of them
repetition allowed,
order doesn't matter.

Interestingly, we can look at the arrows instead of the circles, and say "we accept r + (n−1) positions and desire to choose (n−1) of them to take arrows", and the respond is the aforementioned:

(r + n − ane)! r!(due north − 1)! = ( r + n − 1 r ) = ( r + n − 1 n − 1 )

Then, what about our instance, what is the respond?

(three+5−1)! 3!(5−1)! = seven! three!4! = 5040 6×24 = 35

At that place are 35 means of having iii scoops from 5 flavors of icecream.

In Conclusion

Phew, that was a lot to absorb, so mayhap you could read information technology again to be sure!

Merely knowing how these formulas work is only one-half the battle. Figuring out how to interpret a real world situation can be quite hard.

But at least you now know the 4 variations of "Lodge does/does not thing" and "Repeats are/are not allowed":


 Repeats allowed No Repeats
Permutations (order matters): due northr due north! (n − r)!
Combinations (order doesn't matter): (r + north − 1)! r!(northward − one)! north! r!(due north − r)!

708, 1482, 709, 1483, 747, 1484, 748, 749, 1485, 750