Neural Sync Active

Week 5: Counting Principles & Combinatorics

Registry Synced

Week 5: Counting Principles & Combinatorics

3003 words

15 min read

2026-09-12

Reading compass

Now · TL;DR

Statistics for Data Science I — Week 5: Counting Principles & Combinatorics

IITM’s Week 5 moves into counting methods and factorials, beginning the transition from descriptive statistics toward probability.

TL;DR

Probability often starts with:

\boxed{ P(E)=\frac{\text{number of favorable outcomes}}{\text{number of possible outcomes}} }

when outcomes are equally likely.

So before probability, we need to answer:

How many possible outcomes are there?

The core Week 5 ideas are:

addition principle
multiplication principle
factorial
ordered arrangements
counting without listing everything
avoiding overcounting
complementary counting intuition

1. Why counting matters

Suppose a password has:

2 letters
followed by 3 digits

How many possible passwords exist?

Listing them manually is absurd.

Counting principles let us compute the answer directly.

This becomes essential for probability.

2. Addition principle

If one task can happen in:

m

ways and another mutually exclusive task can happen in:

n

ways, then either task can happen in:

\boxed{m+n}

ways.

3. Example

Suppose you can travel from A to B by:

3 bus routes
2 train routes

If you choose either a bus or train, total choices:

3+2=5.

So:

\boxed{5}

ways.

4. Why mutual exclusivity matters

The addition rule works directly when the options do not overlap.

If some outcome belongs to both groups, simply adding counts double-counts it.

This leads later to inclusion-exclusion ideas.

5. Multiplication principle

If a process has multiple stages:

stage 1 has $m$ choices
for each choice, stage 2 has $n$ choices

then total outcomes:

\boxed{mn}

This is also called the fundamental counting principle.

6. Example

Suppose:

4 shirts
3 pairs of trousers

An outfit consists of one shirt and one trouser.

Total outfits:

4\times3=12.

So:

\boxed{12}

7. Multi-stage version

If stages have:

n_1,n_2,\dots,n_k

choices, total outcomes:

\boxed{ n_1n_2\cdots n_k }

provided each stage proceeds for every earlier valid choice.

8. Example: PIN

A 4-digit PIN uses digits:

0,1,\dots,9.

If repetition is allowed, each position has:

10

choices.

Therefore:

10^4=10000.

9. Example: no repetition

Suppose a 4-digit code uses digits

0

–

9

with no repeated digit.

Choices:

First:

10

Second:

9

Third:

8

Fourth:

7

Total:

10\cdot9\cdot8\cdot7.

Thus:

\boxed{5040}

10. Leading-zero trap

A 4-digit number is different from a 4-digit code.

For a 4-digit number:

first digit cannot be $0$

So if repetition is allowed:

First digit:

9

choices:

1,\dots,9.

Remaining three digits:

10

choices each.

Total:

9\cdot10^3=9000.

11. Factorial

For a positive integer

n

\boxed{ n!=n(n-1)(n-2)\cdots2\cdot1 }

Examples:

5!=5\cdot4\cdot3\cdot2\cdot1=120.

3!=6.

12. Zero factorial

By definition:

\boxed{ 0!=1 }

This may look strange initially, but it makes combinatorial formulas work consistently.

13. Factorial recursion

A useful identity:

\boxed{ n!=n(n-1)! }

Example:

6!=6\cdot5!.

This is often useful for simplification.

14. Simplifying factorial expressions

Example:

\frac{7!}{5!}.

Since:

7!=7\cdot6\cdot5!,

we get:

\frac{7!}{5!} = 7\cdot6 = 42.

Do not expand everything unless necessary.

15. Arranging distinct objects

Suppose there are:

n

distinct objects.

How many ways can they be arranged in a line?

First position:

n

choices.

Second:

n-1.

Continue until:

1.

Therefore:

\boxed{ n! }

16. Example

Arrange four distinct books:

A,B,C,D.

Number of arrangements:

4!=24.

17. Why order matters

Compare:

ABC

and:

BAC.

If arrangements are being counted, these are different outcomes.

So whenever order matters, counting is usually larger.

18. Counting ordered selections

Suppose we choose:

president
vice-president
secretary

from 10 people.

These roles are different.

Choices:

President:

10

Vice-president:

9

Secretary:

8.

Total:

10\cdot9\cdot8=720.

Order/role matters.

19. General ordered selection

Choose and arrange

r

objects from

n

distinct objects.

The count is:

