Note: The Friday Sept 13 office hour has been moved to Thursday Sept 12
Supplementary Material
Integer Partitions (by H. Wilf, first 15 pages)
Derangements (by D. White)
Catalan Numbers (by D. White)
Sums of Powers and Stirling Numbers (by D. Stanton)
Matchings (by D. White)
Chromatic Polynomials (by D. White)
Matrices: Walks and Spanning Trees (by G. Musiker)
Gale-Shapley (by D. Austin)
Homework #1: Text: 1.3: 2 1.3:3 1.8: 6,12,20,21,23,32 2.1:9,12 2.5: 2,3
Additional Problems for HW #1
E1: Let $inv(\pi)$ be the number of inversions of a permutation $\pi=\pi_1\pi_2\cdots \pi_n$. $$ inv(\pi)=|\{(i,j): i\lt j, \pi_i\gt \pi_j\}|. $$ An inversion is a pair of numbers out of order. For example, if $\pi=6257134$, then $inv(\pi)=5+1+3+3+0+0=12.$
(a) If $\pi$ is a permutation on $\{1,2,\cdots,n\}$ of length $n$, what
is the maximum value of $inv(\pi)$?
(b) What is the average value of $inv(\pi)$ over all permutations
of $n$?
(c) How many permutations $\pi$ of $n$ have $inv(\pi)=1$? have
$inv(\pi)=2$?
E2: Let $V$ be the complex vector space of homogeneous polynomials of degree $n$ in three variables $x$, $y$, and $z$.
(a) What is $dim(V)$?
(b) What is the answer to (a) if we have $k$ variables instead of $3$
variables?
E3: Let $a_n$ be the number of non-negative integer solutions
$(e_1,e_2,e_3,e_4)$ to $e_1+e_2+e_3+e_4=n$ such that $e_3$ is even,
$2\le e_2 \le 5$, and $e_4\ge 3.$
(a) What is $A(x)=\sum_{n=0}^\infty a_n x^n$?
(b) Use (a) and calculus to find $a_n.$
E4: How many compositions of $n$ have exactly $k$ parts, with each part at least 3?
Homework #2: Text:3.6:3 3.8: 6,8,10,13 4.2: 8,9 4.3: 7,8,9,12,16
Additional Problems for HW #2
E1: (a) Show that the derangement numbers $D_n$ satisfy $$ \sum_{n=0}^\infty D_n \frac{x^n}{n!}=\frac{e^{-x}}{1-x}. $$
(b) Using (a) prove that the expected number of fixed points of a permutation is 1.
E2: Show combinatorially that for $n\ge 2$ the derangement numbers satisfy $$ D_n=(n-1)(D_{n-1}+D_{n-2}). $$
E3: Using the PIE, find the number of permutations of length $n$ such that $i+1$ does not immediately follow $i$, for $i$ from $1$ to $n-1.$ Show your answer is $D_n+D_{n-1}$.
E4: (a) Find the value of the Stirling number $S(n,n-1).$
(b) Find the value of the Stirling number $S(n,n-2).$
E5: What is $1^2+2^2+4^2+5^2+7^2+8^2+\cdots+(3n-2)^2+(3n-1)^2$?
Note: The Due Date for HW #3 is moved to Monday October 21. Two topics: integer partitions and Catalan numbers
Homework #3
E1: Find a closed formula for the number of partitions of $n$ into parts which are $1$'s or $2$'s.
E2: Use generating functions to find an equinumerous set of partitions to those partitions where each part has multiplicity at most 2.
E3: Using the base 2 bijection, which partition into odd parts corresponds to the partition with distinct parts $$ \lambda= 18+15+12+9+4+2+1. $$
E4: By considering the largest $NW$ justified square in the Ferrers diagram of a partition, prove $$ \prod_{k=1}^\infty \frac{1}{1-x^k}=\sum_{j=0}^\infty \frac{x^{j^2}}{(1-x)^2(1-x^2)^2\cdots (1-x^j)^2}. $$
E5: How many partitions have at most 3 parts and have the largest part at most 4?
E6: TRUE or FALSE? Give a proof or a counterexample. The number of partitions of $n$ which do not contain a part of size $1$ is $p(n)-p(n-1).$
E7: (a) How many block walks from $(0,0)$ to $(6,6)$ stay at or above the diagonal?
(b) How many block walks from $(0,0)$ to $(6,6)$ which stay at or above the diagonal first hit
the diagonal at $(4,4).$
(c) How many block walks from $(0,0)$ to $(6,6)$ which stay at or above the diagonal hit the diagonal
at least at $(2,2)$ and $(5,5)$?
E8: How many non-crossing handshakes are there with 14 people in a circle, if person 1 shakes with person 8?
E9: If a blockwalk from $(0,0)$ to $(n,n)$ is chosen at random, what is the probability that it stays at or above the diagonal?
E10: A leaf of a tree is a vertex of degree 1. A complete binary tree is a tree so that each non-leaf vertex has 2 sons. A rooted complete binary tree is a tree $T=(r,T_1,T_2)$ with a vertex r (called the root), which has left subtree $T_1$ and right subtreei $T_2$, either empty or complete binary trees.
For example there is exactly 1 rooted complete binary tree on 3 vertices, and
there are 2 rooted complete binary trees on 5 vertices.
(a) Draw all 5 rooted complete binary trees on 7 vertices.
(b) Prove that a rooted complete binary tree has $2n+1$ vertices, $n+1$ of which are leaves
(c) Prove that the number of rooted complete binary trees on $2n+1$ vertices is $C_n.$
E11: How many sequences of $n$ left and $n$ right parentheses are there which could be parsed correctly in a computer program? For example (()()) is allowed but ())(() is not. For $n=2$ there are a total of 2: (()) and ()().
Homework #4 Due Monday Nov 4 Text: 3.8.14, 6.5.3,6.6.2,6.7.5(has typo u=v mod p-1) ,6.8.5,6.9.3,6.10.10.
Additional Problems
E1:
Show that the Catalan numbers satisfy
$$
C_n \approx \frac{2^{2n}}{\sqrt{\pi} n^{3/2}}.
$$
E2: Using the normal approximation, how large should $n$ be so that if a fair coin is flipped $n$ times, at least 95% of the time you see between 49% and 51% heads?
E3: What is $$ \lim_{n\to\infty}\left( \frac{1}{5n+1}+\frac{1}{5n+2}+\cdots+ \frac{1}{7n}\right) ? $$
E4:(a) Suppose that $a$ is small. Expand
$$
-1/a*w+1/a^2*log(1+w*a)
$$
in a power series in $a$, up to $a^4.$
(b) Use (a) to show that the next term in Stirling's formula is
$$
n!\approx \left( \frac{n}{e}\right)^n \sqrt{2\pi n}
\left( 1+\frac{1}{12n}+O(\frac{1}{n^2})\right).
$$
Homework #5 Due Monday November 25
HW#5 Text: 7.2.7, 7.2.9, 7.2.11, 7.3.5, 7.3.9, 7.3.10, 8.1.3, 8.5.3, 8.5.4, 8.5.9, 9.2.3, 9.2.8
Additional Problems
E1: How many labeled trees are there on $\{1,2,\cdots,n\}$ such that
vertex 1 has degree $k$?
E2: Show that the following graphs are Hamiltonian:
(a) The vertices and edges of the
3-dimensional unit cube
(b) The complete bipartite graph $K_{n,n}$.
E3: Use the Marriage Theorem to prove that the following bipartite graph has a matching with $\binom{n}{k}$ edges. Let $A$ be the set of all $k$-subsets of $\{1,2, \cdots, n\}$. Let $B$ be the set of all $k+1$-subsets of $\{1,2, \cdots, n\}$. Connect edges $A-B$ if $A\subset B.$ Assume $2k+1 \le n.$
E4: TRUE or FALSE? The number of spanning trees of $K_n$ which use the edge $1-2$ is $2n^{n-3}.$
E5: Find the number of spanning trees in the complete bipartite graph $K_{n,m}$ using the matrix tree theorem.
Homework #6 Due Monday December 9
Text: 10.4.6, 10.4.8, 10.4.9, 12.3.1, 12.3.4, 13.4.2
Additional Problems
E1: Suppose the Gale-Shapley algorithm is applied which is optimal for the men with $n\ge 3$ men and women. Can 2 men be matched to their last choice, or is this impossible?
E2: If $M$ has first choice $W$ and $W$ has first choice $M$, show that $M-W$ in any stable marriage.
E3: Give an example to show that the men getting their first choices, or the the women getting their first choices could both be stable marriages in a single preferential list.
E4: Let the preference lists be given by cyclic permutations:
$$
M_1: (W_1,W_2,W_3,\cdots,W_n)\\
M_2: (W_2,W_3,W_4,\cdots,W_1)\\
M_3: (W_3,W_4,W_5,\cdots,W_2)\\
\vdots \\
M_n: (W_n,W_1,W_2,\cdots,W_{n-1})\\
$$
and
$$
W_1: (M_2,M_3,M_4,\cdots,M_1)\\
W_2: (M_3,M_4,M_5,\cdots,M_2)\\
W_3: (M_4,M_5,M_6,\cdots,M_3)\\
\vdots \\
W_n: (M_1,M_2,M_3,\cdots,M_{n})\\
$$
(a) Fix an integer $k$ between $1$ and $n$.
Suppose each man $M_i$ is matched to his $k$th choice. What is this matching?
(b) Is the marriage in (a) stable?
E5: TRUE of FALSE? If G is a connected weighted simple graph with distinct edge costs, then a minimum spanning tree must contain the two smallest cost edges.
E6: Show that it is impossible to have a connected planar graph, all of whose faces are hexagons, with each vertex degree at least 3.
Exam 3 key points
1. a forest of 4 trees
2. 50 edges
3. optimal for men= worst for men so only one stable marriage
4. 1/e(k-1)!
5. use Hall's thm
6. True
Exam 3 Scores Course Numerical Grade Course Letter Grade
Secret! 62 1.91 C
Polyester 67 2.26 C+
Dolphin 98 4.15 A
Laplace 93 3.86 A
November 76 2.46 B-
Contigo64 65 1.80 C
0418 98 4.23 A
RTB 71 2.37 C+
Haxorus 53 2.91 B
RoseannB 73 2.81 B
Bingo 95 4.08 A
coffee 52 2.64 B-
pebbles 81 2.93 B
heyjune 55 2.02 C
secretsecret 79 3.22 B+
fathomless 93 4.01 A
52899 63 2.36 C+
High score =100
Median =77
Exam 3 grade distribution
90-100 A (7)
65-89 B (9)
50-64 C (5)
Course Grade Distribution
A (7)
B+ (3)
B (3)
B- (2)
C+ (3)
C (3)
You were a good class and have a good vacation!