Counting: This principle provides a clear and efficient way to

determine every possible outcome when independent choices

come together.
Type of counting:
 The product rule
 The sum rule
 Pigeonhole Principle
 Permutation Principle
 Combination Principle
 Subtraction Rule

(1): The Product Rule:

If a task has several steps and each step has some choices,the
total ways to do the task is found by multiplying the choices of
all [Link] short, just multiply the options at each step to get
the total.

Descriptive example:
1.A boutique hotel has 10 vacant rooms. Two VIP guests, Sara
and Rony, arrive and must each get one room. No room can be
shared. How many ways can the rooms be assigned to them?

Solution:

 Total rooms = 10
 Guests = Sara and Rony
 Each guest must get a different room

We need to find the total number of ways to assign rooms to

both guests.

Sara can be assigned any of the 10 vacant rooms.

 After Sara has choosen her room, 1 room is no longer
available.

Rony can choose from the remaining 9 rooms.

Using the product rule, the total number of ways to assign

rooms is:
Total ways=10×9=90

Hence, the rooms can be assigned to Sara and Rony in 90

different ways.

Illustrative Example: 2
A password is 6 characters long, and each character can be a
digit (0–9). How many passwords contain at least one 0?
Solution:
Each of the 6 positions can be any digit 0–9 → 10 choices per
position.
So, Total = 10^6=1000000.
If no position is 0, each position has 9 choices (1–9).

9^2 =81, 9^3=729, 9^4 =6,561, 9^5 =59,049, 9^6=531,441

Number with no 0 = 9^6. Compute it stepwise:

Number with at least one 0 = Total − (no 0):

=
1,000,000−531,441=468,559.
So, 468,559 Passwords contains at least one 0.

Additional example 1:
A secure lock requires a 6-digit code. Each digit can be from 0
to 9, but no digit can repeat. How many such codes can be
created?

Solution:
In this case there are many ways.

 First digit: 10 choices

 Second digit: 9 choices
 Third digit: 8 choices
 Fourth digit: 7 choices
 Fifth digit: 6 choices
 Sixth digit: 5 choices

Total codes = 10×9×8×7×6×5 = 151,200

Therefore, the total number of 6-digit secure codes without

repetition is 151,200.

Additional example 2:
A conference center has 10 empty conference rooms. Two
keynote speakers, Alex and Sophia, need separate rooms. How
many ways can the rooms be assigned to them?

Solution:

Firstly,Alex arrives first. He can pick any of the 10 rooms,it

doesn’t matter which one. So for Alex, there are 10 possible
choices.

Then,Sophia comes next. She can’t pick the same room Alex
already choose. That leaves 9 remaining rooms for her.

To find the total number of ways both can get rooms, we just
multiply Alex’s choices by Sophia’s choices:

10×9=90
So,there are 90 different ways the two speakers can end up in
separate rooms.

Additional example 3:

A bookstore is creating custom gift packages. Each package

includes 1 book from 6 titles, 1 bookmark from 3 designs, and 1
optional keychain from 4 options (none or exactly one). How
many different gift packages can be created?

Solution:

In this case the task is to get he total package of gift.

Firstly, There are 6 books available, so there are 6 choices for

the book.

Then,There are 3 bookmark designs, so there are 3 choices for

the bookmark.

The keychain is optional. You can choose none (1 way) or

exactly one from 4 options (4 ways).

Total keychain choices=1+4=5

Lastly,Multiply the number of choices for each independent

decision:

6×3×5=90

Therefore,There are 90 different gift packages possible.

(2):The sum Rule:

If there are two or more mutually exclusive tasks, and the first
task can be done in m ways and the second in n ways, then the
total number of ways to perform either task is m+n.

Illustrative problem 1:

An online course platform lists 8 beginner courses, 6

intermediate, and 4 advanced. Intermediate courses require
completion of a specific beginner course which the student
hasn’t taken, so those intermediate courses are unavailable.
How many courses can the student choose now ?

Solution:

Here, the student can choose one course from the following
types:

1. Beginner courses: 8 courses (all available)

2. Intermediate courses: 6 courses (but unavailable because
prerequisites not met)
3. Advanced courses: 4 courses (available)

