Skip to content

The multiplication principle, factorials and binomial coefficients

Probability, grade 11 (5 units) Lesson 12 of 16Learning

The multiplication principle, factorials and binomial coefficients

The multiplication principle

The multiplication principle: when a choice is made in several stages, and the number of options at each stage does not depend on what was chosen at the stages before it, the number of all the options is the product of the numbers of options at the stages.

A business lunch at the restaurant “Tastymatics” has one starter out of two.
It has one main course out of four.
It has one dessert out of three.

Each starter can go with each of the four main courses: 2⋅4=8\displaystyle {2\cdot4}={8} pairs. Each such pair can go with each of the three desserts:

2⋅4⋅3=242\cdot4\cdot3=24

24 different business lunches can be put together. The tree of the choice has 24 paths – a path for each lunch.

Ordered selections

An ordered selection chooses several different objects one after another, where the order matters: who is chosen first, who second. Each choice leaves one option fewer for the next.

In a computer game each player chooses a character (an avatar) out of 6 characters.
A character already chosen is not free for the others.
6 children play the game, and choose characters one after another.

  • The first child chooses out of 6 characters, the second out of the 5 left, and so on to the last, who has one character left: 6⋅5⋅4⋅3⋅2⋅1=7206\cdot5\cdot4\cdot3\cdot2\cdot1=720
  • If only 4 children play, the choice stops after four stages: 6⋅5⋅4⋅3=3606\cdot5\cdot4\cdot3=360
Factorials

The product of all the natural numbers from 1 to n\displaystyle n is called n\displaystyle n factorial, written n!\displaystyle n!:

n!=1⋅2⋅3⋅⋯⋅n\displaystyle n!=1\cdot2\cdot3\cdot\dots\cdot n
  • 3!=1⋅2⋅3=6\displaystyle {3!}={1\cdot2\cdot3}={6}; 6!=720\displaystyle {6!}={720}.
  • 0!\displaystyle 0! is defined as 1, so that the formulas below hold also when all the objects, or none of them, are chosen.

Factorials write an ordered selection in short. 6⋅5⋅4⋅3\displaystyle 6\cdot5\cdot4\cdot3 lacks only 2⋅1=2!\displaystyle {2\cdot1}={2!} at its end, so 6⋅5⋅4⋅3=6!2!\displaystyle {6\cdot5\cdot4\cdot3}={\frac{6!}{2!}}. In general, the number of ways to choose k\displaystyle k different objects out of n\displaystyle n, one after another:

n⋅(n−1)⋅⋯⋅(n−k+1)=n!(n−k)!\displaystyle n\cdot(n-1)\cdot\dots\cdot(n-k+1)=\frac{n!}{(n-k)!}
Choosing without regard to order

When a group is chosen and the order in which its members were chosen does not matter, the number of groups is the number of ordered selections divided by k!\displaystyle k! – the number of orders of each group.

3 dancers out of 10 are chosen for a dance show.

  • Three different roles – the lead dancer, the second dancer and the third dancer: the order matters, 10⋅9⋅8=720\displaystyle {10\cdot9\cdot8}={720} ways.
  • Three identical roles: the group of Ron, Maya and Tom appears 3!=6\displaystyle {3!}={6} times among the 720 ordered selections – once for each order of the three. So the number of groups is: 7203!=7206=120\frac{720}{3!}=\frac{720}{6}=120

The number of ways to choose k\displaystyle k objects out of n\displaystyle n, without regard to order, is the binomial coefficient (nk)\displaystyle \binom{n}{k} (read “n\displaystyle n choose k\displaystyle k”):

(nk)=n!k!(n−k)!\displaystyle \binom{n}{k}=\frac{n!}{k!(n-k)!}

For the dancers: (103)=10!3!⋅7!=10⋅9⋅83!=120\displaystyle {\binom{10}{3}}={\frac{10!}{3!\cdot7!}}={\frac{10\cdot9\cdot8}{3!}}={120}.

Paths with exactly k\displaystyle k successes

The binomial coefficient counts paths in a tree as well. Each path in a tree of n\displaystyle n stages, each stage a success or a failure, is fixed by the stages that were successes – so (nk)\displaystyle \binom{n}{k} paths have exactly k\displaystyle k successes.

A player takes 5 shots at the basket. Each shot is a success (S) or a failure (F).

To get exactly 2 successes, choose the two successful shots out of 5; the rest are failures:

