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.
Best Answer
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.