¿Cuál es el número de latina rectángulos, dado el número de la reducción de la latina rectángulos?

Question

A mi director de tesis doctoral se llama el siguiente resultado algo a lo largo de las líneas: "El teorema en la teoría de los cuadrados latinos con la más incorrecta de las pruebas" (entonces, para mi vergüenza, se procedió a señalar un error en mi "prueba" en el momento). Lo voy a plantear demostrando que es un problema.

Definición: Un $k \times n$ *latina rectángulo* es $k \times n$ matriz con los símbolos de $\{1,2,\ldots,n\}$ para que cada símbolo se produce exactamente una vez en cada fila y en la mayoría de los una vez en cada columna. Por ejemplo:

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

es una $3 \times 4$ latina rectángulo.

Definición: Una latina rectángulo se llama reducido si la primera fila es $(1,2,\ldots,n)$ y la primera columna es $(1,2,\ldots,k)^T$.

El de arriba latina rectángulo no se reduce, pero esta es:

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

Deje $L_{k,n}$ el número de $k \times n$ latina rectángulos. Deje $R_{k,n}$ ser el número de la reducción de la $k \times n$ latina rectángulos.

Teorema: Para todos los $1 \leq k \leq n$, \[L_{k,n}=\frac{n!(n-1)!}{(n-k)!}R_{k,n}.\]

Problema: Demostrar que (y comprobar la prueba).

Answer 1

Considere el siguiente algoritmo de reducción:

1. Mover la única columna en la que se $1$ es el primer elemento a la izquierda (se extrae y se coloca como la primera columna).
2. Aplicar la única inyección que los mapas de la $j$th elemento en la primera columna de a $j$.
3. Aplicar la única permutación en el $n-1$ columnas a la derecha de la primera columna de la primera fila $1\ldots n$.

Tomando nuestros pasos a la inversa para descifrar una forma reducida, tenemos $(n-1)!$ opciones en el tercer paso, $(n-1)^{\underline{k-1}} = (n-1)!/(n-k)!$ opciones en el segundo paso, y $n$ opciones en el primer paso, para un total de $$(n-1)!\frac{(n-1)!}{(n-k)!}n = \frac{n!(n-1)!}{(n-k)!}.$$

Más formalmente, podemos definir

• $A_{k,n}$ como el número de latina rectángulos cuya parte superior izquierda de valor es $1$.
• $B_{k,n}$ como el número de latina rectángulos cuyas más a la izquierda de la columna se reduce.

A continuación, mostramos el siguiente: $$\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

Así que me voy a dar la prueba de lo que estoy acostumbrado. Se basa en lo que (me han llevado a creer) Brendan McKay se acuñó el "principio de conexión": Supongamos que usted tiene un bipartito multi-gráfico, con piezas de $A$ e $B$. Supongamos que cada vértice $A$ tiene el grado $c$ y cada vértice $B$ tiene el grado $d$. A continuación,$Ac=Bd$.

Decimos que una latina rectángulo está normalizada si la primera fila es $(1,2,\ldots,n)$. Deje $K_{k,n}$ el número de $k \times n$ normalizado latina rectángulos. Por permuting las columnas de a $k \times n$ latina rectángulo, generamos $n!$ distintos latina rectángulos de que exactamente uno se normaliza. Por lo tanto $L_{k,n}=n! K_{k,n}$.

Ahora vamos a probar la identidad de $K_{k,n}=\frac{(n-1)!}{(n-k)!} R_{k,n}$.

Tomamos el conjunto de todos los normalizado, $k \times n$ latina rectángulos y tomar B el conjunto de todos los reducidos $k \times n$ latina rectángulos. [En realidad, B es un subconjunto de A, así que esto es estrictamente hablando un poco sospechoso, pero esto se puede superar este problema mediante el etiquetado (no voy a hacer esto aquí, ya que es un poco sucio).]

Deje $G$ el grupo de permutaciones de $\{1,2,\ldots,n\}$ que fija 1. Dado cualquier reducido latina rectángulo $L \in B$ e $\alpha \in G$ podemos construir una normalizado latina rectángulo: a partir de $L$, permutar las columnas por $\alpha$, luego permutar los símbolos por $\alpha$. Llamar a este cuadrado latino $L_\alpha$.

Construimos el bipartito multigraph por: por cada $L \in B$ agregar un borde de $L$ a $L_\alpha$ para todos los $\alpha \in G$. Desde $L_\alpha$ podría igualdad de $L_\beta$, el gráfico puede no ser sencillo.

Cada vértice $B$ tiene el grado $(n-1)!$. Por lo que es suficiente para mostrar que cada vértice $A$ tiene el grado $(n-k)!$. Hay una arista entre el $L=(l_{ij}) \in A$ y algunos vértice en $B$ para cada permutación $\alpha \in G$ satisfacción $\alpha(i)=l_{i1}$ para todos los $1 \leq i \leq k$. Hay $(n-k)!$ tales permutaciones, y por lo tanto cada vértice $A$ tiene el grado $(n-k)!$.