Final Project Documentation: 1 Recurrence Relations/Dynamic Programming

Final Project Documentation
Nashir Janmohamed
Due 11:59 pm, Monday, May 25
1 Recurrence Relations/Dynamic Programming

1.1 Bell numbers
The Bell numbers represent the number of ways to count partitions of (or equiv-
alently equivalence relations on) an n element set. The n-th bell number is given
by the recurrence
n
X n−1
Bn = Bn−k
k−1
k=1
for n ≥ 0.
1.2 Catalan numbers

The Catalan numbers form a sequence of natural numbers that occur in various
counting problems, often involving recursively-defined objects. They can be
expressed by the recurrence relation
n
X
Cn+1 = Ci Cn−1
i=0
for n ≥ 0.
Their closed form is given by

2n 2n
−
n n+1
1.3 Fibonacci numbers

The Fibonacci numbers, commonly denoted Fn , form a sequence such that each
number is the sum of the two preceding ones, with F0 = 0, F1 = 1, and the
recurrence given by
Fn = Fn−1 + Fn−2
for n > 1.
1
1.4 Stirling numbers of the first kind
1.5 Stirling numbers of the second kind
2 Permutations and Combinations

2.1 Combinations without repetition
A combination without repetition is a selection of items from a collection, such
that the order of selection does not matter. A k-combination of an n element
set S is a subset of k distinct elements. The number of k-combinations is equal
to the binomial coefficient given by

n n!
=
k (n − k)! k!
2.2 Permutations without repetition

k-permutations of n are the different ordered arrangements of a k-element subset
of an n-set. This number is given by
n!
P (n, k) = n · (n − 1) · (n − 2) · . . . (n − k + 1) =
(n − k)!
2.3 Combinations without repetition

A k-combination with repetitions allowed is a sequence of k not necessarily
distinct elements of S, where order is not taken into account, i.e. the number
of ways to sample k elements from a set of n elements allowing for duplicates
but disregarding different orderings. Using the stars and bars method, it can be
shown that this number is given by

n+k−1
k
2.4 Permutations with repetition

Permutations with repetition are ordered arrangements of k elements from a set
S with n elements where repetition is allowed. The number of permutations
with repetition of size k is simply k n (except if k > n, where the result is 1).
2.5 Generate permutations of a string

Given a string s of length n, generate all n! permutations of s. For example, all
the permutations of “the” are [“the”, “teh”, “het”, “hte”, “eth”, “eht”].
2
2.6 Generate all bit strings of length n
Given an integer n, all bit strings of length n can be recursively constructed by
appending a 0 and a 1 to all bit strings of length n − 1.
Thus, there are 2 ∗ (sn−1 ) bit strings of length n. Since there are 2 bit strings
of length 1, there are 2n bit strings of length n.
3 Relations
3.1 # of relations
A relation on an n element set S is a subset of S × S, or equivalently, an element
of the power set of S × S. There are
2
2|S||S| = 2n
such subsets.
3.2 # of transitive relations

There is no known closed formula for counting the number of transitive relations.
The (perhaps inefficient) approach taken in this algorithm is as follows
(1) Generate all possible relations for an n element set (given by the power
set of the cartesian product of the set {1, 2, 3, . . . , n})
(2) For each relation generated in (1), check that for each (a, b), if there is a
point of the form (b, c), then (a, c) must be in the relation
3.3 # of (ir)reflexive relations

A relation is reflexive if all elements are related to themselves, or equivalently,
all entries on the main diagonal of the matrix representation of the relation must
be 1. There are n2 entries in the matrix and n entries on the main diagonal.
For the remaining n2 − n off diagonal entries, the ordered pair may or may not
be in the relation. Thus, there are
2
−n
2n
reflexive relations. The argument for irreflexive relations is the same, with the
exception that all entries on the main diagonal of the matrix representation of
the relation must be 0.
3.4 # of symmetric relations

A relation R is symmetric if for all (a, b) that are in R, (b, a) is also in R. Each
element on the diagonal may or may not be related to itself, and similarly for
3
n

all the 2 two element subsets (with distinct elements). Thus, there are
n n(n+1)
2( 2 )+n = 2 2
symmetric relations on a set with n elements.
3.5 # of antisymmetric relations

