There are 8 methods for preparing an egg. For any of those methods, there are 3 different egg consistencies one can choose from. All of these methods and consistencies can be attained using one of 5 different colors of eggs. Then, when choosing a method, a consistency, and a color, there are 8 × 3 × 5 = 120 ways to choose to make a meal from an egg.
Counting Techniques
PINs or passwords are needed for many things and the rules for creating them are often complicated. Many passwords are required to contain at least 8 characters and at least 1 each of
- lower-case letter
- upper-case letter
- number
- punctuation mark
Counting methods are used to identify the number of possible outcomes of an experiment in multiple stages. They are important in the discussion of probability since, when outcomes are equally likely, we can find the probability of an event by dividing the number of outcomes within that event by the total number of possible outcomes.
Methods for counting are based 'the multiplication principle' which states that, to find the number of possible outcomes for an experiment that takes place in multiple stages, we multiply the number of possibilities at each stage.
If an experiment takes place in k stages with $n_i$ possible outcomes at stage $i$, the total number of possible outcomes is $n_1\cdot n_2 \cdot \cdots \cdot n_k$.
Example: Suppose a password had to be chosen according to strict rules: a lower-case letter first, a digit second,
an upper-case letter third. How many ways are there to do this?
There are 26 lower-case letters, 10 digits, and 26 upper-case letters so the number of such passwords would be 26*10*26 = 6760.
There are 26 lower-case letters, 10 digits, and 26 upper-case letters so the number of such passwords would be 26*10*26 = 6760.
Use the applet to see how many passwords are possible for the given password lengths. Adjust the number of characters with the slider.
For more information about passwords and
hacking, see this interesting article from Scientific American.
Example: A restaurant offers 3 choices for appetizer, 2 for main course, and 5 for dessert. How many meal variations are possible if a diner chooses
1 of each?
There are 3 × 2 × 5 = 30 different meal variations.
There are 3 × 2 × 5 = 30 different meal variations.
Example: How many ways are there to create a 4 digit PIN?
This is an experiment in 4 stages. At each stage there are 10 possible outcomes (the digits 0, 1, ..., 9) thus there are $10\cdot 10\cdot 10\cdot 10 = 10,000$ possible outcomes for the entire experiment.
This is an experiment in 4 stages. At each stage there are 10 possible outcomes (the digits 0, 1, ..., 9) thus there are $10\cdot 10\cdot 10\cdot 10 = 10,000$ possible outcomes for the entire experiment.
In many experiments, we choose some number of objects (k) from a larger number (n) of possibilities. When choosing a 4 digit PIN, we choose
four digits from the ten available, so n=10 and k=4.
Sometimes, the same options are available at each stage. In this case, each stage can be likened to drawing tickets, labeled with the options, from a box.
Since the options stay the same, it is as if we replace the tickets after each draw. This is called choosing 'with replacement'. In the case of the PIN
a digit is chosen from among the ten possibilities and then retained to (possibly) be chosen again.
With replacement: an object once chosen is available to be chosen again at the next stage.
Without replacement: an object once chosen is not available to be chosen again at any subsequent stage.
Example: How many ways are there to create a 4 digit PIN if no digit can be repeated?
This is still an experiment in 4 stages but in this case, the number of options decreases by one at each stage. The digits cannot be repeated thus they are chosen without replacement. Thus there are $10\cdot 9\cdot 8\cdot 7 = 5,040$ possible outcomes for the entire experiment.
This is still an experiment in 4 stages but in this case, the number of options decreases by one at each stage. The digits cannot be repeated thus they are chosen without replacement. Thus there are $10\cdot 9\cdot 8\cdot 7 = 5,040$ possible outcomes for the entire experiment.
Two common counting scenarios involve counting the number of ways k objects can be chosen from n objects, without replacement (no repeats).
The difference between these scenarios lies in whether or not the selections are ordered/distinguishable or not.
Example: Ordered/distinguishable vs. not
- Scenario: A group of 4 students is chosen from the student body of 150 students to form the student government at a high school.
- Distinguishable: The students each have a set position: president, vice-president, secretary, and treasurer.
- Indistinguishable: The students work together as a committee without set roles.
- Scenario: Prizes are given out for the top 3 performers out of 20 who participate in a sales drive.
- Ordered: The highest performer receives $\$$100, the second highest receives $\$$50, and the third receives $\$$20.
- Unordered: The top three receive $\$$50 each.
When k objects are chosen from n without replacement, the results are called permutations if order matters and combinations If it does not.
Permutation: An arrangement of $k$ objects chosen without replacement from $n$ objects when order matters.
Combination: An unordered arrangement of $k$ objects chosen without replacement from $n$ objects.
Permutations: Choose $k$ objects from $n$ objects without replacement, order matters.
Consider a simple game in which a player tries to guess a sequence of 3 numbers chosen from the digits 0, 1, 2, 3, 4, where order matters and digits cannot be repeated (they are chosen without replacement). How many possibilities are there? The options are shown below.
To count the number of possibilities, apply the multiplication principle: there are five options for the first choice, four for the second,
and three for the last. That gives 5 × 4 × 3 = 60 possibilities.
More generally, the number of ways to choose k objects from n objects without replacement if order doesn't matter is (n-1) × (n-2) × ... × (n-k+1).
$n! = n\cdot (n-1)\cdot(n-2)\cdots 2\cdot 1$
The number of permutations of k objects chosen from n, $P^n_k$, can be expressed in terms of factorials:
$\small{n\cdot(n-1)\cdot(n-2)\cdots(n-k+1) = \frac{n\cdot(n-1)\cdot(n-2)\cdots (n-k+1) \cdot (n-k) \cdot (n-k-1) \cdots 2 \cdot 1}{(n-k)\cdot (n-k-1)\cdots 2 \cdot 1} = \frac{n!}{(n-k)!}}$.
$P^n_k=\frac{n!}{(n-k)!}$
Example: How many ways are there to choose a 6 character password using only lower-case letters, with no repetitions?
In a password, order always matters. Since this has specified no repetitions, we are drawing without replacement. There are $P_6^{26}=165,765,600$ ways to choose a 6 letter password, using only lower-case letters, without replacement.
In a password, order always matters. Since this has specified no repetitions, we are drawing without replacement. There are $P_6^{26}=165,765,600$ ways to choose a 6 letter password, using only lower-case letters, without replacement.
Combinations: Choose $k$ objects from $n$ objects, no replacement, order doesn't matter.
When choosing without replacement, if order doesn't matter, then orderings such as 0123 and 3012 are redundant thus
there are many fewer ways to choose 4 numbers than if order does matter. The table of permutations is shown below. Notice that all columns
within a row show different orderings of the same selection of three numbers. If order doesn't matter, these orderings are redundant. All the
combinations are contained within any single column.
To find the number or arrangements in this case (called combinations), divide the
number of permutations by the number of redundant orderings, $k!$.
The number of combinations of $k$ objects chosen from $n$ objects is denoted $C_k^n$ or, more commonly, $\binom{n}{k}$.
$C^n_k = \binom{n}{k}=\frac{n!}{(n-k)!k!}$
Example: In IP4, a pick-four Lottery, a player who chooses play type 'Box' seeks to identify the 4 numbers that will be drawn by the lottery officials regardless of order. How many ways
are there to choose 4 numbers from 0 to 9 if there are no repetitions and order does not matter? What is the probability of winning?
There are $\binom{10}{4} = 210$ ways to choose 4 numbers without replacement or respect to order. Since two numbers are drawn daily, the probability of winning using this play type is $P(win)=\frac{2}{210} = 0.010$
There are $\binom{10}{4} = 210$ ways to choose 4 numbers without replacement or respect to order. Since two numbers are drawn daily, the probability of winning using this play type is $P(win)=\frac{2}{210} = 0.010$
At first glance, this question seems to be one about rearranging 6 objects, where order matters. However, upon closer inspection, we realize that we
have two 'T's to place (say, T1 and T2) and four 'F's (say, F1, F2, F3, and F4), and it becomes clear that T1F1F2T2F3F4 is the same as T2F3F1T1F4F2.
So, some of the order matters, but not all of it. In fact, what really matters is which of the six spots we choose to place a 'T' in. In the cases above,
we simply chose spots 1 and 4 to place a 'T' in (or spots 4 and 1, which is equivalent).
This begins to look like a combination. We have to choose two spots from six spots (without replacement) for a 'T' to be placed, where the order doesn't matter. Then, there are $C_2^6=\binom{6}{2}=6!/(6-2)!2!=15$ ways to fill out the quiz with two 'T's and four 'F's.
Since there is only 1 of those 15 combinations that is the correct set of answers, the probability that you get 100% by guessing is 1/15 = 0.067.
This begins to look like a combination. We have to choose two spots from six spots (without replacement) for a 'T' to be placed, where the order doesn't matter. Then, there are $C_2^6=\binom{6}{2}=6!/(6-2)!2!=15$ ways to fill out the quiz with two 'T's and four 'F's.
Since there is only 1 of those 15 combinations that is the correct set of answers, the probability that you get 100% by guessing is 1/15 = 0.067.