Questions tagged [derangements]

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

Filter by
Sorted by
Tagged with
-1 votes
0 answers
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?
user avatar
  • 1
0 votes
2 answers
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 ...
user avatar
2 votes
2 answers
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 ...
user avatar
4 votes
1 answer
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-...
user avatar
1 vote
0 answers
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, ...
user avatar
  • 11
0 votes
0 answers
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 ...
user avatar
  • 1,639
4 votes
1 answer
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 ...
user avatar
  • 43
0 votes
0 answers
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 ...
user avatar
  • 1,898
1 vote
1 answer
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!$....
user avatar
  • 532
0 votes
1 answer
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 ...
user avatar
1 vote
1 answer
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!}$ ...
user avatar
0 votes
1 answer
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: ...
user avatar
6 votes
1 answer
148 views

What is the probability that two randomly selected derangements of order $n$ are derangements of each other?

First, let's acknowledge that if $n=1$ then $P(A_1)=0$, since there are no derangements of a set of order one; and if $n=2$, $P(A_2)=0$, since there is only one derangement of a set of order two. For $...
user avatar
  • 1,137
0 votes
3 answers
74 views

Modified Derangement : In how many ways can they enter these houses so that no one goes into their own house.

There are four persons $A,B,C$ and $D$ such that $A$ has two houses whilst $B,C$ and $D$ have one house each. In how many ways can they enter these houses so that no one goes into their own house. My ...
user avatar
  • 7,062
5 votes
0 answers
67 views

Recurrence of number of derangement of $[n]$ with $k$ cycles

Let $d(n,k)$ be the number of derangement of $[n]$ with $k$ cycles. Derive a recurrence for $d(n,k)$. I know the formula for $d(n,k)$(which involves unsigned Stirling number of the first kid) but I am ...
user avatar
  • 375
2 votes
0 answers
65 views

Probability that all the $n$ letters are not placed in the right envelope

There are $n$ letters and $n$ addressed envelopes. If the letters are placed in the envelopes at random, what is the probability that all the letters are not placed in the right envelope? The number ...
user avatar
  • 3,566
5 votes
2 answers
167 views

Derangement with extra box

I was going through PnC questions and I came across this problem. Four balls numbered $1,2,3,4$ are to be placed into five boxes numbered $1,2,3,4,5$ such that exactly one box remains empty and no ...
user avatar
4 votes
1 answer
143 views

How to say $!n$ out loud [closed]

Is there a common way to pronounce the expression $!n$ for the number of derangements of $n$ objects, other than "The number of derangements of $n$ objects?" Something like "factorial $...
user avatar
  • 51.4k
0 votes
1 answer
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 ...
user avatar
0 votes
0 answers
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 ...
user avatar
  • 242
1 vote
0 answers
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 ...
user avatar
  • 1,306
0 votes
0 answers
13 views

Derangements vs Factorial Ratio [duplicate]

It's true that $[{\frac{n!}{e}}] = !n$, where $!n$ is equal to the subfactorial or the number of derangements for a number $n$ and $[n]$ is equal to the integer closest to $n$. For example, $!4 = [\...
user avatar
  • 409
0 votes
2 answers
47 views

Count permutations where some items should be deranged while rest can be placed anywhere (rank derangements)

As the title says, I am looking for a way to count permutations of $n$ (permutations of the set $(0, 1,\dots, n-1)$) where $k, 0 \le k \le n$ items should not stay in same place (be deranged), while ...
user avatar
  • 2,013
0 votes
0 answers
74 views

Counting intuitively the combinations in the hat-check problem

The problem of counting the number of ways $n$ people randomly take $n$ hats, assuming that they can take their own hat, is quite intuitive: the first person has $n$ hats to choose from, the second ...
user avatar
  • 53
4 votes
0 answers
52 views

Derangements of the letters of the word PURPLE [duplicate]

In a Youtube video on the channel @blackpenredpen, the number of derangements of the word "PURPLE" is calculated as $$\frac{!6 \,- \,!5\, -\, !5\, - \,!4}{2!}$$ I don't understand two ...
user avatar
2 votes
1 answer
186 views

Derangement Question: last person has correct seat

I have encountered a derangement problem described as follow: n people will take n seats indexed as 1,2,3...,n; they choose seat one by one starting from person 1. For first n-1 people, they are not ...
user avatar
  • 103
0 votes
0 answers
19 views

Limiting distribution of generalized derangement

Suppose there are $N$ people in a party. Each of them brings $k$ gifts. When the party is over, each of them takes $k$ gift randomly. Denote $T$ is the number of gifts return to its original giver. ...
user avatar
1 vote
1 answer
82 views

Number of ways to arrange no matches?

I am trying to understand this "matching problem". given n distinct objects, number each of them. We are said to have a "match" if we permute the n objects, and the ith object is ...
user avatar
1 vote
3 answers
141 views

Number of derangement on $(1, 1, 2, 2, 3, 3, 4, 4)$

How many 8-tuples of $[4]^8=\{1,2,3,4\}^8$ are there s.t. every number in $[4]$ appears exactly twice, and $i$ never appears on the $i$th place for all $i\in[4]$? There are $8!/16$ different tuples ...
user avatar
  • 865
-2 votes
1 answer
71 views

The number of one-one functions $f : \{1, 2, 3, 4, 5\} \to \{0, 1, 2, 3, 4, 5\}$ such that $f(1) \neq 0, 1$. [closed]

This question was asked in the ISI PGDSMA entrance exam. Can anyone help me in this? I am getting $480$ as answer.
user avatar
2 votes
1 answer
145 views

Proof of derangement relation $nD_{n-1}+(-1)^n=D_n$

