Week Date Sections
from FS2009
Part/ References Topic/Sections Notes/Speaker
1 Sept 7 I.1, I.2, I.3 Combinatorial
Structures
FS: Part A.1, A.2
Comtet74
Handout #1
(self study)
Symbolic methods
2 14 I.4, I.5, I.6 Unlabelled structures
3 21 II.1, II.2, II.3 Labelled structures I
4 28 II.4, II.5, II.6 Labelled structures II
5 Oct 5 III.1, III.2 Combinatorial parameters
FS A.III
(self-study)
Combinatorial
Parameters Asst #1 Due
6 12 IV.1, IV.2 Multivariable GFs
7 19 IV.3, IV.4 Analytic Methods
FS: Part B: IV, V, VI
Appendix B4
Stanley 99: Ch. 6
Handout #1
(self-study)
Complex Analysis
8 26
IV.5 V.1
Singularity Analysis
9 Nov 2 Asymptotic methods Asst #2 Due
10
9 VI.1 Sophie
12 A.3/ C
Random Structures
and Limit Laws
FS: Part C
(rotating
presentations)
Introduction to Prob. Mariolys
11
18 IX.1 Limit Laws and Comb Marni
20 IX.2 Discrete Limit Laws Sophie
12
23 IX.3 Combinatorial instances of discrete Mariolys
25 IX.4 Continuous Limit Laws Marni
13 30 IX.5 Quasi-Powers and Gaussian limit laws Sophie
14 Dec 10 Presentations Asst #3 Due
Dr. Marni MISHNA, Department of Mathematics, SIMON FRASER UNIVERSITY
Version of: 11-Dec-09

f acul ty of sc ience MATH 895-4 Fall 2010
depar tment of mathemat ics Course Schedule MATH 343, ASSIGNMENT #2
Due date: Friday October 9, on canvas
Preamble: expectations
As for the first assignment, a significant part of the mark will be based on the quality of the writing
of your proofs, i.e. your proofs should b correct obviously and well written. By correct I mean that
you should prove the correct statement and the proof should be complete and not take shortcuts (like
the too common statement “it is obvious that . . . ” for a fact that is actually not obvious). By well
written, I mean that it should be readable by someone else than you, in our case the person who will
mark your assignment; as a general rule, when I read a proof to mark it, if I do not understand the
argument because the writing is imprecise or confusins, I consider the proof as wrong. Be aware that
if you provide the correct counting formula but your proof is absent or wrong, then you can not expect
to get even half of the marks: an unproved correct result or a correct result backed up by an incorrect
on unreadable proof is not worth much.
The same principle ppl es to the code you will have to write in Maple. I will provide a template
file that you will have o complete in order to answer the programming question; please start from
this template and complete it. When you write code, it is not only aimed at generating experimental
results, but also to be read, again by someone who will mark your assignment. So like for a proof, if
the reader can not understand what you do in your code, then it will not be worth many marks. The
Maple file you will give as part of your assignment is a document and should be treated as such and
great care should be taken that it is not only correct but also well written and readable.
If you work on a question but do not get a full answer, then show your work anyway. You will
learn more by struggling on questions than by answering easy questions. And partial work might be
rewarded.
Preamble: plagiarism
The questions asked in this assignment are quite standard and likely you can find online answers to
some of them or even solutions of previous MATH 343 assignments that contain these questions. It
is obviously better that you try to find the solution by yourself, alone or by working in groups (while
respecting social distancing, please). If you understand a solution from another source (online or the
work of someone else), it is actually not a problem in itself, as long that you understand the solution
you write. The best way to ensure that you stay within the rules is to actually write your solution
yourself alone, without copying or reading a document that contains this solution, either online or the
solution of one of your classmates). If you actually understand the solution you want to propose, then
you should be able to write it alone; if you need to read some document, then this is that you did not
udnerstand the solution you propose and you need to work more on it.
Be aware that for every assignment I am myself searching online for possibly available solutions to
the questions in the assignment and it will not be difficult for me to detect plagiarism; computer-
assisted tools are also available to me to check copies that I deem to be dubious.
So always take care that there is a fine line between understanding from sources and plagiarism;
my best advice to avoid crossing this line is the one I provided above: write your proof alone, with
MATH 343, DR. C. CHAUVE, FALL 2020 1
Week Date Sections
from FS2009
Part/ References Topic/Sections Notes/Speaker
1 Sept 7 I.1, I.2, I.3 Combinatorial
Structures
FS: Part A.1, A.2
Comtet74
Handout #1
(self study)
Symbolic methods
2 14 I.4, I.5, I.6 Unlabelled structures
3 21 II.1, II.2, II.3 Labelled structures I
4 28 II.4, II.5, II.6 Labelled structures II
5 Oct 5 III.1, III.2 Combinatorial parameters
FS A.III
(self-study)
Combinatorial
Parameters Asst #1 Due
6 12 IV.1, IV.2 Multivariable GFs
7 19 IV.3, IV.4 Analytic Methods
FS: Part B: IV, V, VI
Appendix B4
Stanley 99: Ch. 6
Handout #1
(self-study)
Complex Analysis
8 26
IV.5 V.1
Singularity Analysis
9 Nov 2 Asymptotic methods Asst #2 Due
10
9 VI.1 Sophie
12 A.3/ C
Random Structures
and Limit Laws
FS: Part C
(rotating
presentations)
Introduction to Prob. Mariolys
11
18 IX.1 Limit Laws and Comb Marni
20 IX.2 Discrete Limit Laws Sophie
12
23 IX.3 Combinatorial instances of discrete Mariolys
25 IX.4 Continuous Limit Laws Marni
13 30 IX.5 Quasi-Powers and Gaussian limit laws Sophie
14 Dec 10 Presentations Asst #3 Due
Dr. Marni MISHNA, Department of Mathematics, SIMON FRASER UNIVERSITY
Version of: 11-Dec-09

