Counting principles

This chapter introduces the fundamental principles of counting, which are indispensable for quantifying arrangements and selections in discrete mathematics. Mastery of factorials, permutations, and combinations, alongside the multiplication and addition principles, is critical for success in solving a wide array of combinatorial problems frequently encountered in examinations.

---

Chapter Contents

| Topic |

|---|-------| | 1 | Factorials | | 2 | Multiplication principle | | 3 | Addition principle | | 4 | Permutations | | 5 | Combinations |

---

We begin with Factorials.

Part 1: Factorials

Factorials

Overview

Factorials appear everywhere in counting. They give a compact way to write long products such as

\qquad n(n-1)(n-2)\cdots2\cdot1

and they naturally count arrangements of distinct objects. In CMI-style combinatorics, factorials are not just notation; they are tools for simplifying products, counting permutations, and transforming expressions into standard forms. ---

Learning Objectives

❗ By the End of This Topic

After studying this topic, you will be able to:

Define $n!$ correctly and use the convention $0!=1$ .

Simplify factorial expressions efficiently.

Interpret factorials as counting arrangements of distinct objects.

Recognize factorial patterns in permutations and products.

Avoid common algebraic mistakes involving factorial notation.

---

Core Definition

📖 Factorial

For a positive integer $n$ ,

$\qquad n!=n(n-1)(n-2)\cdots3\cdot2\cdot1$

Also, by convention,

$\qquad 0!=1$

---

Basic Identities

📐 Main Factorial Identities

For positive integers $n$ :

$\qquad n!=n\cdot(n-1)!$

$\qquad (n+1)!=(n+1)n!$

$\qquad \dfrac{n!}{(n-r)!}=n(n-1)\cdots(n-r+1)$ for $0\le r\le n$

$\qquad \dfrac{(n+1)!}{n!}=n+1$

---

Why $0!=1$

❗ Why This Convention Matters

From
$\qquad 1!=1\cdot0!$
we must have
$\qquad 0!=1$

This makes the factorial identities and counting formulas consistent.

---

Factorials as Counting

📖 Arrangement Interpretation

The number of ways to arrange $n$ distinct objects in a line is

$\qquad n!$

Reason:

$n$ choices for the first position

$n-1$ for the second

$n-2$ for the third

and so on

So the total number of arrangements is

\qquad n(n-1)(n-2)\cdots1=n!

---

Standard Counting Uses

📐 Common Counting Forms

Number of arrangements of $n$ distinct objects:

\qquad n!

Number of ordered selections of $r$ objects from $n$ distinct objects:

\qquad \dfrac{n!}{(n-r)!}

---

Simplification Strategy

💡 How to Simplify Factorials

When simplifying a factorial expression:

Expand only as much as needed.

Cancel common factors quickly.

\qquad n!=n(n-1)!

repeatedly.

Avoid expanding very large factorials completely unless necessary.

---

Minimal Worked Examples

Example 1 Simplify

\qquad \dfrac{6!}{4!}

Write

\qquad 6!=6\cdot5\cdot4!

\qquad \dfrac{6!}{4!}=30

--- Example 2 How many ways can

5

distinct books be arranged on a shelf? The answer is

\qquad 5!=120

So the number of arrangements is

\boxed{120}

. ---

High-Value Observations

❗ Very Useful Facts

Factorials grow very fast.

$n!$ is defined only for non-negative integers in this school-level setting.

If $1\le k\le n$ , then $k$ divides $n!$ .

Quotients like

\qquad \dfrac{n!}{(n-1)!},\ \dfrac{n!}{(n-2)!}

should be simplified by cancellation, not brute-force expansion.

---

Common Mistakes

⚠️ Avoid These Errors

❌ Thinking $0!=0$

✅ Correct value is

0!=1

❌ Writing $n!+1=(n+1)!$

✅ This is false

❌ Expanding every factorial fully

✅ Expand only enough to cancel

❌ Using factorials for non-integers in basic counting problems

✅ Here factorials are for non-negative integers

---

CMI Strategy

💡 How to Think in Exams

If the expression is a quotient of factorials, cancel structurally.

If the problem involves arranging distinct objects, think of $n!$ immediately.

If only a few terms survive after cancellation, do not expand more than needed.

Always remember the convention $0!=1$ .

---

Practice Questions

:::question type="MCQ" question="The value of

\dfrac{6!}{4!}

is" options=["

15

","

20

","

30

","

60

"] answer="C" hint="Expand only enough to cancel." solution="We write

\qquad 6!=6\cdot5\cdot4!

\qquad \dfrac{6!}{4!}=6\cdot5=30

Hence the correct option is

\boxed{C}

." ::: :::question type="NAT" question="How many ways can

5

distinct books be arranged on a shelf?" answer="120" hint="Arrangements of

n

distinct objects are counted by

n!

." solution="The number of arrangements of

5

distinct objects is

\qquad 5!=120

