Midterm Revision
Let \(\alpha\in \mathbb{C}\), define \((1+s)^{\alpha}=\sum_{n=0}^{\infty}\frac{\left(\alpha\right)_{n}}{n!}s^{n}\) where \((\alpha)_{n}= \begin{cases} 1,n=0 \\ \alpha(\alpha-1)...(\alpha-n+1),n>0 \end{cases}\)
\(\frac{1}{1-s}=1+s+s^{2}+...\) and \(\exp(s)=1+\frac{s}{1!}+\frac{s^{2}}{2!}+\frac{s^{3}}{3!}+...\)
The handshaking lemma
Let \(\Gamma=(E,V)\) be a finite (\(\#\text{vertices}<\infty\)) simple graph, then \(2\#E=\sum_{v\in V}\deg(v)\)
Corollary
Every tree has a leaf. (leaf is a degree \(1\) vertex)
Proposition
\(\Gamma=(V,E)\) is a tree iff \(\#V=n\), then \(\#E=n-1\)
Cayley's formula(Borchardt)
The number of labelled trees on \(n\) vertices equals \(n^{n-2}\)
Theorem
Let \(n\geq 2\), then there is a bijection between the set of labelled trees on \(n\) vertices and Prüfer codes of index \(n\)
Tree \(\rightarrow\) code
Step: Take the leaf with the smallest label, delete it and write the label of the adjacent vertex into the code. Do until only two vertices left.
Example: For the tree:
, we have 
Code \(\rightarrow\) Tree
Make a list of labels, together with the expected degrees
Example: 3111, then write the list: 14 21 32 41 51 61
Some folklore character had 5 children. Among his descendants, 100 had exactly 3 children, all others left no children. How many descendants did this guy have?
There will be not cycle since every cycle should have two distinct path, but it's clearly these two paths should go through Ivan
The first equation is Sum of Total Degrees
Sum of degrees = (Degree of IVAN) + (Sum of degrees of the 100) + (Sum of degrees of the 1)
The second equation is Vertices and Edges in a Tree(\(\#E+1=\#V\))
The number of vertices (#V) is the total number of people: IVAN (1 person) + the 100 descendants who had 3 children + the x descendants who had no children.
Midterm 2 coverage:
Generating functions/formal power series
Standard formal power series -- coefficient expansions
Rational formal power series and partial fraction decomposition
Generating functions for linear recurrences with constant coefficients
Basic notions of graph theory: vertices, edges, degree
Subgraphs, induced subgraphs
Walks, paths, cycles. Connectedness.
Trees and Cayley formula