MAT344H1S Introduction to Combinatorics
Assignment 7
Due Monday Mar 22 at 10:00 pm
(to be submitted on Crowdmark)
In the problems asking to compute the generating functions final answers should not con-
tain infinite summation.
1. Let an be the number of integral solutions of the equation x1+x2+x3+x4 = n,n ≥ 0,
where x1, . . . , x4 satisfy one of the conditions below. In each case, find the generating
function for the sequence an.
a. −10 ≤ xi ≤ 10, for i = 1, . . . , 4.
b. xi ≥ 0 for i = 1, . . . , 4, x1, x3 are odd and x2, x4 are even.
c. 0 ≤ x1 ≤ 100 and x1 is divisible by 3, x2, x3, x4 ≥ 0.
2. Using the method of generating functions, find the number of integral solutions of
the equation x1 + x2 + x3 = n, satisfying −2 ≤ x1 ≤ 2, x2 ≥ 0, x3 ≥ 0, x1 and x2 are
even.
3. Fix a finite alphabet X with |X| = k. Find the generating function for the number an
of X-strings of length n. We let a0 = 1.
4. Let an be the number of strings of symbols {a, b, c, 1, 2, 3} of lengthn, such that exactly
one of the symbols in a string is a digit. Find the generating function of the sequence
an. Your answer should be a ratio of two polynomials.
5. Ice Cream Ultra-X 9000 consists of several layers of cones, followed by several layers
of ice cream, followed by several layers of toppings.
Each topping is one of the following 6 options: Chocolate, Fudge, Strawberry
syrup, Caramel syrup, Butterscotch syrup, Marshmallow fluff.
Each ice cream is one of the following 5 options: Vanilla, Chocolate, Strawberry,
Mint, Green tea.
Each cone is either a plain waffle or a chocolate waffle.
Find the generating function for the number of different Ice Cream Ultra-X 9000
recipes consisting of n layers, if each recipe must have at least one layer of topping,
ice cream and cone, different flavors may repeat several times and their order matters
(of course).
Here is an example of a recipe with 10 layers (3 layers of cone + 5 layers of ice
cream + 2 layers of topping):
Plain cone in chocolate cone in plain cone, with a layer of Vanilla ice cream, layer
of Strawberry ice cream, then two layers of Mint ice cream, followed by another layer
of Strawberry ice cream, covered by Marshmallow fluff, and then covered by the
Caramel syrup.
1
26. Let dn be the number of derangments of a set of size n, and let D(x) =
∑
n≥1 dnx
n be
the corresponding generating function. Prove that it satisfies the following differen-
tial equation:
xD ′(x) = D(x)
(
1
x
− 1
)
−
x
1+ x
.
You may use the recursive formulas from the Exercise 22 to the Chapter 7 of the
textbook without proof, if needed.
























































学霸联盟