Probablity of fixed points in permutations

In summary, the probability of fixed points in permutations refers to the likelihood of a permutation containing at least one element that remains in its original position after the permutation has been applied. This probability is calculated by dividing the number of permutations with at least one fixed point by the total number of possible permutations. It is significant in various fields such as mathematics and computer science, as it helps in analyzing the randomness of a given permutation. The number of elements in a permutation affects the probability of fixed points, with a higher number of elements decreasing the likelihood. Real-life applications of this concept include cryptography, genetics, and computer algorithms.
  • #1
Dragonfall
1,030
4
Randomly permute (1,...,n). What is the probability that exactly i points are fixed?

I think it should be

[tex]\binom{n}{i}\frac{(n-i-1)!}{n!}[/tex]

Is it right?

If so, is the expected number of fixed points (I know it's 1):

[tex]\sum_{i=0}^{n}i\binom{n}{i}\frac{(n-i-1)!}{n!}[/tex]

But it doesn't sum to 1, I think
 
Last edited:
Physics news on Phys.org
  • #2
How is (n-i-1)! defined when i = n?
 
  • #3
It isn't. Nevermind. I was approaching the problem in a unnecessarily hard way.
 

FAQ: Probablity of fixed points in permutations

What is the concept of "probablity of fixed points" in permutations?

The probability of fixed points in permutations refers to the likelihood of a permutation containing at least one element that remains in its original position after the permutation has been applied.

How is the probability of fixed points calculated in permutations?

The probability of fixed points is calculated by dividing the number of permutations that contain at least one fixed point by the total number of possible permutations.

What is the significance of the probability of fixed points in permutations?

The probability of fixed points in permutations is important in various fields, such as mathematics and computer science, as it can help in analyzing the randomness of a given permutation and predicting the likelihood of certain outcomes.

How does the number of elements in a permutation affect the probability of fixed points?

The probability of fixed points tends to decrease as the number of elements in a permutation increases. This is because the higher the number of elements, the more possible ways there are for the elements to be rearranged, making it less likely for any given element to remain in its original position.

What are some real-life applications of the concept of probability of fixed points in permutations?

The concept of probability of fixed points in permutations has various applications, such as in cryptography, where it is used to analyze the security of encryption algorithms. It is also used in genetics to study the likelihood of certain traits being inherited from parents. Additionally, it is used in computer algorithms for sorting and shuffling data.

Similar threads

I Using a probability argument I got the sum. Can it be done directly?
Replies
10
Views
1K
MHB Binomial Distribution: Likelihood Ratio Test for Equality of Several Proportions
Replies
1
Views
2K
MHB Probability of misprints on each page
Replies
7
Views
2K
MHB Where Did the Monte Carlo Simulation Go Wrong?
Replies
1
Views
1K
MHB Probability of Assigning r Balls in n Urns with m Urns Containing k Balls
Replies
1
Views
2K
B The Probability that N and E bridge hands have the same number of spades?
Replies
5
Views
1K
I Stuck on the probability of rolling 'p' with 'n' s-sided dice
Replies
3
Views
1K
A Calculating Probability of N Points on a Line Being Within Given Distance
Replies
7
Views
2K
I The set of nonzero values of pmf is at most countable
Replies
2
Views
755
Mathematical Induction with binomial sum
Replies
9
Views
633

Hot Threads

Recent Insights

Back
Top