Math 172—Combinatorics—Spring 2010Problem Set 12Suggested study exercises: Chapter 8, Ex. 20, 21Problems:A. Call a permutation of a finite set X, together with a linear ordering of its cycles,a cycle-ordered permutation of X. Find a formula for the exponential generating functionP∞n=0cnxn/n!, where cnis the number of cycle-ordered permutations of a set X with nelements.B. An involution is a permutation σ : X → X such that σ2is the identity permutation.(i) Show that the number of involutions of X is equal to the number of partitions of theset X in which every block has 1 or 2 elements.(ii) Find a formula for the exponential generating functionP∞n=0tnxn/n!, where tnis thenumber of involutions of a set X with n elements.(iii) Derive a formula for tnfrom part (ii).C. Given a combinatorial species F, let Fedenote the species of F structures on sets ofeven size, i.e. Fe(X) = F(X) if |X| is even, and Fe(X) = ∅ if |X| is odd. Similarly, let Fobe the species of F structures on sets of odd size.(i) Show that the exponential generating functions for these species are given byFe(x) =F (x) + F (−x)2, Fo(x) =F (x) − F (−x)2(ii) Use part (i) to show that the exponential generating function for the species ofpermutations with all cycles of even length is given byr11 − x2,and for the species of permutations with all cycles of odd length byr1 + x1 − x.(iii) Use part (ii) to deduce the result given as Theorem 6.24 in your textbook.D. A weighted species is a species of combinatorial stuctures F, together with a weightfunction w : F(X) → N for every finite set X. As usual for species, we require that theweight assigned to an F structure on X does not depend on the names of the labels. Inparticular, the weight enumeratorfn(t) =Xa∈F (X)tw(a)should depend only on n = |X|, and not on the specific set X chosen. Hence, given a weightedspecies (F, w), we can associated to it a mixed ordinary and exponential generating functionF (x, t) =∞Xn=0fn(t)xnn!.Provided that we define the weight of a product or composite structure to be the sum ofthe weights of its pieces, the product and composition principles will work for these mixedgenerating functions just like they do for exponential generating functions (compositionmeans composition as functions of x in this setting).(i) Consider the species of permutations, weighted by w(σ) = (number of cycles of σ), sothe mixed generating function isP (x, t) =∞Xn=0Xkc(n, k)tkxnn!.Find a closed formula for P (x, t) from exponential generating function principles.(ii) Use the (extended) binomial theorem to show that the formula in (i) is equivalent tothe formulaXkc(n, k)tk= t(t + 1) · · · (t + n − 1),given in Lemma 6.13 in your textbook.(iii) Repeat part (i) for permutations with all cycles of even length.(iv) Use part (iii) to re-derive the result of Problem Set 8, Problem