What is the number of Latin rectangles given the number of reduced Latin rectangles?

Question

My PhD supervisor called the following result something along the lines: "The theorem in the theory of Latin squares with the most incorrect proofs" (then, to my embarrassment, proceeded to point out an error in my "proof" at the time). I'll pose proving it as a problem.

Definition: A $k \times n$ *Latin rectangle* is a $k \times n$ matrix with symbols from $\{1,2,\ldots,n\}$ for which each symbol occurs exactly once in each row and at most once in each column. For example:

1 2 4 3
2 3 1 4
4 1 3 2

is a $3 \times 4$ Latin rectangle.

Definition: A Latin rectangle is called reduced if the first row is $(1,2,\ldots,n)$ and the first column is $(1,2,\ldots,k)^T$.

The above Latin rectangle is not reduced, but this one is:

1 2 3 4
2 3 4 1
3 4 1 2

Let $L_{k,n}$ be the number of $k \times n$ Latin rectangles. Let $R_{k,n}$ be the number of reduced $k \times n$ Latin rectangles.

Theorem: For all $1 \leq k \leq n$, \[L_{k,n}=\frac{n!(n-1)!}{(n-k)!}R_{k,n}.\]

Problem: Prove it (and double-check your proof).

Answer 1

Consider the following reduction algorithm:

1. Move the unique column in which $1$ is the first element to the left (extract it and put it as the first column).
2. Apply the unique injection that maps the $j$th element in the first column to $j$.
3. Apply the unique permutation on the $n-1$ columns to the right of the first column which makes the first row $1\ldots n$.

Taking our steps in reverse to unscramble a reduced form, we have $(n-1)!$ choices in the third step, $(n-1)^{\underline{k-1}} = (n-1)!/(n-k)!$ choices in the second step, and $n$ choices in the first step, to a total of $$(n-1)!\frac{(n-1)!}{(n-k)!}n = \frac{n!(n-1)!}{(n-k)!}.$$

More formally, we could define

• $A_{k,n}$ as the number of Latin rectangles whose upper left value is $1$.
• $B_{k,n}$ as the number of Latin rectangles whose left-most column is reduced.

Then we show the following: $$\begin{align*} L_{k,n} &= n A_{k,n}, \\ A_{k,n} &= \frac{(n-1)!}{(n-k)!} B_{k,n}, \\ B_{k,n} &= (n-1)R_{k,n}. \end{align*}$$

Answer 2

So I'll give the proof I'm used to. It relies on what (I've been led to believe) Brendan McKay coined the "switching principle": Suppose you have a bipartite multi-graph, with parts $A$ and $B$. Suppose every vertex in $A$ has degree $c$ and every vertex in $B$ has degree $d$. Then $Ac=Bd$.

We say a Latin rectangle is normalised if the first row is $(1,2,\ldots,n)$. Let $K_{k,n}$ be the number of $k \times n$ normalised Latin rectangles. By permuting the columns of a $k \times n$ Latin rectangle, we generate $n!$ distinct Latin rectangles of which exactly one is normalised. Hence $L_{k,n}=n! K_{k,n}$.

We will now prove the identity $K_{k,n}=\frac{(n-1)!}{(n-k)!} R_{k,n}$.

We take A to be the set of all normalised $k \times n$ Latin rectangles and take B to be the set of all reduced $k \times n$ Latin rectangles. [Actually, B is a subset of A, so this is strictly speaking a bit suspect, but this can be overcome this problem by labelling (I won't do this here, as it's a bit messy).]

Let $G$ be the group of permutations of $\{1,2,\ldots,n\}$ that fix 1. Given any reduced Latin rectangle $L \in B$ and $\alpha \in G$ we can construct a normalised Latin rectangle by: starting from $L$, permute the columns by $\alpha$, then permute the symbols by $\alpha$. Call this Latin square $L_\alpha$.

We construct the bipartite multigraph by: for every $L \in B$ add an edge from $L$ to $L_\alpha$ for all $\alpha \in G$. Since $L_\alpha$ might equal $L_\beta$, the graph might not be simple.

Every vertex in $B$ has degree $(n-1)!$. So it is sufficient to show that every vertex in $A$ has degree $(n-k)!$. There is an edge between $L=(l_{ij}) \in A$ and some vertex in $B$ for each permutation $\alpha \in G$ satisfying $\alpha(i)=l_{i1}$ for all $1 \leq i \leq k$. There are $(n-k)!$ such permutations, and hence every vertex in $A$ has degree $(n-k)!$.