MATH 3160 PROBLEM SET #5
DUE WEDNESDAY, NOVEMBER 3RD
Key concepts: generating functions, counting with repetitions, the generalized
binomial formula
• Read §2.6 from Harris, Hirst & Mossinghoffup to §2.6.3 inclusively.
•Written Assignment: solve the following problems:
1. Exercise 3 (p. 170) in Harris, Hirst & Mossinghoff. [20p]
Prove the cancellation identity for generalized binomial coefficients: if α is a
real number, and k,m are nonnegative integers, then(
α
k
)(
k
m
)
=
(
α
m
)(
α−m
k−m
)
.
2. Combinatorial approach to counting with repetitions [20p]
The goal of this exercise is to give a combinatorial proof of the formula for count-
ing with repetitions ((2.36) in Harris, Hirst & Mossinghoff ).
Letm,n be positive integers. Consider the following lottery games:
L1 The player chooses m not necessarily distinct numbers from 1, 2, . . . ,n.
The order is unimportant.
L2 The player chooses m distinct numbers from 1, 2, . . . ,n +m − 1. The
order is unimportant.
Prove that the number of possible tickets in the two games is equal, by ex-
hibiting an explicit bijective correspondence between them.
Deduce (2.36) in Harris, Hirst & Mossinghoff (that the number of combinations
with repetitions is
(
n+m−1
m
)
) combinatorially.
3. Exercise 6.b) (p. 175) in Harris, Hirst & Mossinghoff. [20p]
The following coins were in circulation in the United States in 1875: the Indian-
head penny, a bronze two-cent piece (last minted in 1873), a silver three-cent
piece (also last minted in 1873), a nickel three-cent piece, the shield nickel (worth
five cents), the seated liberty half-dime, dime, twenty cent piece (produced for
only four years beginning in 1875), quarter, half dollar, and silver dollar, and
the Indian-head gold dollar. (We ignore the trade dollar, minted for circulation
between 1873 and 1878, as it was issued for overseas trade. This coin holds the
distinction of being the only U.S. coin to be demonetized.)
Write down a generating function in the form of a rational function for the
number of ways to make k cents in change in 1875.
1
2 DUE WEDNESDAY, NOVEMBER 3RD
Optional: use a computer algebra system1 to find the number of ways to
make one dollar in change in 1875.
4. Exercise 10 (p. 177) in Harris, Hirst & Mossinghoff. [20p+20p]
A hungry math major visits the school’s cafeteria and wants to know the num-
ber of ways sk to take k servings of food, including at least one main course, an
even number (possibly zero) of side vegetables, an odd number of rolls, and at
least two desserts. The cafeteria’s food can be distinguished only in the coarsest
way: Every dish is either a main course, a side vegetable, a roll, or a dessert.
There is an unlimited supply of each kind of dish available.
(a) Express
∑
skx
k as a rational function.
(b) Prove that
sk =
(⌊k+1
2
⌋
3
)
+
(⌈k+1
2
⌉
3
)
.
Note. Recall that bxcmeans x rounded down to the next integer, while dxemeans
x rounded up to the next integer.
Collaboration on the homework is allowed at the stage where you try to come
up with ideas to solve the problems, but you must write your solutions alone
in your own words. Moreover, you must acknowledge the people with whom
you’ve collaborated. If you use external sources, you must acknowledge them
as well. I am happy to provide hints.
Write neatly in complete and connected sentences. Proofs should be com-
plete, concise, and rigorous, without sounding excessively formal.
1In class, I used cocalc with SageMath

学霸联盟



























































































学霸联盟