\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{latexsym}
\usepackage[pdftex]{graphicx}
\usepackage{url}
\usepackage{mathrsfs}
\usepackage{multicol}
\usepackage{hhline}
\usepackage{hyperref}
\usepackage{wrapfig}
\hypersetup{colorlinks=true}
\pagestyle{empty}
\usepackage{tikz}
\usetikzlibrary{calc,trees,positioning,arrows,fit,shapes,calc}
\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\setlength{\textwidth}{6in}
\setlength{\topmargin}{-0.4in}
\setlength{\textheight}{8.5in}
\begin{document}
\begin{center}
Latin Squares: Transversals and counting of Latin squares\\
Jenny Zhang, Yian Huang\\
February 22, 2015\\
\end{center}

Author: Jenny Zhang

First, let's preview what mutually orthogonal Latin squares are. Two Latin squares $L_1=[a_{ij}]$ and $L_2=[b_{ij}]$ on symbols $\{1,2,...n\}$, are said to be orthogonal if every ordered pair of symbols occurs exactly once among the $n^2$ pairs $(a_{ij}, b_{ij})$, $1\leq i\leq n$, $1\leq j\leq n$.

Now, let me introduce a related concept which is called transversal. A transversal of a Latin square is a set of n distinct entries such that no two entries share the same row, column or symbol.

This is an example of mutually orthogonal latin squares.
\\$L_1$=
\begin{align*}
\begin{bmatrix}
2 & 3 & 1\\
1 & 2 & 3\\
3 & 1 & 2
\end{bmatrix}
\end{align*}
$L_2$=
\begin{align*}
\begin{bmatrix}
2 & 1 & 3\\
1 & 3 & 2\\
3 & 2 & 1
\end{bmatrix}
\end{align*}
\\We have (2,2), (3,1), (1,3), (1,1), (2,3), (3,2), (3,3), (1,2), (2,1)



Theorem 1. A Latin square has an orthogonal mate if and only if it can be decomposed into n disjoint transversal.

If we consider the exactly n cells of the Latin square $L_2$ all of which contain the same fixed entry h say($1\leq h \leq n$), then the entries in the corresponding cells of the Latin square $L_1$ must all be different, otherwise the squares would not be orthogonal.  Since the symbol h occurs exactly once in each row and column of the latin square $L_2$, we see that the n entries of $L_1$ corresponding to the entry h in $L_2$ is a transversal.

Orthogonal latin squares exist for all orders $n\notin \{2,6\}$. For n=6, there is no pair of orthogonal squares, but we get close. We have an example which contain 4 disjoint transversals.
\begin{align*}
\begin{bmatrix}
1_a & 2 & 3_b & 4_c & 5 & 6_d\\
2_c & 1_d & 6 & 5_b & 4_a & 3\\
3 & 4_b & 1 & 2_d & 6_c & 5_a\\
4 & 6_a & 5_c &1 & 3_d & 2_b\\
5_d & 3_c & 2_a & 6 & 1_b & 4\\
6_b & 5 & 4_d & 3_a & 2 & 1_c\\
\end{bmatrix}
\end{align*}

Partial Latin Square

Partial latin square of order n is a matrix of order n in which each cell is either blank or contains one of $\{1,2,...,n\}$, and which has the property that no symbol occurs twice within any row or column. A cell which is not blank is said to be filled. A partial latin square with every cell filled is call latin square. The set of partial latin squares of order n is denotes by $PLS(n)$, and the set of latin squares of order n by $LS(n)$. We say $P_1 \in PLS(n)$ is said to be completable if there is some $L \in LS(n)$ such that L contains P. On the other hand, P is said to be maximal if the only partial latin square which contains P is P itself.

We coin the name k-plex of order n for a $K\in PLS(n)$ in which each row and column of K contains exactly k filled cells and each symbol occurs exactly k times in K. The entries on a transversal of a latin square form a 1-plex.

We say that two plexes in the same square is parallel if they have no filled cells in common. The union of an a-plex and a parallel b-plex of a latin square L is an (a+b)-plex of L. However it is not in general possible to split an (a + b)-plex into an a-plex and a parallel b-plex.

Next, let me present a few theorems about the k-plex:

Theorem 1. If $n > 2$ then there exists $L \in LS(n)$ which contains a k-plex for each k satisfying $0 \leq k \leq n$.

