# Combinatorics Exercises

• Describe bijections from the number of legal strings of size $2n$ to the number of legal lattice paths from $(0,0)$ to $(n,n)$, and the number of triangulations of an $(n+2)$-gon.
• Show that a tree with $n$ vertices has exactly $n-1$ edges.
• Prove that a finite graph is bipartite if and only if it contains no cycles of odd length.
• Show that every simple graph has two vertices of the same degree.
• Prove that the sum of the degrees of the vertices of any finite graph is even.
• Give a combinatorial proof of Fermat’s little theorem. That is, show $(k^{p}-k)/p$ is the number of elements in some particular set. Thinking about strings of beads and necklaces could be useful here.
• Let $f(x) = \sum_{n = 0}F_{n}x^{n}$ be a formal power series where $F_{n}$ is the $n$-th Fibonacci number. Prove $f(x) = \frac{1}{1-x-x^{2}}$ as formal power series.
• Prove that the average number of fixed points in a permutation on $n$ letters is $1$.
• Prove that in the last millennium you had an ancestor $A$ such that there is a person $P$ which was both an ancestor of the mother and father of $A$. For simplicity, you may assume generations reproduce every $25$ years, the current population is less than $10^{10}$, and population has always increased with time.
• Let $F_{n}$ be the $n$-th Fibonacci number, and let $\varphi$ be the golden ratio. Prove $\lim_{n \to \infty}\frac{F_{n+1}}{F_{n}} = \varphi$.