DP IB Maths: AA HL

Revision Notes

1.7.2 Permutations & Combinations

Test Yourself

Permutations

 What are Permutations?

  • A permutation is the number of possible arrangements of a set of objects when the order of the arrangements matters
  • A permutation can either be finding the number of ways to arrange n items or finding the number of ways to arrange r out of n items

How many ways can n different objects be arranged?

  • When considering how many ways you can arrange a number of different objects in a row consider how many of the objects can go in the first position, how many can go in the second and so on
  • For n = 2 there are two options for the first position and then there will only be one option to go in the second position so:
    • The first object has two places it could go and the second object has one place
    • By the fundamental counting principle both objects have 2 × 1 places to go
    • For example to arrange the letters A and B we have
      • AB and BA
  • For n = 3 there are three options for the first position and then there will be two options for the second position and one for the third position so
    • The first object has three places it could go, the second object has two places and the third object has one place
    • By the fundamental counting principle the three objects have 3 × 2 × 1 places to go
    • For example to arrange the letters A, B and C we have
      • ABC, ACB, BAC, BCA, CAB and CBA
  • For n objects there are n options for the first position, n - 1 options for the second position and so on until there is only one object left to go in final position
  • The number of permutations of n different objects is n factorial (n!)
    • Where n factorial blank equals n blank cross times open parentheses n minus 1 close parentheses cross times open parentheses n minus 2 close parentheses cross times horizontal ellipsis blank cross times 2 blank cross times 1
    • For 5 different items there are 5 factorial blank equals 5 blank cross times 4 blank cross times 3 blank cross times 2 equals 120 blankpermutations
    • For 6 different items there are 6 factorial blank equals 6 blank cross times blank 5 blank cross times 4 blank cross times 3 blank cross times 2 equals blank 720 blankpermutations
    • It is easy to see how quickly the number of possible permutations of different items can increase
    • For 10 different items there are 10! = 3 628 800 possible permutations

What are factorials?

  • Factorials are a type of mathematical operation (just like +,  -,  ×,  ÷)
  • The symbol for factorial is !
    • So to take a factorial of any non-negative integer, n, it will be written n! and pronounced ‘n factorial’
  • The factorial function for any positive integer, n, is n factorial equals n blank cross times open parentheses n minus 1 close parentheses cross times open parentheses n minus 2 close parentheses cross times horizontal ellipsis blank cross times 2 blank cross times 1
    • For example, 5 factorial is 5 factorial equals 5 blank cross times 4 blank cross times 3 blank cross times 2 blank cross times 1
  • The factorial of a negative number is not defined
    • You cannot arrange a negative number of items
  • 0! = 1
    • There are no positive integers less than zero, so zero items can only be arranged once
  • Your GDC will have a mode for calculating factorials, make sure you can put yours into the correct mode
  • Most normal calculators cannot handle numbers greater than about 70!, experiment with yours to see the greatest value of x such that your calculator can handle x!

What are the key properties of using factorials?

  • Some important relationships to be aware of are:
    • n factorial equals n blank cross times open parentheses n minus 1 close parentheses factorial blank
      • Therefore fraction numerator n factorial over denominator open parentheses n minus 1 close parentheses factorial end fraction equals n
    • n factorial equals n blank cross times open parentheses n minus 1 close parentheses blank cross times open parentheses n minus 2 close parentheses factorial blank
      • Therefore fraction numerator n factorial over denominator open parentheses n minus 2 close parentheses factorial end fraction equals n blank cross times left parenthesis n minus 1 right parenthesis
  • Expressions with factorials in can be simplified by considering which values cancel out in the fraction
    • Dividing a large factorial by a smaller one allows many values to cancel out
      • fraction numerator 8 factorial over denominator 5 factorial end fraction blank equals blank fraction numerator 8 blank cross times 7 blank cross times 6 blank cross times 5 blank cross times 4 blank cross times 3 blank cross times 2 blank cross times 1 over denominator 5 blank cross times 4 blank cross times 3 blank cross times 2 blank cross times 1 end fraction blank equals blank 8 blank cross times 7 blank cross times 6 blank

