1
$\begingroup$

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

$\endgroup$
7
  • $\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$ Oct 13, 2010 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, 2010 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, 2010 at 11:41
  • 1
    $\begingroup$ Sorry, this is incorrect. $\endgroup$
    – zhoraster
    Oct 13, 2010 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, 2010 at 12:09

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.