MATH 239 - Intro to Combinatorics

Instructor: P. Haxell
MC 6308
Office Hours: M 3-4, W 2:30-3:20
Mon Sept. 19 - 2:30 - 3:00
Nov 8. Midterm

Topics

Enumeration ~ 5 weeks

Graph Theory ~ 7 weeks

Lecture 1 - Sept 9th

What is enumeration about?

Typical Question: How many elements of a given set S have a given property?
We’ll answer such questions by encoding the properties of S using an algebraic expression called the generating series for S.

Then to answer the question, we will find a certain coefficient in the generating series.

eg: How many ways can you choose a dozen doughnuts if the available flavours are: Chocolate, Maple, Lemon, and Plain (at least 12 of each are available)?
The generating series for this problem is $\frac{1}{(1-x)^4}$
The answer is the coefficient of $x^{12}$ in $\frac{1}{(1-x)^4}$ which we denote by $[x^{12}]\frac{1}{(1-x)^4}$
eg: Same question but now only 3 chocolate, and 5 maple are available (other 2 have > 12 still).
The generating series becomes $\frac{(1-x^4)(1-x^6)}{(1-x)^4}$
The answer is $[x^{12}]\frac{(1-x^4)(1-x^6)}{(1-x)^4}$

Basic Counting Review

• For a set A we write $|A|$ for the number of elements of A
• For finite sets A and B recall $A\cup B = \{x:\ x\epsilon A\ or\ x\epsilon B\ (or\ both)\}$
• $A\cap B = \{x: x\epsilon A\ and\ x\epsilon B\}$
• Then $|A\cup B| = |A| + |B| - |A\cap B|$
• If A and B are disjoint (ie. $A\cap B = \phi (empty)$) then $|A\cup B| = |A| + |B|$
• The Cartesian product is $A \times B = \{(a,b) : a \epsilon A, b \epsilon B\}$
• Then $|A\times B| = |A||B|$
• For a positive integer k, then the Cartesian power of A is $A^k = \{(a_1, a_2, ... , a_k): a_i \epsilon A\ for\ each\ i\}$
  
  • i.e. the set of all ordered k-tuples of elements of A then $|A^k| = |A|^k$

eg: In the doughnut shop there are 3 chocolate, 5 maple, 19 lemon and 17 plain doughnuts left. Describe the set $S_0$ of all collections of doughnuts that can be formed (size of the collection not specified) as a Cartesian product.
Answer: $S_0$ as CP is : (chocolate) {0, 1, 2, 3} x (maple) {0, 1, 2, 3, 4, 5} x (lemon) {0, 1, … , 19} x (plain) {0, 1 , … , 17}

eg: No box contains BOTH chocolate and maple this time
Answer: $S_0$ as CP is :
$S_1$ = {0, 1, 2, 3} x {0} x {0, 1, … , 19} x {0, 1 , … , 17} $\cup$ {0} x {1, 2, 3, 4, 5} x {0, 1, … , 19} x {0, 1 , … , 17}

Let m be a positive integer
eg: Let S be the set of all subsets of {1, 7, … , m}. Fix k.
How many elements of S have size k?
ie. How many k-subsets (subsets of size k) of {1, … , m} are there?

Theorem: the number of k-subsets of {1, … , m} is $\frac{m(m-1) (m-k+1)}{k!}$

Proof: Let (B is binomial) B(m,k) denote he number of k-subsets of {1, … , m}
Consider the set $\mathscr{L}$ of ordered k-tuples of distinct elements of {1, … , m}
Then $|\mathscr{L}| = m(m-1)...(m-k+1)$
Now count $|\mathscr{L}|$ as follows: make a list of all B(m, k) k-subsets of {1, … , m} and then order each subset in all k! possible ways.
So $|\mathscr{L}| = B(m,k)k!$
Hence, $m(m-1) .. (m-k + 1) = |\mathscr{L}| = B(m,k)k!$
So, $B(m,k) = \frac{m(m-1)...(m-k+1)}{k!} \ \ \square$

Lecture - 5

Formal Power Series

Recall that for a fps (formal power series) A(x) we denote by $[x^n]A(x)$ the coefficient of $x^n$ in $A(x)$.