f acul ty of sc ience MATH 895-4 Fall 2010
depar tment of mathemat ics Course Schedule MATH 343, ASSIGNMENT #2
your own words, without reading and copying any of your sources. Another good advice is that if you
actually rely on some sources (online, ook, group work, . . . ) to understand how to answer a question,
then cite your sources in your solution. Yo will not be penalized if you work using external sources
of documentation, but only if you copy them and do not cite them.
Preamble: how to hand-in your assignment
Given the fact this course is not given in-person, you must submit your assignment through canvas.
Please refer to http://www.sfu.ca/canva /student-guide/assignments/submit-an-assignment/
to learn how to do it. Also, please typeset your assignment; any typsetting method is fine (word, libre
office, google doc, LATEX, . . . ) but your assignment must be submitted as a PDF file, but for a coding
part that must be submitted as a maple Worksheet that we can run.
Question 1
Consider Algorithm 3 of lecture 16, th t generates all permutations of size n in lexicographic order.
Prove that there are two successive permutations that differ by exactly n positions.
Question 2
This question deals also with permutations. Algorithm 3 of lecture 16 is an iterative CAT algorithm
that generates all permutations. In this question we will study a recursive algorithm. It is based
on the idea we did see in the Fisher-Yates algorithm, to generate permutations by swapping pairs of
symbols.
Algorithm 1: Generating all permutations?
1 Permute (m: integer, pi: word)
2 if m = 0 then print pi
3 else
4 for i from 1 to m do
5 swap pii and pim
6 Permute (m− 1, pi)
7 swap pii and pim
8
9 AllPermutations (n)
10 pi := 1 2 · · · n
11 Permute (n)
The algorithm is different from previously seen recursive algorithms in that it is not based on a
counting formula (at least not as it is presented).
MATH 343, DR. C. CHAUVE, FALL 2020 2
Week Date Sections
from FS2009
Part/ References Topic/Sections Notes/Speaker
1 Sept 7 I.1, I.2, I.3 Combinatorial
Structures
FS: Part A.1, A.2
Comtet74
Handout #1
(self study)
Symbolic methods
2 14 I.4, I.5, I.6 Unlabelled structures
3 21 II.1, II.2, II.3 Labelled structures I
4 28 II.4, II.5, II.6 Labelled structures II
5 Oct 5 III.1, III.2 Combinatorial parameters
FS A.III
(self-study)
Combinatorial
Parameters Asst #1 Due
6 12 IV.1, IV.2 Multivariable GFs
7 19 IV.3, IV.4 Analytic Methods
FS: Part B: IV, V, VI
Appendix B4
Stanley 99: Ch. 6
Handout #1
(self-study)
Complex Analysis
8 26
IV.5 V.1
Singularity Analysis
9 Nov 2 Asymptotic methods Asst #2 Due
10
9 VI.1 Sophie
12 A.3/ C
Random Structures
and Limit Laws
FS: Part C
(rotating
presentations)
Introduction to Prob. Mariolys
11
18 IX.1 Limit Laws and Comb Marni
20 IX.2 Discrete Limit Laws Sophie
12
23 IX.3 Combinatorial instances of discrete Mariolys
25 IX.4 Continuous Limit Laws Marni
13 30 IX.5 Quasi-Powers and Gaussian limit laws Sophie
14 Dec 10 Presentations Asst #3 Due
Dr. Marni MISHNA, Department of Mathematics, SIMON FRASER UNIVERSITY
Version of: 11-Dec-09

