xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

留学生论文指导和课程辅导

无忧GPA：https://www.essaygpa.com

工作时间：全年无休-早上8点到凌晨3点

微信客服：xiaoxionga100

微信客服：ITCS521

离散数学代写-344H1S-Assignment 7

时间：2021-03-17

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.

学霸联盟

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.

学霸联盟