n(n-1)\cdots(n-r+1).

This can be written:

\boxed{ \frac{n!}{(n-r)!} }

This is the permutation formula, which Week 6 develops more explicitly.

20. Example

Choose gold, silver and bronze medalists from 8 finalists.

Gold:

8

Silver:

7

Bronze:

6.

Total:

8\cdot7\cdot6=336.

21. Repetition allowed vs forbidden

This distinction is crucial.

Suppose we create a 3-letter string from 26 letters.

Repetition allowed

Each position:

26

choices.

Total:

26^3.

No repetition

Choices:

26,\ 25,\ 24.

Total:

26\cdot25\cdot24.

22. Decision question

Before counting, ask:

Can an object be used again?

If yes:

\text{choices may stay constant}

If no:

\text{available choices decrease}

This single question prevents many errors.

23. Ordered vs unordered

Another essential question:

Does order matter?

Compare selecting Alice and Bob:

\{A,B\}

with arranging:

(A,B)

and:

(B,A).

For selection:

\{A,B\}=\{B,A\}.

For order-sensitive outcomes:

(A,B)\neq(B,A).

24. Counting tree intuition

For a multi-stage problem, a tree can help.

Suppose first choice:

A,B

and second choice:

1,2,3.

Then:


text
        start
       /     \
      A       B
    / | \   / | \
   1  2  3 1  2  3

There are:

2\cdot3=6

leaves/outcomes.

The multiplication principle is essentially compressed tree counting.

25. Addition vs multiplication

A common distinction:

"OR"

Often suggests addition.

m+n

"AND / then"

Often suggests multiplication.

mn

But do not mechanically rely on words alone; inspect whether options overlap and whether stages are sequential.

26. Example

A student can choose:

one of 4 mathematics electives
or one of 3 physics electives

Total:

4+3=7.

But if they must choose:

one mathematics elective
and one physics elective

total:

4\cdot3=12.

27. Complementary counting

Sometimes it is easier to count what you do not want.

General idea:

\boxed{ \text{desired count} = \text{total count} - \text{undesired count} }

This becomes especially useful in probability.

28. Example

How many 3-digit strings over digits

0

–

9

contain at least one zero?

Total strings:

10^3=1000.

Strings with no zero:

Each position has:

9

choices:

1,\dots,9.

So:

9^3=729.

Therefore strings with at least one zero:

1000-729=271.

Thus:

\boxed{271}

29. "At least one" mental shortcut

Questions involving:

at least one
not all
at least one success

often become easier through complements.

Instead of directly counting many overlapping cases:

\boxed{ \text{at least one} = \text{total} - \text{none} }

30. Inclusion-exclusion intuition

Suppose:

A

and:

B

are two sets of outcomes.

If we add:

|A|+|B|,

anything in both is counted twice.

So:

\boxed{ |A\cup B| = |A|+|B|-|A\cap B| }

This is the basic two-set inclusion-exclusion principle.

31. Example

In a group:

20 know Python
15 know Java
8 know both

How many know at least one?

20+15-8=27.

So:

\boxed{27}

32. Why subtract the intersection?

People in both groups were counted:

once in Python
once in Java

So they were counted twice.

Subtract once to leave exactly one count.

33. Three-set inclusion-exclusion intuition

For three sets:

A,B,C,

the pattern is:

|A\cup B\cup C|

= |A|+|B|+|C|

-|A\cap B|-|A\cap C|-|B\cap C|

+|A\cap B\cap C|.

The final triple intersection is added back because it gets over-subtracted.

34. Distinct vs identical objects

Suppose three balls are:

R,G,B.

They are distinct.

But if all three balls are physically identical, rearranging them does not create new distinguishable outcomes.

Counting depends on what counts as a different outcome.

This is one of the deepest recurring combinatorics questions.

35. Repeated objects

Consider arranging letters:

AAB.

If all letters were treated distinct:

3!=6.

But the two A's are identical.

Actual distinct arrangements:

AAB,\ ABA,\ BAA.

So:

3

arrangements.

The general repeated-object formula comes naturally in permutations.

36. Why naive $3!$ overcounts

Imagine temporarily labeling A's:

A_1,A_2,B.

Then:

A_1A_2B

and:

A_2A_1B

look different under labels.

But after removing labels both become:

AAB.

So each actual arrangement was counted:

2!

times.

Thus:

\frac{3!}{2!}=3.

37. General repeated-object arrangement

If there are

n

objects with repeated groups:

