Combinations and Permutations

What's the Difference?

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

in speech

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

in speech

"The combination to the rubber is 472" . At present we do care near the lodge. "724" won't work, nor will "247". It has to be exactly 4-7-ii.

So, in Mathematics we apply more precise linguistic communication:

  • When the order doesn't thing, it is a Combination.
  • When the order does matter it is a Permutation.

permutation lock

So, we should actually call this a "Permutation Lock"!

In other words:

A Permutation is an ordered Combination.


thought To help you lot to retrieve, think "Permutation ... Position"

Permutations

There are basically 2 types of permutation:

  1. Repetition is Allowed: such as the lock in a higher place. Information technology could be "333".
  2. No Repetition: for example the first 3 people in a running race. You can't be first and second.

1. Permutations with Repetition

These are the easiest to calculate.

When a thing has north different types ... we have n choices each time!

For case: choosing iii of those things, the permutations are:

n × northward × n
(n multiplied 3 times)

More more often than not: choosing r of something that has n unlike types, the permutations are:

north × n × ... (r times)

(In other words, there are n possibilities for the starting time option, Then there are n possibilites for the 2nd choice, and and then on, multplying each time.)

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

northward × northward × ... (r times) = nr

Instance: in the lock above, there are 10 numbers to choose from (0,ane,ii,3,4,v,six,7,8,ix) and we cull 3 of them:

10 × ten × ... (3 times) = 103 = i,000 permutations

And then, the formula is but:

nr
where n is the number of things to choose from,
and we choose r of them,
repetition is allowed,
and lodge matters.

2. Permutations without Repetition

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

pool balls

Example: what order could 16 pool balls be in?

Afterwards choosing, say, number "14" we tin't choose information technology over again.

So, our first selection has 16 possibilites, and our adjacent choice has 15 possibilities, so 14, thirteen, 12, eleven, ... etc. And the total permutations are:

16 × 15 × 14 × 13 × ... = 20,922,789,888,000

Merely perhaps we don't want to cull them all, just 3 of them, and that is then:

sixteen × 15 × fourteen = 3,360

In other words, in that location are 3,360 dissimilar ways that three puddle balls could be arranged out of 16 assurance.

Without repetition our choices get reduced each time.

But how exercise we write that mathematically? Answer: we apply the "factorial function"

!

The factorial function (symbol: ! ) simply means to multiply a serial of descending natural numbers. Examples:

  • 4! = 4 × three × ii × 1 = 24
  • seven! = seven × 6 × five × four × 3 × two × 1 = v,040
  • 1! = i
Note: it is generally agreed that 0! = 1. It may seem funny that multiplying no numbers together gets united states of america 1, simply it helps simplify a lot of equations.

So, when we want to select all of the billiard balls the permutations are:

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

But when we want to select merely iii nosotros don't desire to multiply afterwards 14. How do we practise that? There is a neat fob: we divide by 13!

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

That was neat: the 13 × 12 × ... etc gets "cancelled out", leaving merely sixteen × fifteen × xiv.

The formula is written:

n! (n − r)!

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

Example Our "lodge of 3 out of xvi puddle balls case" is:

16! (16−three)! = 16! 13! = 20,922,789,888,000 half-dozen,227,020,800 = 3,360

(which is just the same equally: 16 × 15 × 14 = iii,360)

Example: How many ways tin get-go and second place be awarded to 10 people?

10! (10−2)! = 10! 8! = 3,628,800 xl,320 = ninety

(which is but the same equally: 10 × 9 = 90)

Annotation

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

P(n,r) = nPr = nPr = north! (n−r)!

Examples:

  • P(ten,ii) = 90
  • xP2 = ninety
  • xPtwo = 90

Combinations

There are also two types of combinations (remember the order does not matter now):

  1. Repetition is Allowed: such as coins in your pocket (5,5,5,10,10)
  2. No Repetition: such every bit lottery numbers (2,xiv,fifteen,27,thirty,33)

1. Combinations with Repetition

Actually, these are the hardest to explain, so nosotros volition come up back to this later.

2. Combinations without Repetition

This is how lotteries work. The numbers are drawn one at a time, and if we take the lucky numbers (no matter what order) nosotros win!

The easiest way to explain it is to:

  • assume that the social club does thing (ie permutations),
  • then alter it and then the lodge does not affair.

