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?
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 ♦Commented 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$– jgonagleCommented 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$– Zsbán AmbrusCommented 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$– jgonagleCommented 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$– Brendan McKayCommented May 18, 2012 at 0:31
|
Show 5 more comments
1 Answer
$\begingroup$
$\endgroup$
3
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.
answered Jun 1, 2012 at 20:40
-
$\begingroup$ @Mark: Thanks. I'm having a little trouble following your final step. $\endgroup$ Commented 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$ Commented 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$ Commented Nov 5, 2012 at 11:20