Study Guides (390,000)
CA (150,000)
UW (7,000)
MATH (600)
MATH239 (90)

MATH239 Lecture Notes - Lecture 30: Formal Power Series, Weight Function, BijectionExam

Course Code
Katz Eric
Study Guide

This preview shows half of the first page. to view the full 3 pages of the document.
Math 239 Fall 2016 Assignment 3 Solutions
1. For any positive integer n, let Snbe the set of all subsets of {1, . . . , n}. We define a weight function wwhere
for each XSn,w(X) is the sum of all the elements in X, with w() = 0. Let ΦSn(x) be the generating series
of Snwith respect to w.
(a) {5 marks}Use the Sum Lemma to prove that for any n2,
ΦSn(x) = (1 + xnSn1(x).
Solution. We partition Sninto two sets Anand Bn, where Anconsists of all subsets of {1, . . . , n}that do
not contain n, and Bnconsists of all subsets of {1, . . . , n}that contain n. Since Sn=AnBnis a disjoint
union, by Sum Lemma, ΦSn(x) = ΦAn(x) + ΦBn(x).
Note that An=Sn1as these are subsets of {1, . . . , n 1}, so ΦAn(x) = ΦSn1(x).
Now an element of Bnis a subset of {1, . . . , n}that consists of {n}union with a subset of {1, . . . , n 1}.
We can define a bijection f:BnSn1where f(X) = X\ {n}. Notice that w(X) = w(f(X)) + nsince
the only difference between the two sets is the element n. So
ΦBn(x) = X
xw(f(X)) =xnX
where the second last equality is due to the fact that fis a bijection, so we are summing over every element
in Sn1.
Combining the results, we get ΦSn(x) = ΦAn(x) + ΦBn(x) = ΦSn1(x) + xnΦSn1(x) = (1 + xnSn1(x).
(b) {2 marks}Use part (a) to prove that
ΦSn(x) =
(1 + xi).
Solution. We use induction on n. When n= 1, S1={∅,{1}}, so ΦS1(x) = 1 + x. Assume the result for
ΦSn1(x). Then by part (a),
ΦSn(x) = (1 + xnSn1(x) = (1 + xn)
(1 + xi) =
(1 + xi).
2. {5 marks}Let m0. Suppose we have an unlimited supply of nickels, dimes and quarters. How many ways
can we make mcents using these coins such that there are even number of nickels, and the number of quarters
is at least the number of dimes? Your solution must include the definition of a set and a weight function. You
may say that the answer to the question is some coefficient of some simplified formal power series.
Solution. Each collection of coins can be represented by a triple (n, d, q) where each n, d, q are non-negative
integers representing the number of nickels, dimes and quarters in the collection, respectively. We need an even
number of nickels, so n∈ {0,2,4,6, . . .}. Let Skbe those collections with exactly kdimes. Since qd, we see
Sk={0,2,4,6, . . .} × {k} × {k, k + 1, k + 2, k + 3 . . .}.
So the set of all possible collections can be enumerated by S=Sk0Sk. We define the weight function wwhere
for each collection (n, d, q), w(n, d, q) = 5n+ 10d+ 25q. This represents the value of a collection in cents.
You're Reading a Preview

Unlock to view full version