DM-09

Course 9

Counting Principles

Learn systematic techniques for counting: from basic rules to permutations, combinations, and the powerful binomial theorem.

Learning Objectives

Apply the product and sum rules
Calculate permutations
Calculate combinations
Apply the binomial theorem
Use the pigeonhole principle
Handle repetition in counting

1. Basic Counting Rules

Theorem 9.1: The Product Rule

If a procedure can be broken into tasks where task 1 can be done in $n_1$ ways and task 2 can be done in $n_2$ ways, then the entire procedure can be done in $n_1 \times n_2$ ways.

Theorem 9.2: The Sum Rule

If a task can be done in $n_1$ ways or $n_2$ ways (disjoint), then the task can be done in $n_1 + n_2$ ways.

Example: Product and Sum Rules

Product Rule: How many license plates have 3 letters followed by 4 digits?

$26^3 \times 10^4 = 175,760,000$

Sum Rule: Choose one elective from 5 science or 3 humanities courses:

$5 + 3 = 8$ choices

2. Permutations

Definition 9.1: Permutation

A permutation is an ordered arrangement. An r-permutationof n elements is an ordered arrangement of r of these elements.

P(n, r) = \frac{n!}{(n-r)!} = n(n-1)(n-2)\cdots(n-r+1)

Theorem 9.3: Permutations with Repetition

r-permutations of n objects with repetition allowed:

n^r

Theorem 9.4: Permutations of Multisets

Permutations of n objects where there are $n_1$ of type 1, $n_2$ of type 2, etc.:

\frac{n!}{n_1! \cdot n_2! \cdots n_k!}

3. Combinations

Definition 9.2: Combination

An r-combination is an unordered selection of r elements.

\binom{n}{r} = \frac{n!}{r!(n-r)!} = \frac{P(n,r)}{r!}

Theorem 9.5: Combinations with Repetition

Selecting r elements from n types with repetition allowed:

\binom{n+r-1}{r}

4. Binomial Theorem

Theorem 9.6: The Binomial Theorem

(x + y)^n = \sum_{k=0}^{n} \binom{n}{k} x^{n-k} y^k

Theorem 9.7: Pascal's Identity

\binom{n+1}{k} = \binom{n}{k-1} + \binom{n}{k}

5. Pigeonhole Principle

Theorem 9.8: The Pigeonhole Principle

If $k+1$ or more objects are placed into k boxes, then at least one box contains two or more objects.

Theorem 9.9: Generalized Pigeonhole Principle

If N objects are placed into k boxes, then at least one box contains at least $\lceil N/k \rceil$ objects.

Example: Pigeonhole Applications

In 367 people, at least 2 share a birthday
Among any 5 integers, 2 have the same remainder mod 4

Practice Quiz

Counting Principles Quiz

Questions

Correct

Accuracy

How many ways can you arrange 5 different books on a shelf?

Easy

Not attempted

What is

\binom{7}{3}

Easy

Not attempted

If a restaurant offers 4 appetizers, 6 main courses, and 3 desserts, how many different 3-course meals are possible?

Easy

Not attempted

How many 4-digit PINs are possible using digits 0-9 with repetition allowed?

Medium

Not attempted

In how many ways can a committee of 3 be chosen from 8 people?

Medium

Not attempted

According to the Pigeonhole Principle, if 13 people are in a room, at least how many were born in the same month?

Medium

Not attempted

What is the coefficient of

x^3y^2

(x+y)^5

Medium

Not attempted

How many ways can you select 3 items from 5 types with repetition allowed?

Hard

Not attempted

How many permutations are there of the letters in 'MISSISSIPPI'?

Hard

Not attempted

What is

\sum_{k=0}^{n} \binom{n}{k}

Hard

Not attempted

Frequently Asked Questions

When do I use permutations vs combinations?

Permutations: Order matters. "Who finishes 1st, 2nd, 3rd?"

Combinations: Order doesn't matter. "Which 3 people are on the team?"

What does 'with repetition' mean?

Without repetition: Each object used at most once.

With repetition: Objects can be reused.

How do I remember the combination formula?

Think: "permutations divided by duplicate orderings" — $\binom{n}{r} = \frac{P(n,r)}{r!}$

Why is the pigeonhole principle useful?

It proves existence without construction. You can show something must exist without finding the specific example.