Since the student can only pick one course, the options are
mutually exclusive—they can choose a beginner course or an
intermediate course or an advanced courses.

Total courses available = (Beginner courses)

(Intermediate courses)+(Advanced courses)

Total courses available = 8+0+4

Total courses available = 12

By the sum rule, the student has 12 courses to choose from.

Illustrative Example 2:

In a computer system, a password can be created in one of two

ways: It can be a 4-digit number (where each digit can be from
0 to 9). Or it can be a 3-letter code (where each letter can be
from A to Z). How many possible passwords are there in total?

Solution:

Here, the two options are mutually exclusive:

 Option 1: 4-digit number

 Option 2: 3-letter code

Option 1: 4-digit number

 Each digit can be 0–9, so 10 choices per digit.

 Number of 4-digit numbers = 10×10×10×10=10^4
=10000

Option 2: 3-letter code

 Each letter can be A–Z, so 26 choices per letter.

 Number of 3-letter codes = 26×26×26= 26^3 =17576.

Total passwords = 10000 + 17576 = 27576

By the sum rule, the total number of possible passwords is:

27,576

Additional example 1:
An online learning platform offers 8 beginner courses, 6
intermediate courses, and 4 advanced courses. Intermediate
courses can only be taken after completing a specific beginner
course, which the student has not yet completed. Additionally,
advanced courses require completion of any two intermediate
courses, but the student is currently unable to take more than
one intermediate course at a [Link] many courses can the
student choose to enroll in at this moment?

Solution:

 Beginner courses: No problem, the student can take all

8 courses.
 Intermediate courses: The required beginner course
hasn’t been done, so the student can’t take any.
 Advanced courses: The student hasn’t completed
enough intermediate courses, so these are also
unavailable.

Here, the options are:

 Beginner courses → 8
 Intermediate courses → 0
 Advanced courses → 0

Add them together:

8+0+0=8
Right now, the student can enroll in 8 courses , all beginner
courses.

Additional Example 2:

In a computer system, a user can create a password in one of

two ways. The first option is a 4-digit number, where each digit
can be from 0 to 9, but the first digit cannot be 0. The second
option is a 3-letter code, where each letter can be from A to Z,
but letters cannot be [Link] many possible passwords
can a user create in total?
Solution:

 First digit: cannot be 0 → choices = 9 (digits 1–9)

 Second digit: can be 0–9 → choices = 10
 Third digit: can be 0–9 → choices = 10
 Fourth digit: can be 0–9 → choices = 10

Now multiply the choices (Fundamental Counting Principle):

4-digit
numbers=9×10×10×10=9000

 First letter: 26 choices (A–Z)

 Second letter: cannot repeat the first → 25 choices
 Third letter: cannot repeat first two → 24 choices

Multiply the choices:

3-letter codes=26×25×24=15600

Total passwords = 4-digit numbers+3-letter codes

= 9000+15600 = 24600

The user can create 24,600 possible passwords in total.

Additional Example 3:

A bakery sells 6 types of bread, 5 types of cakes, and 4 types of

cookies.
Two items are counted as both bread and cake. If a customer
buys exactly one item, how many distinct options are
available?

Solution:

If we ignore the overlap, the total number of items would be:

 6 (bread)+5 (cakes)+4 (cookies)=15

The 2 items that are both bread and cake are double-counted
in the total above.

To avoid double counting, we subtract them once:

15−2=13

Therefore, the customer has 13 distinct options to choose from.

(3)permutation Rule:

The permutation rule states that the number of ways to

arrange r objects out of n distinct objects in a specific order is
give by.

A university is choosing a president, vice-president, secretary,

treasurer, and sports captain from 200 students. In how many
different ways can these 5 positions be filled?

Solution:

In this case the task is to find the choices. The choices are:

President: 200 choices

Vice-President: 199 remaining choices


Secretary: 198 remaining choices



Treasurer: 197 remaining choices



Sports Captain: 196 remaining choices




If we multiply them:

P(200,5)= 200×199×198×197×196

So,the total ways = 304,278,004,800

Finally, there are 304,278,004,800 ways to assign the 5
positions among 200 students.

Illustrative Example 2:

A library is awarding prizes to readers. From 50 students, how

many ways can it select a best reader, a second-best reader,
and a third-best reader?

