Notes/Discrete Structures/Counting.md

---
type: theoretical
---

# Key Concepts

## Permutations

A permutation is an arrangement of objects in a specific order.

- Without Repetition[^1]: The number of permutations of $n$ distinct objects taken $r$ at a time is denoted by $nP_r$ and calculated as:
  Let f (n) = 7n + 3n2 + n2n and g(n) = 3n  
n . Prove that f (n) = O(g(n))$$
  nP_r = \frac{n!}{(n - r)!}
  $$
  

- With Repetition (Unlimited Repeats)[^2]: If objects can repeat, the number of permutations of $n$ objects taken $r$ at a time is:
  $$
  n^r
  $$

- With Repetition (Limited Repeats) [^3]: If there are $k_1$ objects of one type, $k_2$ of another, ..., and $k_t$ of type $t$, the number of permutations is:
  $$
  \frac{n!}{k_1! \cdot k_2! \cdot \ldots \cdot k_t!}
  $$
  

---

## Combinations

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

- Without Repetition: The number of combinations of $n$ distinct objects taken $r$ at a time is denoted by $nC_r$ or $\binom{n}{r}$, and is calculated as:
  $$
  nC_r = \binom{n}{r} = \frac{n!}{r!(n - r)!}
  $$

- With Repetition: If repetition is allowed, the number of combinations of $n$ objects taken $r$ at a time is:
  $$
  \binom{n + r - 1}{r}
  $$

---

## Examples

### Counting Strings Over an Alphabet
How many strings of length 3 can we form with the alphabet $\Sigma = \{a, b, c, d, e\}$?

- Since there are 5 choices for each position, the total number of strings is:
  $$
  5 \cdot 5 \cdot 5 = 5^3 = 125
  $$

### Combinations Without Repetition
How many subsets of size 3 can we form from $A = \{a, b, c, d, e\}$?

- First, calculate the number of permutations:
  $$
  \frac{5!}{(5-3)!} = 5 \cdot 4 \cdot 3
  $$
  Divide by $3!$ to account for order:
  $$
  \frac{5 \cdot 4 \cdot 3}{3!} = 10
  $$

### Combinations With Repetition
In a restaurant offering 12 desserts, how many ways can you choose 4 desserts (allowing repeats)?

- Using the formula for combinations with repetition:
  $$
  \binom{12 + 4 - 1}{4} = \binom{15}{4} = 1365
  $$

---

## The Pigeonhole Principle

If $n$ items are placed into $m$ containers and $n > m$, at least one container must hold more than one item.

- If there are 13 pigeons and 12 pigeonholes[^6], at least one hole must contain more than one pigeon.


---

## Recurrence Relations

A recurrence relation defines a sequence by relating each term to previous terms.

- The Fibonacci sequence is defined by:
  $$
  F(n) = F(n - 1) + F(n - 2)
  $$
  with initial conditions $F(0) = 0$ and $F(1) = 1$.

### Solving Recurrence Relations

1. Backtracking[^7]: Repeatedly substitute the recurrence relation to find a pattern.
   

2. Linear Homogeneous[^8] Recurrence Relations:
   These have the form:
   $$
   a_n = c_1 a_{n-1} + c_2 a_{n-2} + \ldots + c_k a_{n-k}
   $$
   "Homogeneous" means there is no constant term (e.g., no $+ b$ at the end).

   - Solution: Solve the characteristic equation:
     $$
     r^k - c_1 r^{k-1} - c_2 r^{k-2} - \ldots - c_k = 0
     $$
     The roots $r$ determine the general form of the sequence.

[^1]: Permutations without repetition mean that each object can be used only once in the arrangement.
[^2]: Permutations with unlimited repetition mean objects can repeat any number of times.
[^3]: Limited repetition adjusts for identical items that are indistinguishable.
[^6]: The pigeonhole principle is a basic observation about "fitting" items into containers.
[^7]: Backtracking solves recurrences by substituting values until a pattern emerges.
[^8]: Linear homogeneous recurrence relations depend only on earlier terms, without constants.