6.2: Possibility Trees and Advanced Counting
Each of the analyses discussed in "Counting I" can be illustrated by drawing a tree. Take another look at Section 2.1 and Section 2.2 of the readings on the sum rule and the product rule. These will be covered in a subunit below but are mentioned here to explain what a possibility tree is. If you illustrate these rules by drawing a tree, it will depict all the elements of a union of disjoint sets (sum rule) and of the product of sets (multiplication rule). If these sets represent outcomes for events, then the tree is called a possibility tree.
6.2.1: Possibility Trees and the Multiplication Rule
Read up to Section 1.3. Look at the line drawings beginning in Section 1.3 and in following sections; these are possibility trees. Realize that they are just representations of functions used in modeling a problem. Note the modeling advice and steps 1 - 4 on pages 1 - 9.
Multiplication often applies to each level of the tree, i.e. each node at level 1 is expanded (multiplied) by the same number of branches at level 2, and so on, for each level. If the outcomes of an event for a probability problem are modeled using a tree is called a possibility tree.
6.2.2: Permutation
Read Section 1.3 for the definition of a permutation, how to count permutations, and a reminder of Stirling's formula, which approximates n!
6.2.3: Counting Elements of Sets: Addition, Product, and Division Rules
Revisit Section 2, "Two Basic Counting Rules," of the reading to reinforce your understanding of the counting rules, focusing on 2.1: "The Sum Rule" and 2.2: "The Product Rule."
Read from the beginning through Section 1.2; then study the division rule covered in Section 2. Lastly, study Section 3, which discusses counting elements of the union of sets, extending the addition rule: disjoint sets and, then, non-disjoint sets.
The difference rule is as follows: the number of elements in B - A equals (the number of elements in B) minus (the number of elements in B intersect A). In symbols # (B - A) = # (B) - # (B
A).
6.2.4: Combinations
Read Section 1 on pages 1 - 3. Section 1.1 and Section 1.2 discuss counting sequences; Section 1.3 discusses counting combinations.
6.2.5: The Algebra of Combinations
Read this article for more information on the algebra of combinations.
Pascal's triangle is a simple, manual way to calculate binomial coefficients.
Look at the table at the bottom of the reading. The first column, (0,1,2,3,4,5), contains the numbers of the rows - the 0th row, 1st row, 2nd row, etc. - and corresponds to the exponent 'n' in (x + y)n .
Ignore the first column for the moment. Take the nth row and shift it n spaces to the left, i.e. the 0th row is not shifted, the 1st row is shifted 1 space to the left, the 2nd row is shifted 2 spaces to the left, the 3rd row is shifted 3 spaces to the left, etc. This shifting results in a shape of a triangle - '1' is at the top of the triangle in the 0th row, '1 1' is next in the 1st row offset by one space (so that the '1' at the top is above the space in '1 1'), etc. This triangle for n from 0 to 5 generalizes to any n and is called Pascal's triangle. These numbers are the coefficients for the binomial equation presented in the following subunit.
Read Section 2, which defines the binomial expansion expressed in the binomial theorem, that is, the expansion of (a + b)n. The binomial expansion is very important because it is used to make approximations in many domains, including the sciences, engineering, weather forecasting, economics, and polling.
The expansion of (a + b)n is a polynomial whose coefficients are the integers in the nth row of Pascal's Triangle.