MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

(Am not mathematician, sorry in advance for the sloppy notations.)

Consider the class of permutations of $n$ elements such that for each permutation $\pi$ in this class, and for each $x$ in $\{1,\dots,n\}$, $\pi(x)$ can take only two fixed distinct values.

My question is: what's the expected number of cycles of size $m$ for such a class of permutations? In particular, does it differ from the case of a uniformly random permutation?

Guess that a first step is to determine the size of these classes. For $n=2^k$, one can show that such a class contains $2^{2^{n-1}}$ such permutations (see each element as a $k$-bit string, and the permutation as a nonsingular feedback shift register, then count the number of distinct feedback functions).

Thanks for any hint or reference to related previous work.

share|cite|improve this question
You say "the class" but you have not specified what collection of permutations you mean, only given a condition. Also, I don't think you mean $2^{2^{n-1}}$. For any $m$, it is easy to construct permutations which satisfy the condition which have no cycles of length $m$, so perhaps you are thinking of additional conditions you haven't mentioned. – Douglas Zare Oct 13 '10 at 10:50
Sorry I meant $2^{2^{k-1}}=2^{n/2}$. A class is characterized by the two values that $\pi(x)$ can take, for each $x$. – user10024 Oct 13 '10 at 11:20
The answer depends on how the values which $\pi(x)$ can take related for different $x$. If, say $\pi(x)\in \{x,x+1\}\pmod n$, then there are either $n$ cycles or $1$ cycle. – zhoraster Oct 13 '10 at 11:41
Sorry, this is incorrect. – zhoraster Oct 13 '10 at 11:44
But the first statement is still correct: The answer depends on how the values which $\pi(x)$ can take related for different $x$. Say, $n=2m$. (i) Let $\pi(1)\in\{1,2\}$, $\pi(2)\in\{1,2\}$, $\dots$, $\pi(2m-1)\in\{2m-1,2m\}$, $\pi(2m)\in\{2m-1,2m\}$, then there $3n/4$ cycles on average. (ii) $\pi(x)\in \{x,x+1\}\pmod n$. Then the permutations look like products of disjoint cycles $(k\,k+1\,\dots,k+j)$ (this is also $\mod n$). And here the expected number is around $n$ (this is the expected number of maximal unicolor fragments in a two-colored necklace). – zhoraster Oct 13 '10 at 12:09

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.