Notes/Discrete Structures/Counting.md

type
theoretical

Key Concepts

Permutations

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

• Without Repetition¹: 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)²: If objects can repeat, the number of permutations of n objects taken r at a time is:

  
  n^r
  

• With Repetition (Limited Repeats) ³: 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⁴, 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⁵: Repeatedly substitute the recurrence relation to find a pattern.

2. Linear Homogeneous⁶ 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. ↩︎

4. The pigeonhole principle is a basic observation about "fitting" items into containers. ↩︎

5. Backtracking solves recurrences by substituting values until a pattern emerges. ↩︎

6. Linear homogeneous recurrence relations depend only on earlier terms, without constants. ↩︎