I Challenge You

A Latin rectangle consists of a $k \times n$ matrix, all of whose entries are integers between $1$ and $n$ , with the property that none of the $k$ rows of $n$ numbers contain a repeated digit, and none of the $n$ columns of $k$ numbers contain a repeated digit. A normalised Latin rectangle is a Latin rectangle whose first row is the numbers $1,2,3,\ldots,n$ (in order) and whose first column iis the numbers $1,2,\ldots,k$ (in order). Let $L(k,n)$ be the number of normalised $k \times n$ Latin rectangles.

Say that a $k \times n$ Latin rectangle is semi-normalised when its first row is $1,2,3,\ldots,n$ (in order) (with no restriction on the shape of the first column), and let $S(k,n)$ be the number of semi-normalised Latin rectangles. Any semi-normalised Latin rectangle gives us a solution to the posting problem, with the elements in the second row telling us which receiving counter Postman 1,2,3,4,5,6 is assigned to, and the elements in the third row telling us which receiving counter Letter Group 1,2,3,4,5,6 is assigned to. For each Letter Group, there are $2$ ways of sorting the letters into envelopes so that no envelope is in the correct envelope. Thus the number of possible solutions to the problem is $S(3,6) \times 2^6$ It is also clear that $S(k,n) \; = \; (n-1)(n-2)L(k,n)$ since any normalised Latin rectangle can be renumbered to form a seminormalised Latin rectangle in $(n-1)(n-2)$ ways as follows:

• choose an ordered pair $(a,b)$ of distinct integers from the numbers $2,3,4,\ldots,n$ ,
• let $\pi_{a,b}$ be the permutation of $\{1,2,3,\ldots,n\}$ for which $\pi_{a,b}(1) = 1$ , $\pi_{a,b}(2) = a$ , $\pi_{a,b}(3) = b$ , and with $\pi_{a,b}(4), \pi_{a,b}(5),\ldots,\pi_{a,b}(n)$ running through the remaining numbers between $1$ and $n$ (excluding $1,a,b$ ) in order,
• replace every entry $u$ in the normalised Latin rectangle by $\pi_{a,b}(u)$ ,
• reorder the columns of the resulting rectangle so that the first row again reads $1,2,3,\ldots,n$ (in order).

Thus the number of posting arrangements is $2^6 \times 20 \times L(3,6)$ . It is a standard result that $L(3,6) = 1064$ , which tells us that the number of posting rearrangements is $64 \times 20 \times 1064 = \boxed{1361920}$ .

---

It is worth noting that the answer is also $64$ times the number of ordered pairs $(\pi,\sigma)$ such that both $\pi$ and $\sigma$ are derangements of $1,2,3,4,5,6$ , and moreover such that $\pi^{-1}\sigma$ is also a derangement.

This is a slightly more easier, albeit still complicated case of derangement than this problem , as there are $3$ independent variables to be considered instead of $2$ , and taking any one fixed, the remaining two are deranged with respect to each other. For this problem, these variables are: (1) The receiving counters, (2) The postmen, and (3) The letter groups

By a very brute force approach, we can determine the total number of possible combinations. First, we fix any of the three variables. Then, we count the derangements of one of the remaining with respect to the fixed variable. Then, once we determine that, we compare each derangement will all the other derangments, and count those pairs that do not have any common element in any position.

From that, I got $21280$ .

Now, going back to the problem, notice that there were two other conditions. (1) That the letters on the letter groups are already pre arranged, and thus, are already grouped accordingly, and (2) That the letters are not placed on their proper envelopes.

If each letter group has $2$ derangements, then this will give us $(2)^6$ derangements for all letter groups considered.

So, all in all we have

$2^6 \cdot 21280$

$= 1361920$