MATH 475 Final: MATH475 BOYLE-M SPRING2005 0101 FINAL SOL

• School: University of Maryland
• Department: Mathematics
• Course: MATH 475
• Professor: All

Document Summary

Final exam solutions (take-home part: let be a random permutation of the set {1, 2, . Solution (a) let ek be the set of permutations of {1, 2, . n} which contain a cycle of length k. For an integer with n/2 < k n, the probability of ek is number of sets of k vertices for the cycle. Number of ways to cyclically order the k vertices in the cycle. Number of ways to permute the remaining n k vertices. Note there is no doublecounting above because the permutation has at most one cycle of length greater than n/2. Thus for n odd, we have pn = prob(cid:18) n k= n/2 ek(cid:19) = n. 1(cid:19)! (cid:21)2 and so when n is even we get. 2 n2 . (b) let be the euler constant, thus. Then lim n pn = lim n (cid:18) n. = lim n (ln(n) + ) (ln(n/2) + )