121 lines
3.5 KiB
Markdown
121 lines
3.5 KiB
Markdown
---
|
|
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. |