Skip to main content

Questions tagged [derangements]

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

Filter by
Sorted by
Tagged with
0 votes
1 answer
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 ...
Johann Carl Friedrich Gauß's user avatar
4 votes
2 answers
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 ...
ajotatxe's user avatar
  • 65.9k
2 votes
2 answers
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 ...
H4z3's user avatar
  • 802
1 vote
0 answers
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-...
julianiacoponi's user avatar
0 votes
0 answers
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 ...
julianiacoponi's user avatar
1 vote
0 answers
42 views

Is this matrix determinant's connection to the Partial Derangement / Rencontres numbers / subfactorial known?

$\mathbf{SETUP}$ For my theoretical physics PhD I have been studying a model that requires the inversion of an $n \times n$ matrix of this form: $$ \mathbf{A}_n= \begin{pmatrix} 1 & -a_{...
julianiacoponi's user avatar
-1 votes
1 answer
30 views

number of permutations without stable element [closed]

I know the number of permutation is $n!$ and number of permutation without stable point is $$!n = n!\sum_{k=0}^n(−1)^k/k!$$ Is it known the number of permutation pairs $(p,p')$ such that $p(i) \neq p'(...
ondrej60's user avatar
2 votes
1 answer
57 views

Multiderangement probability goes to $e^{-k}$

It's well known that the probability of a $n$-permutation being a derangement is about $e^{-1}$ when $n$ is large. But how about if we have $k$ of each number, i.e. we have multipermutations of $M_{k,...
ploosu2's user avatar
  • 9,763
4 votes
2 answers
88 views

How many ways to derange $n$-numbers, ignoring the direction?

Derangement is a permutation of the elements of a set in which no element appears in its original position. In other words, a derangement is a permutation that has no fixed points. The recursive ...
athos's user avatar
  • 5,355
1 vote
1 answer
72 views

Derangements for couples in a round table

Question: Let ( m(n) ) denote the number of ways of seating ( n ) married couples around a circle such that no husband sits next to his wife. Then, the remainder obtained on dividing ( m(5) ) by ( 5 ) ...
OpateItZOpatoOpate's user avatar
0 votes
0 answers
30 views

Proving the Greatest Integer Fucntion (G.I.F) of (50!/e + 1/2) is D50(derangement)

Prove that, If D(n) denotes dearrangement for n objects, then D(50) = [ 50/e! + 1/2 ] Where [.] denotes the greatest integer function. Through exapnsion i generated 50/e! but how can we adjust the &...
OpateItZOpatoOpate's user avatar
7 votes
1 answer
161 views

Reference for a combinatorial identity involving the number of derangements

Let $$c_n=n!\sum\limits_{k=0}^n (-1)^k \frac{1}{k!}$$ be the number of derangements of $n$ elements. The following combinatorial identity is coming up in my research: $$\sum\limits_{j=1}^{n-2}c_{n-j}{...
Ryan Hendricks's user avatar
0 votes
0 answers
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 ...
Vedant Khandelwal's user avatar
1 vote
1 answer
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) ...
An5Drama's user avatar
  • 416
1 vote
0 answers
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$ ...
alice123019's user avatar
2 votes
2 answers
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 ...
alice123019's user avatar
0 votes
2 answers
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 ...
alice123019's user avatar
7 votes
2 answers
786 views

The n-person hat matching problem in probability for n=3, doesn't match derangement formula

Suppose all $n$ people at a party throw their hats in the center of the room. Each person then randomly selects a hat. The probability that none of the $n$ people selects their own hat is $$1/2! - 1/3!...
user106742's user avatar
2 votes
3 answers
85 views

Confused about this proof for derangements formula $n ! \sum_{k=0}^n \frac{(-1)^k}{k !} $

For proving $D(n) = n ! \sum_{k=0}^n \frac{(-1)^k}{k !}$, in this post under "derivation of closed form from Recursion", the fact is used that $\frac {(-1)^n}{n!} + \frac {D(n-1)}{(n-1)!}= \...
Princess Mia's user avatar
  • 3,029
0 votes
1 answer
72 views

For counting the number of derangements, does it matter whether we preclude fixed points or just an item being at any unique index for the count?

I have learnt that a derangement is a permutation with no fixed points. When considering the number of derangements of an ordered list, I am trying to justify why we would get the same number if we ...
Princess Mia's user avatar
  • 3,029
0 votes
0 answers
33 views

Proof of the derangement theorem [duplicate]

I have been trying to find the proof of the derangement theorem, and have checked out some materials on them (since its proof has not been taught to us). But I have not been able to understand much of ...
Anne's user avatar
  • 125
1 vote
2 answers
136 views

Bijection between derangements and permutations whose first ascent is in even position

Define an ascent of a permutation, $w$, to be an index, $1\le i\le n$, such that $w_i<w_{i+1}$. Furthermore, we adopt the convention that $n$ is always an ascent. This convention is not typical, ...
Kandinskij's user avatar
  • 3,536
2 votes
1 answer
129 views

Counting $\{a,a,b,b,c,c,d,d,d \}$ derangements. [duplicate]

Exam question: Let $D(d_{1},d_{2},...,d_{k})$ denote the number of derangements of a multiset where there are $d_{i}$ copies of elements of the $i$-th kind, for $i=1,...,k$. This means the ...
Michał's user avatar
  • 675
0 votes
2 answers
94 views

The number of ways to arrange 8 rooks on the chessboard satisfying the condition

I have an interesting combinatorial math problem as follows How many ways are there to arrange 8 rooks on the chessboard such that no rook is on the main diagonal (the diagonal connecting the top left ...
Question 's user avatar
0 votes
0 answers
76 views

Deranged generous gift giving in the limit

I was writing a routine for a game and stumbled upon some algorithm issues and a theoretical question about it. Here I'm mostly concerned with the latter, which may be phrased as a sort of graph ...
Nikolaj-K's user avatar
  • 12.3k
1 vote
0 answers
36 views

How to find the recurrence sequence of the generalized Derangement?

I recently learned about the generalized Derangement problem. And I know how to use Laguerre polynomials to find the general term. But it seems difficult to write programs to calculate definite ...
ame's user avatar
  • 11
1 vote
1 answer
63 views

What is the conceptual misunderstanding in the hat-check problem (derangements)?

The hat-check problem goes something like this: there are N letters that correspond to N envelopes. They get put in randomly. What is the probability that none of them are in the correct envelope (and ...
Sean's user avatar
  • 11
0 votes
1 answer
42 views

Can't understand how did it go from $(\frac{D_{N-x}}{(N-x)!} - {e^{-1}}) \frac{1}{x!}$ to $(\frac{D_{x}}{x!} - {e^{-1}}) \frac{1}{N-x!}$

I am not able to understanding a passage on a paper that talk about total variation between the law of numbers of fixed points in a random permutations ($\pi_{N}(x)$) and the Poisson distribution with ...
enrico didoli's user avatar
0 votes
0 answers
102 views

Why doesn’t this solution to the hat matching problem work?

I am trying to understand why this solution to a specific case of the hat matching problem is incorrect. The problem goes like this: $n$ professors each place their hat for a total $n$ hats into a bag....
thegreataverage's user avatar
3 votes
1 answer
87 views

how many unique numbers will appear in simulation?

I am from ukraine and I start taking course on the computer programming. My classmate tells me about this website for interesting discussion and information about mathematics. Today we learn about ...
Ole Willa's user avatar
2 votes
1 answer
122 views

I want to find the number of permutations of the set $\{1,2,3,4,5,6\}$ if not one element is in that position as in the original input $1 2 3 4 5 6$.

The answer given is $5 \times 4 \times 3 \times 2 \times 1 \times 1$. I am trying to understand the solution. For the first position we must choose an element from the set $\{2,3,4,5,6\}$. Then for ...
HMPtwo's user avatar
  • 475
4 votes
0 answers
56 views

Derangement after derangement

n people can be seated on n chairs in n! different ways. These are permutations. If the people get up and sit down again in such a way that nobody sits on the same chair they sat on before, this can ...
oz1cz's user avatar
  • 171
2 votes
1 answer
98 views

How to use Lagrange inversion to count derangements?

Let $\mathcal{D_n}$ be the class of derangements, i.e. the class of permutations without fixpoints, on $[n]$ and set $\mathcal{D} = \cup_{n \ge 1} \mathcal{D}_n$. We know that the EGF of $\mathcal{D}$ ...
3nondatur's user avatar
  • 4,222
0 votes
0 answers
47 views

Counting number of derangements with extra numbers without an index

Say I have a set of numbers 1 through N, E.g. {1,2,3,4,5,6} I want to find the number of derangements, but for e.g the first 4 places {a,b,c,d} where there are of course the numbers 1 through 4 that ...
j9208sk's user avatar
1 vote
1 answer
96 views

Integral problem involving derangements and improper integrals

I am curious to see how to solve the following problem: Let $$I(n)=\int_0^{\infty}(t-1)^ne^{-t}dt$$ If $D(n)$ is the number of derangements of $n$, then what is $I(42)-D(42)$. This problem is found ...
Moh's user avatar
  • 111
0 votes
0 answers
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: ...
Jonas Broe Bendtsen's user avatar
4 votes
1 answer
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) [...
Sherlock9's user avatar
  • 245
0 votes
0 answers
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 ...
Priti Bisht's user avatar
2 votes
1 answer
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 ...
Leibniz-Z's user avatar
  • 1,019
1 vote
0 answers
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 ...
3nondatur's user avatar
  • 4,222
1 vote
1 answer
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 ...
Siddharth Gurumurthy's user avatar
3 votes
1 answer
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 ...
Justin 's user avatar
-1 votes
1 answer
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 ...
user avatar
0 votes
1 answer
304 views

Gift exchange activity with n people and k gift(probability)

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-...
Louis.'s user avatar
  • 307
0 votes
0 answers
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 ...
John's user avatar
  • 13
2 votes
1 answer
73 views

Derangements, Combinations, Permutations Dice and Presents

$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 ...
user avatar
0 votes
1 answer
73 views

Shuffling Four Kinds of Each Two Cards So That None of Them Remains in the Same Place [closed]

I am asking for your help with solving the problem. I encountered this problem in a blog post about derangements. The author of the blog stated the answer is $297$. I solved by tree diagram for $1$, $...
Account's user avatar
  • 79
1 vote
2 answers
101 views

Derangements: Probability that exactly $r$ players get their own name.

Suppose $n$ competitors in a tournament organize a sweep stake on the result of the tournament. Their names are placed in an urn, and each player pays a dollar to withdraw one name from the urn. The ...
HMPtwo's user avatar
  • 475
0 votes
0 answers
35 views

Prove that two definitions of Rencontres number are equivalent

Let $m>1$ be an integer. Let $P(m)$ be the set of permutations of $\{0,\dots,m-1\}$. Then the $m$th Rencontres number $R(m)$ may be defined in any of these ways: the number of rencontres of the ...
Rosie F's user avatar
  • 2,988
0 votes
1 answer
78 views

Combinatorics based on recursion

The question that I came across is - There are $n$ men who have to give up their hats and coats before entering a hall, and on leaving they receive back a coat and hat randomly. We are asked to count ...
Sam's user avatar
  • 11

1
2 3 4 5