Substitution: Let A(x) = $\Sigma_{i\geq0}a_ix^i$ and $B(x)=\Sigma_{i\geq0}b_ix^i$ be fps. Suppose that the constant coefficient $b_0$ of B(x) is 0. Then A(B(x)) is a fps.
Proof:
Since $b_0 =0$ we can write $B(x)=xC(x)$ where $C(x) = b_1 + b_2x + b_3x^2 ...$
Then $A(B(x)) = a_0 + a_1xC(c) + a_2x^2C^2(x) + ...$
To show this a fps, we need to show that for every $h\geq$0, $[x^n]A(B(x))$ is a finite rational number. The good thing is: $[x^n]A(B(x)) = [x^n](a_0 + a_1xC(x) + ... + a_nx^nC^n(x))$ and $a_0 + a_1xC(x) + ... + a_nx^nC^n(x)$ is a fps since it is a finite sum of finite products of fps, which is a fps $\square$.
What goes wrong when $b_0 \neq = 0$?
We get $A(B(x)) = a_0 + a_1(b_0 + b_1x + ...) + a_2(b_0 + b_1x + ...)^2 ...$
Then for example $[x^0]A(B(x)) = a_0 + a_1b_0 + a_2b_0^2 + a_3b^3_0 + ...$ which is NOT in general a finite rational number. So in general, A(B(x)) is not a fps.

Inverse: Let A(x) be a fps. We say the fps C(x) is the (multiplicative) inverse of A(x) if $A(x)C(x) = 1 \ \ \ \ \ \ \ (= 1 + 0x + 0x^2 + 0x^3 + ...)$
e.g.:
$\Phi_{\mathscr{N}\geq0} = \Sigma_{i \geq 0}x^i =(\frac{1}{1-x})$ has inverse $C(x) = 1 - x$

Note: Multiplication of fps is symmetric therefore we can write $C(x)A(x)= (1-x)(1+x+x^2+....) = \\A(x)C(x) = (1+x+x^2+....)(1-x)$ We write $C(x) = A^{-1}(x)$
Check: $(1-x)(1+x+x^2+x^3 +) = 1 + x-x+x^2 -x^2 +x^3 -x ^3 +... \\= 1 + 0x + 0x^2 +... = 1$

Thm: The fps A(x) has an inverse if and only if $a_0 = [x^0] A(x)$ is non-zero
Proof: (=>) suppose C(x) is the inverse of A(x)
Then $[x^0]A(x)C(x) = [x^0](\Sigma_{i\geq0}a_ix^i)(\Sigma_{i\geq0}c_ix^i) \\= a_0c_0 = 1$
Therefore $a_0 \neq 0$
{<=} Supposed $a_0 \neq0$. Then we can write $A(x) = a_0(1-xB(x))$ where $B(x)=\frac{-a_1}{a_0} - \frac{a_2x}{a_0} + \frac{a_3x^2}{a_0} ...$
we claim $C(x) = \frac{1}{a_0} (1+ xB(x) + xB^2(x) + x^3B^3(x) + ...)$ is a fps: note that it is xB(x) substituted into $\frac{1}{a_0}(1 + x + x^2 + x^3 ...)$ and xB(x) has constant coefficient 0. Thus C(x) is a fps.
Then $A(x)C(x) = a_0(1-xB(x))\frac{1}{a_0}(1+xB(x) + x^2B^2(x) ...) = 1 \\+ xB(x) - xB(x) + x^2B^2(x) - x^2B^2(x) ... = 1$
So $C(x) = A^{-1}(x)$ by definition $\square$

eg. The inverse of $A(x) = 2 + 6x + 16x^2$ is $A(x) = 2(1+3x + 8x^2) = 2(1-x(-3-8x))$
Then $A^{-1}(x) = \frac{1}{2} (1+x(-3-8x) + x^2(-3-8x)^2) +x^3(-3 -8x)^3 ...)$
It is usually more convenient to express this as $\frac{1}{2}\frac{1}{1-x(-3-8x)}=\frac{1}{2}\frac{1}{1+3x+8x^2}$

Note that if A(x) has an inverse, then it is unique: Since if A(x)B(x) = 1 and A(x)C(x) =1. Then C(x)A(x)B(x) = C(x) => B(x) = C(x)
Note that if A(x) has an inverse and B(x) has an inverse then A(x)B(x) has inverse $A^{-1}(x)B^{-1}(x)$

Lecture 7

eg. How many