CS-274 - Math-284 Combinatorics and Probability
Homework - May 28, 1998
Instructor: László Babai Ryerson 164 e-mail: laci@cs
Student: Nick Russo e-mail: n-russo@uchicago.edu

1.

Prove that the number of $2 \times n$ latin rectangles is asymptotically equivalent to $\frac{\left(n!\right)^2}{e}$.

The numbers in the top row can be ordered n! ways, so the total number of latin rectangles is n! times the number of ways to construct a second row such that no conflict is implied.

There are n! total ways to arrange the elements of the second row, so there are less than n! ways that are ``good''.

I should be able to use Inclusion/Exclusion to count the number of permutations that fix 1, those that fix 2, those that fix 1 and 2, etc... and in doing so, I should be able to find out the size of the set of ``good'' permutations.

When I use Inclusion/Exclusion, I find that:

$$\left\vert \left\{ good\ permutations \right\} \right\vert \sum_{i=0}^{n}{n \choose i}\left(n-i\right)! \cdot \left(-1\right)^{i}$$ = (1)

$$- {n \choose 1}\left(n-1\right)! + {n \choose 2}\left(n-2\right)! - \cdots$$ =

But each term contains $\left(n-i\right)!$ on the top, and hidden away in the bottom term, so they cancel out and leave $\frac{n!}{i!}$.

$$\sum_{i=0}^{n} \frac{n!}{i!} \left(-1\right)^i$$ = (2)

$$n! \cdot \sum_{i=0}^{n} \frac{1}{i!} \left(-1\right)^i$$ = (3)

But that sum is just an expansion of $\frac{1}{e}$ ¹, as $n \rightarrow \infty$, so we have the number of ``good permutaions'' $\sim n! \cdot \frac{1}{e}$. Then, as noted above, the total number of latin rectangles $\sim n! \times \frac{n!}{e}$, or $\frac{n!^2}{e}$.