Therefore the answer is

\boxed{120}

." ::: :::question type="MSQ" question="Which of the following statements are true?" options=["

0!=1

","

(n+1)!=(n+1)n!

","

\dfrac{n!}{(n-2)!}=n(n-1)

for

n\ge2

","

n!+1=(n+1)!

"] answer="A,B,C" hint="Use the basic factorial identities." solution="1. True.

True by definition.

True, because

\qquad n!=n(n-1)(n-2)!

False.

Hence the correct answer is

\boxed{A,B,C}

." ::: :::question type="SUB" question="Simplify

\dfrac{8!}{5!\,3!}

." answer="

56

" hint="Cancel first, then divide by

3!

." solution="Write

\qquad 8!=8\cdot7\cdot6\cdot5!

\qquad \dfrac{8!}{5!\,3!}=\dfrac{8\cdot7\cdot6}{3\cdot2\cdot1}=56

Therefore the answer is

\boxed{56}

." ::: ---

Summary

❗ Key Takeaways for CMI

$n!$ is the product of the first $n$ positive integers.

The convention $0!=1$ is essential.

Factorials count arrangements of distinct objects.

The identity $n!=n(n-1)!$ is the key simplification tool.

Expand only as much as needed when simplifying factorial expressions.

---

💡 Next Up

Proceeding to Multiplication principle.

---

Part 2: Multiplication principle

Multiplication Principle

Overview

The multiplication principle is the most basic and most powerful counting tool in combinatorics. Whenever a task is completed in stages, and each stage has a certain number of choices, the total number of outcomes is usually found by multiplying the numbers of choices stage by stage. In CMI-style problems, this principle appears in passwords, arrangements, digit-formation, path counting, and many disguised counting situations. ---

Learning Objectives

❗ By the End of This Topic

After studying this topic, you will be able to:

Apply the multiplication principle to multi-stage counting problems.

Separate a counting problem into correct stages.

Handle restrictions such as “without repetition” and “first digit cannot be zero”.

Distinguish when multiplication is needed and when addition is needed.

Use the multiplication principle as a foundation for permutations and factorial-based counting.

---

Core Idea

📖 Multiplication Principle

If a process has two stages, where:

the first stage can be done in $m$ ways, and

for each choice of the first stage, the second stage can be done in $n$ ways,

then the total number of ways to perform the whole process is

\qquad m \cdot n

More generally, if a process has stages with

n_1,n_2,\dots,n_k

choices respectively, then the total number of outcomes is

\qquad n_1n_2\cdots n_k

---

Why It Works

❗ Product Structure

The multiplication principle works when the final outcome is formed by making one choice after another.

So if an outcome is built as

stage $1$

then stage $2$

then stage $3$

the total count is found by multiplying the number of valid choices at each stage.

---

Standard Formula

📐 Stage-by-Stage Counting

If there are:

$n_1$ choices for stage $1$

$n_2$ choices for stage $2$

$\dots$

$n_k$ choices for stage $k$

then total number of outcomes is

\qquad n_1n_2\cdots n_k

---

When Repetition Is Allowed

📐 With Repetition

If a symbol can be reused, then the number of choices often stays the same at each stage.

Example:
Number of $4$ -letter strings formed using $5$ letters with repetition allowed:

$\qquad 5^4$

---

When Repetition Is Not Allowed

📐 Without Repetition

If a chosen object cannot be reused, the number of available choices decreases after each stage.

Example:
Number of ways to arrange $4$ distinct books on a shelf:

$\qquad 4\cdot3\cdot2\cdot1=24$

---

Important Restrictions

❗ Common Restrictions

No repetition

The number of choices decreases.

Leading digit cannot be zero

The first stage has fewer choices than the others.

Last digit must satisfy a condition

It is often easier to choose the last stage first.

Certain positions are fixed

Count the fixed stage first, then multiply the remaining choices.

---

Minimal Worked Examples

Example 1 How many

3

-letter codes can be formed from the letters

A,B,C,D

if repetition is allowed? There are

$4$ choices for the first letter

$4$ choices for the second letter

$4$ choices for the third letter

So the total number is

\qquad 4\cdot4\cdot4=64

--- Example 2 How many

3

-digit numbers can be formed from the digits

1,2,3,4

without repetition? There are

$4$ choices for the first digit

$3$ choices for the second digit

$2$ choices for the third digit

So the total number is

\qquad 4\cdot3\cdot2=24

---

Multiplication vs Addition

⚠️ Do Not Mix Them Up

Use the multiplication principle when the task happens in stages.

Use the addition principle when you are choosing between disjoint alternatives.

---

CMI Strategy

💡 How to Attack Counting Problems

Break the task into stages.

Decide the number of valid choices at each stage.

Check whether repetition is allowed.

Check whether any position has a special restriction.

Multiply carefully.

If the problem seems difficult, try choosing the most restricted stage first.

---

Common Mistakes

⚠️ Avoid These Errors

