4
$\begingroup$

What is the probability of two permutations on set X of size m (i.e. |X|=m) having at least n points of intersection? By this I mean that if two permutations, which I'll call g(x) and h(x), map a member x to g(x) for the first permutation and x to h(x) for the second permutation, what is the chance that g(x)=h(x) for at least n values of x?

$\endgroup$
10
  • 3
    $\begingroup$ You could also consider the permutation $h^{-1}g$, and see how many elements it fixes. What is your motivation for considering this problem? $\endgroup$
    – David Roberts
    May 17, 2012 at 10:36
  • $\begingroup$ I have a heuristic algorithm that assigns nodes between two isomorphic graphs of size m. i want to find the chance that given a random assignment of nodes, that at least n of them will be correct. For the time being, im assuming the isomorphism is unique. I'd like to know so that I can compare the random case to my algorithm's performance. The problem statement seems simple enough (or maybe the exactly n correct assignments case) that I figured it might be a well known question. $\endgroup$
    – jgonagle
    May 17, 2012 at 10:57
  • 2
    $\begingroup$ I agree with David Roberts: if g and h are independent uniform random permutations, then $ f := gh^-1 $ is also a uniform random permutation, and the number you want is just the number of fixpoints of that one permutation. So forget about g and h and just find the distribution of the number of fixed points of a single uniform random permutation f, which is a well-known problem. $\endgroup$ May 17, 2012 at 11:28
  • $\begingroup$ thanks, that makes a lot of sense. wish i could give both of you some rep points $\endgroup$
    – jgonagle
    May 17, 2012 at 12:28
  • 1
    $\begingroup$ @Igor: As $h$ ranges over all permutations, so does $gh$ for any fixed $g$. That's all that is needed to see it is obvious. $\endgroup$ May 18, 2012 at 0:31

1 Answer 1

6
$\begingroup$

You can use inclusion-exclusion to show that the number of permutations in $S_m$ having at least $n$ fixed points is $$\sum_{k=n}^m (-1)^{k-n}{k-1\choose n-1}{m\choose k}(m-k)! = m! \sum_{k=n}^m (-1)^{k-n}\frac{1}{k!}{k-1\choose n-1}$$

We describe now how to obtain the lefthand expression. The ${m\choose k}$ comes from choosing $k$ fixed points, the $(m-k)!$ counts permutations in $S_m$ having these $k$ fixed points, and then $(-1)^{k-n}{k-1\choose n-1}$ is an inclusion-exclusion counting coefficient, namely the Möbius function $\mu (\hat{0},\hat{1})$ on the subposet of the Boolean algebra of subsets of $\{ 1,\dots ,k \} $ where we exclude the subsets having size $1\le i \le n-1$.

One way to calculate this Möbius function is to use that each rank-selection of the Boolean algebra is lexicographically shellable. The desired Möbius function will be $(-1)^{k-n}$ multiplied by the number of so-called ``descending chains'' in the lexicographic shelling, which in this case is the number of permutations in $S_k$ that are ascending in the first $n$ letters and then descending after that, which in particular forces the letter $k$ to be the $n$-th letter in the permutation (in one-line notation).

This includes the well-known special case (usually phrased in terms of derangements) that the number of permutations in $S_m$ with at least one fixed point is $\sum_{k = 1}^m (-1)^{k-1} {m\choose k}(m-k)! $ which equals $ - (-m! + \sum_{k= 0}^m(-1)^k {m\choose k}(m-k)!) $. As $m$ goes to infinity, this approaches $ -m!(-1 + 1/e) = m!(1-1/e)$. A good reference for the $n=1$ case is chapter 2 of Enumerative Combinatorics, Volume 1, by Richard Stanley. The original source for lexicographic shellability is Anders Björner's paper ``Shellable and Cohen-Macaulay partially ordered sets''.

Added later: the comments above mention the recontres numbers. These give an approach for obtaining the $n>1$ case as a consequence of the $n=1$ case -- by choosing your fixed point set and then counting derangements on the remaining letters, summing over the possible fixed point sets. This results in a double sum, with an alternating sum as the inner sum.

$\endgroup$
3
  • $\begingroup$ @Mark: Thanks. I'm having a little trouble following your final step. $\endgroup$ Nov 5, 2012 at 2:50
  • $\begingroup$ @Patricia: There was a small typo: $j$ should vary from $0$ to $k−n$ in the final two sums. The final equality then follows from the identity $\sum_{i=0}^b (-1)^i \binom{a}{i} = \binom{a-1}{b}$. I'll delete the original comment and repost the corrected version. $\endgroup$ Nov 5, 2012 at 11:19
  • $\begingroup$ Just to expand on the final paragraph: The number of permutations of a set of size $m$ with exactly $r$ fixed points is $\binom{m}{r} (m-r)! \sum_{j=0}^{n-r} (-1)^j / j!$. Hence the number of permutations with at least $n$ fixed points is $m! \sum_{j,r} (-1)^j/ r!j!$, where the sum is over all $j$ and $r$ such that $r \ge n$ and $j+r \le m$. Now observe that the summands for which $j+r = k$ contribute $m! \sum_{j=0}^{k-n} (-1)^j/(k-j)!j!$ $= \frac{m!}{k!} \sum_{j=0}^{k-n} (-1)^j \binom{k}{j}$ $= \frac{m!}{k!} (-1)^{k-n} \binom{k-1}{k-n}$. The elegant formula in Patricia Hersh's answer follows. $\endgroup$ Nov 5, 2012 at 11:20

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.