Spring/Fall 2010
Permutations Agreeing in \(k\) Positions
Stephen Curry
Department of Mathematics and Statistics, Zayed University, Dubai, United Arab Emirates
Abstract
In this article we develop recursive and closed form formulas for the number of permutations on \(n\) objects that agree with a given permutation in exactly \(k\) positions.
Introduction
The genesis of this investigation lies in a conversation the author had with Mr. Mahmoud Elgibali, an Instructor of Arabic and Islamic Studies at Zayed University in the United Arab Emirates. During the conversation Mr. Elgibali related an ancient practice of Persian leaders: making important military and other governmental decisions based on entries of a ten by ten matrix, each row of which and each column of which contained the integers from one through ten. Mr. Elgibali asked if the author could construct such a square of numbers, and he left the gathering with a simple example of one made up of shifts of an ordering of the integers \(1, 2, \dots, 10\).
Since no two rows of such a square can have identical entries in any position, we quickly became interested in constructing permutations whose \(i^{\mathrm{th}}\) positions were not equal to the \(i^{\mathrm{th}}\) positions of a given permutation. From that starting point we proceeded to develop both recursive and closed form formulas for the number of permutations of \(n\) symbols that have exctly \(k\) positions with entries equal to those of a given permutation of the same \(n\) symbols.
Conventions and Preliminaries
We say that a permutation \(q\) on \(n\) symbols is a one-to-one function \(q\) from \(\{1,2,\dots,n\}\) onto \(\{1,2,\dots,n\}\). Of course, we could use any symbols; however, for convenience, we shall use the integers from \(1\) to \(n\). We say that the permutations \(q\) and \(p\) agree at the \(i^{\mathrm{th}}\) position if, and only if, \(q(i)=p(i)\).
We shall denote by \(P_k(n)\) the number of permutations on \(n\) symbols that agree with a given permutation in exactly \(k\) positions. Of course, we should require \(k\leq n\); however, for convenience we shall agree that \(P_k(n)=0\) for \(k>n\). We note that \(P_k(n)\) is independent of the given permutation, and for convenience we shall take the given permutation to be the identity, \(p(i)=i\) for each \(i\in\{1, 2, \dots, n\}\).
We note that \(P_0(1)=0\) and \(P_0(2)=1\). For \(n\geq 1\), \(P_n(n)=1\). Thus, it is consistent to take \(P_0(0)=0\).
\(\mathbf {P_0(n)}\)
We begin with a recursive formula for \(P_0(n)\):
Theorem 1: For each positive integer \(n\geq 2\), \(P_0(n)=n P_0(n-1)+(-1)^n\).
We have noted that the statement is true for \(n=1\) and \(n=2\), and we proceed inductively.
If \(q\) is a permutation on \((n+1)\) symbols and does not agree with the identity at any position, then we know that for some \(a\ne n+1\), \(q(n+1)=a\). One of two cases must hold: either (1) \(q(a)\ne n+1\) or (2) \(q(a)=n+1\).
Consider the first case where \(q(n+1)=a\) and \(q(a)\ne n+1\). There is a \(j\in\{1, 2, \dots ,n\}\setminus\{a\}\) so that \(q(j)=n+1\). If we swap the values of \(q(j)\) and \(q(n+1)\), so that \(q(j)=a\), and consider only the set \(\{q(1), q(2), \dots , q(n)\}\), omitting \(q(n+1)\) from consideration, we have a permutation on \(n\) symbols, with \(q(i)\ne i\) for any \(i\in\{1, 2, \dots, n\}\). We should note that this process does not necessarily yield distinct \(n\)-symbol permutations when we operate on distinct \((n+1)\)-symbol permutations. For example, the permutations \(\{4\ 1\ 2\ 3\}\) and \(\{3\ 4\ 2\ 1\}\) both yield \(\{3\ 1\ 2\}\). However, our interest lies in reversing this process and counting the number of distinct permutations on \((n+1)\) symbols that can be constructed from a given permutation on \(n\) symbols in this manner.
Each permutation \(q'\) on \(n\) symbols yields \(n\) distinct permutations on \((n+1)\) symbols by selecting \(j=1, 2, \dots, n\), setting \(q(n+1)=q'(j)\) and \(q(j)=n+1\). None of the permutations thus constructed agree with the identity at any position. Thus, we have \(nP_0(n)\) permutations on \((n+1)\) symbols having the form of case (1).
Consider the second case where \(q(a)=n+1\) and \(q(n+1)=a\). Now, consider only \(\{q(1), q(2), \dots, q(a-1), q(a+1), \dots, q(n)\}\). This is simply a permutation on the \((n-1)\) symbols \(\{1,2,\cdots ,a-1, a+1,\cdots ,n\}\) that does not agree with the permutation \(\{1\ 2\ \cdots a-1\ a+1\ \cdots n\}\) at any position, and there are \(nP_0(n-1)\) of these, for we may take \(a=1, 2, \dots , n\). There is clearly a one-to-one correspondence between permutations on \((n+1)\) symbols of the second type and permutations of the symbols \(\{1,2,\cdots ,a-1, a+1,\cdots ,n\}\) that do not agree with \(\{1\ 2\ \cdots a-1\ a+1\ \cdots n\}\) at any position. Thus, we have \(nP_0(n-1)\) permutations on \((n+1)\) symbols having the form of case (2).
However, \(nP_0(n-1)=P_0(n)-(-1)^n=P_0(n)+(-1)^{n+1}\). Combining the totals from these two cases, we have \[P_0(n+1)=(n+1)P_0(n)+(-1)^{n+1}.\]
An example should illustrate and motivate the subsequent theorem.
Example: We take \(n=8\). \(P_0(8)=8P_0(7)+1=8(7P_0(6)-1)+1\dots \) \[P_0(8)=8(7(6(5(4(3P_0(2)-1)+1)-1)+1)-1)+1\] \[P_0(8)=\frac{8!}{2!}-\frac{8!}{3!}+\frac{8!}{4!}-\frac{8!}{5!}+\frac{8!}{6!}-\frac{8!}{7!}+1.\] Adding and subtracting \(8!\), and rewriting \(1\) as \(8!/8!\), we have: \[P_0(8)=8!\left( 1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}-\frac{1}{5!}+\frac{1}{6!}-\frac{1}{7!}+\frac{1}{8!}\right) .\]
Generalizing and considering the remainder term for alternating series, we have:
Theorem 2: As \(n\rightarrow\infty\), \(\displaystyle P_0(n)\rightarrow\frac{n!}{e}\), and \(\displaystyle \left|P_0(n)-\frac{n!}{e}\right|<\frac{1}{n+1}\).
From this, we can say that \(\displaystyle P_0(n)=\frac{n!}{e}\), rounded to the nearest integer.
\(\mathbf {P_k(n)}\)
In this section we find formulas for \(P_k(n)\) for \(k\leq n\). Two of these are closed form and do not require a recursive formula; however, we include the recursive formula for completeness and because it is a generalization of the recursive formula for \(P_0(n)\).
Theorem 3: \(P_k(n)={n \choose k }P_0(n-k)\).
We are counting the number of permutations on \(n\) objects which agree with the identity in \(k\) positions. The formula is an expression of our selecting \(k\) positions in which the permutation agrees with the identity, while the other \((n-k)\) positions do not agree with the identity. For computation purposes we might prefer:
Corollary 1: \(\displaystyle P_k(n)=\frac{n!}{k!}\sum_{i=0}^{n-k}\frac{(-1)^i}{i!}\).
We are tempted to use the approximation \(\displaystyle P_k(n)\approx \frac{n!}{k!e}\), rounded. However, when \(k\ne 0\), the earlier termination of the finite series \(\displaystyle \sum_{i=0}^{n-k}\frac{(-1)^i}{i!}\) leaves us with increasing differences between \(P_k(n)\) and \(n!/(k!e)\) as \(n\) gets larger and as \(k\) gets larger. For example, using the remainder approximation for alternating series, we have \(|P_3(8)- 8!/(3!e)|<\frac{56}{6}\), \(|P_3(10)- 10!/(3!e)|<\frac{90}{6}\), and \(|P_4(10)- 10!/(4!e)|<\frac{180}{6}\). In the case where \(n=10\) and \(k=4\), the approximation gives \(55,623\), while the actual value of \(P_4(10)\) is \(55,650\). The error is less than \(0.1\%\), but for a count, the approximation formula does not yield exact results when \(k>0\), as it does when \(k=0\).
We now turn to the recursive formula for \(P_k(n)\).
Theorem 4: For each \(n\geq 2\), and for each \(k\) such that \(0\leq k < n\), \(P_k(n)=nP_k(n-1)+{n \choose k}(-1)^{n+k}\).
From Theorem 3 we know that \(P_k(n-1)={n-1 \choose k}P_0(n-1-k)\), and we have that \[nP_k(n-1)+{n \choose k}(-1)^{n+k}=n{n-1 \choose k}P_0(n-1-k)+{n \choose k} (-1)^{n+k}.\] Noting that \((-1)^{n+k}=(-1)^{n-k}\), we have \[nP_k(n-1)+{n \choose k}(-1)^{n+k}={n \choose k}((n-k)P_0(n-1-k)+(-1)^{n-k}).\] From Theorem 1, we have \(P_0(n-k)=(n-k)P_0(n-1-k)+(-1)^{n-k}\). Thus, by Theorem 3, we have \[P_k(n)=nP_k(n-1)+{n \choose k}(-1)^{n+k}.\]