❌ Multiplying when the cases should be added

✅ Multiply only for sequential stages.

❌ Forgetting that repetition is not allowed

✅ Reduce the number of choices after each use.

❌ Allowing zero as the first digit in a number

✅ First digit of a number cannot be zero.

❌ Treating all positions equally when one position has a special condition

✅ Sometimes the last or first position should be chosen first.

---

Practice Questions

:::question type="MCQ" question="How many

3

-digit numbers can be formed from the digits

1,2,3,4

without repetition?" options=["

12

","

24

","

36

","

64

"] answer="B" hint="Choose the digits stage by stage." solution="There are

4

choices for the first digit,

3

for the second, and

2

for the third. So the total number is

\qquad 4\cdot3\cdot2=24

. Hence the correct option is

\boxed{B}

." ::: :::question type="NAT" question="How many

4

-letter strings can be formed from the letters

A,B,C,D,E

if repetition is allowed?" answer="625" hint="Each stage has the same number of choices." solution="At each of the

4

positions, there are

5

choices. Hence the total number of strings is

\qquad 5^4=625

. Therefore the answer is

\boxed{625}

." ::: :::question type="MSQ" question="Which of the following statements are true?" options=["If a task has

3

stages with

2,4,5

choices respectively, then the total number of outcomes is

2\cdot4\cdot5

","If repetition is not allowed, the number of choices may decrease from stage to stage","The multiplication principle is used for disjoint either-or cases","To count

4

-digit numbers, the first digit cannot be zero"] answer="A,B,D" hint="Separate sequential counting from case-wise counting." solution="1. True, by the multiplication principle.

True, because used objects cannot be reused.

False. Disjoint either-or cases are handled by the addition principle.

True. A number cannot begin with zero.

Hence the correct answer is

\boxed{A,B,D}

." ::: :::question type="SUB" question="How many

4

-digit even numbers can be formed from the digits

1,2,3,4,5

without repetition?" answer="

48

" hint="Choose the last digit first." solution="For an even number, the last digit must be

2

4

, so there are

2

choices for the units digit. After fixing the last digit, there are

4

choices for the first digit, then

3

choices for the second digit, and

2

choices for the third digit. So the total number is

\qquad 2\cdot4\cdot3\cdot2=48

Therefore the answer is

\boxed{48}

." ::: ---

Summary

❗ Key Takeaways for CMI

The multiplication principle counts multi-stage processes.

Total count is found by multiplying valid choices at each stage.

Restrictions such as no repetition or no leading zero must be built into the stage count.

Harder counting problems often become easy once the stages are chosen correctly.

The multiplication principle is the basis for permutations, factorials, and many later counting formulas.

---

💡 Next Up

Proceeding to Addition principle.

---

Part 3: Addition principle

Addition Principle

Overview

The addition principle is the first major rule of counting. It is used when a task can happen through different non-overlapping cases, and the total number of ways is the sum of the counts of those cases. In CMI-style counting, the main difficulty is not the formula itself, but checking whether the cases are really disjoint. ---

Learning Objectives

❗ By the End of This Topic

After studying this topic, you will be able to:

State and apply the addition principle correctly.

Recognize when cases are mutually exclusive.

Split a counting problem into clean non-overlapping cases.

Distinguish addition principle from multiplication principle.

Avoid double counting when cases overlap.

---

Core Idea

📖 Addition Principle

If a task can be done in:

$m$ ways by one method

$n$ ways by another method

and the two methods cannot happen together, then the total number of ways is

\qquad m+n

More generally, if a task can be done through several mutually exclusive cases, then the total number of ways is the sum of the numbers of ways in those cases.

❗ Key Condition

The cases must be disjoint.

If the same outcome is counted in two different cases, then simple addition gives overcounting.

---

Addition vs Multiplication

📐 Do Not Mix These Up

Addition principle: choose one case out of different disjoint cases

Multiplication principle: perform one step and then another step

Examples:

choosing a card that is either a king or a queen $\rightarrow$ add

choosing a shirt and then a trouser $\rightarrow$ multiply

---

Standard Examples

Example 1 How many integers from

1

100

are divisible by

2

or equal to

99

? Numbers divisible by

2

from

1

100

\qquad 50

Also

99

is not divisible by

2

, so it gives one extra number. Total:

\qquad 50+1=51

So the answer is

\boxed{51}

. --- Example 2 A student can choose either a Mathematics book from

5

books or a Physics book from

3

books. In how many ways can the student choose one book? These are disjoint choices:

choose a Mathematics book: $5$ ways

choose a Physics book: $3$ ways

So total ways:

\qquad 5+3=8

Hence the answer is

\boxed{8}

. ---

When Addition Principle Applies

💡 Use It When

Use the addition principle when:

the word “or” appears in a counting problem

the valid outcomes are split into separate cases

each final outcome belongs to exactly one case

one choice is made from one among several categories

---

