Counting Principles: The Fundamental Theorem of Counting

Master counting principles with the fundamental theorem: addition rule, multiplication rule, permutations, combinations through 5 detailed exercises with visual examples and step-by-step solutions.

Solution: Exercises 1 to 3
1 Addition Principle
Exercise 1
A restaurant offers 5 appetizers, 8 main courses, and 4 desserts. If a customer chooses exactly one item from each category, how many different meal combinations are possible?
Definition:

Addition Principle: If events A and B are mutually exclusive, the total number of outcomes is n(A) + n(B). For independent events, use the multiplication principle.

Counting method:
  1. Identify if events are independent (can occur simultaneously) or mutually exclusive (cannot occur simultaneously)
  2. For independent events: use multiplication principle
  3. For mutually exclusive events: use addition principle
  4. Multiply the number of choices in each category
Appetizers
5
Main Courses
8
Desserts
4
Total
5 × 8 × 4
Step 1: Identify the categories

We have 3 independent categories: appetizers, main courses, desserts

Step 2: Determine the number of choices

Appetizers: 5 choices, Main courses: 8 choices, Desserts: 4 choices

Step 3: Apply the multiplication principle

Since these events are independent (we can choose one from each category), we multiply the number of choices: 5 × 8 × 4

Step 4: Calculate the total

5 × 8 × 4 = 40 × 4 = 160

Total meal combinations: 160
Final answer:

There are 160 different possible meal combinations.

Applied rules:

• Multiplication Principle: For independent events, multiply the number of outcomes

• Independent Events: Choosing an appetizer doesn't affect main course choices

• Sequential Decisions: Each choice is made independently of others

2 Multiplication Principle
Exercise 2
A license plate consists of 3 letters followed by 3 digits. How many different license plates are possible if repetition is allowed?
Definition:

Multiplication Principle: If one event can occur in m ways and another independent event can occur in n ways, then both events can occur in m × n ways.

Letter Positions
26 × 26 × 26
Digit Positions
10 × 10 × 10
Total
26³ × 10³
Step 1: Analyze the structure

License plate format: LLL-DDD (3 letters followed by 3 digits)

Step 2: Count choices for each position

Letters: 26 possible choices for each position (A-Z)
Digits: 10 possible choices for each position (0-9)

Step 3: Apply multiplication principle

First letter: 26 ways
Second letter: 26 ways
Third letter: 26 ways
First digit: 10 ways
Second digit: 10 ways
Third digit: 10 ways

Step 4: Calculate total combinations

Total = 26 × 26 × 26 × 10 × 10 × 10 = 26³ × 10³ = 17,576,000

Total license plates: 17,576,000
Final answer:

There are 17,576,000 different possible license plates.

Applied rules:

• Multiplication Principle: Independent choices multiply

• Repetition Allowed: Each position has full range of choices

• Position Independence: Choice for one position doesn't affect others

3 Permutations
Exercise 3
In how many ways can 5 people be seated in a row of 5 chairs?
Definition:

Permutation: An arrangement of objects in a specific order. The number of permutations of n objects taken r at a time is P(n,r) = n!/(n-r)! When arranging all n objects, it's n!

Available Seats
5
People to Seat
5
Arrangements
5!
Step 1: Understand the problem

We need to arrange 5 distinct people in 5 distinct seats (order matters)

Step 2: Apply the permutation principle

First seat: 5 people can sit here
Second seat: 4 remaining people can sit here
Third seat: 3 remaining people can sit here
Fourth seat: 2 remaining people can sit here
Fifth seat: 1 remaining person can sit here

Step 3: Calculate using factorial

Total arrangements = 5 × 4 × 3 × 2 × 1 = 5! = 120

Step 4: Verify the pattern

This follows the general formula for permutations of n objects: n!

Total seating arrangements: 120
Final answer:

There are 120 different ways to seat 5 people in 5 chairs.

Applied rules:

• Permutation Formula: n! for arranging n distinct objects

• Order Matters: Seating position is important

• Distinct Objects: Each person is unique

Counting Principles and Formulas
Addition: n(A ∪ B) = n(A) + n(B) if A ∩ B = ∅
Addition Principle
Multiplication Principle
n(A) × n(B)
For independent events
Permutations
P(n,r) = n!/(n-r)!
Order matters
Combinations
C(n,r) = n!/[r!(n-r)!]
Order doesn't matter
Key Definitions:

Counting: Determining the number of possible outcomes in a sample space

Fundamental Theorem: The foundation of combinatorics: addition and multiplication principles

Permutation: An arrangement where order matters

Combination: A selection where order doesn't matter

Counting Methodology:
  1. Identify the problem type: Addition vs multiplication, permutation vs combination
  2. Determine if order matters: Use permutation if yes, combination if no
  3. Check for repetition: Adjust calculations accordingly
  4. Apply the appropriate formula: Calculate the result