Solution:

In this case the task is to find the ways of reader. We have:

1. Best reader: 50 choices (any of the 50 students can win)

2. Second-best reader: 49 remaining choices (one student is
already chosen)
3. Third-best reader: 48 remaining choices (two students
are already chosen)

If we multiply them:

P(50,3)=50×49×48 = 117,600

So, there are 117,600 different ways to select a best reader, a

second-best reader, and a third-best reader from 50 students.

Additional example 1:

A talent show has 15 participants. The judges will award gold,

silver, and bronze medals. How many ways can the top 3
winners be chosen?

Solution:

The prizes are distinct (gold, silver, bronze).

  Gold medal: 15 choices (any of the 15 participants)
 Silver medal: 14 remaining choices (one participant
already got gold)
 Bronze medal: 13 remaining choices (two participants
already awarded)

By permutation rule, answer is:

15×14×13 = 2,730

So, there are 2,730 different ways to award the gold,

silver, and bronze medals to 15 participants.

Additional example 2:

An office has 6 desks and 4 new employees. Each employee

must get a different desk. How many ways can the desks be
assigned?

Solution:

In this case the task is to find [Link] have:

1. First employee: 6 choices (any of the 6 desks)

2. Second employee: 5 remaining choices (one desk already
taken)
3. Third employee: 4 remaining choices
4. Fourth employee: 3 remaining choices

By using permutation rule,answer is:

6×5×4×3=360

So, there are 360 different ways to assign 4 employees to 6

desks.
Additional example 3:

A license plate has 2 letters followed by 2 digits. Letters can

be A, B, C, D (4 letters) and digits can be 0, 1, 2, 3, 4 (5 digits).
Letters and digits can be repeated. How many license plates
are possible?

Solution:

In this case the task is to find the license. We have:

 Number of ways to choose letters = 4 × 4 = 16

 Number of ways to choose digits = 5 × 5 = 25

By using permutation repetation rule, the answer is:

Total ways are = 25 × 16 = 400

So, total 400 plates are possible for license.

Additional example 4:

An ice cream shop has 5 flavors (vanilla, chocolate,

strawberry, mango, coffee) and 3 toppings (nuts, chocolate
syrup, sprinkles). A customer can choose one flavor and one
topping, and flavors/toppings can be repeated for different
customers. How many different ice cream choices are
possible?

Solution:

In this case the task is to find the [Link] have:

 Number of flavors = 5
 Number of toppings = 3
By using permutation repetation rule, the answer is:

Total numbers are = 5 × 3= 15

So, total 15 choices ice cream are possible.

Additional example 5:

A lock has 3 distinct digits (0–9) and all must be used. How
many different codes are possible?

Solution:

In this case the task is to find the different [Link] have:

 Number of digits available = 10

 Number of digits in the code = 3

By using permutation all item are taken:

Total arrangements = P(10,3) = 10 × 9 × 8 = 720

So, there will be 720 different codes are possible.

THE PIGEONHOLE PRINCIPLE:

If you have k boxes but more than k objects to put in them,

then at least one box will end up with two or more objects.

Illustrative Example 1:

A math test has scores from 0 to 20. Show that at least two students must
have the same score if the number of students exceeds 22.

Solution:

Given:
Scores range from 0 to 20 , so there are 21 possible scores. To show that at
least two students have the same score,
we've to first find pigeonholes and pigeons from this problem statement.
Here,
Pigeonholes: Possible scores = 0, 1, 2, …, 20 =21 scores
Pigeons: Students taking the test
Step by step explanation:
Suppose we assign scores to students one by one:
• Student 1 → Score 0
• Student 2 → Score 1
• Student 21 → Score 20
Now we have one student left, Student 22, who must receive a score from 0 to
20.
But all 21 scores are already taken. So, Student 22 must get a score that
another student already has.
Appling the Pigeonhole Principle
The Pigeonhole Principle states: If n pigeons are placed into m pigeonholes and
n > m, then at least one pigeonhole must contain more than one pigeon.
Here, n = 22 students, m = 21 scores
Since 22 > 21, at least one score must be shared by at least two students. So, at
least two students must have the same score if the number of students
exceeds 22.
Pigeonhole Generalized Principal:
We can also show using pigeonhole Generalized Principal.
Here,
 Objects N=22N = 22N=22 students.
 Boxes K=21K = 21K=21 scores