How do we find r  permutations of n items?

  • If we only want to find the number of ways to arrange a few out of n  different objects, we should consider how many of the objects can go in the first position, how many can go in the second and so on
  • If we wanted to arrange 3 out of 5 different objects, then we would have 3 positions to place the objects in, but we would have 5 options for the first position, 4 for the second and 3 for the third
    • This would be 5 × 4 × 3 ways of permutating 3 out of 5 different objects
    • This is equivalent to begin mathsize 16px style fraction numerator 5 factorial over denominator 2 factorial end fraction equals fraction numerator 5 factorial over denominator open parentheses 5 minus 3 close parentheses factorial end fraction end style
  • If we wanted to arrange 4 out of 10 different objects, then we would have 4 positions to place the objects in, but we would have 10 options for the first position, 9 for the second, 8 for the third and 7 for the fourth
    • This would be 10 × 9 × 8 × 7 ways of permutating 4 out of 10 different objects
    • This is equivalent to begin mathsize 16px style fraction numerator 10 factorial over denominator 6 factorial end fraction equals fraction numerator 10 factorial over denominator left parenthesis 10 minus 4 right parenthesis factorial end fraction end style
  • If we wanted to arrange r out of n different objects, then we would have r positions to place the objects in, but we would have n options for the first position, begin mathsize 16px style open parentheses n minus 1 close parentheses end style for the second, begin mathsize 16px style open parentheses n minus 2 close parentheses end style for the third and so on until we reach begin mathsize 16px style open parentheses n minus open parentheses r minus 1 close parentheses close parentheses end style
    • This would be begin mathsize 16px style n cross times open parentheses n minus 1 close parentheses cross times... cross times open parentheses n minus r plus 1 close parentheses end style ways of permutating r out of n different objects
    • This is equivalent to begin mathsize 16px style fraction numerator n factorial over denominator open parentheses n minus r close parentheses factorial end fraction end style
  • The function fraction numerator size 16px n size 16px factorial over denominator begin mathsize 16px style stretchy left parenthesis n minus r stretchy right parenthesis factorial end style end fractioncan be written as begin mathsize 16px style straight P presuperscript n subscript r end style
    • Make sure you can find and use this button on your calculator
  • The same function works if we have n spaces into which we want to arrange r objects, consider
    • for example arranging five people into a row of ten empty chairs

Permutations when two or more items must be together

  • If two or more items must stay together within an arrangement, it is easiest to think of these items as ‘stuck’ together
  • These items will become one within the arrangement
  • Arrange this ‘one’ item with the others as normal
  • Arrange the items within this ‘one’ item separately
  • Multiply these two arrangements together

Permutations when two or more items cannot be all together

  • If two items must be separated …
    • consider the number of ways these two items would be together
    • subtract this from the total number of arrangements without restrictions
  • If more than two items must be separated…
    • consider whether all of them must be completely separate (none can be next to each other) or whether they cannot all be together (but two could still be next to each other)
    • If they cannot all be together then we can treat it the same way as separating two items and subtract the number of ways they would all be together from the total number of permutations of the items, the final answer will include all permutations where two items are still together
    • If the items must all be completely separate then
      • lay out the rest of the items in a line with a space in between each of them where one of the items which cannot be together could go
      • remember that this could also include the space before the first and after the last item
      • You would then be able to fit the items which cannot be together into any of these spaces, using the r permutations of n items rule left parenthesis scriptbase straight P subscript r end scriptbase presubscript blank presuperscript n right parenthesis
      • You do not need to fill every space