A relation R is antisymmetric if for all (a, b) that are in R, if (b, a) is in R,
then a = b. There are two choices for every element on the diagonal. For the
remaining n2 two element subsets (with distinct elements) with elements a and
b, either (a, b) ∈ R and (b, a) 6∈ R, (a, b) 6∈ R and (b, a) ∈ R, or (a, b) 6∈ R and
(b, a) 6∈ R, so there are 3 choices for each two element subset. Thus, there are
n n(n−1)
2n 3( 2 ) = 2n 3 2
antisymmetric relations on a set with n elements.
3.6 # of equivalence relations

A relation R on a set A is an equivalence relation if it is reflexive, symmetric, and
transitive. For each a ∈ A, the equivalence class of a is given by [a] = {x | xRa}.
The equivalence classes form a partition of A, and so the number of equivalence
relations on a set S is given by the number of partitions of a set S. So, this num-
ber is equivalent to the Bell number (number of partitions/equivalence relations
for an n element set) which we can compute directly.
n
X n−1
Bn = Bn−k
k−1
k=1
for n ≥ 0.
4
4 Sets
4.1 Generate power set
The power set of a set S is the set of all subsets of S, denoted by P(S). For
each element in S, it either is or is not in a subset of S, so there are two choices
for each element of S in each subset. Thus, there are 2|S| subsets of S.
4.2 Generate cartesian product

The Cartesian product of two sets A and B, denoted A × B, is the set of all
ordered pairs (a, b) where a ∈ A and b ∈ B. In terms of set-builder notation,
that is
A × B = { (a, b) | a ∈ A and b ∈ B }
This function can be called with either one or two sets. If one set A is passed,
then the result will be A × A. If two sets are passed, separate them with a
semicolon, i.e. “1, 2, 3; 4, 5”.
5 Recurrence
5.1 Solve linear homogeneous recurrence relations with
constant coefficients (LHCCRRs)
A linear homogeneous recurrence relation with constant coefficients (LHCCRR)
of degree k is a recurrence relation of the form
an = c1 an−1 + c2 an−2 + · · · + ck an−k
where c1 , c2 , . . . , ck ∈ R and ck 6= 0. The characteristic equation (1) is
rk − c1 rk−1 − c2 rk−2 − . . . ck = 0
Suppose that (1) has t distinct roots r1 , r2 , . . . , rt with multiplicities m1 , m2 , . . . , mt ,
respectively, so that mi ≥ 1 for i = 1, 2, . . . , t and m1 + m2 + · · · + mt = k. Then
a sequence an is a solution of the recurrence relation if and only if
an =(α1,0 + α1,1 n + · · · + α1,m1 −1 nm1 −1 )r1n

+ (α2,0 + α2,1 n + · · · + α2,m2 −1 nm2 −1 )r2n
+ · · · + (αt,0 + αt,1 n + · · · + αt,mt −1 nmt −1 )rtn
for n = 0, 1, 2, . . . , where αi, j are constants for 1 ≤ i ≤ t and 0 ≤ j ≤ mi − 1.

(This implementation only solves recurrence relations with non-complex roots.)
6 Isomorphisms
maybe total orders?
5
7 Default
No documentation provided.

Final Project Documentation: 1 Recurrence Relations/Dynamic Programming

Uploaded by

Copyright:

Available Formats

Final Project Documentation: 1 Recurrence Relations/Dynamic Programming

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Final Project Documentation: 1 Recurrence Relations/Dynamic Programming

Uploaded by

Copyright:

Available Formats

Final Project Documentation

1 Recurrence Relations/Dynamic Programming

1.2 Catalan numbers

1.3 Fibonacci numbers

2 Permutations and Combinations

2.2 Permutations without repetition

2.3 Combinations without repetition

2.4 Permutations with repetition

2.5 Generate permutations of a string

3.2 # of transitive relations

3.3 # of (ir)reflexive relations

3.4 # of symmetric relations

symmetric relations on a set with n elements.

3.5 # of antisymmetric relations

antisymmetric relations on a set with n elements.

3.6 # of equivalence relations

4.2 Generate cartesian product

an =(α1,0 + α1,1 n + · · · + α1,m1 −1 nm1 −1 )r1n

for n = 0, 1, 2, . . . , where αi, j are constants for 1 ≤ i ≤ t and 0 ≤ j ≤ mi − 1.

You might also like