n_1,n_2,\dots,n_k

where:

n_1+\cdots+n_k=n,

then distinct arrangements:

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

This is useful even if permutations are formally emphasized next week.

38. Example: MISSISSIPPI-style logic

Suppose the word is:

AABC.

Total letters:

4.

A appears twice.

Distinct arrangements:

\frac{4!}{2!} = \frac{24}{2} = 12.

39. Circular arrangement intuition

Linear arrangements:

ABC,\ BCA,\ CAB

are different positions in a row.

But around a circle, rotations may represent the same arrangement.

For

n

distinct people around a round table:

\boxed{ (n-1)! }

because we can fix one person's position and arrange everyone else relative to them.

Treat this as supplementary unless your Week 5 lectures explicitly emphasize circular counting.

40. Example: round table

Five people around a circular table:

(5-1)!=4!=24.

In a line:

5!=120.

Different because rotating everyone together does not create a new circular seating.

41. Counting with restrictions

Many problems impose conditions.

Example:

How many 4-digit numbers contain no repeated digits?

First digit:

9

choices.

Second digit:

9

choices because

0

becomes allowed but the first digit is unavailable.

Third:

8.

Fourth:

7.

Total:

9\cdot9\cdot8\cdot7.

So:

\boxed{4536}

42. Restriction-first strategy

When restrictions exist, often count the most constrained position first.

Example:

Arrange 5 people if Alice must sit first.

Alice's position fixed:

1

way.

Remaining four:

4!

ways.

So:

\boxed{24}

43. "Together" problems intuition

Suppose A and B must stay together in a row with C, D, E.

Treat:

AB

as one block.

Then objects are:

[AB],C,D,E

which gives:

4!

arrangements.

Within the block:

AB

or:

BA

gives:

2!

orders.

Total:

4!\cdot2!=48.

44. "Not together" strategy

Often:

\boxed{ \text{not together} = \text{total} - \text{together} }

Again, complementary counting simplifies the problem.

45. Example

Five distinct people arranged in a row.

Total:

5!=120.

A and B together:

4!\cdot2=48.

Therefore A and B not together:

120-48=72.

46. Slots method intuition

Suppose vowels/consonants must alternate.

Instead of trying random arrangements, draw position types first.

Example for:

3 consonants
2 vowels

possible structure:


text
C V C V C

Then arrange consonants in their slots and vowels in theirs.

This slot method is useful for restriction problems.

47. Factorial growth

Factorials grow extremely quickly.

Examples:

5!=120

10!=3,628,800

20!\approx2.43\times10^{18}.

This is why brute-force enumeration becomes impossible surprisingly fast.

48. Counting and probability

Suppose all outcomes are equally likely.

Then:

\boxed{ P(E) = \frac{|E|}{|S|} }

where:

$S$ = sample space
$E$ = event

Counting lets us calculate both numerator and denominator.

Formal probability arrives later, but this is the bridge.

49. Example: die

A standard die has:

6

possible outcomes.

Even outcome set:

\{2,4,6\}

contains:

3.

So:

P(\text{even}) = \frac36 = \frac12.

Here counting is trivial.

For cards/passwords/selections, combinatorics makes the same logic feasible.

50. Sample space

The sample space is the set of all possible outcomes.

Notation commonly:

S

or:

\Omega.

Example: two coin tosses:

S= \{HH,HT,TH,TT\}.

Therefore:

|S|=4.

51. Counting two coin tosses

Each toss has:

2

possibilities.

Two tosses:

2\cdot2=2^2=4.

For

n

independent binary choices:

\boxed{2^n}

possible sequences.

52. Example: three coin tosses

2^3=8

possible ordered sequences.

These are:

HHH,HHT,HTH,HTT,THH,THT,TTH,TTT.

Common mistake: adding sequential choices

Suppose:

5 shirts
4 trousers

Outfits are not:

5+4=9.

You choose one of each, so:

5\cdot4=20.

Common mistake: multiplying alternatives

If you may choose either:

one of 4 buses
or one of 3 trains

you do not multiply:

4\cdot3.

You choose only one mode:

4+3=7.

Common mistake: forgetting order

Choosing two students for a committee:

\{A,B\}

is usually the same committee as:

\{B,A\}.

But choosing:

president = A
vice-president = B

is different from swapping roles.

Always ask:

\boxed{\text{Does order matter?}}

Common mistake: repetition assumption

A password problem may allow repetition unless stated otherwise.

A "choose 3 different students" problem explicitly forbids repetition.

