What is the average number of matches when randomly picking letters

Question

Suppose we have three pieces of paper. On the first one you have the letter A, on the second on the letter B, and on the third one the letter C.

Now suppose I'm going to randomly pick each one from a bag.

A match happens if I pick the letter in its right alphabetical order. If I pick ABC, for instance, I have three matches. If instead I pick ACB, I have just one match, for the A.

Question 1: if you repeat this exercise, what is the average number of matches? I believe it is 1, and you can see my reasoning on the image below:

Question 2: is there an easy way or a formula to calculate this average for a larger number of letters? For example, what is the average number of matches if we do this exercise with 10 letters?

Curious fact: this problem came up when trying to estimate the average number of correct guesses a person would have on a beer tasting blind test if guessing randomly.

Answer 1

The answer to both questions is $1$. This is because given a random permutation of $n$ letters (call then $1,2,...,n$), the probability that a particular letter $i$ is in the correct place is $1/n$, so the expected number of correct letters is $n(1/n)=1$.

More formally, let $\sigma_1...\sigma_n$ be a random permutation and let $I_k$ be the indicator variable for the event $\sigma_k=k$. We have $E[I_k]=1/n$, so by linearity of expectation the number of correct letters is $$E[I_1+...+I_n]=E[I_1]+...+E[I_n]=n(1/n)=1$$

Answer 2

We have for permutations with fixed points marked the combinatorial class

$$\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})).$$

This gives the mixed generating function

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

The desired quantity is then given by (the term $u^k z^n/n!$ representing a permutation of $n$ elements with $k$ fixed points) should contribute $k z^n/n!$)

$$[z^n] \left. \frac{\partial}{\partial u} G(z, u) \right|_{u=1} \\ = [z^n] \left. \frac{1}{1-z} \exp(uz-z) z \right|_{u=1} \\ = [z^n] \frac{z}{1-z}.$$

This is zero for $n=0$ and evaluates to

$$\bbox[5px,border:2px solid #00A000]{1}$$

otherwise. Here the EGF includes the factor $n!$ that produces the average.