Rectángulo latino

En matemáticas combinatorias , un rectángulo latino es una matriz r  ×  n (donde r  ≤  n ), que utiliza n símbolos, normalmente los números 1, 2, 3, ...,  n o 0, 1, ..., n − 1 como sus entradas, sin que ningún número aparezca más de una vez en cualquier fila o columna. ^[1]

Un rectángulo latino de n  ×  n se denomina cuadrado latino . Los rectángulos latinos y los cuadrados latinos también pueden describirse como las coloraciones óptimas de los grafos de torre o como coloraciones óptimas de los bordes de grafos bipartitos completos . ^[2]

Un ejemplo de un rectángulo latino de 3 × 5 es: ^[3]

Un rectángulo latino se llama normalizado (o reducido ) si su primera fila está en orden natural y también lo está su primera columna. ^{[4] [5]}

El ejemplo anterior no está normalizado.

Sea L ( k, n ) el número de rectángulos latinos normalizados k × n . Entonces, el número total de rectángulos latinos k × n es ^[6]

${\displaystyle {\frac {n!(n-1)!L(k,n)}{(nk)!}}.}$

Un rectángulo latino de 2 × n corresponde a una permutación sin puntos fijos . Estas permutaciones se han denominado permutaciones discordantes . ^[4] Una enumeración de permutaciones discordantes con una permutación dada es el famoso problème des rencontres . La enumeración de permutaciones discordantes con dos permutaciones, una de las cuales es un simple desplazamiento cíclico de la otra, se conoce como problème des ménages reducido . ^[4]

El número de rectángulos latinos normalizados, L ( k , n ) , de tamaños pequeños viene dado por ^[6]

Cuando k = 1, es decir, solo hay una fila, dado que los rectángulos latinos están normalizados, no hay elección de lo que puede ser esta fila. La tabla también muestra que L ( n − 1, n ) = L ( n , n ) , lo que se deduce de que si solo falta una fila, la entrada faltante en cada columna se puede determinar a partir de la propiedad del cuadrado latino y el rectángulo se puede extender de forma única a un cuadrado latino.

La propiedad de poder extender un rectángulo latino al que le falta una fila a un cuadrado latino mencionada anteriormente se puede fortalecer significativamente. Es decir, si r  <  n , entonces es posible agregar n  −  r filas a un rectángulo latino r  ×  n para formar un cuadrado latino, utilizando el teorema del matrimonio de Hall . ^[7]

Un cuadrado semilatino es otro tipo de cuadrado latino incompleto. Un cuadrado semilatino es una matriz n × n , L , en la que algunas posiciones están desocupadas y otras están ocupadas por uno de los números enteros {0, 1, ..., n − 1 }, de modo que, si un número entero k aparece en L , entonces aparece n veces y no hay dos k que pertenezcan a la misma fila o columna. Si hay m números enteros diferentes en L , entonces L tiene índice m . ^[8]

Por ejemplo, un cuadrado semilatino de orden 5 e índice 3 es: ^[8]

Un cuadrado semilatino de orden n e índice m tendrá nm posiciones ocupadas. Surge la pregunta: ¿es posible completar un cuadrado semilatino para formar un cuadrado latino? Aunque parezca sorprendente, la respuesta es siempre.

Sea L un cuadrado semilatino de orden n e índice m , donde m < n . Entonces L puede completarse hasta un cuadrado latino. ^[8]

Una forma de demostrar esto es observar que un cuadrado semilatino de orden n e índice m es equivalente a un rectángulo latino m × n . Sea L = || a _ij || un rectángulo latino y S = || b _ij || un cuadrado semilatino, entonces la equivalencia está dada por ^[9]

${\displaystyle b_{ij}=k{\text{ si y sólo si }}a_{kj}=i.}$

Por ejemplo, el rectángulo latino 3×5

es equivalente a este cuadrado semilatino de orden 5 e índice 3: ^[9]

ya que, por ejemplo, un ₁₀ = 3 en el rectángulo latino entonces b ₃₀ = 1 en el cuadrado semilatino.

En estadística , los rectángulos latinos tienen aplicaciones en el diseño de experimentos . ^{[ ¿Cómo? ]}

• Diseño combinatorio
• Arcoiris a juego

• Brualdi, Richard A. (2010), Combinatoria introductoria (5.ª ed.), Prentice Hall, ISBN 978-0-13-602040-0
• Colbourn, Charles J.; Dinitz, Jeffrey H. (2007), Manual de diseños combinatorios (2.ª ed.), Boca Raton: Chapman & Hall/ CRC, ISBN 978-1-58488-506-1
• Dénes, J.; Keedwell, AD (1974), Cuadrados latinos y sus aplicaciones , Nueva York-Londres: Academic Press, p. 547, ISBN 0-12-209350-X, Sr.  0351850
• Stones, Douglas S. (2010), "Las múltiples fórmulas para el número de rectángulos latinos", Electronic Journal of Combinatorics , 17 (1): Artículo 1, 46, doi : 10.37236/487 , MR  2661404

• Mirsky, L. (1971), Teoría transversal: una descripción de algunos aspectos de las matemáticas combinatorias, Academic Press, ISBN 0-12-498550-5, OCLC  816921720
• Riordan, John (2002) [1958], Introducción al análisis combinatorio , Dover, ISBN 978-0-486-42536-8

• Weisstein, Eric W., "Rectángulo latino", mathworld.wolfram.com , consultado el 12 de julio de 2020