Do not assume one convention for every question.

Common mistake: code vs number

Code:

0123

may be perfectly valid.

Four-digit number:

0123

is actually:

123,

not a 4-digit number.

So the first-position rule differs.

Common mistake: factorial arithmetic

5!

does not mean:

5.

It means:

5\cdot4\cdot3\cdot2\cdot1=120.

Also:

0!=1.

Common mistake: expanding huge factorials

To simplify:

\frac{100!}{98!},

do not calculate

100!

Cancel:

100!=100\cdot99\cdot98!.

So:

\boxed{ \frac{100!}{98!}=100\cdot99=9900 }

Common mistake: double counting

Suppose you count outcomes under two categories and those categories overlap.

Adding directly counts intersection twice.

Use:

|A\cup B| = |A|+|B|-|A\cap B|.

Common mistake: directly counting "at least one"

"At least one" often creates many overlapping cases.

Try the complement first:

\boxed{ \text{at least one} = \text{all} - \text{zero} }

Usually much cleaner.

62. Counting-problem workflow

For almost every Week 5 counting problem, ask in this order:


text
1. What counts as one outcome?
2. Are there stages?
3. Is this OR or AND?
4. Does order matter?
5. Is repetition allowed?
6. Are there restrictions?
7. Are cases mutually exclusive?
8. Would complement be easier?
9. Am I double-counting anything?

This is more useful than memorizing isolated formulas.

63. Formula sheet

Addition principle

For mutually exclusive alternatives:

\boxed{ m+n }

Multiplication principle

For sequential choices:

\boxed{ mn }

Factorial

\boxed{ n!=n(n-1)\cdots1 }

Zero factorial

\boxed{ 0!=1 }

Arrange $n$ distinct objects

\boxed{ n! }

Ordered selection of $r$ from $n$

\boxed{ \frac{n!}{(n-r)!} }

Repeated symbols

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

Two-set inclusion-exclusion

\boxed{ |A\cup B| = |A|+|B|-|A\cap B| }

64. Mental classification map


text
COUNTING PROBLEM
│
├── alternatives?
│      └── add
│
├── sequential stages?
│      └── multiply
│
├── arrange all distinct objects?
│      └── n!
│
├── choose/order only some?
│      └── n!/(n-r)!
│
├── repeated objects?
│      └── divide duplicate permutations
│
└── "at least one" / "not"?
       └── consider complement

65. Weeks 4 → 5 transition

Weeks 1–4 mostly dealt with observed data.

Week 5 starts asking about possible outcomes, whether or not they have occurred.

That is the bridge to probability:

\boxed{ \text{Observed patterns} \rightarrow \text{Possible outcomes} \rightarrow \text{Probability} }

66. What you should actually master

By the end of Stats 1 Week 5, you should be able to:

Use the addition principle.
Use the multiplication principle.
Recognize when to add vs multiply.
Calculate and simplify factorials.
Know: $0!=1.$
Count arrangements of distinct objects.
Count ordered multi-stage choices.
Distinguish order-sensitive from order-insensitive settings conceptually.
Distinguish repetition allowed vs forbidden.
Handle leading-zero restrictions.
Use complementary counting for "at least one."
Avoid double counting.
Use basic inclusion-exclusion.
Count arrangements with repeated identical objects.
Translate a verbal counting problem into a structured sequence of choices.

If those are comfortable, Stats 1 Week 5 is under control.

Quick Recall & Flashcards

Test your active recall before proceeding to practice problems. Format:

Question :: Answer.

Week 5 Diagnostic: A cafeteria offers 4 soups, 5 main courses, and 3 desserts. How many distinct meal combinations (1 soup, 1 main, 1 dessert) can a student choose? :: Answer: 60 — By the Rule of Product: 4 * 5 * 3 = 60.
Week 5 Diagnostic: If 13 pigeons fly into 12 pigeonholes, at least one pigeonhole must contain at least how many pigeons? :: Answer: 2 — By the Pigeonhole Principle, ceil(13 / 12) = 2.

Practice & Self-Check

Attempt these diagnostic questions to verify your operational understanding.

Question 1

A cafeteria offers 4 soups, 5 main courses, and 3 desserts. How many distinct meal combinations (1 soup, 1 main, 1 dessert) can a student choose?

NAT

3 Unit Assessment

Question 2

If 13 pigeons fly into 12 pigeonholes, at least one pigeonhole must contain at least how many pigeons?

NAT

3 Unit Assessment