Assignment 4-

1. For each of the following sequences a₀, a₁, a₂, . . . , determine a closed form for the generating series A(x) = a₀ + a₁x + a₂x² + · · · .

(a) a_n = 0 if n is odd, a_n = 3ⁿ if n is even.

(b) a_n = _i=0∑ⁿb_ic_n-i where the sequence b₀, b₁, b₂, . . . has generating 1/(1-x)² and the sequence c₀, c₁, c₂, . . has generating series 1/√(1-x).

2. Briefly explain why the number of ways to change n cents into pennies, nickels, dimes, and quarters is the coefficient of xⁿ in

1/(1 - x)(1 - x⁵)(1 - x¹⁰)(1 - x²⁵),

and use this along with a computer to determine the number of ways of changing a dollar into pennies, nickels, dimes and quarters.

3. In this problem, we will show that the average number of comparisons in the QUICKSORT algorithm for sorting n distinct numbers is O(n log n). This algorithm takes a list of n distinct numbers, and sorts them in order from least to greatest. The algorithm runs as follows. First, select a random number p in the list. Then, compare p to all other elements in the list. If an element is less than p, place it in the list anywhere before p. If an element is greater than p, place it in the list anywhere after p. Then, recursively apply this algorithm to the sublist of elements falling before p, and the sublist of elements falling after p, while leaving p in its place. Thus, if an is the average number of comparisons in the QUICKSORT algorithm to sort n distinct numbers, we have a₀ = 0 and for n ≥ 1,

a_n = n - 1 + (1/n) _i=0∑ⁿ(a_i-1 + a_n-i)

(a) Let f(x) be the generating series for the sequence {a₀, a₁, a₂, . . .}. Deduce that

f'(x) - (2/1 - x)f(x) = 2x/(1 - x)³.

(b) Using differential equations, one can conclude (formally) that

f(x) = -2(x + log(1 - x))/(1 - x)²

(you do not need to show this). Use this, along with the fact that there is a constant M > 0 such that k=1∑n 1/k < M · log n (you can assume this result), to show that there is a constant C > 0 such that the average number of comparisons in the QUICKSORT algorithm is less than C · n log n.

4. Let A ⊂ {0, 1}^∗ be the set of binary strings in which each block of 0s has odd length, and each block of 1s has length one or two. Let A(x) = _n=0∑^∞a_nxⁿ be the generating series for A with respect to length (i.e. with respect to the weight function ω: A → {0, 1, 2, 3, . . .} given by ω(a) = number of bits in a). Show that every string in A can be uniquely described by the regular expression

(∅ ∪ (00)^∗0)((1 ∪ 11)(00)^∗0)^∗(∅ ∪ 1 ∪ 11).

and use this to find A(x), and hence a recurrence equation for a_n.

5. A beautiful theorem of Lagrange allows us to extract coefficients of generating series that satisfy certain functional equations. Lagrange's Theorem states that if f(x) is a generating series that satisfies the functional equation f(x) = x · g(f(x)) where g is some other function, then

[xⁿ]f(x) = 1/n[y^n-1]gⁿ(y).

We will use this to count cubic plane planted trees. A cubic plane planted tree is a plane planted tree, all of whose vertices are adjacent to at most 4 other vertices.

(a) Let C be the set of cubic plane planted trees, and let ∈ be the unique cubic plane planted tree with only one non-root vertex (as in class). Explain why there is a bijection between C - { ∈} and

k=1∪3{ ∈} × C^k

that preserves the number of non-root vertices and deduce that if C(x) is the generating series for C with respect to the weight function ω: C → {0, 1, 2, . . .} defined by ω(c) = number of non-root vertices in c, then

C(x) = x · (1 - C⁴(x)/1 - C(x)).

(b) Use Lagrange's Theorem to deduce that the number of cubic plane planted trees on n vertices is