When It Does Not Apply Directly

⚠️ Overlapping Cases

If two cases overlap, then simple addition is wrong.

For two sets $A$ and $B$ ,
$\qquad |A\cup B|=|A|+|B|-|A\cap B|$

So when cases overlap, subtract the overlap.

This is the beginning of the inclusion-exclusion idea. ---

Casework Structure

📐 Counting by Cases

If a problem can be split into disjoint cases $C_1,C_2,\dots,C_k$ , then

$\qquad \text{Total count} = N(C_1)+N(C_2)+\cdots+N(C_k)$

Common case splits:

even / odd

contains a fixed element / does not contain it

first digit chosen from one set / first digit chosen from another set

exactly $0,1,2,\dots$ objects of a certain type

::: ---

Minimal Worked Examples

Example 3 How many positive integers less than

100

are either one-digit or multiples of

10

? One-digit positive integers:

\qquad 9

Multiples of

10

less than

100

\qquad 10,20,\dots,90

so there are

\qquad 9

such numbers. These two cases are disjoint, so total:

\qquad 9+9=18

Hence the answer is

\boxed{18}

. --- Example 4 How many letters in the English alphabet are vowels or consonants? Vowels:

\qquad 5

Consonants:

\qquad 21

Since every letter is exactly one of these, total:

\qquad 5+21=26

---

Common Mistakes

⚠️ Avoid These Errors

❌ Adding counts of overlapping cases directly

✅ First check whether the cases overlap

❌ Using addition where multiplication is needed

✅ Ask: is this “one case or another case”, or “first step then second step”?

❌ Poor case splitting

✅ Cases must cover all possibilities and be disjoint

❌ Missing one of the cases

✅ Write the case structure explicitly before counting

---

CMI Strategy

💡 How to Attack Addition Principle Problems

Search for the word “or”.

Split the problem into cases.

Check that the cases do not overlap.

Count each case separately.

Add the counts.

If overlap exists, subtract the repeated count.

---

Practice Questions

:::question type="MCQ" question="A number is chosen from the set

\{1,2,3,4,5,6,7,8,9\}

. The number of ways to choose an even number or the number

7

is" options=["

4

","

5

","

6

","

7

"] answer="B" hint="Count disjoint cases." solution="Even numbers are

2,4,6,8

, so there are

4

choices. Also

7

is one extra choice and is not even. Hence total ways are

\qquad 4+1=5

So the correct option is

\boxed{B}

." ::: :::question type="NAT" question="A student can choose either one of

6

pens or one of

4

pencils. In how many ways can the student choose one item?" answer="10" hint="Use the addition principle." solution="Choose a pen in

6

ways or a pencil in

4

ways. These cases are disjoint. So the total number of ways is

\qquad 6+4=10

Hence the answer is

\boxed{10}

." ::: :::question type="MSQ" question="Which of the following statements are true?" options=["If two cases are disjoint, total count is the sum of the counts","Addition principle is usually used when the word 'or' appears","If cases overlap, simple addition may overcount","Addition principle and multiplication principle are always the same"] answer="A,B,C" hint="Think about disjoint case counting." solution="1. True.

True.

True, because overlap causes repeated counting.

False, since addition and multiplication apply in different situations.

Hence the correct answer is

\boxed{A,B,C}

." ::: :::question type="SUB" question="How many integers from

1

20

are either odd or divisible by

4

?" answer="

15

" hint="Split into disjoint cases." solution="Odd integers from

1

20

\qquad 1,3,5,\dots,19

so there are

\qquad 10

such numbers. Integers divisible by

4

from

1

20

\qquad 4,8,12,16,20

so there are

\qquad 5

such numbers. These two cases are disjoint because no multiple of

4

is odd. Therefore the total count is

\qquad 10+5=15

Hence the answer is

\boxed{15}

." ::: ---

Summary

❗ Key Takeaways for CMI

The addition principle counts outcomes split into disjoint cases.

The total is the sum of the counts of those cases.

The most important check is whether the cases overlap.

“Or” often suggests addition, while “and then” usually suggests multiplication.

Clean casework is the heart of successful basic counting.

---

💡 Next Up

Proceeding to Permutations.

---

Part 4: Permutations

Permutations

Overview

A permutation is an arrangement in which order matters. This topic is one of the foundations of counting, and it appears in direct counting, restricted arrangements, ranking arguments, and word problems. In CMI-style questions, the key is to separate selection from arrangement and to know when factorial language is the correct model. ---

Learning Objectives

❗ By the End of This Topic

After studying this topic, you will be able to:

Distinguish between combinations and permutations.

Count arrangements of all objects and arrangements of selected objects.

Use factorial notation efficiently.

Solve restricted permutation problems using blocks or complements.

Handle arrangements with repeated identical objects when needed.

---

Core Idea

📖 What is a permutation?

A permutation is an arrangement in which the order of objects matters.

Examples:

arranging books on a shelf

