• 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
 elim Moderator Posts: 578 Joined: Feb 2010 Reputation: 0
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\}$$
05-20-2010, 01:03 PM
Post: #2
 elim Moderator Posts: 578 Joined: Feb 2010 Reputation: 0
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!}$$
08-16-2010, 03:36 PM
Post: #3
 elim Moderator Posts: 578 Joined: Feb 2010 Reputation: 0
RE: Nowhere matching permutations on $$\left\{1, \cdots, n\right\}$$

08-28-2010, 11:31 AM
Post: #4
 elim Moderator Posts: 578 Joined: Feb 2010 Reputation: 0
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 »

Forum Jump: