Counting Mappings
(a) Let X = {1,2,...,n} and Y = {1,2,...,m}. How many distinct functions f are there from X to Y?
(b) How many of these functions f are injective?
(c) For functions f as in part (a), consider the (ordered) lists .
How many distinct such lists are there? How many are there if we only consider surjective functions?
2 Counting on Graphs
(a) How many distinct undirected graphs are there with n labeled vertices? Assume that there can be at most one edge between any two vertices, and there are no edges from a vertex to itself.
(b) How many ways are there to color a bracelet with n beads using n colors, such that each bead has a different color? Note: two colorings are considered the same if one of them can be obtained by rotating the other.
(c) How many distinct cycles are there in a complete graph with n vertices? Assume that cycles cannot have duplicated edges. Two cycles are considered the same if they are rotations or inversions of each other (e.g. (v1,v2,v3,v1), (v2,v3,v1,v2) and (v1,v3,v2,v1) all count as the same cycle).
(d) How many ways are there to color the faces of a cube using exactly 6 colors, such that each face has a different color? Note: two colorings are considered the same if one of them can be obtained by rotating the other.
3 Captain Combinatorial
Please provide combinatorial proofs for the following identities.
.
. .