assigning ranks

forming ordered strings without repetition

arranging letters in a word

If order matters, think permutation. If order does not matter, think combination. ---

Factorial Notation

📐 Factorial

For a positive integer $n$ ,

$\qquad n! = n(n-1)(n-2)\cdots 2\cdot 1$

Also,

$\qquad 0! = 1$

Some useful values:

$1! = 1$

$2! = 2$

$3! = 6$

$4! = 24$

$5! = 120$

---

Permutations of Distinct Objects

📐 All Objects Arranged

The number of ways to arrange $n$ distinct objects in a row is

$\qquad n!$

📐 Arranging

r

n

Distinct Objects

The number of ways to choose and arrange $r$ objects from $n$ distinct objects is

$\qquad {}^nP_r = \dfrac{n!}{(n-r)!}$

Reason:

first place: $n$ choices

second place: $n-1$ choices

continue until $r$ places are filled

::: ---

Selection Versus Arrangement

❗ The Most Important Distinction

If a problem asks:

“which objects?” → selection

“in what order?” → arrangement

A permutation often has two parts:

choose the objects

arrange them

For example, arranging 3 of 5 distinct books:

\qquad \binom{5}{3}\cdot 3! = {}^5P_3 = 60

This identity is extremely useful:

\qquad {}^nP_r = \binom{n}{r}r!

::: ---

Restricted Permutations

💡 Method 1: Block Method

If two or more objects must stay together, treat them as one block first.

Example:
Arrange $A,B,C,D$ with $A$ and $B$ together.

Treat $(AB)$ as one unit along with $C,D$ :
$\qquad 3!$ ways

Inside the block, $A,B$ can switch:
$\qquad 2!$ ways

Total:
$\qquad 3!\cdot 2! = 12$

💡 Method 2: Complement Method

If two objects must not be together, count:

$\qquad \text{total arrangements} - \text{arrangements with them together}$

This is often faster than direct casework. ---

Repeated Objects

📐 Permutations with Identical Objects

If among $n$ total objects,

$a_1$ are identical of one kind

$a_2$ are identical of another kind

etc.

then the number of distinct arrangements is

\qquad \dfrac{n!}{a_1!a_2!\cdots a_k!}

Example: Arrangements of the word LEVEL: There are

5

letters with

L

repeated

2

times and

E

repeated

2

times. So the number of distinct arrangements is

\qquad \dfrac{5!}{2!2!} = 30

::: ---

Standard Patterns

📐 High-Value Permutation Forms

Arrangements of all distinct objects:

\qquad n!

Arrangements of $r$ selected from $n$ :

\qquad {}^nP_r

Two specified objects together:

use blocks

Two specified objects not together:

total minus together

Repeated letters:

divide by factorials of multiplicities

---

Minimal Worked Examples

Example 1 How many ways can 5 distinct students stand in a line?

\qquad 5! = 120

--- Example 2 How many ways can 3 out of 6 distinct books be arranged on a shelf?

\qquad {}^6P_3 = \dfrac{6!}{3!} = 6\cdot 5\cdot 4 = 120

---

Common Mistakes

⚠️ Avoid These Errors

❌ Using combinations when order matters

✅ Use permutations if arrangement is important

❌ Using $n!$ when only $r$ positions are being filled

✅ Use

{}^nP_r

❌ Forgetting internal arrangement inside a block

✅ If objects are grouped, arrange both the block and its contents

❌ Forgetting to divide by repeated identical objects

✅ Use multiset arrangement formula when objects are identical

---

CMI Strategy

💡 How to Attack Permutation Problems

First ask: are all objects used, or only some of them?

Then ask: are all objects distinct?

If a restriction says “together”, use a block.

If a restriction says “not together”, use complement.

If repeated letters appear, divide by factorials of multiplicities.

---

Practice Questions