Going back to our puddle ball example, let'due south say we just want to know which 3 pool balls are chosen, not the social club.

We already know that 3 out of 16 gave us 3,360 permutations.

Merely many of those are the same to united states now, because we don't care what lodge!

For example, let united states say balls one, 2 and 3 are chosen. These are the possibilites:

Order does matter Order doesn't thing
ane 2 three
ane 3 ii
2 1 3
2 three 1
3 one 2
three two 1
1 2 three

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

In fact at that place is an like shooting fish in a barrel way to work out how many means "1 2 3" could be placed in order, and nosotros accept already talked about it. The respond is:

3! = 3 × 2 × 1 = 6

(Some other case: 4 things can exist placed in 4! = 4 × 3 × two × i = 24 different ways, try information technology for yourself!)

And so we adapt our permutations formula to reduce it by how many means the objects could be in order (because we aren't interested in their order any more):

n! (n−r)! x 1 r! = n! r!(n−r)!

That formula is so important information technology is oftentimes only written in big parentheses like this:

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

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

It is often called "n choose r" (such every bit "16 cull three")

And is also known as the Binomial Coefficient.

Notation

All these notations mean "n choose r":

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

But remember the formula:

north! r!(due north − r)!

Example: Pool Assurance (without order)

Then, our pool brawl case (now without society) is:

sixteen! iii!(16−3)!

= 16! three! × thirteen!

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

= 560

Notice the formula 16! 3! × 13! gives the aforementioned answer every bit 16! 13! × 3!

So choosing 3 balls out of sixteen, or choosing 13 assurance out of 16, have the same number of combinations:

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

In fact the formula is nice and symmetrical:

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

Besides, knowing that xvi!/13! reduces to 16×15×fourteen, nosotros can salve lots of calculation past doing it this way:

sixteen×15×14 3×2×1

= 3360 vi

= 560

Pascal's Triangle

We can also use Pascal's Triangle to observe the values. Become down to row "northward" (the pinnacle row is 0), and so along "r" places and the value in that location is our answer. Hither is an extract showing row sixteen:

1 14 91 364 ...
1 15 105 455 1365 ...
one 16 120 560 1820 4368 ...

1. Combinations with Repetition

OK, now we can tackle this one ...

ice cream

Let united states say there are five flavors of icecream: banana, chocolate, lemon, strawberry and vanilla.

We tin can accept three scoops. How many variations volition at that place be?

Let's use letters for the flavors: {b, c, 50, due south, v}. Example selections include

  • {c, c, c} (three scoops of chocolate)
  • {b, 50, v} (one each of banana, lemon and vanilla)
  • {b, 5, 5} (one of assistant, ii of vanilla)

(And only to be clear: There are northward=5 things to choose from, we choose r=3 of them,
order does not matter, and we can echo!)

Now, I can't describe directly to y'all how to summate this, but I tin bear witness you a special technique that lets you work it out.

bclsv

Think near the water ice cream being in boxes, we could say "movement by the first box, and then take 3 scoops, then movement along iii more than boxes to the stop" and we will have 3 scoops of chocolate!

So it is like we are ordering a robot to become our ice foam, but it doesn't modify anything, we still get what we want.

We tin can write this down as acccaaa (arrow means move, circle ways scoop).

In fact the three examples above can exist written like this:

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

Notice that there are ever iii circles (3 scoops of water ice foam) and 4 arrows (nosotros demand to movement 4 times to go from the 1st to 5th container).

So (being general here) there are r + (north−one) positions, and we want to cull r of them to have circles.

This is like maxim "we have r + (north−i) pool balls and want to cull r of them". In other words it is at present similar the pool assurance question, only with slightly changed numbers. And we can write information technology like this:

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

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

Interestingly, nosotros can await at the arrows instead of the circles, and say "we have r + (northward−ane) positions and want to choose (north−1) of them to have arrows", and the answer is the same:

(r + n − ane)! r!(n − ane)! = ( r + n − 1 r ) = ( r + n − i n − 1 )

So, what nigh our case, what is the answer?

(three+5−1)! 3!(5−ane)! = 7! 3!four! = 5040 six×24 = 35

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

In Determination

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

Simply knowing how these formulas piece of work is just half the boxing. Figuring out how to interpret a existent world situation can be quite difficult.

But at to the lowest degree you now know the 4 variations of "Order does/does not matter" and "Repeats are/are not allowed":


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

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