http://www.ck12.org Chapter 12. Discrete Math
You can see where the six comes from by making a decision chart and using the Fundamental Counting Principle.
First, determine how many decisions you are making. Here, there are only two decisions to make (1: choose an
option fromA; 2: choose an option fromB), so you will have two “slots” in your decision chart. Next, think about
how many possibilities there are for the first choice (in this case there are 3) and how many possibilities there are for
the second choice (in this case there are 2). The Fundamental Counting Principle says that you can multiply those
numbers together to get the total number of outcomes.
Another type of counting question is when you have a given number of objects, you want to choose some (or all)
of them, and you want to know how many ways there are to do this. For example, a teacher has a classroom of
30 students, she wants 5 of them to do a presentation, and she wants to know how many ways this could happen.
These types of questions have to do withcombinationsandpermutations.The difference between combinations
and permutations has to do with whether or not the order that you are choosing the objects matters.
- A teacher choosing a group to make a presentation would be acombinationproblem, becauseorder does not
matter. - A teacher choosing 1st, 2nd, and 3rdplace winners in a science fair would be apermutationproblem, because
theorder matters(a student getting 1stplace vs. 2ndplace are different outcomes).
Recall that the factorial symbol, !, means to multiply every whole number up to and including that whole number
together. For example, 5!= 5 · 4 · 3 · 2 ·1. The factorial symbol is used in the formulas for permutations and
combinations.
Combination Formula:The number of ways to choosekobjects from a group ofnobjects is –
nCk=
(n
k)
=k!(nn−!k)!Permutation Formula:The number of ways to chooseand arrangekobjects from a group ofnobjects is –
nPk=k!
(n
k)
=k!·k!(nn−!k)!=(n−n!k)!Notice that in both permutation and combination problems you are not allowed to repeat your choices. Any time
you are allowed to repeat and order does not matter, you can use a decision chart. (Problems with repetition where
order does not matter are more complex and are not discussed in this text.)
Whenever you are doing a counting problem, the first thing you should decide is if the problem is a decision chart
problem, a permutation problem, or a combination problem. You will find that permutation problems can also be
solved with decision charts. The opposite is not true. There are many decision chart problems (ones where you are
allowed to repeat choices) that could not be solved with the permutation formula.
Note: Here you have only begun to explore counting problems. For more information about combinations, permuta-
tions, and other types of counting problems, consult a Probability text.
Example A
You are going on a road trip with 4 friends in a car that fits 5 people. How many different ways can everyone sit if
you have to drive the whole way?
Solution:A decision chart is a great way of thinking about this problem. You have to sit in the driver’s seat. There