#OK to post test
#Hari Amoor, December 16, 2020, Final Exam

# Problem 1

# Part (a)

# Combinatorially, we see that the number of walks on the given lattice that satisfy the desired property is
# 30 * 25 * 20 = 15000 walks.

# Part (b)

# We can visualize the 3D lattice, i.e. on a Cartesian coordinate grid, and see that the region where x >= y >= z
# geometrically represents half of the region. Thus, intuitively, there are 7500 walks -- half as many as in Part (a).

# Problem 2

# Part (a)

# An equivalent problem to the given is to find the cardinality of the formal language [2] specified in the problem.
# We note that a word in the language must have thirty characters, each of which are in the given alphabet; thus, with some
# combinatorial intution, we see that there are 4 * 4 * 4 * ... * 4 = 4^30 such words.

# Part (b)

# We compute that there are b(300) = 12540744464728110353 words using a dynamic programming algorithm to efficiently compute
# the open recursive form in Part (c).

# Part (c)

# The requested explicit formula is below for alphabet \Alpha:

# p(n) = sum_{k \in \Alpha} p(n-k)

# Problem 3

# Part (a)

# The exponential generating-function (EGF) that enumerates set partitions is EG(B_{n}, x) = \sum_{n=0}^{\infty} B_{n} \cdot \frac{x^{n}}{n!} = exp(exp(x) - 1), where B_{i} is the i-th Bell number[3].
# Similarly, the number of partitions on the supplied set is the 51st Bell number B_{51} = 3263983870004111524856951830191582524419255819477.

# Problem 4

# Part (a)

# The super-set partitions are enumerated below:

# {{{1, 2, 3}}, {{1}, {2, 3}}, {{2}, {1, 3}}, {{3}, {1, 2}}, {{1}, {2}, {3}}}

# We produce this result by iteratively computing each set partition.

# Problem 5

# Part (a)

# We arrive at p(1000) = 24061467864032622473692149727991 with the following recurrence relation:

# p(n) = \sum_{k \in \mathbb{Z} \setminus \{0\}} (-1)^{k+1}p(n-k(3k-1)/2)

# This identity is provided in [1] -- we can compute this result, i.e. with Maple, in polynomial time-complexity.

# Part (b)

# The number of integer partitions satisfying the desired property is q(1000), where q(n) is OEIS sequence A000009; we cannot compute this result explicitly due to time and space constraints
# in using Maple. However, we do note that the answer for Part (c) is also equal to q(1000) by a specific case of Glaisher's Theorem (although this property was first discovered by Euler)[1].

# Part (c)

# Same answer as (b).

# Problem 6

# Part (a)

# According to Cayley's Formula[4], the number of labelled trees is n^(n-2) in the number of vertices. Now, we see that each such vertex, for some n, can either be rooted or not rooted; thus,
# we consider this transformation between a single labelled tree and n distinct rooted trees. Hence, the number of such trees is combinatorially (n*n^(n-2))(31) = 31^30 trees (we denote
# function application with the (<expression>)(<value>) macro-notation).

# Problem 7

# Part (a)

# We compute BT(4) = {[[[], []], [[], []]], [[[], []], [[], []]]}.

# NOTE: I developed the intuition for most of the problems through the lecture material and the textbooks. The references provided are sectioned Wikipedia articles, cited rather
# than the Bogart textbook (which I used extensively) for brevity.

# References

# [1]: https://en.m.wikipedia.org/wiki/Partition_function_(number_theory)
# [2]: https://en.wikipedia.org/wiki/Formal_language
# [3]: https://en.wikipedia.org/wiki/Bell_num
# [4]: https://en.wikipedia.org/wiki/Cayley%27s_formula