f acul ty of sc ience MATH 895-4 Fall 2010
depar tment of mathemat ics Course Schedule MATH 343, ASSIGNMENT #2
2.1.
Use this algorithm to write the 24 permutations of size 4, in the order they are generated by the
algorithm.
2.2.
Prove that this algorithm indeed generates all permutations of n.
2.3.
Is this algorithm CAT? Justify your answer by finding a formula for the number of swaps done by the
algorithm to generate all permutations of size n.
2.4.
Modify this algorithm in order it generates derangements (see assignment 1) instead of permuta-
tions.
Question 3
This question deals with integer partitions. A partition of n is an ordered list of integers p1 ≥ p2 ≥
· · · ≥ pk > 0 such that
∑k
i=1 pi = n. For example (3, 3, 1) is a partition of n = 7. The natural
representation of an integer partition is the word p1p2 · · · pk; in our example this is the word 331.
Each pi is called a part.
3.1.
We denote by p(n, k) the number of partitions of n such that the largest part is k. So p(n, k) = 0 if
k > n. Prove the following recurrences for p(n, k) (if n ≥ k):
p(n, k) = p(n− 1, k − 1) + p(n− k, k)
p(n, k) =
min(k,n−k)∑
j=1
p(n− k, j)
Hint: you can prove the second recurrence from the first one.
3.2.
We now extend the lexicographic order to words of different length, that we call the general lexico-
graphic order. Let w1 and w2 be two words of respective length n1 and n2, with n1 ≤ n2. w1 is smaller
than w2 in the general lexicographic order if w1[1, n1] is smaller than w2[1, n1] in the lexicographic
order. In other words, we use the usual lexicographic order on the prefixes of w1 and w2 of length n1.
MATH 343, DR. C. CHAUVE, FALL 2020 3
Week Date Sections
from FS2009
Part/ References Topic/Sections Notes/Speaker
1 Sept 7 I.1, I.2, I.3 Combinatorial
Structures
FS: Part A.1, A.2
Comtet74
Handout #1
(self study)
Symbolic methods
2 14 I.4, I.5, I.6 Unlabelled structures
3 21 II.1, II.2, II.3 Labelled structures I
4 28 II.4, II.5, II.6 Labelled structures II
5 Oct 5 III.1, III.2 Combinatorial parameters
FS A.III
(self-study)
Combinatorial
Parameters Asst #1 Due
6 12 IV.1, IV.2 Multivariable GFs
7 19 IV.3, IV.4 Analytic Methods
FS: Part B: IV, V, VI
Appendix B4
Stanley 99: Ch. 6
Handout #1
(self-study)
Complex Analysis
8 26
IV.5 V.1
Singularity Analysis
9 Nov 2 Asymptotic methods Asst #2 Due
10
9 VI.1 Sophie
12 A.3/ C
Random Structures
and Limit Laws
FS: Part C
(rotating
presentations)
Introduction to Prob. Mariolys
11
18 IX.1 Limit Laws and Comb Marni
20 IX.2 Discrete Limit Laws Sophie
12
23 IX.3 Combinatorial instances of discrete Mariolys
25 IX.4 Continuous Limit Laws Marni
13 30 IX.5 Quasi-Powers and Gaussian limit laws Sophie
14 Dec 10 Presentations Asst #3 Due
Dr. Marni MISHNA, Department of Mathematics, SIMON FRASER UNIVERSITY
Version of: 11-Dec-09

f acul ty of sc ience MATH 895-4 Fall 2010
depar tment of mathemat ics Course Schedule MATH 343, ASSIGNMENT #2
Prove that the following algorithm (1) generates all partitions of nwith largest part k in lexicographic
order, but (2) is not AT.
Algorithm 2: Generating all partitions of n with largest part k
1 AllPartitionsRecV1 (n, k, t, p)
2 p[t] := k
3 if n = k then
4 print p[1, t] /* Prefix of p of length t */
5 else
6 for j from 1 to min(k, n− k) do AllPartitionsRecV1 (n− k, j, t+ 1, p)
7
8 AllPartitionsV1 (n, k)
9 p := 1 · · · 1 // word composed of n− k 1s
10 AllPartitionsRecV1(n, k, 1, p)
Hint: you can see the algorithm is not CAT y looking at the number of recursive calls on small
values of k.
3.3.
Prove now that the slightly different algorithm is a CAT algorithm to generate integer partitions
lexicographically.
Algorithm 3: Generating all partitions of n with largest part k
1 AllPartitionsRecV2 (n, k, t, p)
2 p[t] := k
3 if n = k or k = 1 then
4 print p[1, t]
5 else
6 for j from 1 to min(k, n− k) do AllPartitionsRecV2 (n− k, j, t+ 1, p)
7 p[t] := 1
8
9 AllPartitionsV2 (n, k)
10 p := 1 · · · 1 // word composed of n− k 1s
11 AllPartitionsRecV2(n, k, 1, p)
Question 4
Implement in Maple the Pru¨fer decoding algorithm. Use it together with one of the random words
generation algorithms seen in class to generate at least 100 random Cayley trees of size 20 and
estimate the expected height of a Cayley tree of size 20.
MATH 343, DR. C. CHAUVE, FALL 2020 4

欢迎咨询51作业君