Linked Questions

3
votes
2answers
14k views

De-arrangement in permutation and combination [duplicate]

This article talks about de-arrangement in permutation combination. Funda 1: De-arrangement If $n$ distinct items are arranged in a row, then the number of ways they can be rearranged such ...
0
votes
1answer
441 views

Derangement problems [duplicate]

d(1)=0,d(2)=1,d(3)=2,d(4)=9,d(5)=44 Verify that d(5) = 44 and thus that the probability of a random rearrangement of 5 objects being a derangement is 44/120 = 0:3666 So i've been trying google/...
2
votes
1answer
114 views

Number of permutations without constants [duplicate]

Possible Duplicate: I have a problem understanding the proof of Rencontres numbers (Derangements) Given a vector of n elements, how can I calculate the number of "true" permutations, i.e. ...
1
vote
0answers
64 views

Deriving the formula for derangements: $\text{Round}\left[\frac{n!}{e}\right]$ [duplicate]

I saw on wikipedia that a formula for derangements is $\text{Round}\left[\frac{n!}{e}\right]$ However, how did they arrive at this elegant formula? Does it have to do with $ !n=n! \sum _{k=0}^n \...
1
vote
0answers
49 views

12 numbered pigeonholes and balls [duplicate]

This problem was inspired by this James Randi challenge. Given $12$ numbered ($1$ to $12$) pigeonholes and $12$ numbered balls (also from $1$ to $12$); what is the probability that a random ...
0
votes
0answers
31 views

How to find the total number of exchanges? [duplicate]

Given n objects held by n people, how to find the total number of valid exchanges, where a valid exchange means that all persons hold different objects after the exchange? eg for 4 objects 1 2 3 4: ...
0
votes
0answers
29 views

How can we derive Derangement Theorem? [duplicate]

can anyone please help me to derive the given result for finding number of ways in which N objects can be arranged such that no object goes to their proper place which is given by $N!\left(1-\frac{1}{...
0
votes
0answers
26 views

Number of permutations $\sigma\in S_n$ with $\sigma(k)\neq k$ for all $k=1,\ldots,n$ [duplicate]

For the symmetry group $S_n$ ($n\geq1$), how many permutations $\sigma$ exist with the property that $\sigma$ doesn't map any element of $\{1,\ldots,n\}$ to itself? I know I can try to do a counting ...
0
votes
1answer
15 views

A question on counting and probability: Six friends hold a Christmas present swap. Each person brings a present, and puts it into a sack… [duplicate]

Question: Six friends hold a Christmas present swap. Each person brings a present, and puts it into a sack. Once all six presents are in the sack, each participant in turn then draws out a present at ...
24
votes
4answers
1k views

Show that : $\sum\limits_{\sigma \in S_n} (\mbox{number of fixed points of } \sigma)^2= 2 n!$

I came across this result while doing some representation theory of the permutation group $S_n$ $$ \sum\limits_{\sigma \in S_n} (\mbox{number of fixed points of } \sigma)^2 = 2 n!$$ This can be ...
14
votes
4answers
7k views

Exponential Generating Function For Derangements

I have been introduced to the concept of exponential generating functions a few days ago. However, my understanding of them are still quite limited, and I would like to see some examples. Earlier this ...
15
votes
3answers
10k views

Combinatorial argument to prove the recurrence relation for number of derangements

Give a combinatorial argument to prove that the number of derangements satisfies the following relation: $$d_n = (n − 1)(d_{n−1} + d_{n−2})$$ for $n \geq 2$. I am able to prove this ...
9
votes
2answers
2k views

$\frac{1}{e}=$“Probability that every chocolate goes into a wrong spot”.

While watching a video by Po Shen Loh I found something strange.In the video, He said that: Suppose I have a box of chocolates having $100$ chocolates, and I drop them all on the ground, and then I ...
5
votes
2answers
160 views

Derangements with extra chairs

This was a question on my combinatorics final. Suppose $m$ people are sitting in a room with $n$ chairs. If everyone leaves and comes back, how many ways can they sit down such that no one gets ...
2
votes
1answer
2k views

4 People Gift Exchange

4 people are exchanging gifts. How many combinations are there so that no one receives their own gift? I tried this problem myself, and got 3!. My friends told me that it's 9. I got 3! because I ...

15 30 50 per page