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
a_{n} be the number of
bacteria at the end of n hours.
Because the number of bacteria
doubles every hour, the relationship
a_{n}
= 2a_{n−1}
holds whenever n is a positive integer.
This recurrence relation,
together with the initial condition
a_{0} = 5, uniquely determines
a_{n} for
all nonnegative integers n.
A linear homogeneous recurrence relation of degree k with
constant coefficients is a recurrence relation of the form
a_{n} = c_{1}a_{n − 1}
+ c_{2}a_{n − 2} + ··· +
c_{k}a_{n − k},
where c_{1}, c_{2}, ...,
c_{k} are real numbers, and c_{k} ≠ 0
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.
The generating function for the sequence a_{0},
a_{1} , ... , a_{k}, ...
of real numbers is the infinite series
G(x)=a_{0} +a_{1}x+ ···
+ a_{k}x^{k} +··· =
∑ a_{k}x^{k}
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
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.