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:

“The rising power of the United States in world affairs ... requires, not a more compliant press, but a relentless barrage of facts and criticism.... Our job in this age, as I see it, is not to serve as cheerleaders for our side in the present world struggle but to help the largest possible number of people to see the realities of the changing and convulsive world in which American policy must operate.”
—James Reston (b. 1909)

“At thirty years a woman asks her lover to give her back the esteem she has forfeited for his sake; she lives only for him, her thoughts are full of his future, he must have a great career, she bids him make it glorious; she can obey, entreat, command, humble herself, or rise in pride; times without number she brings comfort when a young girl can only make moan.”
—Honoré De Balzac (1799–1850)

“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)