# Questions tagged [derangements]

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

230 questions
Filter by
Sorted by
Tagged with
78 views

### Number of possible circles with at least two people

I was given this question: In how many possible ways can we arrange $n$ people in circles such that the order between the circles does not matter, but the order ...
212 views

### An alternative way to solve a classic problem of combinatorics

The problem is to count how many permutations in $S_n$ have no fixed points. Let call this number $f(n)$, and define the set $N=\{1,\ldots,n\}$. The 'classic' solution is using the exclusion-inclusion ...
• 65.9k
86 views

### Closed form of the recursion $D_{n+1} = n(D_n + D_{n-1})$

I got this problem from chapter five of Titu Andreescu A path to combinatorics for undergraduates. I'm asked to give a closed form to the given recursion given that $D_1 = 0$ and $D_2 = 1$. And I know ...
• 802
1 vote
39 views

### How to explain arithmetic form of surprising equality that connects derangement numbers to non-unity partitions?

$\mathbf{SETUP}$ By rephrasing the question of counting derangements from "how many permutations are there with no fixed points?" to "how many permutations have cycle types that are non-...
28 views

### Is this matrix adjugate's connection to combinatorial sequences known?

$\mathbf{SETUP}$ (Same setup as my previously posted question on determinants, but this time for the adjugate.) For my theoretical physics PhD I have been studying a model that requires the inversion ...
1 vote
42 views

126 views

### How many one to one functions f: A→A have at least one fixed point?

Let $A = \{1,2,3, ..., 7\}$. A function $f: A → A$ is said to have a fixed point if for some $x \in A$, $f(x) = x$. How many one- to-one functions $f: A → A$ have at least one fixed point? This is a ...
1 vote
49 views

### The range of the probability of the derangement for $n$ people

Recently, when I self-learnt Discrete Mathematics and Its Applications 8th by Kenneth Rosen, I found something with confusion. In the description of the probability of the derangement (proofwiki link) ...
• 416
1 vote
63 views

### Matching problem in a recursive way

Suppose there are $n$ people invited to a party. Seats are assigned and a name card is made for each guest. However, floral arrangements on the table unexpectedly obscure the name cards. When the $n$ ...
• 145
88 views

### Show $P_n = \frac{1}{2!} - \frac{1}{3!} + \frac{1}{4!} - \dots + \frac{(-1)^n}{n!}$ given $P_n = \frac{n-1}{n} P_{n-1} + \frac1n P_{n-2}$

Show that $P_n = \frac{1}{2!} - \frac{1}{3!} + \frac{1}{4!} - \dots + \frac{(-1)^n}{n!}$ given $P_n = \frac{n-1}{n} P_{n-1} + \frac1n P_{n-2}$, $P_1 = 0$, $P_2 = \frac12$ I have absolutely no clue ...
• 145
69 views

### The matching problem in a recursive view

Suppose there are n people invited to a party. Seats are assigned and a name card is made for each guest. However, floral arrangements on the table unexpectedly obscure the name cards. When the n ...
• 145
786 views

• 111
19 views

### Arrangement of element such that no two share the same position nor the same order [duplicate]

My friend asked me an interesting question yesterday: Say you have six names, which you have to sort in six groups. The order of the names must always be different between the groups, such that: ...
152 views

### The number of partial derangements of a $52$-card deck (ignoring suits)

I was reading this paper by Ekhad, Koutschan, and Zeilberger titled "There are EXACTLY 1493804444499093354916284290188948031229880469556 Ways to Derange a Standard Deck of Cards (ignoring suits) [...
• 245
127 views

### Probability of $5$ persons getting their exact car key

$5$ persons play with their car keys such that after the game none leaves with his own key and everybody has exactly one key. It is not possible for all five of them to meet at one place again. If the ...
• 461
252 views

### Number derangements of six letters, where one letter goes in specified envelope, is $D(5)+D(4)$?

There are $6$ letter$\{L_1,L_2,L_3,L_4,L_5,L_6\}$ and $6$ addressed envelope $\{E_1,E_2,E_3,E_4,E_5,E_6\}$. The correct place for $L_i$ is $E_i$. Find total cases in which $L_1$ goes to $E_3$ and no ...
• 1,019
1 vote
77 views

### Computing the coefficients of the egf of derangements

Recall that a derangement is a permutation with no fixed points and let $\mathcal{D}$ be the combinatorial class of derangements. Find the exponential generating function $D(z)$ of $\mathcal{D}$ and a ...
• 4,222
1 vote
73 views

### $n$ permutations in $S_n$, no two of which agree on any point

Q: How many tuples of permutations ($\sigma_1$,..$\sigma_n$), $\sigma_i \in S_n$ have the property that no two of them agree on any element? This is sort of a generalization of derangements, but I ...
128 views

### There's 100 boxes and 100 balls, both labeled. What's the probability that at least one box has a ball with same number?

Randomly place 100 balls, labeled from 1 to 100, in the 100 boxes, also labeled. What is the chance that at least one box contains the ball with matching label? Wouldn't this be a binomial ...
• 51
57 views

### Problem on giving of gifts to specific people.

My good friend Keith asked me a math question. It goes like this: Persons A, B, C, D receive individual gifts. But when the gifts are wrapped up, they look identical so there's no way to tell them ...
304 views

I have the following question: There is a gift exchange activity among n persons. In this activity, everyone prepares k gifts which have the same packaging. All gifts are then put in a non-...
• 307
131 views

### The derangement problem with everyone having two items

The derangement problem is like, "There are n people each having a hat. All the n hats are put in a box. Suppose each person takes one hat randomly from the box. What is the probability that no ...
• 13
$1$. Five students each take a mock exam, following which the exam scripts are redistributed among the students so that each student marks one script. How many possible ways are there to redistribute ...