Combinatorics: Counting Principles and Tree Diagrams - Lecture Notes

Combinatorics: Counting Principles and Tree Diagrams

• What is combinatorics?

  • The mathematics of counting: determining how many ways an experiment (in a broad sense) can be performed.

  • An “experiment” could be as simple as flipping a coin, rolling a die, or more complex multi-step processes.

  • The goal is to determine how many outcomes or ordered results are possible, not necessarily to list them all by hand.

• Sample space and cardinality

  • The set of all possible outcomes is called the sample space, denoted by capital S.

  • The cardinality of the sample space is the number of outcomes, written as |S|.

  • Examples:

  • Coin flip (fair coin): S = {H, T}, |S| = 2.

  • Fair six-sided die: S = {1, 2, 3, 4, 5, 6}, |S| = 6.

  • When rolling two dice (ordered pairs), the sample space is the Cartesian product SA × SB:

  • |SA| = 6, |SB| = 6 → |S| = 6 × 6 = 36.

  • This is why the sample space for two dice is 36 ordered outcomes (e.g., (1,1), (1,2), …, (6,6)).

  • A single act of an experiment is called a stage. Multi-stage experiments grow very quickly in cardinality.

• Factorials

  • Factorial notation: n! = n imes (n-1) imes (n-2) imes \,\cdots\, \times 2 \times 1

  • Example: 10! = 10 \times 9 \times 8 \times \cdots \times 1 = 3\,628\,800

  • Calculator tips (TI-30XA, etc.): use the factorial key to compute factorials rapidly.

  • When dividing factorials, cancel common factors carefully, just like algebra:

  • E.g., \frac{10!}{5!} = \frac{10\cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5!}{5!} = 10\cdot 9 \cdot 8 \cdot 7 \cdot 6 = 30\,240.

  • Very large factorials may exceed calculator display; use expansion to cancel terms instead:

  • \frac{80!}{78!} = \frac{80\cdot 79\cdot 78!}{78!} = 80\cdot 79 = 6\,320.

• The Fundamental Counting Principle (FCP)

  • Also called the Multiplication Principle.

  • If an experiment has k stages with n1, n2, …, nk possible outcomes at each stage, the total number of outcomes is: N = n1 \times n2 \times \cdots \times nk = \prod{i=1}^k ni.

  • The order of multiplication does not matter for the final count, but it helps to organize by stages.

  • Practical use: list the number of outcomes for each stage, then multiply.

  • Two common pitfalls:

  • Restrictions: some stages may have limited options (e.g., first spot cannot be zero).

  • Repetition: whether an element may be reused in later stages or not (affects the counts).

  • When describing a problem, it helps to draw a template with a bar for each stage and write the number of outcomes above each bar; notes below each bar describe the stage.

• When to use restrictions and repetition

  • If a stage has restrictions, count those possibilities first.

  • Example: first digit cannot be 0 when forming a 7-digit number; first stage would have 9 possibilities instead of 10.

  • Determine whether repetition is allowed:

  • If repetition is allowed, you can reuse elements in later stages (multiply by the same count for each stage).

  • If repetition is not allowed, each subsequent stage has one fewer option (the product decreases accordingly).

  • Reading story problems: look for explicit restrictions and whether repetition is allowed or not; these change the product.