Proof: If $n > 2$ and $n\neq 6$, a celebrated result says that there are two orthogonal latin squares of order n. So there will be transversal in the latin square, then there will at least be 1-plex in the latin square. For n = 6 there is no pair of orthogonal squares, however we found a latin square order 6 which contains 4 parallel transversals that I talked about before. What we just proved is that if 0 ≤ k ≤ n and n > 2 then there is a completable k-plex of order n. However, our next result shows that not all k-plexes are completable.

Theorem 2. If $1 < k < n$ and $k > \frac{n}{4}$ there exists an uncompletable k-plex of order n.

Theorem 3. For $k \leq \frac{n}{4}$ every k-plex of order n is contained in a $(k + 1)-plex$ of order $4n$.

Author:Yianhuang
\section{Introduction}
In this presentation, I'm going to introduce the concept of Latin Rectangle and the counting of $2\times n$ latin rectangle.
\section{latin rectangle $L=l_{ij}$ }
For $1\le k\le n$, k x n latin rectangle is the $k\times n$ array $L=l_{ij}$ with entries from $\{1,2,...,n\}$ such that the entries in each row and each column are distinct.
\\For k=2, a 2 x n latin rectangle is the $2\times n$ array $L=l_{ij}$ with entries from $\{1,2,...,n\}$ such that the entries in each row and each column are distinct.
\\We can also say a $k\times n$ latin rectangle part of $n\times n$ latin square.
\section{reduced latin rectangle $R_ij$}
We say $R_ij$ is reduced latin rectangle if The first row is $(1,2,....n)$ and the first column is $(1,2,....n)^{T}$.
For instance, this is considered a reduced latin rectangle. $\begin{array}{|c|c|c|c|c|}\hline 1 & 2 & 3 &4 \\\hline 2 & 4 & 1 &3 \\\hline 3 & 1 & 4 & 2\\\hline\end{array}$\\
\\For Reduced Latin Rectangle, we have some very interesting things to talk about. But today I'm going to discuss a reduced Latin Rectangle in a $2\times n$ form, which is like:
\\$\begin{array}{|c|c|c|c|c|}\hline 1 & 2 & 3 &4 \\\hline 2 & 4 & 1 &3\\\hline\end{array}$\\
\\ The cool thing of a reduced latin rectangle is once we find all possible latin rectangle to a reduced latin rectangle, we can us Permutation to find all possible latin rectangles!
\\ For instance, for a 2x3 latin rectangle we can easily know there are basically 2 types of reduced latin rectangles which are:
\\$\begin{array}{|c|c|c|c|c|}\hline 1 & 2 & 3 \\\hline 2 &3 &1\\\hline\end{array}$ and $\begin{array}{|c|c|c|c|c|}\hline 1 & 2 & 3 \\\hline 3 & 1 & 2\\\hline\end{array}$\\
\\ And if written as tuples, there are six permutations of the set $\{1,2,3\}$, namely: (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), and (3,2,1), which means we can substitute with any of its
6 permutations all permutations have 2 types of reduced latin rectangles.
In this case, if we substitute $\{1,2,3\}$ with $\{1,3,2\}$ we get new latin rectangles!
\\$\begin{array}{|c|c|c|c|c|}\hline 1& 3 & 2 \\\hline 3 &2 &1\\\hline\end{array}$ and $\begin{array}{|c|c|c|c|c|}\hline 1 & 3 & 2 \\\hline 3 & 1 & 2\\\hline\end{array}$\\
\\And since we have 6 of such permutations, we can say we have $6\times2=12$ $3\times 2$ Latin Rectangles in total.
In general, for a $2\times n$ Latin Rectangle, since we have $n!$ permutations, the possible Latin rectangle $L_ij$ is $n! R_ij$ \\
\section{number of $2\times n$ reduced latin rectangles }
For $2\times n$ latin rectangles, since we've already know once we find the total number of $R_ij$, we can find the total number of latin rectangle $L_ij$.
\\\\To count $R_ij$, our easy way is by using bijection:
\\\\In below $2 \times 3$ case,  we can easily "draw" all the possibilities and we can eventually find 2 graphs.
\\\\In below $2 \times 4$ case,  after we randomly link 2 vertexes together, we find a pattern in which is very similar to the $2 \times 3$ case but for each bijection due to the 1 number difference, we can draw 3 kind of graphs, so the whole number of latin rectangle after we link  2 vertexes together is 3 and since we can randomly like give 3 kinds of first random vertexes link, all the possibilities and we can eventually find is $3\times 3=9$ graphs.
\\\\\\\\when we come to $2 \times 5$ case,  after we randomly link 2 vertexes together, like what we just did to 4, we find a pattern in which is very similar to the $2 \times 4$ case but for each bijection due to the 1 number difference, we can draw 4 this kind of of graphs, and in each of the graph, when we continue to randomly link 2 vertexes together, we find 2 kinds of graphs, one kind is a $2 \times 3$ latin rectangle and the other kind is 3 latin rectangle that appears in the $2 \times 4$ case.
Then we notice a interesting pattern:
which is the number of $2 \times 5$ latin rectangle is (n-1) times number of  $2 \times 3$ and $2 \times 4$ latin rectangle. This is all what this class is going to talk about. The next class I' m going to discuss how to solve this equation:
$N_{n}=(n-1)(N_{n-1}+N_{n-2})$
\\\\\\\\\\\\\\\\\\\\
\\\\\\\\\\\\\\\\\\\\

