# Questions tagged [derangements]

For questions on derangements, permutations of a set without fixed points.

170 questions
Filter by
Sorted by
Tagged with
18 views

### Derangements Algorithm [duplicate]

I was asked these questions and I didn't know how to answer? 1. write an algorithm to generate uniformly randon derangments of size K 2. what is the complexity of that algorithm?
27 views

### Derangements, finding best possible $k$

I have to find the best possible $k\in\mathbb{N}$ such that for all sufficiently big $n\in\mathbb{N}$ less than $1$% of all permutations $[n]$ have at least $k$ fixed points. I don't really ...
56 views

### Question about a step in a derangement proof

I read a proof about derangement and I didn't understand this step: $d_n - nd_{n-1} = -(d_{n-1}-(n-1)d_{n-2}) \implies d_n=nd_{n-1}+(-1)^n$ I see that we have $S_n = -S_{n-1}$ if $S$ is the stuff on ...
276 views

### A little help with Derangements

In the textbook I'm using to train Olympic combinatorics Combinatorial problems in Mathematical competitions by Yao Zhang there is a problem which I personally found peculiarly interesting the Euler-...
1 vote
29 views

### What is the probability that at least one suitcase ends up with its original traveller? [duplicate]

There are travellers who have $n$ identical suitcases which they unwittingly did not label, and there suitcases are arriving on the baggage carousel. Each traveller selects a suitcase at random, ...
32 views

### Probability that no student gets his own paper back [duplicate]

A teacher has her class of 75 students correct their own homework. She collects the papers, shuffles them, and passes one to each student. What is the approximate probability that no student receives ...
87 views

### Find the number of failed Secret Santa games for N people

N people play Secret Santa. They draw their names out of a box where: A person draws a name from the box If they draw their own name the game is failed Else the next person draws a name and this ...
25 views

### How to understand the first term in the derangement recursion formula? [duplicate]

The recursion formula for derangement is $D_{n} = (n-1) ( D_{n-1} + D_{n-2})$. The $D_{n-2}$ term arises, AFAIK, from the both the element chosen and its corresponding destination element swapping ...
1 vote
69 views

### Permutations with matching

Suppose that I have the set $S=\{1,2,3,4,5\}$. I will label the elements as $S_i$ where $i=1,…,5$. So, for example, $S_1=1, S_2=2$ and so on. I call $\tilde{S}^k$ Any permutation of $S$ for $k=1,…,5!$....
62 views

### Permutations of letters and envelopes

enter image description hereI am stucked on a problem. It goes as following: In how many ways can n letters can be placed in m ( m is greater than n) adressed envelopes , such that no letter is put in ...
1 vote
77 views

### Solve the recurrence $x_n = 4n(n-1) \cdot (x_{n-1} + 2 (n-1) x_{n-2})$ for $x_1 = 0$ and $x_2 = 16$

How do I get the nth term of the following sequence? $$x_n = 4n(n-1) \cdot (x_{n-1} + 2 (n-1) x_{n-2}), \, x_1 = 0, \, x_2=16$$ I've tried defining the auxiliar sequence $y_n$ as $\frac{x_n}{n!}$ ...
89 views

### The Matching Problem: Probability of At Least One Man Selecting His Own Hat

I came across this example question in this book (Full Solution on pg56)by Sheldon Ross there are some intermediate steps in this problem that have stumped me. The Question & Book Explanation: ...
148 views

57 views

### Closed form expression‎ of double-way matching problem (Special case of derangement)

Is there a "closed form expression‎" for below problem ? Problem : "N" guests gave their raincoats and their umbrellas to the doorman at the entrance of the “Marlinspike” mansion ...
41 views

### name for derangement with unique neighbors

If a row of people must reorder themselves so that nobody is sitting in the same seat as before, that's a derangement. Is there a name for the derangement wherein no person in their new seat is has ...
1 vote
25 views

### Empirical application for probability of $h$-deranged permutations

Background For $n \in \mathbb{N}$ distinct items, there are a total of $n!$ permutations of them. A derangement is a permutation in which not a single item is in its 'natural position'. The number of ...
13 views

1 vote
67 views

1 vote
111 views

### Inclusion Exclusion combinatorics problem.

Seven people leave their jackets on a rack. In how many ways can their jackets be returned so that no one gets their own coat back? Clearly this invokes the Inclusion exclusion principle of the form: ...
60 views

### Derangements Problem: Color Water

The problem: say I want to sell 4 different types of colored water: red, green, blue, and yellow. I also want to use colorful bottle caps, which are also red, green, blue, and yellow. However, I'm not ...
I have been given the following problem: There are $n$ envelopes and $n$ letters, randomly assigned. Let $A_i =$ the event where the $i$th letter goes to the $i$th envelope (a match). Then \$P(A_i)=\... 