Combinatorics

Combinatorics is the branch of mathematics that deals with counting.

It answers questions like:

• How many ways can something happen?
• How many outcomes are possible?
• How many selections or arrangements exist?

Combinatorics is the backbone of probability, competitive exams, computer science, cryptography, and machine learning.

---

Why Combinatorics Is Important

Before calculating probability, we must know how many outcomes exist.

Combinatorics helps us:

• Count outcomes correctly
• Avoid guessing
• Handle complex probability problems
• Design efficient algorithms

Incorrect counting leads to wrong probability.

---

Basic Counting Principle

If an event can happen in m ways and another independent event can happen in n ways, then both events together can happen in:

m × n ways

This is called the Fundamental Counting Principle.

---

Example: Basic Counting

Suppose:

• You have 3 shirts
• You have 2 pants

Total outfits possible:

3 × 2 = 6

This simple rule is used everywhere.

---

Factorial (!)

Factorial is used to count arrangements.

For a positive integer n:

n! = n × (n−1) × (n−2) × … × 1

Also:

0! = 1

---

Example: Factorial

Number of ways to arrange 4 objects:

4! = 4 × 3 × 2 × 1 = 24

Factorials grow very fast.

---

Permutations

A permutation is an arrangement where order matters.

Example:

• Seating arrangements
• Passwords
• Race positions

Changing order creates a new outcome.

---

Permutation Formula

The number of permutations of n objects taken r at a time is:

nP r = n! / (n − r)!

This formula is very important for exams.

---

Example: Permutations

How many ways can we choose 2 students from 5 students where order matters?

5P2 = 5! / 3! = 5 × 4 = 20

---

Permutations of All Objects

If all n objects are arranged:

Number of permutations = n!

Example:

Arranging 6 books on a shelf → 6!

---

Permutations with Repetition

If repetition is allowed:

Number of arrangements = n^r

Example:

• 4-digit PIN using digits 0–9

Total possibilities:

10⁴ = 10000

---

Combinations

A combination is a selection where order does NOT matter.

Example:

• Selecting a team
• Choosing lottery numbers

Order does not create a new outcome.

---

Combination Formula

The number of combinations of n objects taken r at a time is:

nC r = n! / [ r! (n − r)! ]

This is also called a binomial coefficient.

---

Example: Combinations

How many ways can we select 2 students from 5 students?

5C2 = 5! / (2! 3!) = 10

Order does not matter here.

---

Key Difference: Permutation vs Combination

A quick comparison:

Concept	Order Matters?	Example
Permutation	Yes	Seating arrangement
Combination	No	Team selection

---

Combination with Repetition (Idea)

Sometimes selections allow repetition.

Example:

• Choosing candies of the same type multiple times

This is handled using special formulas in advanced combinatorics.

---

Combinatorics in Probability

Probability uses combinatorics to:

• Count favorable outcomes
• Count total outcomes

Probability = favorable / total.

Correct counting is essential.

---

Combinatorics in Competitive Exams

Exams often test:

• Permutation vs combination identification
• Factorial simplification
• Counting logic

One wrong assumption leads to wrong answer.

---

Combinatorics in Computer Science

Computer science uses combinatorics in:

• Algorithm design
• Complexity analysis
• Cryptography

Efficient counting improves performance.

---

Combinatorics in Data Science & ML

Machine learning uses combinatorics in:

• Feature selection
• Model combinations
• Hyperparameter tuning

Search spaces grow combinatorially.

---

Common Mistakes to Avoid

Students often make these mistakes:

• Using permutation instead of combination
• Forgetting factorial simplification
• Ignoring repetition rules

Always ask: Does order matter?

---

Practice Questions

---

Quick Quiz

---

Quick Recap

• Combinatorics is about counting outcomes
• Factorial is used for arrangements
• Permutations → order matters
• Combinations → order does not matter
• Foundation of probability and algorithms

With combinatorics mastered, you are now ready to explore Random Variables, where probability meets numerical values.