\begin{figure}
\center
 \begin{tikzpicture}[ele/.style={fill=black,circle,minimum width=.8pt,inner sep=1pt},every fit/.style={ellipse,draw,inner sep=-2pt}]
  \node[ele,label=left:$1$] (a1) at (0,4) {};
  \node[ele,label=left:$2$] (a2) at (0,3) {};
  \node[ele,label=left:$3$] (a3) at (0,2) {};

  \node[ele,,label=right:$1$] (b1) at (4,4) {};
  \node[ele,,label=right:$2$] (b2) at (4,3) {};
  \node[ele,,label=right:$3$] (b3) at (4,2) {};

  \node[draw,fit= (a1) (a2) (a3) ,minimum width=2cm] {} ;
  \node[draw,fit= (b1) (b2) (b3) ,minimum width=2cm] {} ;
  \draw[->,thick,shorten <=2pt,shorten >=2] (a1) -- (b2);
  \draw[->,thick,shorten <=2pt,shorten >=2] (a2) -- (b3);
  \draw[->,thick,shorten <=2pt,shorten >=2] (a3) -- (b1);
 \end{tikzpicture}
\end{figure}

\begin{figure}
\center
 \begin{tikzpicture}[ele/.style={fill=black,circle,minimum width=.8pt,inner sep=1pt},every fit/.style={ellipse,draw,inner sep=-2pt}]
  \node[ele,label=left:$1$] (a1) at (0,4) {};
  \node[ele,label=left:$2$] (a2) at (0,3) {};
  \node[ele,label=left:$3$] (a3) at (0,2) {};

  \node[ele,,label=right:$1$] (b1) at (4,4) {};
  \node[ele,,label=right:$2$] (b2) at (4,3) {};
  \node[ele,,label=right:$3$] (b3) at (4,2) {};

  \node[draw,fit= (a1) (a2) (a3) ,minimum width=2cm] {} ;
  \node[draw,fit= (b1) (b2) (b3) ,minimum width=2cm] {} ;
  \draw[->,thick,shorten <=2pt,shorten >=2] (a1) -- (b3);
  \draw[->,thick,shorten <=2pt,shorten >=2] (a2) -- (b1);
  \draw[->,thick,shorten <=2pt,shorten >=2] (a3) -- (b2);
 \end{tikzpicture}
\end{figure}

\begin{figure}
\center
 \begin{tikzpicture}[ele/.style={fill=black,circle,minimum width=.8pt,inner sep=1pt},every fit/.style={ellipse,draw,inner sep=-2pt}]
  \node[ele,label=left:$1$] (a1) at (0,4) {};
  \node[ele,label=left:$2$] (a2) at (0,3) {};
  \node[ele,label=left:$3$] (a3) at (0,2) {};
  \node[ele,label=left:$4$] (a4) at (0,1) {};

  \node[ele,,label=right:$1$] (b1) at (4,4) {};
  \node[ele,,label=right:$2$] (b2) at (4,3) {};
  \node[ele,,label=right:$3$] (b3) at (4,2) {};
  \node[ele,,label=right:$4$] (b4) at (4,1) {};

  \node[draw,fit= (a1) (a2) (a3) (a4),minimum width=2cm] {} ;
  \node[draw,fit= (b1) (b2) (b3) (b4),minimum width=2cm] {} ;
 \end{tikzpicture}
\end{figure}

