MAT344H1S讲解、辅导Python编程语言、讲解Java，c/c++
解析C/C++编程|辅导留学生 Statistics统计、回归、迭代
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.