Permutations (DP IB Analysis & Approaches (AA)): Revision Note

Permutations

 What is a permutation?

• A permutation is a rearrangement of different objects where order matters

  • e.g. BDAC is a permutation of ABCD

  • e.g. assigning bronze, silver and gold to Emma, Jay and Flo (in that order)

    • is different to the order 'Jay, Flo and Emma'

What are factorials?

• Factorials (the symbol '') are a mathematical operation on a positive integer, , where you multiply together all the integers that are less than or equal to

  • e.g.

• In general

  • 

• A surprising result is that zero factorial is 1

  • 

How do I use factorials to rearrange n different objects?

• If you have different objects, you can rearrange them in ways

  • e.g. the letters ABCDE are 5 different objects

    • They can be rearranged in ways

  • e.g. if you have 8 people in a line

    • they can be rearranged in ways

How do I rearrange when two (or more) objects must be together?

• This is best shown through examples, by grouping objects together

• e.g. how many ways can you rearrange the letters ABCDE such that the D and E are always together, in either order?

  • Let X = DE

  • This gives ABCX where X = DE

    • There are 4! ways to rearrange ABCX

    • There are 2! ways to rearrange DE

    • so there are 4! × 2! = 48 ways in total

• e.g. how many ways can you rearrange the letters ABCDE such that the D and E are always together in the order DE?

  • Let X = DE

  • This gives ABCX where X = DE

    • There are 4! ways to rearrange ABCX

    • There is only 1 way to 'rearrange' DE

    • so there are 4! × 1 = 24 ways in total

• An X can be used to group three or more letters in the same way

How do I rearrange when two objects cannot be together?

• Start by doing the opposite: find the number of ways in which they can be together

  • Then subtract this from the total number of unrestricted arrangements

• e.g. how many ways can you rearrange the letters ABCDE such that the D and E are never together?

  • Let X = DE

  • This gives ABCX where X = DE

    • There are 4! ways to rearrange ABCX

    • There are 2! ways to rearrange DE

    • so there are 4! × 2! ways in which the D and E are together

  • Now find the number of rearrangements of ABCDE without restrictions

    • This is 5!

  • Lastly subtract 4! × 2! from 5!

    • So there are 5! - 4! × 2! = 72 ways in which the D and E are never together

How do I rearrange when objects must be in specific places?

• This is best shown through a example

• e.g. how many ways can you rearrange the letters ABCDE such that the second letter is either a D or an E and the last letter is an A?

  • It is easier to start in a different order

    • There is 1 choice for the fifth letter (the A)

    • There are 2 choices for the second letter (D or E)

  • At this point, the A has been used and one out of D or E has been used, i.e. 3 letters are left

    • There are 3 choices for the first letter

    • 2 choices for the third letter

    • and 1 choice for the fourth letter

  • The total is 3 × 2 × 2 × 1 × 1 = 12 ways

What is  ?

• stands for the number of ways to permute (rearrange) objects, that have been selected out of different objects

  • where

• The formula is

  • Note that it is not possible to select repeated objects when using

• e.g. how many 3-letter passwords can be made out of 10 different letters?

  • Each of the 10 letters is different

  • You are selecting out of

  • Order matters for passwords

    • so

  • This can be simplified by cancelling

    •