Combinations and Permutations

What's the Difference?

In English we use the give-and-take "combination" loosely, without thinking if the social club of things is important. In other words:

in speech

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

in speech

"The combination to the safe is 472" . Now nosotros practise care about the guild. "724" won't work, nor will "247". Information technology has to be exactly 4-7-2.

So, in Mathematics we use more precise language:

  • When the society doesn't matter, it is a Combination.
  • When the order does thing it 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 help you to remember, think "Permutation ... Position"

Permutations

There are basically two types of permutation:

  1. Repetition is Allowed: such as the lock above. It could exist "333".
  2. No Repetition: for example the showtime three 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 take n choices each fourth dimension!

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

n × north × n
(north multiplied 3 times)

More mostly: choosing r of something that has northward unlike types, the permutations are:

n × northward × ... (r times)

(In other words, there are north possibilities for the first choice, Then there are n possibilites for the second choice, and and then on, multplying each fourth dimension.)

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

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

Instance: in the lock in a higher place, there are 10 numbers to choose from (0,1,two,iii,four,5,half-dozen,7,8,nine) and nosotros choose three of them:

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

So, the formula is simply:

nr
where northward is the number of things to cull from,
and we choose r of them,
repetition is allowed,
and guild matters.

2. Permutations without Repetition

In this case, we have to reduce the number of bachelor choices each time.

pool balls

Case: what order could xvi pool balls be in?

After choosing, say, number "14" nosotros tin can't cull it once again.

Then, our first choice has 16 possibilites, and our next choice has 15 possibilities, and then 14, 13, 12, xi, ... etc. And the total permutations are:

16 × fifteen × 14 × xiii × ... = 20,922,789,888,000

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

xvi × 15 × 14 = 3,360

In other words, there are 3,360 different means that 3 pool balls could be arranged out of sixteen balls.

Without repetition our choices get reduced each time.

But how do we write that mathematically? Answer: we use the "factorial function"

!

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

  • 4! = 4 × 3 × 2 × i = 24
  • 7! = 7 × 6 × five × 4 × iii × 2 × 1 = 5,040
  • 1! = 1
Note: it is more often than not agreed that 0! = 1. It may seem funny that multiplying no numbers together gets us 1, only 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

Only when we desire to select just 3 nosotros don't desire to multiply later 14. How practice nosotros do that? At that place is a swell trick: nosotros divide by 13!

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

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

The formula is written:

n! (due north − r)!

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

Case Our "gild of 3 out of 16 pool balls example" is:

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

(which is just the same as: sixteen × 15 × fourteen = 3,360)

Example: How many ways can first and second identify be awarded to x people?

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

(which is just the same every bit: 10 × 9 = 90)

Notation

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

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

Examples:

  • P(10,2) = 90
  • 10P2 = 90
  • 10P2 = 90

Combinations

There are likewise two types of combinations (remember the social club does not matter at present):

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

ane. Combinations with Repetition

Actually, these are the hardest to explain, and so we will come back to this later.

2. Combinations without Repetition

This is how lotteries work. The numbers are drawn one at a time, and if we have the lucky numbers (no thing what club) we win!

The easiest way to explain it is to:

  • assume that the lodge does matter (ie permutations),
  • then alter information technology so the order does non matter.

Going back to our puddle ball case, let's say we just want to know which 3 pool balls are chosen, not the order.

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

But many of those are the same to the states now, because we don't care what order!

For instance, let us say assurance 1, 2 and 3 are chosen. These are the possibilites:

Order does matter Guild doesn't matter
one 2 3
1 3 2
two 1 3
2 3 one
3 i 2
3 2 one		 1 two iii

So, the permutations accept half-dozen times as many possibilites.

In fact there is an like shooting fish in a barrel way to piece of work out how many ways "i 2 iii" could be placed in guild, and we accept already talked near it. The answer is:

iii! = three × two × 1 = 6

(Another example: 4 things tin be placed in 4! = 4 × 3 × 2 × i = 24 different ways, endeavour it for yourself!)

And so nosotros adjust our permutations formula to reduce information technology by how many ways the objects could be in order (because we aren't interested in their order any more than):

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

That formula is so of import it is often just written in big parentheses like this:

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

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

It is often called "northward choose r" (such equally "xvi choose 3")

And is too known as the Binomial Coefficient.

Annotation

All these notations hateful "n choose r":

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

Just remember the formula:

n! r!(n − r)!

Example: Puddle Balls (without gild)

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

16! 3!(16−iii)!

= xvi! 3! × xiii!

= xx,922,789,888,000 six × 6,227,020,800

= 560

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

So choosing three balls out of 16, or choosing xiii balls out of sixteen, accept the same number of combinations:

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

In fact the formula is nice and symmetrical:

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

Likewise, knowing that xvi!/thirteen! reduces to 16×15×14, we can salve lots of calculation by doing it this way:

xvi×15×14 3×2×1

= 3360 6

= 560

Pascal's Triangle

We can too use Pascal's Triangle to find the values. Get down to row "n" (the meridian row is 0), then forth "r" places and the value at that place is our answer. Here is an extract showing row xvi:

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

one. Combinations with Repetition

OK, now we tin can tackle this 1 ...

ice cream

Let us say in that location are five flavors of icecream: assistant, chocolate, lemon, strawberry and vanilla.

We can have three scoops. How many variations will there be?

Let's utilise letters for the flavors: {b, c, fifty, s, v}. Example selections include

  • {c, c, c} (three scoops of chocolate)
  • {b, l, v} (i each of assistant, lemon and vanilla)
  • {b, v, v} (ane of banana, two of vanilla)

(And just to exist articulate: There are north=v things to cull from, nosotros choose r=3 of them,
social club does not thing, and we can repeat!)

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

bclsv

Think near the ice cream being in boxes, we could say "motion past the first box, then accept three scoops, then move along 3 more boxes to the end" and we will have three scoops of chocolate!

So it is like we are ordering a robot to get our water ice cream, but information technology doesn't change anything, nosotros notwithstanding go what we want.

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

In fact the 3 examples in a higher place tin can be written like this:

And so instead of worrying about different flavors, we accept a simpler question: "how many unlike ways tin nosotros adjust arrows and circles?"

Observe that in that location are ever 3 circles (iii scoops of water ice foam) and 4 arrows (we need to move 4 times to go from the 1st to 5th container).

So (being general hither) in that location are r + (n−1) positions, and we want to choose r of them to have circles.

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

(r + n − 1)! r!(northward − ane)! = ( r + n − one r )

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

Interestingly, we tin look at the arrows instead of the circles, and say "we have r + (n−1) positions and desire to cull (north−1) of them to have arrows", and the respond is the same:

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

And so, what virtually our example, what is the answer?

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

There are 35 ways of having 3 scoops from five flavors of icecream.

In Decision

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

But knowing how these formulas work is only half the battle. Figuring out how to interpret a real world situation can exist quite hard.

Merely at least you now know the four variations of "Club does/does not matter" and "Repeats are/are not immune":


 Repeats immune No Repeats
Permutations (club matters): due northr due north! (north − r)!
Combinations (order doesn't affair): (r + n − 1)! r!(n − 1)! n! r!(n − r)!

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