0
$\begingroup$

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 forbade an item of our list from being at a unique arbitrary position not its own in the list- that when counting the permutations of our list, we only count permutations where an item isn't at an arbitrary unique index- but this forbidden index doesn't have to be its original index in the list. For example, in $[1,2,3]$, we consider only permutations where $1$ isn't the $2$nd position therein, $2$ isn't the first position therein, etc., rather than there being no fixed points, and I am trying to see why counting permutations of this nature would yield the same amount as the number of derangements.

So far, I have reasoned that we have just assigned arbitrary names to the indices when saying that there are no fixed points, which doesn't change anything combinatorically from the perspective of counting. Also, I have thought that if we changed which index a certain item of our list cannot be in a permutation we count, this is essentially counting the derangements of the list in a different order- because there exists a different ordering of the list such that the new indices each item can't go to are now its own. However, I am dissatisfied with these explanations and seek a more formal argument.

$\endgroup$
5
  • 2
    $\begingroup$ Let $S$ be a finite set, let $\psi$ be any permutation of $S$ (viewed as a one-one and onto function from $S$ to $S$. Then there's a bijection between the set of permutations $\phi$ such that for all $s$ in $S$, $\phi(s)\ne\psi(s)$ and the set of all derangements of $S$. Can you see how to construct such a bijection? $\endgroup$ Sep 14, 2023 at 2:59
  • $\begingroup$ @GerryMyerson I actually am not sure what the functions $\phi$ and $\psi$ do- they take in a single element of $S$- how do they return a permutation given a single element? When you say "let $\psi$ be any permutation of $S$" do you mean that it will return the same permutation given whatever element is it's argument? Also, $\phi$ being a set of permutations not a single permutation like $\psi$, how does it return a permutation given an element? $\endgroup$ Sep 14, 2023 at 5:19
  • $\begingroup$ A permutation of a set $S$ is simply a one-one and onto function from $S$ to $S$. So if $\psi$ is a permutation of $S$ then $\psi$ is a one-one and onto function from $S$ to $S$; for each $s$ in $S$, $\psi(s)$ is in $S$; if $s\ne t$ are both in $S$, then $\psi(s)\ne\psi(t)$; for every $t$ in $S$, there exists $s$ in $S$ such that $\psi(s)=t$. $\phi$ is a permutation, not a set of permutations. If I say, the set of numbers $x$ such that $x^2=17$, I'm not saying $x$ is a set of numbers; I'm just saying I've gathered all the numbers whose square is $17$ together in a set. Continued... $\endgroup$ Sep 14, 2023 at 7:26
  • $\begingroup$ ... Similarly, I've gathered all the permutations that never agree with $\psi$ in one set, and all the derangements in another set, and I'm saying there's a bijection between these two sets; given any permutation $\phi$ such that for all $s$ $\phi(s)\ne\psi(s)$, there is a corresponding derangement, and the correspondence between the two sets of permutations is one-one and onto. $\endgroup$ Sep 14, 2023 at 7:31
  • $\begingroup$ If $\delta$ is a derangement, then $\delta\circ\psi=\phi$ is a permutation satisfying for all $s$, $\phi(s)\ne\psi(s)$. $\endgroup$ Sep 14, 2023 at 7:37

1 Answer 1

1
$\begingroup$

Let $D_n$ be the set of derrangements of $\{1,\dots,n\}$. For each $\pi \in D_n$, we have $\pi(i)\neq i$ for all $i \{1,\dots,n\}$.

For each $\sigma\in S_n$, let $E_n(\sigma)$ be the set of permutations $\pi \in S_n$ with the property that $$ \forall i \in \{1,\dots,n\},\quad \pi(i)\neq \sigma(i) $$ I claim that $|D_n|=|E_n(\sigma)|$, no matter what $\sigma$ is. This means that counting derangements is the same as counting permutations which avoid any fixed permutation.

To prove my claim, I will give a bijection from $D_n$ to $E_n(\sigma)$. The bijection is this: given a permutation $\pi \in D_n$, the output of the bijection is the composite permutation $$ \pi\circ \sigma $$ To be clear, this means the permutation whose $i^\text{th}$ entry is $\pi(\sigma(i))$.

Why is this a valid bijection? First of all, the output really is an element of $E_n(\sigma)$. To prove this, note that since $\pi\in D_n$, we have $\pi(j)\neq j$ for all $j$. In particular, letting $j=\sigma^{}(i)$, we get $$ \pi(\sigma(i))\neq \sigma(i), $$ This holds for all $i$, so we conclude $\pi\circ \sigma\in E_n(\sigma)$, as required.

Furthermore, this mapping from $D_n$ to $E_n(\sigma)$ is a bijection, because it has an inverse mapping. Namely, given $\tau\in E_n(\sigma)$, the corresponding permutation in $D_n$ is $\tau\circ \sigma^{-1}$. You can check yourself that these mappings are mutually inverse to each other.


To be clear, this is the strategy I am using to obtain a bijective proof. In general, for sets $X$ and $Y$, to prove that $|X|=|Y|$, it suffices to find a pair of functions $f:X\to Y$ and $g:Y\to X$ with the property that $$ \forall x\in X,\;\; \forall y\in Y,\quad f(g(y))=y\;\text{ and }\;g(f(x))=x $$ This implies that $f:X\to Y$ is a bijection. The fact that $f(g(y))=y$ implies $f$ is surjective, and the fact that $g(f(x))=x$ implies $f$ is injective (check this yourself). Usually, I find that bijective proofs are more natural to complete using this proof outline.

In this case, we have two mappings $$ \begin{align} f:D_n & \to E_n(\sigma) & g:E_n(\sigma)&\to D_n \\ \pi & \mapsto \pi\circ \sigma & \pi &\mapsto \pi\circ \sigma^{-1} \end{align} $$ In my answer, I showed a proof that $f$ was well defined, in the sense that $f(\pi)$ is really an element of $E_n(\sigma)$. All that remains for you to do is to

  • show that $g$ is well-defined; that for all $\pi \in E_n(\sigma)$, that $\pi\circ \sigma^{-1}\in D_n$. [This is pretty similar to the proof I gave that $f$ is well-defined].

  • show that $f( g(\pi))=\pi$ for all $\pi \in E_n(\sigma)$. [As long as you remember how permutation inverses work, this is not hard]

  • show that $g(f(\pi))=\pi$ for all $\pi \in D_n$.

$\endgroup$
2
  • $\begingroup$ Just to clarify, these mappings being mutually inverse to each other isn't necessary to show a bijection, but rather to show bijections in both directions of these sets? $\endgroup$ Sep 16, 2023 at 3:42
  • $\begingroup$ @Shmuel To address your comment, I edited my answer. $\endgroup$ Sep 16, 2023 at 4:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .