Boxed lottery tickets, rencontres numbers and number of degree-$n$ permutations of order exactly $d$

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.

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