Tip 1: Use addition for "OR" situations (mutually exclusive), multiplication for "AND" situations (independent).
Tip 2: Ask yourself: "Does the order matter?" If yes, use permutations; if no, use combinations.
Tip 3: When repetition is not allowed, the number of choices decreases with each selection.
Tip 4: Always verify your answer makes sense in the context of the problem.
Common errors: Confusing permutations and combinations, forgetting to account for restrictions, mixing up addition and multiplication principles.
Key properties: Permutations consider order, combinations ignore order, both assume distinct objects unless stated otherwise.
Essential Formulas:

• Addition Principle: n(A ∪ B) = n(A) + n(B) for disjoint sets

• Multiplication Principle: n(A × B) = n(A) × n(B) for independent events

• Permutation: P(n,r) = n!/(n-r)!

• Combination: C(n,r) = n!/[r!(n-r)!]

Counting Decision Tree
📊
Decision Steps

1. Are events independent ("AND") or mutually exclusive ("OR")?

2. Does order matter in the outcome?

3. Are repetitions allowed?

Addition Principle

For mutually exclusive events

"OR" situations

n(A ∪ B) = n(A) + n(B)

Multiplication Principle

For independent events

"AND" situations

n(A × B) = n(A) × n(B)

Problem Solving Flow
1
Analyze
2
Classify
3
Apply
4
Verify
Counting Relationships
Permutations > Combinations (since order matters in permutations)
Master Counting Principles!
Solution: Exercises 4 to 5
4 Combination Problem
Exercise 4
A committee of 3 people is to be formed from a group of 8 people. How many different committees are possible?
Definition:

Combination: A selection of objects where order does not matter. C(n,r) = n!/[r!(n-r)!]

Total People
8
Committee Size
3
Formula
C(8,3)
Step 1: Identify the problem type

We're selecting 3 people from 8, and the order doesn't matter (committee member A, B, C is the same as B, A, C)

Step 2: Apply combination formula

C(n,r) = n!/[r!(n-r)!]
C(8,3) = 8!/[3!(8-3)!] = 8!/(3! × 5!)

Step 3: Simplify the calculation

C(8,3) = (8 × 7 × 6 × 5!)/(3! × 5!)
= (8 × 7 × 6)/(3 × 2 × 1)
= 336/6
= 56

Step 4: Verify the result

Using the calculator: C(8,3) = 56 ✓

Total committees: 56
Final answer:

There are 56 different possible committees.

Applied rules:

• Combination Formula: Order doesn't matter, so use C(n,r)

• Factorial Simplification: Cancel common terms in numerator and denominator

• Context Verification: Committee formation doesn't depend on order of selection

5 Complex Counting Problem
Exercise 5
A password consists of 2 letters followed by 3 digits. How many passwords are possible if: (a) repetition is allowed, (b) repetition is not allowed?
Definition:

Complex Counting: Problems requiring multiple applications of counting principles with constraints.

Part (a)
26² × 10³
Part (b)
26 × 25 × 10 × 9 × 8
Step 1: Analyze part (a) - repetition allowed

Structure: LL-DDD
First letter: 26 choices
Second letter: 26 choices (repetition allowed)
First digit: 10 choices
Second digit: 10 choices
Third digit: 10 choices

Step 2: Calculate part (a)

Total = 26 × 26 × 10 × 10 × 10 = 26² × 10³ = 676,000

Step 3: Analyze part (b) - no repetition

First letter: 26 choices
Second letter: 25 choices (one letter already used)
First digit: 10 choices
Second digit: 9 choices (one digit already used)
Third digit: 8 choices (two digits already used)

Step 4: Calculate part (b)

Total = 26 × 25 × 10 × 9 × 8 = 468,000

Part (a): 676,000 | Part (b): 468,000
Final answer:

(a) With repetition: 676,000 passwords possible
(b) Without repetition: 468,000 passwords possible

Applied rules:

• Repetition Effects: When repetition is not allowed, available choices decrease

• Multiplication Principle: Apply to each independent position

• Constraint Handling: Adjust calculations based on given conditions

Comprehensive Counting Principles Guide
P(n,r) = n!/(n-r)! | C(n,r) = n!/[r!(n-r)!]
Permutation vs Combination
Key definitions:

Fundamental Counting Principle: If one event can occur in m ways and a second event can occur in n ways, then the two events can occur in m × n ways.

Addition Principle: If two events A and B are mutually exclusive, then A or B can occur in n(A) + n(B) ways.

Multiplication Principle: If two events A and B are independent, then A and B can occur in n(A) × n(B) ways.

Complete methodology:
  1. Understand the problem: Identify what is being counted and any constraints
  2. Determine if order matters: Use permutations if order matters, combinations if not
  3. Check for repetition: Adjust calculations based on whether items can be repeated
  4. Apply the appropriate principle: Addition for OR situations, multiplication for AND situations
