Boxed lottery tickets, rencontres numbers and number of degree-$n$ permutations of order exactly $d$ This is a question that I encountered at work that I am trying to get a deeper understanding of.
We sell tickets in a lottery where you guess $4$ numbers out of range of $36$ (the range is irrelevant to this problem) in an order. Four numbers are drawn. If your first guessed number matches the first drawn number it is considered a match, likewise for the second, third and fourth draws. You get different prizes for how many numbers you get matched.  Matching all four gets you an $S4$ prize, matching three gets you an $S3$ prize and so on.
However we also offer a "boxed" ticket, which is equivalent to buying all $24$ permutations of the $4$ numbers you selected. You can determine how many prizes of each class you will win for the count of matching numbers from this table:
$$\begin{array}{ |c | c | c | c | c | } \hline
\text{Matching Numbers} & S4 & S3 & S2 & S1 \\
4 & 1 & 0 & 6 & 8 \\
3 & 0 & 1 & 3 & 9 \\
2 & 0 & 0 & 2 & 8 \\
1 & 0 & 0 & 0 & 6 \\
\hline
\end{array} $$
Now the "$4$" matching row is the number of permutations of $4$ with $4$, $3$, $2$, $1$ fixed points, i.e. the rencontres numbers $n=4$. This naturally falls out of the problem description and I understand this.
By use of the OEIS database I was able to work out that $3$ matching number row corresponds to number of degree-$n$ permutations of order exactly $2$. Row 2 matching number row corresponds to number of degree-$n$ permutations of order exactly $3$.
I am unsure if this is a genuine correspondence or if it is a coincidence. I am wondering if there is a general way to generate this table, for example for a lottery with n selected numbers.
 A: Building  on the  work  by @AlexFrancisco  in  clarifying the  problem
definition, establishing a recurrence  and providing examples it would
seem that we have the closed form
$$\bbox[5px,border:2px solid #00A000]{
{m\choose k} \sum_{q=0}^{m-k} {m-k\choose q} (-1)^q (n-k-q)!.}$$
This is the number of prizes of  class $k$ with $m$ matches from among
$n$ total. With this formula we  first select the $k$ matches from the
$m$ available ones and combine  them with a generalized derangement of
the rest, which we compute by inclusion-exclusion.
 For the PIE argument we have  that the nodes $Q$ of the underlying
poset represent subsets  $Q\subseteq R$ of the set  of potential fixed
points $R$  of cardinality $m-k$  that are  required not to  be fixed.
The permutations  represented at  $Q$ have the  elements of  $Q$ being
fixed  in addition  to  the  $k$, plus  possibly  more.  This set  has
cardinality  $(n-k-|Q|)!.$  We  ask  about   the  total  weight  of  a
permutation of the $n-k$ remaining elements after the $k$ fixed points
have  been chosen,  where the  weights  at $Q$  are $(-1)^{|Q|}$.   An
admissible permutation has none of the elements of $R$ being fixed and
hence    is   only    included    in    $Q=\emptyset$   with    weight
$(-1)^{|\emptyset|} =  1.$ A  permutation with exactly  $P\subseteq R$
fixed points  in addition to  the $k$ where $P\ne\emptyset$  and hence
$|P|\ge 1$ is included at all nodes $Q\subseteq P,$ for a total weight
of
$$\sum_{Q\subseteq P} (-1)^{|Q|}
= \sum_{q=0}^{|P|} {|P|\choose q} (-1)^q = 0.$$
The total  weight of a permutation  where none of the  elements of $R$
are fixed is  one, and zero otherwise.  We conclude  that the sum term
of  the proposed  formula  counts exactly  those  permutations of  the
remaining $n-k$ elements  where none of the $m-k$ elements  of $R$ are
fixed.
A: Here a general formula for the table will be given.

Step 1: Given distinct $a_1, a_2, \cdots$ and $b_1, b_2, \cdots$, define $A_n = \{a_1, \cdots, a_n\}$ and $B_n = \{b_1, \cdots, b_n\}$ for $n \geqslant 0$, and$$
\mathscr{F}_{m, n} = \{φ: A_m → A_m \cup B_n \mid φ \text{ is injective},\ φ(x) ≠ x,\ \forall x \in A_m\},\\
f(m, n) = |\mathscr{F}_{m, n}|,
$$
  where $m, n \geqslant 0$. Then for $n \geqslant 0$,$$
f(0, n) = 1, \quad f(1, n) = n,\\
f(m, n) = (m + n - 1)f(m - 1, n) + (m - 1)f(m - 2, n). \quad (m \geqslant 2)
$$

