Nowhere matching permutations on \(\left\{1, \cdots, n\right\}\)

05192010, 10:19 AM
Post: #1




Nowhere matching permutations on \(\left\{1, \cdots, n\right\}\)
A permutation \(P\) over \(\left\{1,\cdots,n\right\}\) is called nowhere matching if \(\forall k\in \left\{1,\cdots,n\right\} \quad P(k) \ne k\)
Find the count of all nowhere matching permutations on \(\left\{1,\cdots,n\right\}\) 

05202010, 01:03 PM
Post: #2




RE: Nowhere matching permutations on \(\left\{1, \cdots, n\right\}\)
Let \(E_n = \left\{P \in S_n : P \text{ is nowhere matching}\right\}\) then any \(P \in E_n\) has the form \(C \circ D\)
where \(C\) is a rotation of order \(k>1\): \(C^m(n) \ne n, \; 1 \le m < k, \; C^k(n) = n\) and \(D\) is a nowhere matching permutation over a set of \(nk\) elements. Let \(a_n = E_n\), then we have \(a_1 = 0, \; a_2 = 1\) and the above discussion shows that \(a_{n+1} = n a_{n1} + n(n1) a_{n2} + \cdots + n(n1)\cdots 3 \cdot a_2 + n(n1)\cdots a_1 + n!\) thus \(n a_n = n(n1) a_{n2} + \cdots + n(n1)\cdots 3 \cdot a_2 + n(n1)\cdots a_1 + n!\) and so \(a_{n+1} = n(a_na_{n1}) \quad (n > 1)\) or \(a_{n+1}  (n+1)a_n = (1)(a_n  n a_{n1})\). consequently \(\displaystyle{\prod_{k=2}^{n} (a_{k+1}  (k+1)a_k) = \prod_{k=2}^{n}(1)(a_k  k a_{k1})} \Rightarrow a_{n+1}  (n+1) a_n = (1)^{n1} (1  2 \cdot 0))\) \[a_n = na_{n1} + (1)^n, \quad a_0 = 1 \]This also implies that for \(n \ge 1\), we have \(a_n = n!\sum_{k=0}^n(1)^k /{k!}\) 

08162010, 03:36 PM
Post: #3




RE: Nowhere matching permutations on \(\left\{1, \cdots, n\right\}\)


08282010, 11:31 AM
Post: #4




RE: Nowhere matching permutations on \(\left\{1, \cdots, n\right\}\)
Derangement
In combinatorial mathematics, a derangement is a permutation of the elements of a set such that none of the elements appear in their original position. The numbers of derangements !n for sets of size n are called "de Montmort numbers" or "derangement numbers" (and can be generalized to rencontres numbers); the subfactorial function (not to be confused with the factorial n!) maps n to !n. No standard notation for subfactorials is agreed upon, and n¡ is sometimes used instead of !n. http://en.wikipedia.org/wiki/Derangement 

« Next Oldest  Next Newest »