Using the generalized principle: at least one box will contain at
least

• This confirms that at least two students must have the same
score
Illustrative Example 2:

Suppose we only use a mini-deck that contains just 8 cards: 2

suits (Hearts and Spades ), each with 4 cards. Cards are drawn
at random.

(a) How many cards must be selected to guarantee that at least

two cards of the same suit are chosen?

(b) How many cards must be selected to guarantee that at

least two hearts are chosen?

Solution:

(a) here,

Pigeonholes: Suits = 2
Pigeons: Cards drawn

Step by step explanation:

Imagine we are putting cards into suit “boxes.”

 Draw card 1 → put it in Hearts box

 Draw card 2 → put it in Spades box

Now all 2 boxes have 1 card each. We keep drawing:

 Draw card 3 → goes into one of the 2 boxes (any suit), that
box now has 2 cards

At this point, one suit has 2 cards, the other has 1 card.
  Draw card 4 → goes into the other box, now both boxes
have 2 cards
 Draw card 5 → no matter which suit this card belongs to, it
must go into a box that already has 2 cards, creating 3
cards in that suit

We used the Pigeonhole Principle:

With 3 pigeons (cards) and 2 pigeonholes (suits), some

pigeonhole must contain at least 2 pigeons (cards).

Pigeonhole Generalized Principle:

Here,

 Target,m = 2
 Boxes, K = 2
 Objects, N = ?

Since we have to find the number of objects, we can apply the

generalized pigeonhole principle:

N = (m−1)×K+1 = (2−1)×2+1 = 3

This means, to be sure of having at least 2 cards of the same

suit, one must draw 3 cards.

(b) here,

Pigeons: Successive cards drawn

Step by step explanation:

Let’s think of the worst-case scenario where the person could

be incredibly unlucky and pull all the non-heart cards first.

Card 1 → Spade
Card 2 → Spade
Card 3 → Spade
Card 4 → Spade
Card 5 → Spade
Card 6 → Spade
Card 7 → Spade
Card 8 → Spade
Card 9 → Spade
Card 10 → Spade
Card 11 → Spade
Card 12 → Spade
Card 13 → Spade
Card 14 → Diamond
Card 15 → Diamond
Card 16 → Diamond
Card 17 → Diamond
Card 18 → Diamond
Card 19 → Diamond
Card 20 → Diamond
Card 21 → Diamond
Card 22 → Diamond
Card 23 → Diamond
Card 24 → Diamond
Card 25 → Diamond
Card 26 → Diamond
Card 27 → Club
Card 28 → Club
Card 29 → Club
Card 30 → Club
Card 31 → Club
Card 32 → Club
Card 33 → Club
Card 34 → Club
Card 35 → Club
Card 36 → Club
Card 37 → Club
Card 38 → Club
Card 39 → Club
Now all 39 non-heart cards are drawn → 0 hearts

Card 40 → 1 of Hearts → total hearts = 1

Total cards picked so far = 39 + 1 = 40 → still less than 2

hearts

Card 41 → 2 of Hearts → total hearts = 2

After drawing 41 cards, you are guaranteed to have at least 2

hearts.

Pigeonhole Generalized Principle:

Here,
We want at least 2 hearts specifically
He has 13 hearts + 39 non-hearts
Total = 52 cards

Objects (pigeons): Cards drawn

Boxes (pigeonholes): Not needed in the same simple way —
we reason by the worst-case (unlucky draws)
Target (k): 2 hearts

We have to make it possible to avoid 2 hearts as long as

possible:

Step by step explanation:

 First pick all the cards without hearts:

Card 1 → Spade
Card 2 → Spade
Card 39 → Club

 Now for card 40:

Pick 1 heart → total hearts = 1 → still less than 2 hearts

 So, card 41 → must be a heart which guarantees at least 2

hearts
To guarantee at least 2 hearts, one must draw 41 cards from a
standard 52-card deck.

Additional Example 1:

A class test has scores from 0 to 25. However, the teacher

decides that no student can score exactly 13. Show that if the
number of students exceeds 26, then at least two students
must have the same score.

Solution:

