Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
3  
You could also consider the permutation $h^{-1}g$, and see how many elements it fixes. What is your motivation for considering this problem? –  David Roberts May 17 '12 at 10:36
    
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. –  jgonagle May 17 '12 at 10:57
1  
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. –  Zsbán Ambrus May 17 '12 at 11:28
    
thanks, that makes a lot of sense. wish i could give both of you some rep points –  jgonagle May 17 '12 at 12:28
1  
@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. –  Brendan McKay May 18 '12 at 0:31
show 5 more comments

1 Answer

up vote 5 down vote accepted

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.

share|improve this answer
    
@Mark: Thanks. I'm having a little trouble following your final step. –  Patricia Hersh Nov 5 '12 at 2:50
    
@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. –  Mark Wildon Nov 5 '12 at 11:19
    
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. –  Mark Wildon Nov 5 '12 at 11:20
    
Oh, that's interesting. Thanks. –  Patricia Hersh Nov 5 '12 at 11:57
add comment

Your Answer

 
discard

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

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