(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.

  • $\begingroup$ 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. $\endgroup$ – Douglas Zare Oct 13 '10 at 10:50
  • $\begingroup$ 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$. $\endgroup$ – user10024 Oct 13 '10 at 11:20
  • $\begingroup$ 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. $\endgroup$ – zhoraster Oct 13 '10 at 11:41
  • 1
    $\begingroup$ Sorry, this is incorrect. $\endgroup$ – zhoraster Oct 13 '10 at 11:44
  • 1
    $\begingroup$ 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). $\endgroup$ – zhoraster Oct 13 '10 at 12:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.