School

University of WaterlooDepartment

MathematicsCourse Code

MATH239Professor

Katz EricStudy Guide

FinalThis

**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 deﬁne a weight function wwhere

for each X∈Sn,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 n≥2,

ΦSn(x) = (1 + xn)ΦSn−1(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=An∪Bnis a disjoint

union, by Sum Lemma, ΦSn(x) = ΦAn(x) + ΦBn(x).

Note that An=Sn−1as these are subsets of {1, . . . , n −1}, so ΦAn(x) = ΦSn−1(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 deﬁne a bijection f:Bn→Sn−1where f(X) = X\ {n}. Notice that w(X) = w(f(X)) + nsince

the only diﬀerence between the two sets is the element n. So

ΦBn(x) = X

X∈Bn

xw(X)=X

X∈Bn

xw(f(X))+n=xnX

X∈Bn

xw(f(X)) =xnX

Y∈Sn−1

xw(Y)=xnΦSn−1(x)

where the second last equality is due to the fact that fis a bijection, so we are summing over every element

in Sn−1.

Combining the results, we get ΦSn(x) = ΦAn(x) + ΦBn(x) = ΦSn−1(x) + xnΦSn−1(x) = (1 + xn)ΦSn−1(x).

(b) {2 marks}Use part (a) to prove that

ΦSn(x) =

n

Y

i=1

(1 + xi).

Solution. We use induction on n. When n= 1, S1={∅,{1}}, so ΦS1(x) = 1 + x. Assume the result for

ΦSn−1(x). Then by part (a),

ΦSn(x) = (1 + xn)ΦSn−1(x) = (1 + xn)

n−1

Y

i=1

(1 + xi) =

n

Y

i=1

(1 + xi).

2. {5 marks}Let m≥0. 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 deﬁnition of a set and a weight function. You

may say that the answer to the question is some coeﬃcient of some simpliﬁed 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 q≥d, we see

that

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=Sk≥0Sk. We deﬁne 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