Tip 1: The word "arrange" usually indicates a permutation problem, while "select" or "choose" suggests a combination problem.
Tip 2: When calculating permutations, remember that P(n,n) = n! (arranging all objects).
Tip 3: For problems with restrictions, it's often easier to count the total possibilities and subtract the unwanted ones.
Tip 4: Always consider whether the problem involves "with replacement" or "without replacement".
Common errors: Confusing permutations with combinations, forgetting to adjust for restrictions, misinterpreting "at least" or "at most" conditions.
Key relationships: P(n,r) = C(n,r) × r! (permutations = combinations × arrangements of selected items).
Essential formulas to know:

• Fundamental Principle: For independent events: m × n

• Permutation: P(n,r) = n!/(n-r)!

• Combination: C(n,r) = n!/[r!(n-r)!]

• Relationship: P(n,r) = C(n,r) × r!

• Special case: C(n,r) = C(n, n-r)

Counting Applications and Probability
Advanced Application: Probability Calculations
Counting principles form the foundation for probability calculations. Understanding how to count outcomes is essential for determining probabilities in various scenarios.

Analysis: Counting principles are fundamental to probability theory, statistics, and combinatorial mathematics.

  • Addition: Used for mutually exclusive events (P(A or B) = P(A) + P(B))
  • Multiplication: Used for independent events (P(A and B) = P(A) × P(B))
  • Permutations: Used when order matters in arrangements
  • Combinations: Used when order doesn't matter in selections

Questions & Answers

Question: I'm having trouble knowing when to use permutations versus combinations. How do I decide?

Answer: The key is to ask yourself: "Does the order of selection matter?"

  • Use permutations when order matters: Arranging people in a line, creating passwords, scheduling events
  • Use combinations when order doesn't matter: Selecting committee members, choosing lottery numbers, picking cards from a deck

Example: If you're choosing 3 people from 10 to form a team, it's a combination (the team Alice-Bob-Charlie is the same as Bob-Alice-Charlie). But if you're choosing 3 people from 10 to be president, vice-president, and secretary, it's a permutation (the arrangement matters).

A helpful memory device: "Permutation = Position matters" and "Combination = Collection matters".

Question: How do I know when to use addition versus multiplication in counting problems?

Answer: Think of addition and multiplication in terms of logical operators:

  • Use addition for "OR" situations: When you want to count things that fall into different, non-overlapping categories
  • Use multiplication for "AND" situations: When you're making sequential choices or independent decisions

Example: If you can choose either a sedan OR a truck, and there are 5 sedans and 3 trucks, you have 5 + 3 = 8 choices. But if you're choosing a sedan AND a truck (for different purposes), you have 5 × 3 = 15 combinations.

The addition principle applies to mutually exclusive events, while the multiplication principle applies to independent events.

Question: What's the difference between "with replacement" and "without replacement" in counting problems?

Answer: The difference affects how many choices you have at each step:

  • With replacement: After selecting an item, you put it back, so the number of choices remains the same for each selection
  • Without replacement: After selecting an item, you don't put it back, so the number of choices decreases with each selection

Example: Drawing cards from a deck:
With replacement: You draw a card, note it, put it back, shuffle, then draw again (always 52 choices)
Without replacement: You draw a card and keep it out (52 choices first time, 51 second time, etc.)

Most counting problems assume "without replacement" unless explicitly stated otherwise.

Question: How do I remember the permutation and combination formulas? They look so similar.

Answer: Here are some memory aids for the formulas:

Permutation: P(n,r) = n!/(n-r)!
Think: "Permutation is for Positions (order matters)"
The denominator is (n-r)! to eliminate the extra factorial terms

Combination: C(n,r) = n!/[r!(n-r)!]
Think: "Combination is for Committees (order doesn't matter)"
We divide by r! additionally because the r selected items can be arranged in r! ways

Remember: P(n,r) = C(n,r) × r! - This shows that permutations equal combinations times the arrangements of selected items.

Also, C(n,r) = C(n, n-r) - choosing r items is the same as leaving out (n-r) items.

Question: How are counting principles connected to probability? I see them taught together but don't understand the connection.

Answer: Counting is the foundation of classical probability! The basic probability formula is:

P(Event) = Number of favorable outcomes / Total number of possible outcomes

  • Counting principles help determine the total number of possible outcomes
  • Counting principles help determine the number of favorable outcomes
  • Without accurate counting, probability calculations would be impossible

For example, if you want to find the probability of getting exactly 2 heads in 3 coin flips, you need to count: there are 2³ = 8 total outcomes, and C(3,2) = 3 ways to get exactly 2 heads, so P = 3/8.

This connection makes counting principles essential for understanding probability distributions, statistical inference, and random processes.