Linked Questions

2
votes
2answers
7k views

Fixed-point-free permutations [duplicate]

An $i \in [n]$ is called a fixed point of a permutation $\sigma \in S_n$ if $\sigma(i) = i$. Let $D(n)$ be the amount of permutations $\sigma \in S_n$ without any fixed point. Prove that ...
3
votes
2answers
1k views

Probability of matching events [duplicate]

Possible Duplicate: Number of permutations where n ≠ position n I have the following exercise: Suppose that four guests check their hats when they arrive at a restaurant, and that these hats are ...
3
votes
2answers
394 views

Probability that no balls go in the right boxes [duplicate]

You have n balls, and n boxes. There is a pairing of each ball to a box (and vice versa). If you were to randomly place balls in boxes, what is the probability that none of the balls would go in "...
0
votes
3answers
463 views

How many fix point free permutations of 5 elements are there? [duplicate]

I am trying to find out how many fix point free permutations of 5 elements there are. A permutation is fix point free, if $\pi (i) \neq i$. I am trying to solve this problem using the inclusion ...
2
votes
3answers
362 views

The number of bijections $f$ of $\{1, 2,…, n\}$ such that $f(i) \ne i$ for any $i$ [duplicate]

Show that the number of bijections $f$ of $\{1, 2,..., n\}$ such that $f(i) \ne i$ for any $i$ is equal to $$\sum_{j=0}^{n}(-1)^j\frac{n!}{j!}.$$ Can I get some help for the above problem? I am not ...
1
vote
1answer
536 views

Permutations With No Identity Elements [duplicate]

Possible Duplicate: Number of permutations where n ≠ position n There are $N!$ permutations of the set $\{1,2,\ldots,N\}$ How many of them have zero identity elements? An identity element is an ...
0
votes
2answers
340 views

How many one-to-one functions there $\phi$ from $\{1,2,3,4,5,\}$ to $\{1,2,3,4,5\}$ such that $\phi(i)\neq i$ for $i=1,2,3,4,5$ [duplicate]

How many functions one-to-one $\phi$ from $\{1,2,3,4,5,\}$ to $\{1,2,3,4,5\}$ such that $\phi(i)\neq i$ for $i=1,2,3,4,5$ my attempt: the number of one-to-one functions $\phi$ from $\{1,2,3,4,5,...
1
vote
1answer
348 views

How many ways to permute a sequence leaving no element in its starting position? [duplicate]

Possible Duplicate: Number of permutations where n ≠ position n I've got a HW problem for a Random Signals class I've got mostly figured out, but my approach would require a solution to another ...
0
votes
1answer
124 views

Expected value and probability of a random event [duplicate]

Possible Duplicate: Number of permutations where n ≠ position n Probability of matching events There are n children in a classroom and each child has exactly one toy (so there are n toys in ...
0
votes
1answer
90 views

How to calculate the probability mass function of $X_N$, the number of people getting back their own hat [duplicate]

How do I calculate the pmf of $X_N$, where $X$ is the number of people out of $N$ getting back their own hat after a random hat exchange? How can I calculate it without listing all the possible ...
3
votes
0answers
122 views

Combinatorics problem: Matching messages with envelopes [duplicate]

Possible Duplicate: Number of permutations where n ≠ position n In how many ways can 5 messages be posted in 5 envelopes so that no correct message is posted, if each envelope only has one ...
0
votes
1answer
52 views

A basic probability doubt on derangment [duplicate]

Is there any implication that the probability that a random permutation is a derangment is $\frac{1}{e}$ when $n->\infty$ ?
0
votes
1answer
28 views

Probability of taking seats [duplicate]

Assume n people who are initially assigned seats from 1 t0 n but they don't know their seat number, now they randomly pick up a seat on their own and what would be the probability that no one is ...
1
vote
0answers
23 views

What is the total number of permutations of n digits where all digits will exchange their positions? [duplicate]

As we know, Total number of permutations of the digits 12345 is 5!. Well, I am looking for another interesting fact. How many permutations among them are in the way that no digit is in its original ...
9
votes
4answers
2k views

Proof of subfactorial formula $!n = n!- \sum_{i=1}^{n} {{n} \choose {i}} \quad!(n-i)$

Any hints about how to prove $$!n = n!- \sum_{i=1}^{n} {{n} \choose {i}} \quad!(n-i)$$ from Wikipedia's article on derangements? Here, $!n$ is the number of derangements of a set with $n$ ...

15 30 50 per page