(52)=5!2!⋅3!=5⋅42=10\binom{5}{2}=\frac{5!}{2!\cdot3!}=\frac{5\cdot4}{2}=10

The ten paths, by the places of the two successes: (1,2), (1,3), (1,4), (1,5), (2,3), (2,4), (2,5), (3,4), (3,5), (4,5). For example, (2,5) is the path FSFFS – a success on the second shot and on the fifth.

Exercise 1

An ice-cream kiosk has 3 kinds of cone, 5 flavours of ice cream and 2 kinds of topping.
A portion is one cone, one flavour and one topping.

How many different portions can be put together?

    / – fraction bar · Tab or the arrows – between numerator and denominator, then a note above or below · Enter – check and a new line · * – times · ^ – power, ↓ – end of the power

    / – fraction bar · Tab or the arrows – between numerator and denominator, then a note above or below · Enter – a new line · * – times · ^ – power, ↓ – end of the power

    Exercise 2

    A class has 12 students: 5 girls and 7 boys.

    a

    A chair, a secretary and a treasurer – three different students – are chosen from the students. In how many ways can they be chosen?

      / – fraction bar · Tab or the arrows – between numerator and denominator, then a note above or below · Enter – check and a new line · * – times · ^ – power, ↓ – end of the power

      / – fraction bar · Tab or the arrows – between numerator and denominator, then a note above or below · Enter – a new line · * – times · ^ – power, ↓ – end of the power

      b

      3 representatives are chosen for a meeting with the head teacher. In how many ways can they be chosen?

        / – fraction bar · Tab or the arrows – between numerator and denominator, then a note above or below · Enter – check and a new line · * – times · ^ – power, ↓ – end of the power

        / – fraction bar · Tab or the arrows – between numerator and denominator, then a note above or below · Enter – a new line · * – times · ^ – power, ↓ – end of the power

        c

        Two representatives are chosen: one girl and one boy. In how many ways can they be chosen?

          / – fraction bar · Tab or the arrows – between numerator and denominator, then a note above or below · Enter – check and a new line · * – times · ^ – power, ↓ – end of the power

          / – fraction bar · Tab or the arrows – between numerator and denominator, then a note above or below · Enter – a new line · * – times · ^ – power, ↓ – end of the power

          Exercise 3

          Work out the two binomial coefficients.

          a

            / – fraction bar · Tab or the arrows – between numerator and denominator, then a note above or below · Enter – check and a new line · * – times · ^ – power, ↓ – end of the power

            / – fraction bar · Tab or the arrows – between numerator and denominator, then a note above or below · Enter – a new line · * – times · ^ – power, ↓ – end of the power

            b

              / – fraction bar · Tab or the arrows – between numerator and denominator, then a note above or below · Enter – check and a new line · * – times · ^ – power, ↓ – end of the power

              / – fraction bar · Tab or the arrows – between numerator and denominator, then a note above or below · Enter – a new line · * – times · ^ – power, ↓ – end of the power

              c

              Explain without working them out why (83)=(85)\displaystyle {\binom{8}{3}}={\binom{8}{5}}: think of choosing 3 people out of 8.

              Exercise 4

              A coin is tossed 6 times, and the results are written down in order.

              a

              How many sequences of results are possible?

                / – fraction bar · Tab or the arrows – between numerator and denominator, then a note above or below · Enter – check and a new line · * – times · ^ – power, ↓ – end of the power

                / – fraction bar · Tab or the arrows – between numerator and denominator, then a note above or below · Enter – a new line · * – times · ^ – power, ↓ – end of the power

                b

                In how many sequences do heads come up exactly 4 times?

                  / – fraction bar · Tab or the arrows – between numerator and denominator, then a note above or below · Enter – check and a new line · * – times · ^ – power, ↓ – end of the power

                  / – fraction bar · Tab or the arrows – between numerator and denominator, then a note above or below · Enter – a new line · * – times · ^ – power, ↓ – end of the power

                  c

                  The coin is fair, so all the sequences are equally likely. What is the probability of getting heads exactly 4 times?

                    / – fraction bar · Tab or the arrows – between numerator and denominator, then a note above or below · Enter – check and a new line · * – times · ^ – power, ↓ – end of the power

                    / – fraction bar · Tab or the arrows – between numerator and denominator, then a note above or below · Enter – a new line · * – times · ^ – power, ↓ – end of the power