Permutations when two or more items must be in specific places

  • Most commonly this would be arranging a word where specific letters would go in the first and last place
  • Or arranging objects where specific items have to be at the ends/in the middle
    • Imagine these specific items are stuck in place, then you can find the number of ways to arrange the rest of the items around these ‘stuck’ items
  • Sometimes the items must be grouped
    • for example all vowels must be before the consonants
    • Or all the red objects must be on one side and the blue objects must be on the other
    • Find the number of permutations within each group separately and multiply them together
    • Be careful to check whether the groups could be in either place
      • e.g. the vowels on one side and consonants on the other
      • or if they must be in specific places (the vowels before the consonants)
    • If the groups could be in either place than your answer would be multiplied by two
    • If there were n groups that could be in any order then your answer would be multiplied by n!

Exam Tip

  • The wording is very important in permutations questions, just one word can change how you answer the question
  • Look out for specific details such as whether three items must all be separated or just cannot be all together (there is a difference)
  • Pay attention to whether items must be in alternating order (e.g. red and blue items must alternate, either RBRB… or BRBR…) or whether a particular item must come first (red then blue and so on)
  • If items should be at the ends, look out for whether they can be at either end or whether one must be at the beginning and the other at the end

Worked example

Find the number of ways nine different tasks can be carried out given that two particular tasks must not be carried out consecutively.

1-7-2-ib-aa-hl-pernutations-we-solution

Combinations

What is the difference between permutations and combinations?

  • A combination is the number of possible arrangements of a set of objects when the order of the arrangements does not matter
    • On the other hand a permutation is when the order of arrangement does matter
  • A combination will be finding the number of ways to choose r out of n items
    • The order in which the r items are chosen is not important
    • For example if we are choosing two letters from the word CAB, AB and BA would be considered the same combination but different permutations

How do we find r combinations of n items?

  • If we want to find the number of ways to choose 2 out of 3 different objects, but we don’t mind the order in which they are chosen, then we could find the number of permutations of 2 items from 3 and then divide by the number of ways of arranging each combination
    • For example if we want to choose 2 letters from A, B and C
      • There are 6 permutations of 2 letters:
      • AB, BA, AC, CA, BC, CB
      • For each combination of 2 letters there are 2 (2 × 1) ways of arranging them
      • (for example, AB and BA)
      • So divide the total number of permutations (6) by the number of ways of arranging each combination (2) to get 3 combinations
  • If we want to find the number of ways to choose 3 out of 5 different objects, but we don’t mind the order in which they are chosen, then we could find the number of permutations of 3 items from 5 and then divide by the number of ways of arranging each combination
    • For example if we want to choose 3 letters from A, B, C, D and E
      • There are 60 permutations of 3 letters:
      • ABC, ACB, BAC, BCA, CAB, CBA, ABD, ADB, etc
      • For each combination of 3 letters there are 6 (3 × 2 ×1) ways of arranging them (for example, ABC, ACB, BAC, BCA, CAB and CBA)
      • So divide the total number of permutations (60) by the number of ways of arranging each combination (3! = 6) to get 10 combinations
  • If we want to find the number of ways to choose r items out of n different objects, but we don’t mind the order in which they are chosen, then we could find the number of permutations of r items from n and then divide by the number of ways of arranging each combination
  • Recall that the formula for r permutations of n items is 
    • scriptbase straight P subscript r end scriptbase presubscript blank presuperscript n equals blank fraction numerator n factorial over denominator left parenthesis n blank minus blank r right parenthesis factorial end fraction
  • This would include r! ways of repeating each combination
  • The formula for r combinations of n items is
    • fraction numerator scriptbase straight P subscript r end scriptbase presubscript blank presuperscript n over denominator r factorial end fraction equals blank fraction numerator n factorial over denominator open parentheses n blank minus blank r close parentheses factorial blank r factorial end fraction
  • The function fraction numerator n factorial over denominator open parentheses n blank – blank r close parentheses factorial blank r factorial end fraction can be written as scriptbase straight C subscript r end scriptbase presubscript blank presuperscript n blankor blank open parentheses table row n row r end table close parentheses and is often read as ‘n choose r’
    • Make sure you can find and use this button on your calculator
  • The formulae for permutations and combinations satisfy the following relationship:
    • scriptbase straight C subscript r end scriptbase presubscript blank presuperscript n equals fraction numerator scriptbase straight P subscript r end scriptbase presubscript blank presuperscript n over denominator r factorial end fraction blank
  • The formula scriptbase straight C subscript r end scriptbase presubscript blank presuperscript n equals fraction numerator n factorial over denominator r factorial open parentheses n minus r close parentheses factorial blank end fraction can be found in the formula booklet

