”
MAT344H1S作业 写作、 辅导Python编程语言作业、 写作Java，c/c++课程作业
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) = Pn=0 anxn, FexpL(x) = Pn=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.
“
添加老师微信回复‘’官网 辅导‘’获取专业老师帮助，或点击联系老师1对1在线指导。
