# What is the Probability Generating Function (PGF) for the "Matching Problem"?

I've been working on a set of questions that ask me to prove various results regarding probabilities concerning the classic "matching problem". There are $n$ letters written to different people, and envelopes correspondingly addressed. The letters are shuffled such that any particular letter-envelope allocation is equally likely as any other. Define a "match" if a particular letter is placed in its correct envelope.

The question began by letting the notation $M_{n,j}=n!P(A_{n,j})$ represent the number of permutations resulting in $j$ matches out of $n$ letters, where $A_{n,j}$ is the event that $j$ matches have occurred out of $n$ letters.

Part a) of the question asked me to show that:

$$M_{n,j}={j+1\over n+1}M_{n+1,j+1}$$

I found this easy enough. The next question defined the generating function for the probability of receiving $j$ matches out of $n$ letters: $G_n(z)=\sum_{j=0}^nP(A_{n,j})z^j$, and asked me, using part a) to prove that:

$$G_{n+1}(z)=1+\int_{1}^zG_n(w)dw$$

Once again, I had no trouble doing this using the first result. It was the third part of the question, however, that confused me. It read "hence find the pgf (probability generating function) $G_n(z)$". The result of the next question leads me to believe that the solution is:

$$G_n(z)=\sum_{k=0}^n{(z-1)^k\over k!}$$

That said, I have no idea how to actually reach this conclusion, and would appreciate some help getting there, preferably using properties of generating functions. It would be preferable to avoid using the formula for number of derangements, as we have not covered this in class and therefore is likely not involved in the expected solution.

Thanks!

• As hinted out by the answer below, you can show the claim by a recursive computation. Saying it differently, you can count on mathematical induction. Commented Apr 30, 2018 at 16:16

## 2 Answers

You can get that iteratively: \begin{align} G_{n}(z) & = 1 + \int_1^z G_{n-1}(x_1)dx_1 \\ % & = 1 + \int_1^z \left( 1 + \int_1^{x_1} G_{n-2}(x_2)dx_2\right) dx_1 \\ % & = 1 + (z-1) + \int_1^z \int_1^{x_1} \left( 1 + \int_1^{x_2} G_{n-3}(x_3)dx_3 \right) dx_2 dx_1 \\ % & = 1 + (z-1) + \int_1^z (x_1-1) dx_1 + \int_1^z \int_1^{x_1} \int_1^{x_2} G_{n-3}(x_3)dx_3 dx_2 dx_1\\ % & = 1 + (z-1) + \int_1^z (x_1-1) dx_1 + \int_1^z \int_1^{x_1} \int_1^{x_2} G_{n-3}(x_3)dx_3 dx_2 dx_1\\ % & = 1 + (z-1) + \frac{(z-1) ^2}{2} + \int_1^z \int_1^{x_1} \int_1^{x_2} G_{n-3}(x_3)dx_3 dx_2 dx_1 \end{align} and so forth until $G_{n-n}(z)=G_0(z)=1$

By way of enrichment we observe that the combinatorial class of permutations with fixed points marked is

$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}} \textsc{SET}(\mathcal{U}\mathcal{Z} +\textsc{CYC}_{\ge 2}(\mathcal{Z}))$$

which gives the bivariate GF

$$G(z, u) = \exp\left(uz+\sum_{q\ge 2} \frac{z^q}{q}\right) = \exp\left(uz-z+\sum_{q\ge 1} \frac{z^q}{q}\right) \\ = \exp\left(z(u-1)+\log\frac{1}{1-z}\right) = \frac{1}{1-z} \exp\left(z(u-1)\right).$$

Extracting coefficients we get the PGF

$$[z^n] \frac{1}{1-z} \exp\left(z(u-1)\right) \\ = \sum_{q=0}^n [z^{n-q}] \frac{1}{1-z} [z^q] \exp\left(z(u-1)\right) = \sum_{q=0}^n \frac{(u-1)^q}{q!}$$

as claimed.