首页 > > 详细

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.

联系我们
  • QQ:99515681
  • 邮箱:99515681@qq.com
  • 工作时间:8:00-23:00
  • 微信:codinghelp2
热点文章
程序代写更多图片

联系我们 - QQ: 99515681 微信:codinghelp2
© 2014 www.7daixie.com
程序代写网!