Combinatorics: Introduction

Definition

Combinatorics is the study of counting the number of possible arrangements, selections, and configurations of discrete objects under given rules and restrictions.

More specifically, it includes:

Counting

• the number of ways an event can occur

Permutation

• : arranging objects in order

Combination

• : selecting objects without regard to order

Principles of counting

• : rules such as the addition rule and multiplication rule

Discrete structures

• : finite sets, graphs, sequences, and other countable objects

A simple example:

• If 3 books are placed on a shelf, the number of possible arrangements is the number of permutations of 3 items, which is $3! = 6$.

---

Main Content

1. Counting Principles

Counting principles are the basic tools of combinatorics. They help determine the total number of outcomes without writing them all down.

Addition Principle

• If one task can be done in $m$ ways and another mutually exclusive task can be done in $n$ ways, then the total number of ways is $m+n$.
• Example: Choosing a dessert from 3 cakes or 4 ice creams gives $3+4=7$ choices.
• This principle is used when cases do not overlap.

Multiplication Principle

• If one task can be done in $m$ ways and a second independent task can be done in $n$ ways, then both tasks together can be done in $m \times n$ ways.
• Example: If a shirt can be chosen in 5 ways and pants in 4 ways, then an outfit can be formed in $5 \times 4 = 20$ ways.
• This is the foundation for counting multi-step processes.

A useful way to visualize the multiplication principle is a tree-like structure:

Start
├── Shirt 1
│   ├── Pant 1
│   ├── Pant 2
│   └── Pant 3
├── Shirt 2
│   ├── Pant 1
│   ├── Pant 2
│   └── Pant 3
└── Shirt 3
    ├── Pant 1
    ├── Pant 2
    └── Pant 3

This shows how each choice branches into additional choices.

2. Permutations and Arrangements

Permutations are used when order matters. If objects are arranged in a sequence, then changing the order creates a different arrangement.

Permutation of distinct objects

• The number of ways to arrange $n$ distinct objects is $n!$.
• Example: 4 students can be arranged in $4! = 24$ ways.
• Factorial notation means: $$n! = n \times (n-1) \times (n-2) \times \cdots \times 1$$

Permutation of objects taken r at a time

• The number of ways to arrange $r$ objects selected from $n$ distinct objects is: $${}^nP_r = \frac{n!}{(n-r)!}$$

• Example: Choosing president, vice-president, and secretary from 10 people: $${}^{10}P_3 = \frac{10!}{7!} = 10 \times 9 \times 8 = 720$$

• This is used in ranking, seating, scheduling, and ordering problems.

A key idea in permutations is that the position matters:

• ABC is different from ACB
• 123 is different from 132

3. Combinations and Selections

Combinations are used when order does not matter. The focus is on choosing a group rather than arranging it.

Combination of r objects from n objects

• The number of ways to choose $r$ objects from $n$ distinct objects is: $${}^nC_r = \frac{n!}{r!(n-r)!}$$

• Example: Choosing 3 students from 10 for a committee: $${}^{10}C_3 = \frac{10!}{3!7!} = 120$$

• Here, choosing A, B, C is the same as choosing C, B, A because the order is irrelevant.

Relationship between permutations and combinations

• Permutations count arrangements, while combinations count groups.

• They are related by: $${}^nP_r = {}^nC_r \cdot r!$$

• This relationship shows that after choosing a group, the group can be arranged in $r!$ ways.

Combinations are widely used in:

• committee formation
• lottery selection
• sampling in statistics
• probability calculations

---

Working / Process

1. Identify whether order matters

• If order matters, use permutations.
• If order does not matter, use combinations.
• If the problem involves separate stages or choices, use counting principles.

2. Break the problem into simpler steps

• Count each part individually.
• Decide whether the parts are independent or mutually exclusive.
• Apply the addition or multiplication principle as needed.

3. Apply the correct formula and simplify

• Use factorials, permutation formulas, or combination formulas.
• Reduce expressions carefully to avoid arithmetic errors.
• Check whether the final answer is reasonable for the context.

Example workflow:

• Problem: How many ways can 2 books be chosen from 5?
• Order does not matter, so use combinations: $${}^5C_2 = \frac{5!}{2!3!} = 10$$

Another example:

• Problem: How many ways can 2 students be selected and arranged as speaker and assistant from 5 students?
• Order matters, so use permutations: $${}^5P_2 = \frac{5!}{3!} = 20$$

---

Advantages / Applications

Solves counting problems efficiently

• Combinatorics gives exact answers for large problems without listing every possibility.
• This is especially useful when the number of outcomes is huge.

Supports probability and statistics

• Many probability problems require counting favorable outcomes and total outcomes.
• Combinatorics is essential for computing probabilities in cards, dice, selections, and events.

Used in computer science and discrete structures

• Algorithms, coding theory, database design, and network analysis often rely on combinatorial methods.
• In posets and lattices, combinatorial thinking helps analyze ordered sets, chains, antichains, and subsets.

Other important applications include:

• cryptography
• scheduling
• optimization
• data organization
• graph theory
• experimental design

---

Summary

• Combinatorics studies counting, arrangement, and selection of discrete objects.
• It mainly uses counting principles, permutations, and combinations.
• It is essential in solving structured counting problems quickly and accurately.
• Important terms to remember: counting principle, permutation, combination, factorial, arrangement, selection, discrete structure, order matters, order does not matter