Math 607 Applied Math I: Week 1 Homework¶
Due date: Wednesday, Oct 9.
Please submit a Jupyter notebook with your solutions, via Canvas. No paper submissions, please.
It's absolutely OK if you work together on these problems - and this is especially true for the programming problems, when we want you to be working in pairs at one computer, with one person typing and one person thinking.
We do want everyone to write up each assignment on their own.
Problem 1: counting planar rooted trees¶
A planar rooted binary tree is a collection of nodes such that (a) one of them is the root, (b) each node except the root has a parent, (c) if node $u$ is parent to node $v$ then $v$ is either the left or the right child of $u$, and (d) each node has at most one left child and at most one right child. A recursive definition begins with the empty tree and the one-node tree, and says that every node has a left and a right subtree (which may be empty). Let $T(n)$ denote the number of such trees with a total of $n$ nodes.
(a) Write a program that takes an integer $n$ and computes $T(n)$, based on the above definition (no tricky formulas allowed).
(b) Write a program which geneartes all planar rooted binary trees with $n$ nodes. Make sure they agree with each other. If you know how to do the rest of this problem already for some crazy reason: try writing a program which iterates over these trees one at a time (rather than storing them all in memory at once)
(c) Use your program and the online encyclopedia of integer sequences to find the name of and a formula for this sequence. It is, unfortunately for me, a famous sequence, so there's a good chance you have seen this problem before! Alas.
(d) Derive a recursive formula for the generating function $$G(x) = \sum_{n \ge 0} x^n T(n)$$ for $T(n)$ and solve it to obtain a closed-form expression for $G(x)$. Use this to derive a formula for $T(n)$ (*hint: this may be helpful).
Problem 2: guessing a linear recurrence with constant coefficients¶
Guess a closed-form formula for the sequence of numbers 1, 1, 1, 3, 17, 83, 345, 1291, 4513, 15075, 48809, 154619, 482289, ...
This sequence is in the OEIS (yet). Here is an alternate way: Let $\{a_n\}_{n \geq 0}$ be the above sequence. Then:
(a) Use linear algebra to try and find a linear recurrence with constant coefficients satisfied by ${a_n}$. I'd suggest you use the python package numpy to do your linear algebra.
(b) Let $G(x) = \sum_{n \geq 0}a_nx^n$. Use the recurrence to find an expression for $G(x)$. If you succeeded in part (a), this expression will be a rational function in x.
(c) Use partial fractions on your answer to (b). Then compute taylor series around x=0 for all the resulting terms. The $n$th term of the taylor series is now a closed form expression for $a_n$. Check that it's right.
Problem 3: guessing a linear recurrence with polynomial coefficients¶
Let $$f(k) = \sum_{n=0}^{k} n!$$ and let $G(x)$ be the generating function of the sequence $\{f(k)\}_{k \geq 0}$. I claim that $G$ is a $D$-finite generating function.
(a) Use linear algebra, together with the methods in Problem 2, to guess a linear recurrence relation with polynomial coefficients satisfied by the sequence $\{f(k)\}_{k \geq 0}$. Try and find the simplest recurrence you can (a low-order recurrence with low-degree coefficients).
(b) Prove that the conjectured formula in part (a) is correct. Don't try to solve the recurrence - I don't think there's a formula for $f$ that doesn't have a summation sign in it, sadly.
Problem 4: weird dice¶
Consider two six-sided dice with sides marked as follows:
- Die A has sides marked 1,3,4,5,6,8
- Die B has sides marked 1,2,2,3,3,4
We roll these two dice and add the values to get a random number between 2 and 12.
(a) Show that the random number we get has the same distribution as rolling two ordinary dice and adding the values. This part doesn't need generating functions, but the next part does, so you might as well use them.
(b) Show that
- the ordinary labeling of two dice, and
- the labelling of Die A and Die B
are the only labellings with the property described in part (a), subject to the condition that the smallest number on both dice is 1.
Problem 5: old-school spambot¶
(a) Download the complete works of William Shakespeare. Write a python function which reads in the file, one line at a time, and produces a list $L$ of words in the file, in order. Remove all spaces, but leave the punctuation and capitalization the way they are.
This file has a bunch of non-shakespeare stuff in it - copyright notices, tables of contents, and so forth. You might want to take those out. Also, to save time during testing, you should create a shorter text file, with only some of the works of William Shakespeare.
(b) Write a python program that constructs the following directed graph $G=(V,E)$: $V$ is the set of ordered triples $(w_1, w_2, w_3)$ of consecutive words in $L$, and $E$ is the set of all pairs $((w_1,w_2,w_3),(w_2,w_3,w_4))$ where $(w_1, w_2, w_3, w_4)$ is an ordered quadruple of consecutive words in $L$. Implement the graph as a dictionary whose keys are triples as above, and whose values are lists of possible words $w_4$.
(c) Write a python program which generates vaguely shakespeare-sounding nonsense by carrying out a random walk in $G$. If your program is producing less-than-ideal output, you may want to clean up the file from part (a).