:::question type="MCQ" question="The number of ways to arrange 4 distinct books on a shelf is" options=["

4

","

12

","

24

","

16

"] answer="C" hint="All 4 distinct objects are arranged." solution="The number of arrangements of 4 distinct objects in a row is

\qquad 4! = 24

. Hence the correct option is

\boxed{C}

." ::: :::question type="NAT" question="Find

{}^5P_3

." answer="60" hint="Use the formula

{}^nP_r=\dfrac{n!}{(n-r)!}

." solution="Using the permutation formula,

\qquad {}^5P_3=\dfrac{5!}{(5-3)!}=\dfrac{5!}{2!}=5\cdot 4\cdot 3=60

. Hence the answer is

\boxed{60}

." ::: :::question type="MSQ" question="Which of the following statements are true?" options=["The number of permutations of

n

distinct objects is

n!

","

{}^nP_r=\binom{n}{r}r!

","If two specified objects must be together, block method is often useful","The number of arrangements of the letters of the word AAB is

3!

"] answer="A,B,C" hint="Watch the repeated-letter case carefully." solution="1. True.

True.

False. Since two A's are identical, the number is

\dfrac{3!}{2!}=3

Hence the correct answer is

\boxed{A,B,C}

." ::: :::question type="SUB" question="How many arrangements of the letters of the word LEVEL are possible?" answer="

30

" hint="Use the repeated-object formula." solution="The word LEVEL has 5 letters in total. Here:

$L$ repeats 2 times

$E$ repeats 2 times

$V$ occurs once

So the number of distinct arrangements is

\qquad \dfrac{5!}{2!2!}=\dfrac{120}{4}=30

Therefore the answer is

\boxed{30}

." ::: ---

Summary

❗ Key Takeaways for CMI

Permutations are arrangements where order matters.

Arrange all distinct objects using $n!$ .

Arrange $r$ of $n$ distinct objects using ${}^nP_r$ .

Use block method for “together” restrictions.

Use complement for “not together” restrictions.

Use division by factorials when identical repeated objects appear.

---

💡 Next Up

Proceeding to Combinations.

---

Part 5: Combinations

Combinations

Overview

Combinations are used when we need to select objects without caring about order. This topic is one of the most important counting tools because many harder counting problems reduce to choosing positions, choosing people, or choosing subsets. In CMI-style problems, the real test is not the formula itself, but knowing when order matters and when it does not. ---

Learning Objectives

❗ By the End of This Topic

After studying this topic, you will be able to:

Recognize when a problem is a combinations problem.

Use the formula for $^nC_r$ correctly.

Distinguish combinations from permutations.

Apply symmetry and standard identities to simplify counting.

Solve medium-level selection and committee questions cleanly.

---

Core Idea

📖 What is a Combination?

A combination is a selection of objects where order does not matter.

For example, choosing the team $\{A,B,C\}$ is the same as choosing $\{C,A,B\}$ .

So combinations count selections, not arrangements.

📐 Combination Formula

The number of ways to choose $r$ objects from $n$ distinct objects is

$\qquad {^nC_r} = \dfrac{n!}{r!(n-r)!}$

where $0 \le r \le n$ .

---

Why the Formula Works

If we first arrange

r

objects from

n

, we get

\qquad {^nP_r} = \dfrac{n!}{(n-r)!}

But in each group of

r

selected objects, the

r!

internal orders are all counted separately. So,

\qquad {^nC_r} = \dfrac{{^nP_r}}{r!} = \dfrac{n!}{r!(n-r)!}

❗ Main Principle

Permutation = selection with order

Combination = selection without order

---

Standard Values

📐 Useful Values

${^nC_0}=1$

${^nC_1}=n$

${^nC_n}=1$

${^nC_{n-1}}=n$

${^nC_r}=0$ if $r>n$

📐 Symmetry

$\qquad {^nC_r} = {^nC_{n-r}}$

Choosing $r$ objects to include is the same as choosing $n-r$ objects to exclude.

---

Pascal Identity

📐 Pascal Identity

$\qquad {^nC_r} = {^{n-1}C_r} + {^{n-1}C_{r-1}}$

Reason:
Take one special object. A selection of $r$ objects either:

does not contain it, giving ${^{n-1}C_r}$ possibilities

contains it, giving ${^{n-1}C_{r-1}}$ possibilities

This is one of the most useful identities in combinatorics. ---

Typical Situations Where Combinations Appear

💡 When to Think Combination

Use combinations when the task says:

choose

select

form a committee

pick a subset

choose positions for identical objects

choose which cases happen

and the final outcome does not depend on order.

---

Minimal Worked Examples

Example 1 How many ways are there to choose

3

students from

8

students?

\qquad {^8C_3} = \dfrac{8!}{3!5!} = \dfrac{8\cdot7\cdot6}{3\cdot2\cdot1}=56

So the answer is

\boxed{56}

. --- Example 2 How many diagonals does a polygon with

8

vertices have? Choose any

2

vertices to form a segment:

\qquad {^8C_2}=28

But

8

of these are sides. So number of diagonals is

\qquad 28-8=20

Hence the answer is

\boxed{20}

. ---

Common Patterns

📐 High-Frequency Forms

Choosing $r$ people from $n$ :

\qquad {^nC_r}

Choosing positions of identical objects among total places:

choose the positions of one type, then the rest are fixed

Committee with restrictions:

split into valid cases, then use combinations in each case

Choosing at least / at most:

sum several combination values

---

Common Mistakes

⚠️ Avoid These Errors

❌ Using permutations when order does not matter

✅ Divide by repeated ordering or use combinations directly

❌ Forgetting symmetry

✅ Sometimes

{^nC_{n-r}}

is easier than

{^nC_r}

❌ Treating identical objects as distinct

✅ If objects are identical, combinations often count positions, not labels

❌ Missing restrictions like “at least one” or “exactly two”

✅ Break into cases carefully

---

CMI Strategy

💡 How to Attack Combination Problems

Decide first whether order matters.

If order does not matter, think ${^nC_r}$ immediately.

Use symmetry when it simplifies the arithmetic.

For restrictions, split the problem into clean cases.

For geometric or word problems, convert the situation into a selection problem.

---

Practice Questions

:::question type="MCQ" question="The number of ways to choose

2

students from

7

students is" options=["

14

","

21

","

42

","

49

"] answer="B" hint="Use

{^nC_r}

." solution="We need the number of ways to choose

2

from

7

\qquad {^7C_2}=\dfrac{7\cdot6}{2}=21

So the correct option is

\boxed{B}

." ::: :::question type="NAT" question="Find the value of

{^9C_8}

." answer="9" hint="Use symmetry." solution="By symmetry,

\qquad {^9C_8}={^9C_1}=9

Hence the answer is

\boxed{9}

." ::: :::question type="MSQ" question="Which of the following statements are true?" options=["

{^nC_0}=1

","

{^nC_r}={^nC_{n-r}}

","

{^nC_1}=1

","

{^nC_n}=1

"] answer="A,B,D" hint="Recall standard identities." solution="1. True.

True by symmetry.

False, since

{^nC_1}=n

True.

Hence the correct answer is

\boxed{A,B,D}

." ::: :::question type="SUB" question="How many committees of

4

can be formed from

10

people?" answer="

210

" hint="Order does not matter." solution="A committee is a selection, so we use combinations:

\qquad {^{10}C_4}=\dfrac{10!}{4!6!}=\dfrac{10\cdot9\cdot8\cdot7}{4\cdot3\cdot2\cdot1}=210

Therefore the answer is

\boxed{210}

." ::: ---

Summary

❗ Key Takeaways for CMI

Combinations count selections where order does not matter.

The main formula is $\qquad {^nC_r}=\dfrac{n!}{r!(n-r)!}$ .

Symmetry ${^nC_r}={^nC_{n-r}}$ is extremely useful.

Many counting problems are combinations in disguise.

The main skill is recognizing when the situation is about selection, not arrangement.

---

Chapter Summary

❗ Counting principles — Key Points

Fundamental Principles: The Multiplication Principle applies when tasks are sequential, while the Addition Principle is used for mutually exclusive alternative tasks. These form the bedrock of all combinatorial counting.

Factorials: $n!$ represents the number of distinct arrangements (permutations) of $n$ unique items, serving as a basis for more complex permutation calculations.

Permutations: $P(n, k) = \frac{n!}{(n-k)!}$ calculates the number of ordered arrangements of $k$ items selected from $n$ distinct items, where the sequence of selection matters.

Combinations: $C(n, k) = \binom{n}{k} = \frac{n!}{k!(n-k)!}$ calculates the number of unordered selections of $k$ items from $n$ distinct items, where the sequence of selection does not matter.

Distinction is Key: A critical step in solving counting problems is to correctly identify whether order is important (permutations) or not (combinations), often by careful reading of the problem statement.

Repetitions and Restrictions: Techniques exist to handle permutations with identical items (e.g., dividing by factorials of counts of repeated items) and combinations with replacement, as well as problems with specific constraints or conditions.

Systematic Problem Solving: Complex counting scenarios often require breaking down the problem into smaller, manageable parts, applying the appropriate principle(s) to each part, and then combining the results using the Multiplication or Addition Principle.

---

Chapter Review Questions

:::question type="MCQ" question="How many distinct 4-letter codes can be formed using the letters A, B, C, D, E, F if no letter can be repeated?" options=["120","360","720","1440"] answer="360" hint="Consider the number of choices for each position sequentially, or use the permutation formula." solution="This is a permutation problem since the order of letters in the code matters, and letters cannot be repeated. We need to choose 4 letters from 6 distinct letters and arrange them.
The number of ways to choose the first letter is 6.
The number of ways to choose the second letter is 5 (since one letter is already used).
The number of ways to choose the third letter is 4.
The number of ways to choose the fourth letter is 3.
Using the Multiplication Principle, the total number of codes is $6 \times 5 \times 4 \times 3 = 360$ .
Alternatively, using the permutation formula: $P(6, 4) = \frac{6!}{(6-4)!} = \frac{6!}{2!} = \frac{720}{2} = 360$ ."
:::

:::question type="NAT" question="A committee of 3 men and 2 women is to be formed from a group of 7 men and 5 women. How many different committees can be formed?" answer="350" hint="Committees are unordered selections. Calculate the number of ways to choose men and women separately, then combine." solution="This problem involves combinations because the order in which individuals are chosen for a committee does not matter.
Number of ways to choose 3 men from 7 men: $C(7, 3) = \binom{7}{3} = \frac{7!}{3!(7-3)!} = \frac{7 \times 6 \times 5}{3 \times 2 \times 1} = 35$ .
Number of ways to choose 2 women from 5 women: $C(5, 2) = \binom{5}{2} = \frac{5!}{2!(5-2)!} = \frac{5 \times 4}{2 \times 1} = 10$ .
Since the selection of men and women are independent tasks, we use the Multiplication Principle to find the total number of committees: $35 \times 10 = 350$ ."
:::

:::question type="MCQ" question="How many distinct arrangements can be made from the letters of the word 'MISSISSIPPI'?" options=["11520","34650","69300","77760"] answer="34650" hint="This is a permutation with repetition problem. Identify the total number of letters and the frequency of each distinct letter." solution="The word 'MISSISSIPPI' has 11 letters in total.
Let's count the frequency of each distinct letter:
M: 1
I: 4
S: 4
P: 2
The formula for permutations with repetition is $\frac{n!}{n_1! n_2! \dots n_k!}$ , where $n$ is the total number of items, and $n_i$ is the frequency of each distinct item.
Number of distinct arrangements = $\frac{11!}{1! \times 4! \times 4! \times 2!} = \frac{39,916,800}{1 \times 24 \times 24 \times 2} = \frac{39,916,800}{1152} = 34,650$ ."
:::

:::question type="NAT" question="From a group of 10 students (6 boys, 4 girls), a team of 5 is to be chosen. How many teams can be formed if there must be at least 3 boys?" answer="186" hint="Break this into mutually exclusive cases based on the number of boys, then sum the results." solution="The condition 'at least 3 boys' means we can have teams with 3 boys, 4 boys, or 5 boys. The remaining members of the team will be girls.
Case 1: 3 boys and 2 girls
Number of ways to choose 3 boys from 6: $C(6, 3) = \binom{6}{3} = \frac{6 \times 5 \times 4}{3 \times 2 \times 1} = 20$ .
Number of ways to choose 2 girls from 4: $C(4, 2) = \binom{4}{2} = \frac{4 \times 3}{2 \times 1} = 6$ .
Total for Case 1: $20 \times 6 = 120$ .

Case 2: 4 boys and 1 girl
Number of ways to choose 4 boys from 6: $C(6, 4) = \binom{6}{4} = \frac{6 \times 5}{2 \times 1} = 15$ .
Number of ways to choose 1 girl from 4: $C(4, 1) = \binom{4}{1} = 4$ .
Total for Case 2: $15 \times 4 = 60$ .

Case 3: 5 boys and 0 girls
Number of ways to choose 5 boys from 6: $C(6, 5) = \binom{6}{5} = 6$ .
Number of ways to choose 0 girls from 4: $C(4, 0) = \binom{4}{0} = 1$ .
Total for Case 3: $6 \times 1 = 6$ .

Since these cases are mutually exclusive, we sum the results to find the total number of teams: $120 + 60 + 6 = 186$ ."
:::

---

What's Next?

💡 Continue Your CMI Journey

Having mastered the fundamental counting principles, you are now equipped to tackle more advanced topics in combinatorics and discrete mathematics. These foundational techniques are indispensable for understanding Probability Theory, where calculating favorable outcomes and total sample spaces relies heavily on permutations and combinations. Furthermore, they serve as a prerequisite for exploring concepts in Graph Theory (e.g., counting paths, cycles), Discrete Probability Distributions, and the development of Recurrence Relations and Generating Functions, which offer sophisticated methods for solving complex counting problems and analyzing sequences.

Counting principles

Counting principles

Chapter Contents

| Topic |

Part 1: Factorials

Factorials

Overview

Learning Objectives

Core Definition

Basic Identities

Why 0!=10!=10!=1

Factorials as Counting

Standard Counting Uses

Simplification Strategy

Minimal Worked Examples

High-Value Observations

Common Mistakes

CMI Strategy

Practice Questions

Summary

Part 2: Multiplication principle

Multiplication Principle

Overview

Learning Objectives

Core Idea

Why It Works

Standard Formula

When Repetition Is Allowed

When Repetition Is Not Allowed

Important Restrictions

Minimal Worked Examples

Multiplication vs Addition

CMI Strategy

Common Mistakes

Practice Questions

Summary

Part 3: Addition principle

Addition Principle

Overview

Learning Objectives

Core Idea

Addition vs Multiplication

Standard Examples

When Addition Principle Applies

When It Does Not Apply Directly

Casework Structure

Minimal Worked Examples

Common Mistakes

CMI Strategy

Practice Questions

Summary

Part 4: Permutations

Permutations

Overview

Learning Objectives

Core Idea

Factorial Notation

Permutations of Distinct Objects

Selection Versus Arrangement

Restricted Permutations

Repeated Objects

Standard Patterns

Minimal Worked Examples

Common Mistakes

CMI Strategy

Practice Questions

Summary

Part 5: Combinations

Combinations

Overview

Learning Objectives

Core Idea

Why the Formula Works

Standard Values

Pascal Identity

Typical Situations Where Combinations Appear

Minimal Worked Examples

Common Patterns

Common Mistakes

CMI Strategy

Why $0!=1$