7
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Perhaps I am missing something. With $3$ matching numbers, how can we get an $S2$ prize? If two numbers are in the correct position, the third must also be in the correct position. $\endgroup$ – robjohn Sep 29 '18 at 7:39
  • $\begingroup$ @robjohn for example you select $\{1, 2, 3, 5\}$ but "1,2,3,4" is drawn. So you get prizes for "1,2,5,3", "1,5,3,2" and "5,2,3,1". $\endgroup$ – Q the Platypus Sep 29 '18 at 8:06
  • $\begingroup$ @AlexFrancisco The entries that satisfy $D{4,1}$ that is all the permutations of degree 4 with a single fixed point are "1,3,4,2", "1,4,2,3", "3, 2, 4, 1", "4, 2, 1, 3", "2, 4, 3, 1", "4, 1, 3, 2", "2, 3, 1, 4", "3, 1, 2, 4" that's 8 by my count. what one am I missing? $\endgroup$ – Q the Platypus Sep 29 '18 at 8:21
  • $\begingroup$ @QthePlatypus My mistake. $\endgroup$ – Saad Sep 29 '18 at 8:23
  • $\begingroup$ Can we assume that no one buys a box ticket with duplicate guesses, like "1, 2, 3, 3"? Because that breaks down the table. Can we similarly assume the 4 numbers drawn are distinct? $\endgroup$ – orlp Sep 29 '18 at 10:28
5
+500
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ Inclusion-exclusion principle! Why did I forget that?! This makes everything simple now. $\endgroup$ – Saad Sep 30 '18 at 15:22
4
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Is $C\left(m,k\right) = \dbinom{m}{k}$ ? $\endgroup$ – darij grinberg Sep 30 '18 at 6:51
  • $\begingroup$ @darijgrinberg Yes. $\endgroup$ – Saad Sep 30 '18 at 6:58
  • $\begingroup$ This looks very good. Though I'm still curious why there is the correspondence with the permutation group count. $\endgroup$ – Q the Platypus Sep 30 '18 at 8:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.