I use notation $D_n$ for the number of derangements of an $n$ element set. As in title I seek a proof of $$nD_{n-1}+(-1)^n=D_n. \tag{1}$$ If this is added to its version with $n$ replaced by $n+1$ ...
user avatar
  • 6,647
1 vote
0 answers
34 views

If $n$ balls (numbered $1 \to n$)are distributed in $n$ bins(numbered).Find the probability that no ball goes into the same numbered bin.

I have been thinking about it a lot and my conclusion has been like this : I found the possible places where the $1$st ball can go, it is $(n-1)$.Then the next ball can go to the bin where the number $...
user avatar
  • 1,495
1 vote
0 answers
67 views

How many bijections $ \pi: \{1,2, \dots,n \} \to \{1,2, \dots,n \} $ are there such that $ \pi(j) \neq j $?

Let $n \in \mathbb{N} $. How many bijections $ \pi: \{1,2, \dots,n \} \to \{1,2, \dots,n \} $ are there such that $ \pi(j) \neq j $, for all $j \in \{1,2, \dots,n \} $? My solution is quite simple: $$ ...
user avatar
  • 486
0 votes
2 answers
73 views

Derangement problem but with functions instead of permutations, using inclusion-exclusion.

How many functions $f : [n] \to [n]$ are there with no fixed points, i.e. such that $f(i) \ne i$ for all $i$? Use inclusion-exclusion to solve it.
user avatar
0 votes
0 answers
43 views

All combinatorial derangements of $1,2,3 \cdots k$ with specified rules [duplicate]

Let's say that we have the points $\{1,2,3,...,k\}$. I am looking for all the ways to create a derangement of these points with the following rule: we define a derangement as a permutation $\sigma$ ...
user avatar
0 votes
1 answer
65 views

Derangement question but you stop once you've found a matching pair

It's rather common knowledge to know that if we want to rearrange $N$ distinct items' positions such that none of them appears in its original position, then it is a derangement problem. So if we ...
user avatar
  • 1,232
2 votes
3 answers
143 views

Derangement, gift exchange

Five people have each bought their own Christmas gift. They put the gifts in a sack which then everyone can pull their gift from. In how many ways can the gifts be distributed so that no one gets the ...
user avatar
0 votes
1 answer
44 views

How many ways to put n objects into n bins, with object i not in bin i for 1<=i<=n ?? [duplicate]

How many ways are there to arrange n objects into n bins, subject to the n constraints that the ith object can't go in the ith bin for any 1 <= i <= n ? Each bin has to contain exactly one ...
user avatar
  • 2,434
1 vote
0 answers
172 views

Simple derangement algorithm (secret santa)

In combinatorial mathematics, a derangement is a permutation of the elements of a set, such that no element appears in its original position. - from Wikipedia A real example might be a secret santa ...
user avatar
1 vote
1 answer
108 views

$n$ people have participated in a party. each of whom brought an umbrella and a coat. At the end of the party...

$n$ people have participated in a party. each of whom brought an umbrella and a coat. At the end of the party, everyone picks an umbrella and a coat out of the stack and leaves. $1$. In how many ways ...
user avatar
  • 556
0 votes
0 answers
65 views

Secret Santa problem

I saw this problem on my exams and I just literally wrote down the formula for derangements and derived it but I am not sure if it is the case. This was the problem: Problem: Let there be $n$ number ...
user avatar
0 votes
1 answer
181 views

Probability of $k$ fixed points for a random function from and to $\{1,..,n\}$

I would like to derive the probability mass distribution $p_k$ of the number $k$ of fixed points of a random function from $A:=\{1,..,n\}$ to the same set. I proceed computing the number of ...
user avatar
  • 323
1 vote
1 answer
186 views

The number of permutations with k fixed points

Could someone help me please with this problem? I don't even know how to start it. For 1$\leq$k$\leq$n, find the number of permutations $\theta$ $\in$ $S_n$ that have exactly k fixed points. Thank you ...
user avatar
  • 57
1 vote
1 answer
40 views

How to obtain this formulae for derangement using Principle of Inclusion and Exclusion

Let D(n,k) denotes the number of derangement with total of n elements, and having exactly k fixed positions. So, I want to show that $$D(n,k)=\frac{n!}{k!}\sum_{r=0}^{n-k}(-1)^r\frac{1}{r!}$$, using ...
user avatar
  • 643
0 votes
2 answers
341 views

Why does this probability converge towards $1-\frac{1}{e}$?

Consider this simple problem: If an event has a $1/N$ chance of success, what's the probability of having at least one success after $N$ events? Basically, what's the chance of getting a $20$ if you ...
user avatar
0 votes
1 answer
110 views

Prove that $n! = \sum_{k=0}^n\binom{n}{k}d_k,$ where $d_n$ is the number of derangements of ${1,2,..., n}$.

Prove that $$n! = \sum_{k=0}^n\binom{n}{k}d_k,$$ where $d_n$ is the number of derangements of ${1,2,..., n}$. We know that the number of derangements $d_n$ is given by $$d_n=n!\sum_{k=0}^{n}\frac{(-1)^...
user avatar
  • 391
1 vote
1 answer
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: ...
user avatar
  • 605
-1 votes
1 answer
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 ...
user avatar
0 votes
1 answer
99 views

Number of ways to keep two decks of cards in front of each other with no matching cards facing each other.

A deck of 52 cards are placed face up in a row. We have another similar deck with 52 cards. In how many ways can we place the cards in this new deck in front of the row of 52 cards such that there is ...
user avatar
0 votes
1 answer
129 views

What is the probability of matching numbered letters to numbered envelopes?

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)=\...
user avatar