What do I need to know about combinations?

  • The formula begin mathsize 16px style C presuperscript n subscript r equals fraction numerator n factorial over denominator left parenthesis n minus r right parenthesis factorial r factorial end fraction end style is also known as a binomial coefficient
  • size 16px C presuperscript size 16px n subscript size 16px n size 16px equals size 16px C presuperscript size 16px n subscript size 16px 0 size 16px equals size 16px 1
    • It is easy to see that there is only one way of arranging n objects out of n and also there can only be one way of arranging 0 objects out of n
    • By considering the formula for this, it reinforces the fact that 0! Must equal 1
  • The binomial coefficients are symmetrical, so size 16px C presuperscript size 16px n subscript size 16px r size 16px equals size 16px C presuperscript size 16px n subscript size 16px n size 16px minus size 16px r end subscript
    • This can be seen by considering the formula for size 16px C presuperscript size 16px n subscript size 16px r
    • scriptbase straight C subscript n minus r end subscript end scriptbase presubscript blank presuperscript n equals blank fraction numerator n factorial over denominator left parenthesis n minus r right parenthesis factorial open parentheses n minus left parenthesis n minus r right parenthesis close parentheses factorial end fraction equals blank fraction numerator n factorial over denominator r factorial open parentheses n minus r close parentheses factorial end fraction equals blank scriptbase straight C subscript r end scriptbase presubscript blank presuperscript n

How do I know when to multiply or add?

  • Many questions will ask you to find combinations of a group of different items from a bigger group of a specified number of those different items
    • For example, find the number of ways five questions could be chosen from a bank of twenty different pure and ten different statistics questions
    • The hint in this example is the word 'chosen', this tells you that the order in which the questions are chosen doesn't matter
  • Sometimes questions will have restrictions,
    • For example there should be three pure and two statistics chosen from the bank of questions, 
    • Or there must be at least two pure questions within the group
  • If unsure about whether to add or multiply your options, ask yourself if A and B are both needed, or if A or B is needed
    • Always multiply if the answer is and, and add if the answer is or
    • For example if we needed exactly three pure and two statistics questions we would find the amount of each and multiply them
    • If we could have either five statistics or five pure questions we would find them separately and add the answers

Exam Tip

  • It is really important that you can tell whether a question is about permutations or combinations
    • Look out for key words such as arrange (for permutations) or choose or select (for combinations)
  • Don’t be confused if a question asks for the number of ways, this could be for either a permutations or a combinations question
    • Look out for other clues

Worked example

Oscar has to choose four books from a reading list to take home over the summer.  There are four fantasy books, five historical fiction books and two classics available for him to choose from.  Find the number of ways that Oscar can choose four books if he decides to have:

i)
Two fantasy books and two historical fictions.

1-7-2-ib-aa-hl-combinations-we-solution-i

ii)
At least one of each type of book.

1-7-2-ib-aa-hl-combinations-we-solution-ii

iii)
At least two fantasy books.

1-7-2-ib-aa-hl-combinations-we-solution-iii

You've read 0 of your 0 free revision notes

Get unlimited access

to absolutely everything:

  • Downloadable PDFs
  • Unlimited Revision Notes
  • Topic Questions
  • Past Papers
  • Model Answers
  • Videos (Maths and Science)

Join the 80,663 Students that ❤️ Save My Exams

the (exam) results speak for themselves:

Did this page help you?

Amber

Author: Amber

Amber gained a first class degree in Mathematics & Meteorology from the University of Reading before training to become a teacher. She is passionate about teaching, having spent 8 years teaching GCSE and A Level Mathematics both in the UK and internationally. Amber loves creating bright and informative resources to help students reach their potential.