Random Permutation Statistics - Number of Permutations Containing An Even Number of Even Cycles

Number of Permutations Containing An Even Number of Even Cycles

We may use the Flajolet–Sedgewick fundamental theorem directly and compute more advanced permutation statistics. (Check that page for an explanation of how the operators we will use are computed.) For example, the set of permutations containing an even number of even cycles is given by

$\mathfrak{P}(\mathfrak{C}_{\operatorname{odd}}(\mathcal{Z})) \mathfrak{P}_{\operatorname{even}}(\mathfrak{C}_{\operatorname{even}}(\mathcal{Z})).$

Translating to exponential generating functions (EGFs), we obtain

$\exp \left( \frac{1}{2} \log \frac{1+z}{1-z} \right) \cosh \left( \frac{1}{2} \log \frac{1}{1-z^2} \right)$

$\frac{1}{2} \exp \left( \frac{1}{2} \left( \log \frac{1+z}{1-z} + \log \frac{1}{1-z^2} \right) \right) + \frac{1}{2} \exp \left( \frac{1}{2} \left( \log \frac{1+z}{1-z} - \log \frac{1}{1-z^2} \right) \right).$

This simplifies to

$\frac{1}{2} \exp \left( \frac{1}{2} \log \frac{1}{(1-z)^2} \right) + \frac{1}{2} \exp \left( \frac{1}{2} \log (1+z)^2 \right)$

$\frac{1}{2} \frac{1}{1-z} + \frac{1}{2} (1+z) = 1 + z + \frac{1}{2} \frac{z^2}{1-z}.$

This says that there is one permutation of size zero containing an even number of even cycles (the empty permutation, which contains zero cycles of even length), one such permutation of size one (the fixed point, which also contains zero cycles of even length), and that for, there are such permutations.

Read more about this topic: Random Permutation Statistics

Famous quotes containing the words number of, number, permutations and/or cycles:

“My tendency to nervousness in my younger days, in view of the fact of a number of near relatives on both my father’s and mother’s side of the house having become insane, gave some serious uneasiness. I made up my mind to overcome it.... In the cross-examination of witnesses before a crowded court-house ... I soon found I could control myself even in the worst of testing cases. Finally, in battle.”
—Rutherford Birchard Hayes (1822–1893)

“If we remembered everything, we should on most occasions be as ill off as if we remembered nothing. It would take us as long to recall a space of time as it took the original time to elapse, and we should never get ahead with our thinking. All recollected times undergo, accordingly, what M. Ribot calls foreshortening; and this foreshortening is due to the omission of an enormous number of facts which filled them.”
—William James (1842–1910)

“Motherhood in all its guises and permutations is more art than science.”
—Melinda M. Marshall (20th century)

“The stars which shone over Babylon and the stable in Bethlehem still shine as brightly over the Empire State Building and your front yard today. They perform their cycles with the same mathematical precision, and they will continue to affect each thing on earth, including man, as long as the earth exists.”
—Linda Goodman (b. 1929)