Selections of $r$ objects from a set of $n$ objects: Ordered with repetition $n^{r}$; Ordered without repetition $\frac{n !}{(n-r) !} ;$ Unordered with repetition $\left(\begin{array}{c}n+r-1 \ r\end{array}\right) ;$ Unordered without repetition $\left(\begin{array}{c}n \ r\end{array}\right)$.
Identity $2.8$ For $r \geq 1$ and $n \geq 0,\left(\begin{array}{c}n+1 \ r\end{array}\right)=\left(\begin{array}{c}n \ r\end{array}\right)+\left(\begin{array}{c}n \ r-1\end{array}\right)$.
Identity $2.9$ For $n \geq 0$ and $x, y \in \mathbb{R},(x+y)^{n}=\sum_{r=0}^{n}\left(\begin{array}{l}n \ r\end{array}\right) x^{r} y^{n-r}$.
Identity 2.10 For $n \geq 0, \sum_{r=0}^{n}\left(\begin{array}{l}n \ r\end{array}\right)=2^{n}$
Identity $2.11$ For $r \geq 1$ and $n \geq 0,\left(\begin{array}{l}n \ r\end{array}\right)=\sum_{i=0}^{n-1}\left(\begin{array}{c}i \ r-1\end{array}\right)$.
Identity $2.12$ For $n \geq 1, \sum_{r=0}^{n}(-1)^{r}\left(\begin{array}{l}n \ r\end{array}\right)=0$
Identity T1 For integers $m, n$ and $k$ with $1 \leq k \leq m \leq n, \quad\left(\begin{array}{c}n \ m\end{array}\right)\left(\begin{array}{c}m \ k\end{array}\right)=\left(\begin{array}{l}n \ k\end{array}\right)\left(\begin{array}{c}n-k \ m-k\end{array}\right)$.
Identity T2 For positive integers $k, m, n, \quad\left(\begin{array}{c}n+m \ k\end{array}\right)=\sum_{i=0}^{k}\left(\begin{array}{c}n \ i\end{array}\right)\left(\begin{array}{c}m \ k-i\end{array}\right)$.
Identity T1 For integers $m, n$ and $k$ with $1 \leq k \leq m \leq n, \quad\left(\begin{array}{c}n \ m\end{array}\right)\left(\begin{array}{c}m \ k\end{array}\right)=\left(\begin{array}{c}n \ k\end{array}\right)\left(\begin{array}{c}n-k \ m-k\end{array}\right)$.
Identity T2 For positive integers $k, m, n, \quad\left(\begin{array}{c}n+m \ k\end{array}\right)=\sum_{i=0}^{k}\left(\begin{array}{c}n \ i\end{array}\right)\left(\begin{array}{c}m \ k-i\end{array}\right)$.
The number of derangements of ${1,2, \ldots, n}$ is $n ! \sum_{r=0}^{n} \frac{(-1)^{r}}{r !}$.
The number of permutations of ${1,2, \ldots, n}$ with exactly $k$ fixed points is $\frac{n !}{k !} \sum_{r=0}^{n-k} \frac{(-1)^{r}}{r !}$.
Möbius function For each positive integer $n$ with prime factorisation $n=p_{1}^{e_{1}} p_{2}^{e_{2}} \cdots p_{r}^{e_{r}}$,
$$
\mu(n)= \begin{cases}1 & \text { if } n=1 \ 0 & \text { if } e_{i}>1 \text { for any } i \in{1,2, \ldots, r} \ (-1)^{r} & \text { if } e_{1}=e_{2}=\cdots=e_{r}=1\end{cases}
$$
Theorem 5.17 Taking the sum over all positive divisors $d$ of $n, \sum_{d \mid n} \mu(d)= \begin{cases}1 & \text { if } n=1 \ 0 & \text { if } n>1\end{cases}$
Theorem $6.22$ (Dilworth’s Theorem) In a partially ordered set $P$, the minimum number of chains that partition $P$ is equal to the size of a maximum antichain in $P$.
Theorem $6.23$ In a partially ordered set $P$, the minimum number of antichains that partition $P$ is equal to the length of a maximum chain in $P$.
Theorem 9.40 (The Orbit-Stabilizer Theorem) Suppose a finite group $G$ acts on a set $X$. Then for each $x \in X,|\operatorname{orb}(x)| \times|\operatorname{Stab}(x)|=|G|$.
Theorem $10.42$ (The Counting Theorem) Let $G$ be a finite group acting on a finite set $X$. Then the number $t$ of orbits of the action is given by the formula $t=\frac{1}{|G|} \sum|\operatorname{fix}(g)|$.
Geometric Series $1+t+t^{2}+\cdots+t^{n}=\sum_{r=0}^{n} t^{r}=\frac{1-t^{n+1}}{1-t} \quad t^{0}+t^{1}+t^{2}+\cdots=\sum_{r=0}^{\infty} t^{r}=\frac{1}{1-t}=(1-t)^{-1}$
For a positive integer $n, \quad(1+t)^{n}=\left(\begin{array}{c}n \ 0\end{array}\right) t^{0}+\left(\begin{array}{c}n \ 1\end{array}\right) t^{1}+\left(\begin{array}{l}n \ 2\end{array}\right) t^{2}+\cdots+\left(\begin{array}{l}n \ n\end{array}\right) t^{n}=\sum_{r=0}^{n}\left(\begin{array}{l}n \ r\end{array}\right) t^{r}$
Extended Binomial Theorem
If $n$ is any rational number, then $(1+t)^{n}=1+n t+\frac{n(n-1)}{2 !} t^{2}+\frac{n(n-1)(n-2)}{3 !} t^{3}+\cdots=\sum_{r=0}^{\infty}\left(\begin{array}{l}n \ r\end{array}\right) t^{r}$
If $n$ is positive then $\left(\begin{array}{c}-n \ r\end{array}\right)=(-1)^{r}\left(\begin{array}{c}n+r-1 \ r\end{array}\right) .$ In particular, $\left(\begin{array}{c}-1 \ r\end{array}\right)=(-1)^{r}$
The EGF for selecting an object with unlimited repetition allowed is $1+t+\frac{t^{2}}{2 !}+\frac{t^{3}}{3 !}+\cdots=e^{t}$.
The EGF for selecting an object at least once is $t+\frac{t^{2}}{2 !}+\frac{t^{3}}{3 !}+\frac{t^{4}}{4 !}+\cdots=e^{t}-1$
The EGF for selecting an object at least twice is $\frac{t^{2}}{2 !}+\frac{t^{3}}{3 !}+\frac{t^{4}}{4 !}+\cdots=e^{t}-1-t$.
The EGF for selecting an object an even number of times is $1+\frac{t^{2}}{2 !}+\frac{t^{4}}{4 !}+\frac{t^{6}}{6 !}+\cdots=\frac{e^{t}+e^{-t}}{2}$
The EGF for selecting an object an odd number of times is $\frac{t^{1}}{1 !}+\frac{t^{3}}{3 !}+\frac{t^{5}}{5 !}+\cdots=\frac{e^{t}-e^{-t}}{2}$
Theorem 14.61 The number of odd partitions of $n$ equals the number of distinct partitions of $n$.
Theorem $14.62$ The number of partitions of $n$ of length at most $r$ is equal to the number of partitions of $n$ with largest part at most $r$.
Theorem 14.63 The number of partitions of $n$ that are both odd and distinct is equal to the number of self-conjugate partitions of $n$.
$\mathrm{T}{1}$ $d{2}-1, d_{3}-1, \ldots, d_{\Delta+1}-1, d_{\Delta+2}, d_{\Delta+3}, \ldots, d_{p}$ is graphical.
Theorem $26.82$ A connected graph is Eulerian if and only if each vertex has even degree and is semi-Eulerian if and only if it has exactly two vertices of odd degree. $S \mid$ components, then $G$ is not Hamiltonian. degree at least $p / 2$ then $G$ is Hamiltonian.
Theorem $28.91$ A matching $M$ in a graph $G$ is a maximum matching if and only if there is no augmenting path in $G$
Theorem $28.92$ (Hall’s Theorem) Let $G$ be a bipartite graph with parts $V_{1}$ and $V_{2} .$ Then there exists a matching in $G$ containing all the vertices of $V_{1}$ if and only if for every subset $S \subseteq V_{1}$, the number of vertices adjacent to vertices of $S$ is greater than or equal to the number of vertices in $S .$
MATH2302 – Discrete Mathematics II: Theory & Applications
| Lecturer | Associate Professor Diane Donovan |
| Course Link | UQ Site |
| Faculty | Science |
| Prerequisites | MATH1061 |
| Contact Hours | 3L 1T |
| Semester(s) Taught | Semester 2 |
| Course Units | 2 |
90.3/100Learning Materials ( 86 )Learning Activities ( 100 )Blackboard Management ( 94 )Course Content ( 100 )Course Structure ( 79 )Contact Availability ( 88 )Course Difficulty ( 85 )
This is a qual course, fairly pure but that’s what you wanted, right?
Resources: no textbook, just good course notes. Just studying these notes would be enough for the midsem but I’d give the leccy’s a go before the final. More examples in the notes would be nice so I hope over time they expand it.
My main issue isn’t with this course exactly, but that I was hoping for some more advanced logic after MATH1061, to lead into higher level set theory courses [there’s no 2nd year logic and set theory courses]. The topology was real dece since the only other time you’ve seen it is in an analysis course.
If you’re shakey on math1061 content some areas might be a bit rough.
This isn’t a write-off easy course.
It might seem a bit weird that Math2301 and Math2302 both have bits about group theory… it feels just a little inefficient.
I’ve always been worse with permutations, combinations and counting, so I didn’t really rate that part of the course but I can appreciate that some people love their combinatorics. The graph theory is beautiful, since isn’t too much or too little, and this course would lead nicely into third year courses.
If it were up to me, i’d throw in a whole bunch of tiny, miscellanious maths, recreational bits, everything you might see in a popular science book, or it’d be nice if the lecturers could pose some interesting questions, tell you what’s still open in mathematics, give you a bigger picture, etc.
The difficulty is mostly conceptual, and just getting familiarity. You just practice a lot and you’ll be right, doesn’t feel unfair. If you know your stuff it’s actually pretty easy but you’ve got to work for it.Semester taken
Semester 1 – 2017Your program/major
BSc, Math and Physics MajorIs lecture attendance necessary?
The lectures are worth itIs the textbook necessary?
What\’s a textbookPositives
- MATH1061++
- Fun content
- Bridge for higher graph theory courses
Negatives
- Overlaps with Math2301 a little??
- Notes aren’t always enough to learn from
- Lots of math1061 knowledge expectd
