My Math Forum  

Go Back   My Math Forum > High School Math Forum > Probability and Statistics

Probability and Statistics Basic Probability and Statistics Math Forum


Thanks Tree1Thanks
  • 1 Post By soroban
Reply
 
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.
talip is offline  
 
January 3rd, 2015, 09:57 AM   #2
Math Team
 
Joined: Dec 2013
From: Colombia

Posts: 7,690
Thanks: 2669

Math Focus: Mainly analysis and algebra
It's not clear to me what $n$ is in this case.
v8archie is offline  
January 3rd, 2015, 10:41 AM   #3
Newbie
 
Joined: Jan 2015
From: Turkie

Posts: 9
Thanks: 2

n is a posive integer
talip is offline  
January 3rd, 2015, 10:42 AM   #4
Math Team
 
Joined: Dec 2006
From: Lexington, MA

Posts: 3,267
Thanks: 408

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!

soroban is offline  
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.
talip is offline  
January 4th, 2015, 10:10 AM   #6
Math Team
 
Joined: Dec 2006
From: Lexington, MA

Posts: 3,267
Thanks: 408

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$

Thanks from EvanJ
soroban is offline  
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.
talip is offline  
May 12th, 2015, 07:35 AM   #8
Newbie
 
Joined: Jan 2015
From: Turkie

Posts: 9
Thanks: 2

Quote:
Originally Posted by talip View Post
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
talip is offline  
Reply

  My Math Forum > High School Math Forum > Probability and Statistics

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





Copyright © 2019 My Math Forum. All rights reserved.