MAT344H1S代做、代写Python编程语言、代做Java，c/c++

日期：2020-03-26 08:11

MAT344H1S Introduction to Combinatorics

Assignment 8

Due Sunday March 22 at 10:00 pm

(to be submitted on Crowdmark)

Note: Due to time limitations, only some questions will be graded. In your solutions

for counting problems, you should (briefly) include your reasoning.

1. Compute P10

k=0k2k. Hint: evalute the derivative of Pnk=02kxk at 1.

2. What is the generating function for the sequence an = number of partitions of n into

parts of size ≤ k?

3. What is the generating function for the sequence an = number of partitions of n such

that the part of size k appears < k times, for all k?

4. Let P(n) be the number of partitions of n, let Q(n) be the number of partitions of n

with no parts of size 1. Show that Q(n) = P(n) − P(n − 1)

a. using the generating function;

b. by constructing a bijection.

5. Let X be a finite set, and let L be any set of finite X-strings. Let an = number of strings

of length n in L. Denote FL(x) = P∞n=0 anxn, FexpL(x) = P∞n=0 anxn/n!.

For X = {a, b, . . . , z}, let L be the set of all valid English words. In each of the

following problems your answer should not contain an infinite summation.

a. X0 = {a, b, . . . , z, }, L0

is the set of all words in the alphabet X0

that can be

obtained from a valid English word by adding some number (maybe none) of

to the end of a valid English word. E.g., “combinatorics ” is a word inL, obtained from a valid English word “combinatorics”. Express FL

0(x) through

FL(x).b. X0 = {a, b, . . . , z, }, L0

is the set of all words in the alphabet X0

that can be

obtained from a valid English word by adding even number (maybe none) of

to a valid English word, at any spots. E.g., “ comb inat ori cs” is a

word in L0, obtained from a valid English word “combinatorics”. Express F

exp

that can

be obtained from a valid English word by capitalizing exactly two letters. E.g.,

“cOmbinaTorics” is a word in L

0

, obtained from a valid English word “combinatorics”.

Express FL

0(x) through FL(x).

d. X0 as in c., L0

is the set of all words that can be obtained from a valid English

word by capitalizing any number of letters. E.g., “cOmBiNaToricS” is a word

in L0, obtained from a valid English word “combinatorics”. Express FL

0(x) and

FexpL0 (x) through FL(x) and FexpL0 (x).

6. Passwords are composed from lower- and uppercase letters of the English alphabet,

digits and 34 special characters. What is the exponential generating function of the

sequence an = number of passwords with at least one capital letter, one number and

one special character.

7. Find the number of {0, 1, 2}-strings of length n in which 0 appears an even number of

times and 1 appears an odd number of times.

Extra Practice Problems: The following problems are for your further practice. They are

not to be handed in for grading.

a. Applied Combinatorics by Keller and Trotter, 2017 edition (pdf), Section 8.8: Exercises

# 20-26.