Let’s explore an interesting application of z-transform: solving the classical derangement probability. This problem is often put as the probability that no one gets their own hat, suppose we randomly distribute $n$ hats to $n$ people.

Introduction

The derangement problem is a classic combinatorial problem. Given $n$ distinct items, a derangement is a permutation of these elements, such that no item appears in its original position. For example, let’s consider 3 items $(A, B, C)$. Then, both $(B, C, A)$ and $(C, A, B)$ are its derangements, but $(B, A, C)$ is not since $C$ remains the same position.

Let $D_n$ denote the number of derangements of $n$ distinct items. Then $D_n/n!$ is the probability of obtaining a derangement from a random permutation of $n$ items. Imagine we ask $n$ students to peer grade their assignments and let each student randomly take one assignment from all $n$ assignments. Then this probability is the probability of obtaining a valid grading plan—no one should grade their own assignment.

There are multiple ways to compute this probability. A popular one is based on the inclusion–exclusion principle, such as this AoPS post.

Counting Derangements

To see how $D_n$ is related to $n$, we can divide all $n!$ permutations into $n + 1$ different classes, such that each class $k$ ($k = 0, 1, 2, \dots, n$) contains the permutations where exactly $k$ items do not appear in their original position. Then, each permutation in class $k$ contains $k$ items that form a derangement, and the remaining entries stay the original position. Therefore, the size of class $k$ is $ \binom{n}{k} \cdot D_{k} $. We set $D_0 = 1$ to make the formula consistent for all $k = 0, \dots, n$.

Now, we can take the sum all $(n+1)$ such classes, and we will obtain the equality $$ \sum_{k = 0}^{n} \displaystyle\binom{n}{k} \cdot D_{k} = n!, \quad n = 0, 1, 2, \dots \tag{1} \label{eq:sum} $$

Signal of Probabilities

Note that the derangement probability $D_n/n!$ relies on $n \geq 0$, we can treat it as a discrete-time signal $x[n]$, formally defined as \begin{align} x[n] = \begin{cases} D_n/n!& \text{if $n \geq 0$},\cr 0& \text{otherwise}. \end{cases} \end{align}

Since $\binom{n}{k} = \frac{n!}{(n-k)!k!}$, from \eqref{eq:sum} we obtain $$ \sum_{k = 0}^n \frac{x[k]}{(n-k)!} = 1, \quad n = 0, 1, 2, \dots. \tag{2} \label{eq❌conv} $$

LTI System Behind

We can find a familiar pattern in \eqref{eq❌conv}, which is a sum with index $k$, and inside the sum we have $k$ and $n-k$. This is exactly a convolution of two signals, and one of them seems to be our $x[n]$. It is not hard to write the other signal $x[n]$ is convolved with, and we call this \begin{align*} h[n] = \frac{1}{n!} \cdot u[n], \end{align*} where $u[n]$ is the discrete time unit step function.

Then, the left hand side of \eqref{eq❌conv} becomes $(x \ast h)[n]$, i.e., the output of an LTI system with impulse response $h[n]$, when the input is $x[n]$. Let’s call this output $y[n]$. Then from the right hand side, $y[n]= 1$ for all $n \geq 0$, which means $y[n]$ is nothing but the unit step function $u[n]$.

At this point, we have obtained a standard input-output relation for an LTI system, which looks like this. System

The z-Transform

To determine $x[n]$, we can apply $z$-transform on the convolution equation $y = x \ast h$. We will use the corresponding capital letter to denote the z-transforms of a signal. For example, we denote the $z$-transform of $x[n]$ by $\displaystyle X(z) = \sum_{n} x[n]z^{-n}$. Then, we have $Y(z) = X(z) \cdot H(z)$. Here, $Y(z)$ is the z-transform of $y[n] = u[n]$ and we have $Y(z) = 1/(1 - z^{-1})$. $H(z)$ can be computed from the Taylor series \begin{align} \exp(z) = \sum_{n \geq 0} \frac{z^n}{n!}, \end{align} and we have \begin{align} H(z) = \sum_{n \geq 0} \frac{z^{-n}}{n!} = \exp\left(z^{-1}\right). \end{align}

This suggests that \begin{align} X(z) = \frac{Y(z)}{H(z)} = \frac{1}{1 - z^{-1}} \cdot \exp\left(-z^{-1}\right). \end{align}

Last Step?

Technically we are just one step away from the destination—to apply inverse z-transform on $X(z)$. However, the form of $X(z)$ is not very pleasant for the computation, and we may want to get rid of the denominator. This denominator $1 - z^{-1}$ itself is not complicated. Indeed, it is the $z$-transform of $\delta[n] - \delta[n-1]$, which corresponds to a first-order difference unit.

Following this idea, we can construct this different unit as follows. Let’s feed $x[n]$ to this system, and call the output $w[n]$. System

Then we have \begin{align} w[n] = x[n] - x[n-1] \tag{3} \label{eq:3} \end{align} and with the $z$-transform, \begin{align} W(z) = X(z) (1 - z^{-1}) = \exp\left(-z^{-1}\right). \end{align}

The inverse $z$-transform of $W(z)$ can be obtained again from the Taylor series. Since \begin{align} W(z) = \sum_{n \geq 0} \frac{(-1)^n}{n!}\cdot {z^{-n}} = \sum_{n=-\infty}^\infty \frac{(-1)^n}{n!} \cdot u[n] \cdot z^{-n}, \end{align} we can read \begin{align} w[n] = \frac{(-1)^n}{n!} \cdot u[n]. \end{align}

Finally, we can exploit \eqref{eq:3} to express the derangement probability $x[n]$ as \begin{align} x[n] = x[n] - x[-1]&= \sum_{k = 0}^{n} (x[k] - x[k - 1])\cr &= \sum_{k = 0}^{n} w[k]. \tag{4} \label{eq:4} \end{align} This gives us \begin{align} x[n] = \sum_{k = 0}^{n} \frac{(-1)^k}{k!}. \end{align}

One bonus from the $z$-transform is the limiting behavior of $x[n]$. From \eqref{eq:4}, we obtain \begin{align} \lim_{n \to \infty} x[n] = \sum_{k = 0}^{ \infty} w[k] = \sum_{k} w[k] = W(1) = \frac1e. \end{align}