\begin{figure}
\center
 \begin{tikzpicture}[ele/.style={fill=black,circle,minimum width=.8pt,inner sep=1pt},every fit/.style={ellipse,draw,inner sep=-2pt}]
  \node[ele,label=left:$1$] (a1) at (0,4) {};
  \node[ele,label=left:$2$] (a2) at (0,3) {};
  \node[ele,label=left:$3$] (a3) at (0,2) {};
  \node[ele,label=left:$4$] (a4) at (0,1) {};

  \node[ele,,label=right:$1$] (b1) at (4,4) {};
  \node[ele,,label=right:$2$] (b2) at (4,3) {};
  \node[ele,,label=right:$3$] (b3) at (4,2) {};
  \node[ele,,label=right:$4$] (b4) at (4,1) {};

  \node[draw,fit= (a1) (a2) (a3) (a4),minimum width=2cm] {} ;
  \node[draw,fit= (b1) (b2) (b3) (b4),minimum width=2cm] {} ;
  \draw[->,thick,shorten <=2pt,shorten >=2pt] (a1) -- (b2);
 \end{tikzpicture}
\end{figure}

\begin{figure}
\center
 \begin{tikzpicture}[ele/.style={fill=black,circle,minimum width=.8pt,inner sep=1pt},every fit/.style={ellipse,draw,inner sep=-2pt}]
  \node[ele,label=left:$1$] (a1) at (0,4) {};
  \node[ele,label=left:$2$] (a2) at (0,3) {};
  \node[ele,label=left:$3$] (a3) at (0,2) {};

  \node[ele,,label=right:$1$] (b1) at (4,4) {};
  \node[ele,,label=right:$3$] (b2) at (4,3) {};
  \node[ele,,label=right:$4$] (b3) at (4,2) {};

  \node[draw,fit= (a1) (a2) (a3) ,minimum width=2cm] {} ;
  \node[draw,fit= (b1) (b2) (b3) ,minimum width=2cm] {} ;
  \draw[->,thick,shorten <=2pt,shorten >=2] (a1) -- (b2);
  \draw[->,thick,shorten <=2pt,shorten >=2] (a2) -- (b1);
  \draw[->,thick,shorten <=2pt,shorten >=2] (a3) -- (b3);
 \end{tikzpicture}
\end{figure}
\begin{figure}
\center
 \begin{tikzpicture}[ele/.style={fill=black,circle,minimum width=.8pt,inner sep=1pt},every fit/.style={ellipse,draw,inner sep=-2pt}]
  \node[ele,label=left:$1$] (a1) at (0,4) {};
  \node[ele,label=left:$2$] (a2) at (0,3) {};
  \node[ele,label=left:$3$] (a3) at (0,2) {};

  \node[ele,,label=right:$1$] (b1) at (4,4) {};
  \node[ele,,label=right:$3$] (b2) at (4,3) {};
  \node[ele,,label=right:$4$] (b3) at (4,2) {};

  \node[draw,fit= (a1) (a2) (a3) ,minimum width=2cm] {} ;
  \node[draw,fit= (b1) (b2) (b3) ,minimum width=2cm] {} ;
  \draw[->,thick,shorten <=2pt,shorten >=2] (a1) -- (b2);
  \draw[->,thick,shorten <=2pt,shorten >=2] (a2) -- (b3);
  \draw[->,thick,shorten <=2pt,shorten >=2] (a3) -- (b1);
 \end{tikzpicture}
\end{figure}

\begin{figure}
\center
 \begin{tikzpicture}[ele/.style={fill=black,circle,minimum width=.8pt,inner sep=1pt},every fit/.style={ellipse,draw,inner sep=-2pt}]
  \node[ele,label=left:$1$] (a1) at (0,4) {};
  \node[ele,label=left:$2$] (a2) at (0,3) {};
  \node[ele,label=left:$3$] (a3) at (0,2) {};

  \node[ele,,label=right:$1$] (b1) at (4,4) {};
  \node[ele,,label=right:$3$] (b2) at (4,3) {};
  \node[ele,,label=right:$4$] (b3) at (4,2) {};

  \node[draw,fit= (a1) (a2) (a3) ,minimum width=2cm] {} ;
  \node[draw,fit= (b1) (b2) (b3) ,minimum width=2cm] {} ;
  \draw[->,thick,shorten <=2pt,shorten >=2] (a1) -- (b3);
  \draw[->,thick,shorten <=2pt,shorten >=2] (a2) -- (b2);
  \draw[->,thick,shorten <=2pt,shorten >=2] (a3) -- (b1);
 \end{tikzpicture}
\end{figure}

