Post Reply 
 
Thread Rating:
  • 0 Votes - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Nowhere matching permutations on \(\left\{1, \cdots, n\right\}\)
05-19-2010, 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\}\)
Find all posts by this user
Quote this message in a reply
05-20-2010, 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 \(n-k\) 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_{n-1} + n(n-1) a_{n-2} + \cdots + n(n-1)\cdots 3 \cdot a_2 + n(n-1)\cdots a_1 + n!\) thus
\(n a_n = n(n-1) a_{n-2} + \cdots + n(n-1)\cdots 3 \cdot a_2 + n(n-1)\cdots a_1 + n!\) and so
\(a_{n+1} = n(a_n-a_{n-1}) \quad (n > 1)\) or \(a_{n+1} - (n+1)a_n = (-1)(a_n - n a_{n-1})\). consequently
\(\displaystyle{\prod_{k=2}^{n} (a_{k+1} - (k+1)a_k) = \prod_{k=2}^{n}(-1)(a_k - k a_{k-1})} \Rightarrow a_{n+1} - (n+1) a_n = (-1)^{n-1} (1 - 2 \cdot 0))\) \[a_n = na_{n-1} + (-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!}\)
Find all posts by this user
Quote this message in a reply
08-16-2010, 03:36 PM
Post: #3
RE: Nowhere matching permutations on \(\left\{1, \cdots, n\right\}\)
   
Find all posts by this user
Quote this message in a reply
08-28-2010, 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
Find all posts by this user
Quote this message in a reply
Post Reply 


Forum Jump:


Contact Us | Software Frontier | Return to Top | Return to Content | Lite (Archive) Mode | RSS Syndication