Notes on the combinatorics part of CS2304: Mathematical Foundations of Computer Science.

Review

Textbook:
An invitation to discrete mathematic

Inclusion-Exclusion Principle

General formula:

proved by induction.

Derangements

Let D(n) denote the number of derangements of n elements.

Recurrence

D(n) = (n-1)[D(n-1) + D(n-2)]

initial condition: D(1) = 0, D(2) = 1

Closed form

or written as:

Derivation via the inclusion-exclusion principle

Let A_i denote the set of permutations in which “the i-th element is in its original position”. Then the number of derangements is $|\overline{A_1 \cup A_2 \cup ... \cup A_n}|$, i.e. the number of permutations in which no element is in its original position.

Converting to the complement

• $|A{i_1} \cap A{i2} \cap … \cap A{i_k}|$ denotes the number of permutations in which exactly k elements are in their original positions
• There are ways to choose these k positions
• The remaining n-k positions can be permuted arbitrarily, giving ways
• Therefore $|A_{i_1} \cap A_{i_2} \cap ... \cap A_{i_k}| = \binom{n}{k}(n-k)!$

As n → ∞, converges to , which explains why $D(n) \approx \frac{n!}{e}$

Euler’s totient function

Euler’s totient function is the number of positive integers less than n that are coprime to n.

How to compute it

1. Multiplicativity: if a and b are coprime, then

2. Totient of a prime: if p is prime, then

3. Totient of a prime power: if p is prime and k ≥ 1, then

4. General formula: for any positive integer n, if the prime factorization of n is:

   $$n = p_1^{k_1} \cdot p_2^{k_2} \cdot ... \cdot p_m^{k_m}$$

   then by the inclusion-exclusion principle:

   $$\phi(n) = n - \sum_{i} \frac{n}{p_i} + \sum_{i<j} \frac{n}{p_ip_j} - \sum_{i<j<k} \frac{n}{p_ip_jp_k} + ...$$ $$\phi(n) = n \prod_{i=1}^m (1-\frac{1}{p_i})$$

Generating Function

A generating function is a powerful tool that turns a sequence into a function, usually expressed as a power series:

where is the -th term of the sequence and is a formal variable.

Used for permutation and combination problems:

Used for the probability distribution of a discrete random variable:

3. Applications of generating functions

3.1 Solving recurrence relations

1
2
3
4
5
6
7
8
9
10
11
12

# Example: solving the Fibonacci sequence with a generating function
def fibonacci_generating_function(n):
    # Generating function of the Fibonacci sequence: G(x) = x/(1-x-x^2)
    # Expanding it as a power series yields the n-th term
    import numpy as np
    
    # Compute directly with the recurrence relation
    fib = [0, 1]
    for i in range(2, n+1):
        fib.append(fib[i-1] + fib[i-2])
    
    return fib[n]

3.2 Counting problems

Example: how many ways are there to place identical objects into distinct boxes?

• Generating function:
• The coefficient of in the expansion is the answer

3.3 Applications in probability

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# Use generating functions to compute the probability distribution of the sum of two dice
def dice_sum_probability(sum_value):
    # Generating function of a single die: P(x) = (x^1 + x^2 + ... + x^6)/6
    # Generating function of the sum of two dice: P(x)^2
    
    # Initialize the probability counts
    counts = [0] * 13  # index 0 is unused; the possible sums are 2-12
    
    # Brute-force over all possible outcomes
    for i in range(1, 7):
        for j in range(1, 7):
            counts[i + j] += 1
    
    # Compute the probabilities
    return counts[sum_value] / 36

4. Properties of generating functions

• Addition: adding sequences corresponds to adding generating functions
• Multiplication: convolving sequences corresponds to multiplying generating functions
• Differentiation:
• Integration:

5. Common generating functions

6. Example: computing binomial coefficients

1
2
3
4
5
6
7
8
9
10
11
12

# Use a generating function to compute the binomial coefficient C(n,k)
def binomial_coefficient(n, k):
    # Use the binomial theorem: (1+x)^n = Σ(k=0 to n) C(n,k) * x^k
    if k < 0 or k > n:
        return 0
    
    # Compute the binomial coefficient
    result = 1
    for i in range(1, k+1):
        result = result * (n - i + 1) // i
    
    return result

Translated from the Chinese original.