\begin{figure}
\center
 \begin{tikzpicture}[ele/.style={fill=black,circle,minimum width=.8pt,inner sep=1pt},every fit/.style={ellipse,draw,inner sep=-2pt}]
  \node[ele,label=left:$1$] (a1) at (0,5) {};
  \node[ele,label=left:$2$] (a2) at (0,4) {};
  \node[ele,label=left:$3$] (a3) at (0,3) {};
  \node[ele,label=left:$4$] (a4) at (0,2) {};
  \node[ele,label=left:$5$] (a5) at (0,1) {};


  \node[ele,,label=right:$1$] (b1) at (4,5) {};
  \node[ele,,label=right:$2$] (b2) at (4,4) {};
  \node[ele,,label=right:$3$] (b3) at (4,3) {};
  \node[ele,,label=right:$4$] (b4) at (4,2) {};
  \node[ele,,label=right:$5$] (b5) at (4,1) {};


  \node[draw,fit= (a1) (a2) (a3) (a4)(a5),minimum width=2cm] {} ;
  \node[draw,fit= (b1) (b2) (b3) (b4)(b5),minimum width=2cm] {} ;
 \end{tikzpicture}
\end{figure}

\begin{figure}
\center
 \begin{tikzpicture}[ele/.style={fill=black,circle,minimum width=.8pt,inner sep=1pt},every fit/.style={ellipse,draw,inner sep=-2pt}]
  \node[ele,label=left:$1$] (a1) at (0,5) {};
  \node[ele,label=left:$2$] (a2) at (0,4) {};
  \node[ele,label=left:$3$] (a3) at (0,3) {};
  \node[ele,label=left:$4$] (a4) at (0,2) {};
  \node[ele,label=left:$5$] (a5) at (0,1) {};


  \node[ele,,label=right:$1$] (b1) at (4,5) {};
  \node[ele,,label=right:$2$] (b2) at (4,4) {};
  \node[ele,,label=right:$3$] (b3) at (4,3) {};
  \node[ele,,label=right:$4$] (b4) at (4,2) {};
  \node[ele,,label=right:$5$] (b5) at (4,1) {};


  \node[draw,fit= (a1) (a2) (a3) (a4)(a5),minimum width=2cm] {} ;
  \node[draw,fit= (b1) (b2) (b3) (b4)(b5),minimum width=2cm] {} ;
  \draw[->,thick,shorten <=2pt,shorten >=2] (a1) -- (b2);

 \end{tikzpicture}
\end{figure}

\begin{figure}
\center
 \begin{tikzpicture}[ele/.style={fill=black,circle,minimum width=.8pt,inner sep=1pt},every fit/.style={ellipse,draw,inner sep=-2pt}]
  \node[ele,label=left:$2$] (a1) at (0,4) {};
  \node[ele,label=left:$3$] (a2) at (0,3) {};
  \node[ele,label=left:$4$] (a3) at (0,2) {};
  \node[ele,label=left:$5$] (a4) at (0,1) {};

  \node[ele,,label=right:$1$] (b1) at (4,4) {};
  \node[ele,,label=right:$3$] (b2) at (4,3) {};
  \node[ele,,label=right:$4$] (b3) at (4,2) {};
  \node[ele,,label=right:$5$] (b4) at (4,1) {};

  \node[draw,fit= (a1) (a2) (a3) (a4),minimum width=2cm] {} ;
  \node[draw,fit= (b1) (b2) (b3) (b4),minimum width=2cm] {} ;
   \draw[->,thick,shorten <=2pt,shorten >=2] (a1) -- (b1);

 \end{tikzpicture}
\end{figure}

\begin{figure}
\center
 \begin{tikzpicture}[ele/.style={fill=black,circle,minimum width=.8pt,inner sep=1pt},every fit/.style={ellipse,draw,inner sep=-2pt}]
  \node[ele,label=left:$2$] (a1) at (0,4) {};
  \node[ele,label=left:$3$] (a2) at (0,3) {};
  \node[ele,label=left:$4$] (a3) at (0,2) {};
  \node[ele,label=left:$5$] (a4) at (0,1) {};

  \node[ele,,label=right:$1$] (b1) at (4,4) {};
  \node[ele,,label=right:$3$] (b2) at (4,3) {};
  \node[ele,,label=right:$4$] (b3) at (4,2) {};
  \node[ele,,label=right:$5$] (b4) at (4,1) {};

  \node[draw,fit= (a1) (a2) (a3) (a4),minimum width=2cm] {} ;
  \node[draw,fit= (b1) (b2) (b3) (b4),minimum width=2cm] {} ;
   \draw[->,thick,shorten <=2pt,shorten >=2] (a1) -- (b2);

 \end{tikzpicture}
\end{figure}




\end{document}