Scores range from 0 to 25, but the score 13 is not allowed, so

there are 25 possible scores.
To show that at least two students have the same score, we
first find pigeonholes and pigeons from this problem statement.

Here,

Pigeonholes: Possible scores = 0, 1, 2, …, 12, 14, 15, …, 25 =

25 scores
Pigeons: Students taking the test

Step by step explanation:

Suppose we assign scores to students one by one:

 Student 1 → Score 0
 Student 2 → Score 1
 Student 3 → Score 2
 Student 12 → Score 11
 Student 13 → Score 12
 Student 14 → Score 14 (since 13 is forbidden)
  Student 15 → Score 15
 Student 25 → Score 25

Now we have one student left, Student 26, who must receive a
score from the set of 25 possible scores.

But all 25 scores are already taken.

So, Student 26 must get a score that another student already
has.

Applying the Pigeonhole Principle:

The Pigeonhole Principle states: If n pigeons are placed into m

pigeonholes and n > m, then at least one pigeonhole must
contain more than one pigeon.

Here, n = 25 students, m = 25 possible scores

Since 26 >25, at least one score must be shared by at least

two students.

Pigeonhole Generalized Principle:

We can also show this using the generalized form.

Here,

 Objects N = 26 students
 Boxes K = 25 possible scores

Using the generalized principle: at least one box will contain at

least

⌈ 𝑁 / 𝑘 ⌉=⌈ 26 / 25⌉=2

 This confirms that at least two students must have the

same score.

Additional Example 2:
Suppose we have a mini-deck that contains just 6 cards: 2 suits
(Diamonds and Clubs), each with 3 cards. Cards are drawn at
random.

(a) How many cards must be selected to guarantee that at least

two cards of the same suit are chosen?

(b) How many cards must be selected to guarantee that at

least two Diamonds are chosen?

Solution:

(a)

Here,

Pigeonholes: Suits = 2 (Diamonds, Clubs)

Pigeons: Cards drawn

Step by step explanation:

Imagine we are putting cards into suit “boxes.”

 Draw card 1 → put it in Diamonds box

 Draw card 2 → put it in Clubs box

Now both boxes have 1 card each. We keep drawing:

 Draw card 3 → goes into one of the 2 boxes (any suit), that
box now has 2 cards

At this point, one suit has 2 cards, the other has 1 card.

We used the Pigeonhole Principle:

 With 3 pigeons (cards) and 2 pigeonholes (suits), some

pigeonhole must contain at least 2 pigeons (cards).
Pigeonhole Generalized Principle:

Here,

 Target, m = 2
 Boxes, K = 2
 Objects, N =?

To find the number of objects:

N =(m−1)×K+1 = (2−1)×2+1 = 3

To be sure of having at least 2 cards of the same suit, one must

draw 3 cards.

(b)

Here,

Pigeons: Successive cards drawn

Step by step explanation:

Let’s think of the worst-case scenario where the person could

be incredibly unlucky and pull all the non-Diamond cards first.

 Card 1 → Club
 Card 2 → Club
 Card 3 → Club

Now all 3 non-Diamond cards are drawn → 0 Diamonds

 Card 4 → 1 Diamond → total Diamonds = 1 → still less than

2 Diamonds
 Card 5 → 2 Diamonds → total Diamonds = 2

After drawing 5 cards, you are guaranteed to have at least 2

Diamonds.

Pigeonhole Generalized Principle:

Here,

 We want at least 2 Diamonds specifically

 He has 3 Diamonds + 3 non-Diamonds
 Total = 6 cards

Objects (pigeons): Cards drawn

Boxes (pigeonholes): Not needed in the same simple way —
we reason by the worst-case (unlucky draws)
Target (k): 2 Diamonds

We have to make it possible to avoid 2 Diamonds as long as

possible:

Step by step explanation:

1. First pick all the cards without Diamonds:

a. Card 1 → Club
b. Card 2 → Club
c. Card 3 → Club
2. Now for card 4:
a. Pick 1 Diamond → total Diamonds = 1 → still less than
2 Diamonds
3. Card 5 → must be a Diamond, which guarantees at least 2
Diamonds

To guarantee at least 2 Diamonds, one must draw 5 cards from

this mini-deck.