My Math Forum Special permutation

 Probability and Statistics Basic Probability and Statistics Math Forum

 January 3rd, 2015, 09:11 AM #1 Newbie   Joined: Jan 2015 From: Turkie Posts: 9 Thanks: 2 Special permutation Hi everyone, I have an urgent problem. I could not find the answer for a long time. Here is the problem: What is the number of permutations of n with the following property: Permutation does not include the number i in the position i. Thank you very much.
 January 3rd, 2015, 10:57 AM #2 Math Team   Joined: Dec 2013 From: Colombia Posts: 7,600 Thanks: 2588 Math Focus: Mainly analysis and algebra It's not clear to me what $n$ is in this case.
 January 3rd, 2015, 11:41 AM #3 Newbie   Joined: Jan 2015 From: Turkie Posts: 9 Thanks: 2 n is a posive integer
January 3rd, 2015, 11:42 AM   #4
Math Team

Joined: Dec 2006
From: Lexington, MA

Posts: 3,267
Thanks: 407

Hello, talip!

Quote:
 What is the number of permutations of $n$ with the following property: Permutation does not include the number $i$ in the position $i$.

You are dealing with derangements:
$\quad$a permutation of $n$ objects in which
$\quad$none of the objects is in its original position.

Whoever assigned this problem should be aware
$\quad$that the solution is very elusive and intricate.

Here are some values of the derangement function, $d(n)$:

$\qquad \begin{array}{cc} n & d(n) \\ \hline 2 & 1 \\ 3 & 2 \\ 4 & 9 \\ 5 & 44 \\ 6 & 265 \\ 7 & 1854 \\ 8 & 14,\!833 \end{array}$

Good luck!

 January 4th, 2015, 05:20 AM #5 Newbie   Joined: Jan 2015 From: Turkie Posts: 9 Thanks: 2 Thank you very much for your reply. I need its general function f(n) depending on the independent variable n. I think this problem is more challenging than the one it appears.
January 4th, 2015, 11:10 AM   #6
Math Team

Joined: Dec 2006
From: Lexington, MA

Posts: 3,267
Thanks: 407

Hello, talip!

Quote:
 Thank you very much for your reply. I need its general function $f(n)$ in terms of the variable $n.$ I think this problem is more challenging than it appears.

There is a general function for derangements,
but its derivation is quite intricate and convoluted.

I can give you the formula, but it is quite bizarre.

The number of derangements of $n$ objects, $d(n)$, is given by:

$\qquad d(n) \;=\;(Q - 1)^n \quad \text{ where }Q^n \,=\,n!$

Imagine! $\;$ An exponent becomes a factorial!

Example: $\:d(4)$

$d(4) \;=\;(Q-1)^4$

$\qquad =\; Q^4 - 4Q^3 + 6Q^2 - 4Q + 1$

$\qquad =\; 4! - 4(3!) + 6(2!) - 4(1!) + 1$

$\qquad =\;24 - 24 + 12 - 4 + 1$

$\qquad =\;9$

Note that the first two terms always cancel.

Example: $\:d(6)$

$d(6) \;=\;(Q-1)^5$

$\qquad=\;Q^6 - 6Q^5 + 15Q^4 - 20Q^3 + 15Q^2 - 6Q + 1$

$\qquad=\;6! - 6(5!) + 15(4!) - 20(3!) + 15(2!) - 6(1!) + 1$

$\qquad=\;720 - 720 + 360 - 120 + 30 - 6 + 1$

$\qquad=\;265$

 January 5th, 2015, 08:37 AM #7 Newbie   Joined: Jan 2015 From: Turkie Posts: 9 Thanks: 2 Thank you very much Soroban. It is what I am looking for. What is the method which you used to find the general form of this function? Again, thank you.
May 12th, 2015, 08:35 AM   #8
Newbie

Joined: Jan 2015
From: Turkie

Posts: 9
Thanks: 2

Quote:
 Originally Posted by talip Thank you very much Soroban. It is what I am looking for. What is the method which you used to find the general form of this function? Again, thank you.
Thank you, the explanatory web page is as follows:
Number of derangements - OeisWiki

 Tags permutation, special

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post Denis Algebra 5 March 13th, 2014 11:54 PM nikkor180 Real Analysis 0 June 17th, 2013 11:56 AM naman Algebra 6 March 6th, 2013 05:29 PM uniquesailor Real Analysis 0 January 27th, 2013 03:35 PM suomik1988 Calculus 2 December 8th, 2010 10:08 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top