• Example applications of the FCP (selected problems from the chapter)

  • Example 1: License plates with 5 symbols: first two are letters (A–Z), last three are digits (0–9).

  • Part A (repetition allowed): 5-stage FCP with counts: 2 letters, 2 letters, 10 digits, 10 digits, 10 digits.

  • Count: 26^2 \cdot 10^3 = 676{,}000.

  • Part B (no repetition): 26 × 25 × 10 × 9 × 8 = 468{,}000.

  • Example 2: Five finalists ranked first through fifth.

  • Repetition not allowed (distinct finalists).

  • Count: 5! = 120.

  • Example 3: Itinerary visiting 4 European cities (London, Hamburg, Paris, Zurich).

  • Four stages, repetition not allowed: 4! = 24.

  • Example 4: Committee of 20; appoint president, secretary, treasurer (3 distinct roles).

  • Repetition not allowed; 3 distinct people from 20:

  • Count: 20\times 19\times 18 = 6{,}840. (Not a factorial because it ends before using all 20.)

  • Example 5: Nine-digit Social Security numbers with restrictions:

  • Part (a): begin with 3; end with an even digit other than 0 (i.e., 2,4,6,8).

    • Count: 1 \times 4 \times 10^7 = 40{,}000{,}000.

  • Part (b): number must contain all evens or all odds (digits 0–9 allowed; repetition allowed).

    • Evens: 5 choices per middle position (0,2,4,6,8) across 9 middle positions: 5^9.

    • Odds: similarly 5^9.

    • Total: 5^9 + 5^9 = 2\cdot 5^9 = 3{,}906{,}250. (Note: 5^9 = 1{,}953{,}125; double that is 3{,}906{,}250.)

  • Example 6: Seating 8 boys and 8 girls in a row of 16 such that all boys sit together and all girls sit together.

  • Treat each block as a unit; two block orders (B before G or G before B).

  • Internal orders: 8! for boys, 8! for girls.

  • Count: 2 \cdot 8! \cdot 8! = 2 \cdot 40320 \cdot 40320 = 3{,}251{,}404{,}800.

  • Example 7: Three-digit numbers from digits {1,2,3,4,5,6}, no repetition, even.

  • Last digit must be even: 3 possibilities (2,4,6).

  • First digit: 5 remaining choices (cannot reuse the last digit).

  • Middle digit: 4 remaining choices.

  • Count: 3 \times 5 \times 4 = 60. (Some notes in the transcript contained minor arithmetic typos.)

  • Example 8: Geography test: 10 true/false questions + 10 multiple-choice questions with 5 options each.

  • True/False portion: 2^{10} possibilities.

  • Multiple-choice portion: 5^{10} possibilities.

  • Since this is one test with all 20 questions, multiply: 2^{10} \cdot 5^{10} = (2\cdot5)^{10} = 10^{10}.

  • Perfect score is only 1 out of 10^{10} possible answer patterns.

• Tree diagrams: when to use them

  • A tree diagram is useful for multi-stage experiments with a small number of outcomes per stage.

  • They are particularly valuable when the number of stages varies (not fixed in advance). Examples include:

  • Stopping problems (e.g., draw until a certain event occurs).

  • Steps to draw a tree diagram:

  • Step 1: draw a node for the first stage.

  • Step 2: draw a branch for every possible outcome of that stage.

  • Step 3: at the end of each branch, draw a new node for the next stage and continue.

  • Include stopping points (circles) when the process ends, and continue branches only for paths that do not stop yet.

  • Example A (factory problem): Inspects chips until a defective chip is found or five chips are evaluated.

  • Stopping points appear when a defective chip is observed or after the fifth chip is evaluated.

  • The sample space consists of the distinct paths that end in a stopping point (there can be multiple such paths).

  • Example B (urn problem): Draw until a white marble is selected; there are three colors available at each step (red, white, blue).

  • White is a stopping point; paths continue otherwise.

  • The diagram yields a certain number of distinct stopping paths (nine in the example discussed).

  • In both examples, counting via the tree yields the sample space size by counting completed paths that end in a stopping point.

• Additional practice problems (conceptual summaries and answers)

  • Problem 1: Experiment with four coin flips, two die rolls, and one card draw (7 stages total).

  • Count using FCP: 2^4 \cdot 6^2 \cdot 52 = 29{,}952.

  • Problem 2: Odd numbers between 10 and 500 using digits {1,2,3,6,7} with repetition allowed.

  • Split into two cases: two-digit numbers and three-digit numbers.

  • Two-digit (last digit odd): 3 options for last digit (1,3,7) and 5 options for the first (excluding repeats not required since repetition allowed across digits but must meet range).

  • Three-digit numbers: first digit can be 1, 2, or 3 (to stay below 500); last digit must be odd (1,3,7); middle digit can be any of the 5 digits.

  • Totals: two-digit case = 15, three-digit case = 45; overall total = 60.

  • Problem 3: Deluxe sports car ordering with options:

  • Top: with/without hardtop (2)

  • Rims: with/without spoked (2)

  • Paint: 4 colors (red, white, black, green)

  • Interior: 3 colors (white, beige, black)

  • Total orderings: 2 \cdot 2 \cdot 4 \cdot 3 = 48.

  • Problem 4: Five-digit numbers from digits {2,3,4,7,8}, repetition allowed.

  • 5 choices for each of 5 positions: 5^5 = 3{,}125.

  • Problem 5: Nine vending machines in a row (6 beverages, 3 snacks) with both blocks together.

  • When all beverages are together and all snacks are together, treat each block as a unit.

  • Two block orders (B before S or S before B): factor 2.

  • Internal order within each block (if machines are distinct): 6! for beverages and 3! for snacks.

  • Total: 2 \cdot 6! \cdot 3! = 8640. (If the machines within a block were indistinguishable, the count would be different; here they’re treated as distinct machines.)

  • Problem 6: Urn with 1 red, 1 white, 2 green, 1 blue; draw until red or green appears; 10 outcomes.

  • Problem 7: Three-digit numbers from digits {1,2,3,4,5,6}, no repetition, even.

  • Last digit even: 2,4,6 → 3 options.

  • First digit: from remaining 5 digits (cannot reuse last digit).

  • Middle digit: from remaining 4 digits.

  • Total: 3 \times 5 \times 4 = 60. (Corrected from some transcript typos that appeared to misstate the product.)

  • Problem 8: Geography test with 10 True/False questions followed by 10 multiple-choice questions with 5 options each.

  • True/False portion: 2^{10} possibilities.

  • Multiple-choice portion: 5^{10} possibilities.

  • Total: 2^{10} \cdot 5^{10} = 10^{10}.

