Questions tagged [derangements]
For questions on derangements, permutations of a set without fixed points.
245 questions
0
votes
2
answers
190
views
Number of derangement of $1,1,2,3,4,5,6,7$ [closed]
If there are 8 letters numbered 1 1 2 3 4 5 6 7 (not 12345678) instead there is one 1 extra
and similarly there are envlopes numbered 1 1 2 3 4 5 6 7
assuming that the two letters and the two ...
1
vote
1
answer
90
views
Calculation of the derangements (subfactorial, number of fixed-point-free permutations) from the normal factorial
How can I derive $\boxed{
!n = \left\lfloor \dfrac{n!+1}{e} \right\rfloor,~~~ n \ge 1
}~?$
It is $\boxed{
!n
=n! \displaystyle\sum\limits_{k=0}^{n} \dfrac{(-1)^k}{k!}
}$ (wikipedia).
So I tried ...
- 229
2
votes
3
answers
141
views
Spotting mistake in computing probability of derangement
I have seen some posts here computing the probability of a derangement by first counting the derangements. I would like to know why my attempt to compute the probability directly failed and what I did ...
- 469
0
votes
3
answers
184
views
Coupons in an Envelope with some Derangements.
I gave the Indian Olympiad Qualifier in Mathematics (IOQM) 2025, on September 7th. Following is a combinatorics problem from the exam as follows:
There are 6 coupons numbered from 1 to 6 and 6 ...
- 35
3
votes
1
answer
169
views
How to prove this sum over integer partitions is equal to the number of derangements?
I'm trying to figure out the value of the following sum, $S_n$. It's defined over a set $H_n$ which contains integer partitions of $n$ using only parts of size 2 or greater.
Here are the definitions:
$...
- 964
0
votes
0
answers
66
views
Counting derangements without adjacent consecutive integers [duplicate]
I’m interested in counting permutations of the set $\{1,\ldots, n\}$ with two restrictions:
No element appears in its original position (i.e., derangements).
No two consecutive integers appear next to ...
- 177
0
votes
1
answer
86
views
very confusing derangements problem on matching animals to their food bowls.
image
Two sheep and three goats live on a farm. At feeding time, the farmer puts out two bowls of sheep food and three bowls of goat food. How many ways are there for the animals to eat from the bowls,...
user1651248
2
votes
1
answer
170
views
Hat matching problem (confused at Ross's solution)
This problem is taken from A first course in probability by Sheldon Ross.
Problem Statement
Suppose that each of the N men at a party throws his hat into the center of the room, then each man randomly ...
- 157
10
votes
1
answer
375
views
What is the probability that a geometric random permutation of $\mathbb{N}$ has no fixed points?
UPDATE. The case of geometric distributions seems to be solved: I think we have that for all $\lambda \in (0,1)$, $\mathbb{P}_{p_\lambda}(D(\mathbb{N})) = 0$. But the fundamental question that remains ...
- 236
0
votes
1
answer
220
views
Counting number of functions using derangements
Let $A$ be the set of the first seven natural numbers; let $B$ be the set of the first six even natural numbers. Consider functions $f: A \to B$ such that $f(x) \neq 2x~\forall x \in A$ and $f(x)$ is ...
- 964
3
votes
1
answer
152
views
Number of Fixed Points of a Subset by a Random Permutation
Let $\gamma\in[0,1]$. Consider the subset $A_{n}=\{1,2,...,\lceil n\gamma\rceil\}\subseteq \{1,2,...,n\}$. Let $\sigma$ be permutation of the set $\{1,2,...n\}$ chosen uniformly and randomly.
Let $X_{...
- 1,666
3
votes
1
answer
142
views
Number of ways to place $n$ items in $n \times n$ square so there is one in every row, column, and both diagonals.
Let $P(n)$ denote the number of ways to put $n$ items in an $n \times n$ grid so there is exactly one item in every row, column, and both major diagonals. Thus,
$P(n) = |\{\sigma \in S_n : \exists! \...
- 795
7
votes
0
answers
304
views
Closed form expression for A288208
Trying to resolve my last question, I stumbled on this sequence, A288208, which resolves the case $k=3$. I see that there are various codes proposed to compute the sequence, but there isn't a closed ...
- 1,518
5
votes
2
answers
263
views
Last digit in number of derangements
There is a table at the bottom of the wikipedia article on deranged permutations, where the number of derangements for $1,...,30$ is listed. I noticed that the last digit of $!n$ is zero only when the ...
- 10k
6
votes
1
answer
268
views
Permutations and powers of $e$
It is widely known considering the set $\{1,2,\cdots,\ n\}$ that $ \lim_{n\to\infty}\frac{n!}{!n}=e$ where $!n$ are the derangements.
Less known is the fact that defining $a_n$ as the number of ...
- 1,518