Let n be a positive integer. We sample n numbers a1, a2,..., an from the set {1,...,n} uniformly at random, with replacement. We say that picks i and j with i < j are a match if ai = aj.
What is the expected total number of matches?