- Describe bijections from the number of legal strings of size
to the number of legal lattice paths from
to
, and the number of triangulations of an
-gon.
- Show that a tree with
vertices has exactly
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
is the number of elements in some particular set. Thinking about strings of beads and necklaces could be useful here.
- Let
be a formal power series where
is the
-th Fibonacci number. Prove
as formal power series.
- Prove that the average number of fixed points in a permutation on
letters is
.
- Prove that in the last millennium you had an ancestor
such that there is a person
which was both an ancestor of the mother and father of
. For simplicity, you may assume generations reproduce every
years, the current population is less than
, and population has always increased with time.
- Let
be the
-th Fibonacci number, and let
be the golden ratio. Prove
.