A cyclic permutation or cycle of a set A is a permutation th

A cyclic permutation (or cycle) of a set A is a permutation that cyclically permutes the elements of A. for example, the permutation sigma, with sigma (1) = 2, sigma (2) = 4, sigma (3) = 1, sigma (4) = 5. sigma (5) = 3, is cyclic, and denoted by (12453) or any of its cyclic equivalents, such as (24531) or (31245). It can be shown that every permutation of a set N can be expressed as a product of cycles that cyclically permute disjoint subsets of N, unique except for the order of the cycles. Thus, for example, (153)(24) is the cyclic j decomposition of the permutation a given by sigma (1) = 5, sigma (2) = 4, sigma (3) = 1, sigma (4) = 2, sigma (5) = 3. Prove that t(n, k) is the number of permutations of an n-element sot that have exactly k cycles in their cyclic decomposition.

Solution

For k > 1, a k-cycle is a permutation = (i1, . . . , ik) that acts on X in the following way (1) maps ( i1 i2 . . . ik i1) (a cyclic shift of list entries)

j j for all j not in the list {i1, . . . , ik}                                      

One-cycles (k) are redundant; every one-cycle reduces to the identity map idX , so we seldom write them explicitly, though it is permissible and sometimes useful to do so. The support of a k-cycle is the set of entries supp() = {i1, . . . , ik}, in no particular order. The support of a 1-cycle (k) is the one-point set {k}. Recall that the order of the entries in a cycle (i1, . . . , ik) matters, but cycle notation is somewhat ambiguous: the following symbols (i1, . . . , ik) = (i2, . . . , ik, i1) = (i3, . . . , ik, i1, i2) = . . . = (ik, i1, . . . , ik1) all describe the same operation on X.

Thus (123) = (231) = (312) all specify the same operation 1 2 3 1 in X,

and likewise (i, j) = (j, i) for any 2-cycle.

If we mess up the cyclic order of the entries we do not get the same element in Sn,

for example (123) 6= (132) . In Section 3.1 we also showed how to evaluate products of cycles, and noted the following important fact. (2) If = (m1, . . . , mk) and = (n1, . . . , nr) are disjoint cycles, so that supp() supp( ) = {m1, . . . , mk} {n1, . . . , nr} = then these operations commute = . If supports overlap, the cycles may or may not commute. Since any 1-cycle (k) is the identity operator, certain cycles with overlapping supports such as (4) and (345) do commute, so property (2) only works in one direction; on the other hand an easy calculation of the sort outlined in Example , shows that (23)(345) = (2345), which is not equal to (345)(23) = (2453).

every permutation can be written uniquely as a product of disjoint commuting cycles.