Advanced Counting Techniques

The logistic equation and its iterated versions.
Applications of Recurrence Relations

In this section we will show that recurrence relations can be used to study and to solve counting problems. For example, suppose that the number of bacteria in a colony doubles every hour. If a colony begins with five bacteria, how many will be present in n hours?
To solve this problem, let an be the number of bacteria at the end of n hours. Because the number of bacteria doubles every hour, the relationship an = 2an−1 holds whenever n is a positive integer. This recurrence relation, together with the initial condition a0 = 5, uniquely determines an for all nonnegative integers n.

Some Applications
  1. Rabbits and the Fibonacci Numbers
    fn = fn−1 + fn−2
    I've been multiplying like a rabbit!

    Rabbit breeding pairs.
  2. Codeword Enumeration

    Imagine valid codewords are strings of digits containing even numbers of zeroes. How many such strings of length n are there?
    We can append a digit other than 0 to a valid string. There are nine such digits, so we can do this 9an − 1 ways.
    Or we can append a 0 to an invalid string. There are 10n−1 strings of length n − 1, and an−1 are valid, there are 10n − 1 − an−1 valid n-digit strings obtained by appending a 0 to an n − 1 length string.
    So total valid strings of length n is:
    an = 9an−1 + 10n−1 − an−1
    = 8an−1 + 10n−1
  3. The Towers of Hanoi


    The monks in a temple have the job of moving all of the disks on one peg to another, constrained by these rules:
    1) Only one disk can be moved at a time.
    2) Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack.
    3) No disk may be placed on top of a smaller disk.
    ( Source )



    Recurrence:
    T(n) = 2T(n−1) + 1




    Why is this the recurrence? Well, to move disk n, we first move disks 1 to n - 1 to the spare peg, then move n to the target peg, then move disks 1 to n - 1 to the target peg.

    So we guess the closed-form solution is something like 2n. Why? Well, we multiply by a factor of 2 each recursion!
    Now, let's try writing out a few elements of the sequence:
    T(0) = 0
    T(1) = 2*0 + 1 = 1
    T(2) = 2*1 + 1 = 3
    T(3) = 2*3 + 1 = 7
    T(4) = 2*7 + 1 = 15
    T(5) = 2*15 + 1 = 31
    So is the answer 2n - 1?
    Base case: T(0) = 0 = 20 - 1.
    Yes!
    Now induction: we want to show that, if T(n − 1) = 2(n−1) − 1, then T(n) will equal 2n − 1.
    How proof by induction works: we have proved our base case. Now we try to prove that for any n, if for n − 1 our hypothesis is true, then it is true for n as well. And since we have already proved that for n = 0 it is true, that will mean it will be true for all n whatsoever.
    So we substitute in for n − 1:
    T(n) = 2(2(n−1) − 1) + 1
    = 2 * 2(n−1) − 2 + 1
    = 2n − 1
    And we are done!

    In the fable, the monks must move 64 disks. If they move 1 per second, it will take them: 18,446,744,073,709,551,615 seconds, or 500 billion years.
Solving Linear Recurrence Relations
NOT COVERED SPRING 2018

A linear homogeneous recurrence relation of degree k with constant coefficients is a recurrence relation of the form
an = c1an − 1 + c2an − 2 + ··· + ckan − k, where c1, c2, ..., ck are real numbers, and ck ≠ 0

Theorems:
  1. Theorem 1: Let c1 and c2 be real numbers. Suppose that r2 − c1r − c2 = 0 has two distinct roots r1 and r2. Then the sequence {an} is a solution of the recurrence relation an = c1an − 1 + c2an − 2 if and only if
    an = α1r1n + α2r2n for n = 0, 1, 2, ..., where α1 and α2 are constants.
  2. Theorem 2: Let c1 and c2 be real numbers with c2 ≠ 0. Suppose that r2 − c1r − c2 = 0 has only one root r0. A sequence {an} is a solution of the recurrence relation an = c1an − 1 + c2an − 2 if and only if
    an = α1r0n + α2r0n, for n = 0, 1 , 2 ,..., where α1 and α2 are constants.
  3. Theorem 3: Let c1, c2 ... , ck be real numbers. Suppose that the characteristic equation
    rk − c1rk − 1 − · · · − ck = 0
    has k distinct roots r1, r2, ..., rk. Then a sequence {an } is a solution of the recurrence relationan = c1an − 1 + c2an − 2 + ··· + ckan − k if and only if
    an = α1r1n + α2r2n + · · · + αkrkn for n = 0, 1, 2 ,..., where α1, α2, ..., αk are constants.
Divide-and-Conquer Algorithms and Recurrence Relations

Divide-and-Conquer lecture from Algorithms course
(See sections 4.4 and 4.5.)

Suppose that a recursive algorithm divides a problem of size n into a subproblems, where each subproblem is of size n/b (for simplicity, assume that n is a multiple of b; in reality, the smaller problems are often of size equal to the nearest integers either less than or equal to, or greater than or equal to, n/b ). Also, suppose that a total of g(n) extra operations are required in the conquer step of the algorithm to combine the solutions of the subproblems into a solution of the original problem. Then, if f(n) represents the number of operations required to solve the problem of size n, it follows that f satisfies the recurrence relation
f(n) = af(n/b) + g(n).
This is called a divide-and-conquer recurrence relation.

Generating Functions
NOT COVERED SPRING 2018

The generating function for the sequence a0, a1 , ... , ak, ... of real numbers is the infinite series
G(x)=a0 +a1x+ ··· + akxk +··· = ∑ akxk

Inclusion-Exclusion
NOT COVERED SPRING 2018

The inclusion–exclusion principle is a counting technique which generalizes the familiar method of obtaining the number of elements in the union of two finite sets; symbolically expressed as

where A and B are two finite sets and |S| indicates the cardinality of a set S (which may be considered as the number of elements of the set, if the set is finite). The formula expresses the fact that the sum of the sizes of the two sets may be too large since some elements may be counted twice. The double-counted elements are those in the intersection of the two sets and the count is corrected by subtracting the size of the intersection.
The principle is more clearly seen in the case of three sets, which for the sets A, B and C is given by

Applications of Inclusion-Exclusion
NOT COVERED SPRING 2018

Many counting problems can be solved using the principle of inclusion–exclusion. For instance, we can use this principle to find the number of primes less than a positive integer. Many problems can be solved by counting the number of onto functions from one finite set to another. The inclusion–exclusion principle can be used to find the number of such functions. The famous hatcheck problem can be solved using the principle of inclusion–exclusion. This problem asks for the probability that no person is given the correct hat back by a hatcheck person who gives the hats back randomly.