• Quick notes and key takeaways

  • Use the sample space and its cardinality to frame counting problems.

  • The Fundamental Counting Principle is the primary workhorse for multi-stage experiments: multiply the numbers of outcomes per stage.

  • Distinguish between fixed-length problems (where field sizes are fixed) and problems with varying numbers of stages (where a tree diagram is especially helpful).

  • Use factorials to simplify products when many stages have consecutive decreasing numbers of options (e.g., ranking or selecting without repetition).

  • When numbers get large, use expansion/cancellation with factorials or apply the FCP directly with exponents.

  • When problems involve restrictions (e.g., first digit nonzero, last digit even), apply those restrictions first in the FCP template to avoid overcounting.

  • The word "or" in counting means sum of disjoint cases; do not double-count.

  • Tree diagrams provide a concrete visual for problems where the number of stages varies or where stopping conditions occur.

• Connections to earlier material

  • Set roster notation and basic set theory from Chapter 2 underpin the concept of a sample space and events.

  • Cartesian product concept explains why multi-dice or multi-step experiments multiply outcomes.

  • Factorials form the backbone of many counting problems involving ordering and selection without repetition.

  • The calculator tips (factorial key, expanding factorials) connect to practical computation in homework and tests.

• Ethical/philosophical/practical implications

  • Counting-based models rely on idealized assumptions (e.g., fair coins, fair dice). Real-world deviations affect outcomes and probabilities.

  • Understanding counting helps in decision making, risk assessment, and designing experiments; miscounting can lead to erroneous conclusions.

• Notation recap (for quick reference)

  • Sample space: S; Cardinality: |S|.

  • Factorial: n!.

  • Fundamental Counting Principle: N = \prod{i=1}^k ni.

  • Example expressions:

  • License plates (A): N = 26^2 \cdot 10^3 = 676000.

  • License plates (B): N = 26 \cdot 25 \cdot 10 \cdot 9 \cdot 8 = 468000.

  • Finalists: 5! = 120.

  • Itinerary: 4! = 24.

  • Three-person committee: 20 \cdot 19 \cdot 18 = 6840.

  • SSN (A): 1 \cdot 4 \cdot 10^7 = 4\times 10^7 = 40{,}000{,}000.

  • SSN (B): 2 \cdot 5^9 = 3{,}906{,}250.

  • Seating problem (6): 2 \cdot 8! \cdot 8! = 3{,}251{,}404{,}800.

  • Three-digit evens (A): 3 \cdot 5 \cdot 4 = 60.

  • Three-digit evens under 200 (B): 1 \cdot 3 \cdot 5 = 15.

  • Geography test: 2^{10} \cdot 5^{10} = 10^{10}.

  • Seven-stage problem: 2^4 \cdot 6^2 \cdot 52 = 29952.

  • Odd numbers between 10 and 500 (digits {1,2,3,6,7}, repetition allowed): total 60.

  • Deluxe car: 48.

  • Five-digit numbers (digits {2,3,4,7,8}, repetition allowed): 5^5 = 3125.

  • Vending machines: 2 \cdot 6! \cdot 3! = 8640.

  • Urn until red/green (problem 6): 10 outcomes.

  • Three-digit even from 1–6 (no repetition): 60.

• Note on arithmetic corrections

  • Some numbers in the transcript contained minor arithmetic inconsistencies (e.g., 60 vs 63, or a large product miswritten). The corrected counts are provided above where applicable.

• Quick practice prompts

  • Use the FCP template to solve: a 6-stage problem with two binary stages and four digits in the middle. Write the counts for each stage and multiply.

  • Draw a tree for a problem that stops when a success occurs (e.g., drawing marbles until a certain color appears) and count the number of stopping paths.

• References to start the exam with confidence

  • Be comfortable identifying the sample space and whether repetition is allowed.

  • Practice expanding factorials and canceling where necessary to avoid overflow.

  • Practice converting word problems into the FCP template and recognizing when a tree diagram is more suitable.