Rencontres Numbers

Question

I'm having trouble understanding rencontres numbers, $D_{n,k}$.

The numerical values shown of the wiki page:

https://en.wikipedia.org/wiki/Rencontres_numbers

Looking at n = 3:

1. $D_{3,3} = 1$ I think I understand this because there is only one way to give all three items to the correct person
2. $D_{3,2} = 0$ because if 2 people had the correct item the third person must also have the right item
3. $D_{3,1} = 3$ as there are three different ways to give one person the right item
4. $D_{3,0} = 2$ this is the part I don't understand, I thought the answer should be 1 as there is only one way to give nobody the right item

Can someone please explain why for $n =3$ and $k=0$ the answer is $2$?

Answer 1

You could give item $1$ to person $2$, item $2$ to person $3$ and item $3$ to person $1$, or item $1$ to person $3$, item $2$ to person $1$ and item $3$ to person $2$. That's two ways.

Answer 2

If there are three people ($A, B, C$) and three presents ($a, b, c$), there are two ways in which nobody gets the right present.

$$\begin{align*} &A \;\;\; B \;\;\; C \\\\ &c \;\;\;\; a \;\;\;\; b \\\\ &b \;\;\;\; c \;\;\;\; a \\\\ \end{align*}$$

Answer 3

Since $D_{n,0}$ are the (full) derangement numbers, they count the total number of ways to not give any of $n$ items back to their correct owners, as you correctly describe in your question. (Each item must belong to just 1 owner).

We can think of a 'reason' for $D_{3,0}=2$ by considering the situation graphically in terms of cycles and fixed points.

---

$\mathbf{EXAMPLE}$

Give each item a label 1,2,3; and each person the item belongs to the same label.

An arbitrary example of a way to distribute the items is:

• Item 1 going to person 2, represented graphically by $1\rightarrow 2$.
• Item 2 going to person 1, represented graphically by $2\rightarrow 1$.
• Item 3 going to person 3 (the only option left), is thus $3 \rightarrow 3$.

Putting this all together reveals a graph made of two separate parts:

$1 \rightarrow 2 \rightarrow 1$

and

$ 3\rightarrow 3$

We call the first part (where neither item ends up where it should) a cycle, since it loops back to where it started. This is a cycle with 2 items, and is hence called a 2-cycle. It can be written equivalently as $(12)$.

The second part (where the item returns to its owner) is a self-loop, sometimes called a 1-cycle, but very commonly is called a fixed point. This can be written simply as $(3)$.

Overall, this particular shuffling of the items can be written $(12)(3)$.

---

$\mathbf{REASON}$

Hence, counting all the possible ways of returning items such that no item returns to its correct owner, is the same as counting all possible ways of drawing cycles without drawing any fixed points.

---

$\mathbf{n=3}$

In the case of 3 items, we have only two possible cycles: (123) and (132).

Hence, $D_{3,0}=2$ because there are only 2 ways draw cycles, without fixed points, using 3 items.

---

$\mathbf{n=4}$

This example will clarify why $D_{4,0} = 9$, which might be even more confusing at first glance.

For 4 items, all possible 4-cycles, without any fixed points, seem to be:

• (1234)
• (1243)
• (1324)
• (1342)
• (1423)
• (1432)

This is only 6, not 9... that's not nice. How come?!

Well, there are actually still a few more ways to draw cycles, still without fixed points, by drawing pairs of 2-cycles:

• (12)(34)
• (13)(24)
• (14)(23)

This gives the remaining 3 ways of making sure none of the 4 owners has their precious item returned!

---

$\mathbf{EPILOGUE}$

While the derangement numbers are usually derived via inclusion-exclusion, the insight of the $n=4$ case allows us to describe another derivation: as the sum of all possible cycles over all possible cycle-types defined by integer partitions of $n$ (that don't use the digit 1). (A question I posted highlights my surprise at the arithmetic equality of the two approaches!)