Proof: Obviously $f(0, n) = 1$. For $m = 1$, since $φ(a_1) \in B_n$, then $f(1, n) = n$. Now consider $m \geqslant 2$.
If $φ(a_1) \in B_n$, then intuitively$$
φ|_{A_m \setminus \{a_1\}}: A_m \setminus \{a_1\} \longrightarrow (A_m \setminus \{a_1\}) \cup \bigl( (B_n \setminus \{φ(a_1)\}) \cup \{a_1\} \bigr)
$$
corresponds to a mapping in $\mathscr{F}_{m - 1, n}$ and thus$$
|\{φ \in \mathscr{F}_{m, n} \mid φ(a_1) \in B_n\}| = n f(m - 1, n). \tag{1}
$$
If $φ(a_1) = a_i$ and $φ(a_i) = a_1$, then intuitively$$
φ|_{A_m \setminus \{a_1, a_i\}}: A_m \setminus \{a_1, a_i\} \longrightarrow (A_m \setminus \{a_1, a_i\}) \cup B_n
$$
corresponds to a mapping in $\mathscr{F}_{m - 2, n}$. If $φ(a_1) = a_i$ but $φ(a_i) ≠ a_1$, then intuitively$$
φ|_{A_m \setminus \{a_1\}}: (A_m \setminus \{a_1, a_i\}) \cup \{a_i\} \longrightarrow \bigl( (A_m \setminus \{a_1, a_i\}) \cup \{a_1\} \bigr) \cup B_n
$$
corresponds to a mapping in $\mathscr{F}_{m - 1, n}$. Thus$$
|\{φ \in \mathscr{F}_{m, n} \mid φ(a_1) \in A_m\}| = (m - 1) (f(m - 1, n) + f(m - 2, n)). \tag{2}
$$
Combining (1) and (2) yields$$
f(m, n) = (m + n - 1)f(m - 1, n) + (m - 1)f(m - 2, n).
$$
The rest of this proof focuses on rigorously proving (1) since (2) can be proved analogously.
By symmetry,$$
|\{φ \in \mathscr{F}_{m, n} \mid φ(a_1) \in B_n\}| = n·|\{φ \in \mathscr{F}_{m, n} \mid φ(a_1) = b_1\}|.
$$
On the one hand, for $φ \in \mathscr{F}_{m, n}$ such that $φ(a_1) = b_1$, define $ψ: A_{m - 1} → A_{m - 1} \cup B_n$ as$$
ψ(x) = \begin{cases}
b_1; & x = a_i,\ φ(a_{i + 1}) = a_1\\
a_j; & x = a_i,\ φ(a_{i + 1}) = a_{j + 1}\\
b_j; & x = a_i,\ φ(a_{i + 1}) = b_j
\end{cases},
$$
then $ψ \in \mathscr{F}_{m - 1, n}$. Note that this defines an injective mapping from $\{φ \in \mathscr{F}_{m, n} \mid φ(a_1) = b_1\}$ to $\mathscr{F}_{m - 1, n}$, thus$$
|\{φ \in \mathscr{F}_{m, n} \mid φ(a_1) = b_1\}| \leqslant f(m - 1, n).
$$
On the other hand, for $ψ \in \mathscr{F}_{m - 1, n}$, define $φ: A_m → A_m \cup B_n$ as$$
φ(x) = \begin{cases}
b_1; & x = a_1\\
a_{j + 1}; & x = a_{i + 1},\ ψ(a_i) = a_j\\
a_1; & x = a_{i + 1},\ ψ(a_i) = b_1\\
b_{j + 1}; & x = a_{i + 1},\ ψ(a_i) = b_{j + 1}
\end{cases},
$$
then $φ \in \mathscr{F}_{m, n}$ and $φ(a_1) = b_1$. Note that this is an injective mapping from $\mathscr{F}_{m - 1, n}$ to $\{φ \in \mathscr{F}_{m, n} \mid φ(a_1) = b_1\}$, thus$$
f(m - 1, n) \leqslant |\{φ \in \mathscr{F}_{m, n} \mid φ(a_1) = b_1\}|.
$$
Therefore (1) holds.

Step 2: Given distinct $a_1, a_2, \cdots$, $b_1, b_2, \cdots$, and $c_1, c_2, \cdots$, define $A_n = \{a_1, \cdots, a_n\}$, $B_n = \{b_1, \cdots, b_n\}$, $C_n = \{c_1, \cdots, c_n\}$ for $n \geqslant 0$, and$$
\mathscr{G}_{k, m, n} = \{φ: A_m \cup B_{n - m} → A_m \cup C_{n - m} \mid φ \text{ is injective with exactly } k \text{ fixed points}\},\\
g(k, m, n) = |\mathscr{G}_{k, m, n}|,
$$
  where $k \leqslant m \leqslant n$. Then$$
g(k, m, n) = (n - m)!\, C(m, k) f(m - k, n - m).
$$
  (Note that $g(k, m, n)$ is the number of prizes of class $k$ if there are $m$ matching numbers out of $n$ in total.)

Proof: There are $C(m, k)$ ways to select $k$ fixed points from $A_m$, then $f(m - k, n - m)$ ways to select the images of the rest $m - k$ elements of $A_m$, and then $(n - m)!$ ways to select the images of elements in $B_{n - m}$. Thus$$
g(k, m, n) = (n - m)!\, C(m, k) f(m - k, n - m).
$$
