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]
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 demostrarlo 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]
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 10 = 3 en el rectángulo latino entonces b 30 = 1 en el cuadrado semilatino.
En estadística , los rectángulos latinos tienen aplicaciones en el diseño de experimentos . [ ¿Cómo? ]
