
Probability and Statistics Basic Probability and Statistics Math Forum 
 LinkBack  Thread Tools  Display Modes 
January 3rd, 2015, 08: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, 09:57 AM  #2 
Math Team Joined: Dec 2013 From: Colombia Posts: 7,636 Thanks: 2621 Math Focus: Mainly analysis and algebra 
It's not clear to me what $n$ is in this case.

January 3rd, 2015, 10:41 AM  #3 
Newbie Joined: Jan 2015 From: Turkie Posts: 9 Thanks: 2 
n is a posive integer

January 3rd, 2015, 10:42 AM  #4  
Math Team Joined: Dec 2006 From: Lexington, MA Posts: 3,267 Thanks: 408  Hello, talip! Quote:
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, 04: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, 10:10 AM  #6  
Math Team Joined: Dec 2006 From: Lexington, MA Posts: 3,267 Thanks: 408  Hello, talip! Quote:
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) \;=\;(Q1)^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) \;=\;(Q1)^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, 07: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, 07:35 AM  #8  
Newbie Joined: Jan 2015 From: Turkie Posts: 9 Thanks: 2  Quote:
Number of derangements  OeisWiki  

Tags 
permutation, special 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Special right triangle.  Denis  Algebra  5  March 13th, 2014 10:54 PM 
special name?  nikkor180  Real Analysis  0  June 17th, 2013 10:56 AM 
Special Series  naman  Algebra  6  March 6th, 2013 04:29 PM 
Special Integral  uniquesailor  Real Analysis  0  January 27th, 2013 02:35 PM 
A special thank you  suomik1988  Calculus  2  December 8th, 2010 09:08 PM 