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.