Rectángulo latino - Latin rectangle
En matemática combinatoria , un rectángulo América es un r × n matriz (donde r ≤ n ), usando n símbolos, por lo general 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.
Un rectángulo latino de n × n se llama cuadrado latino .
Un ejemplo de un rectángulo latino de 3 × 5 es:
0 1 2 3 4 3 4 0 1 2 4 0 3 2 1
Normalización
Un rectángulo latino se llama normalizado (o reducido ) si su primera fila está en orden natural y también su primera columna.
El ejemplo anterior no está normalizado.
Enumeración
Sea L ( k, n ) el número de k × n rectángulos latinos normalizados . Entonces el número total de k × n rectángulos latinos es
Un rectángulo latino de 2 × n corresponde a una permutación sin puntos fijos . Estas permutaciones se han denominado permutaciones discordantes . 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 .
El número de rectángulos latinos normalizados, L ( k , n ) , de tamaños pequeños viene dado por
k \ n 1 2 3 4 5 6 7 8 1 1 1 1 1 1 1 1 1 2 1 1 3 11 53 309 2119 3 1 4 46 1064 35792 1673792 4 4 56 6552 1293216 420909504 5 56 9408 11270400 27206658048 6 9408 16942080 335390189568 7 16942080 535281401856 8 535281401856
Cuando k = 1, es decir, solo hay una fila, ya que los rectángulos latinos están normalizados, no hay opción para lo que puede ser esta fila. La tabla también muestra que L ( n - 1, n ) = L ( n , n ) , lo que sigue, ya que si solo falta una fila, la entrada que falta en cada columna se puede determinar a partir de la propiedad del cuadrado latino y el rectángulo se puede determinar únicamente extendido a una plaza latina.
Extensibilidad
La propiedad de poder extender un rectángulo latino al que le falta una fila a un cuadrado latino mencionado 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, usando el teorema del matrimonio de Hall .
Cuadrados semilatinos
Un cuadrado semilatino es otro tipo de cuadrado latino incompleto. Un cuadrado semilatino es una matriz de n × n , L , en la que algunas posiciones están desocupadas y otras posiciones están ocupadas por uno de los enteros {0, 1, ..., n - 1 }, de modo que, si es un entero k ocurre en L , luego ocurre n veces y no hay dos k que pertenezcan a la misma fila o columna. Si m números enteros diferentes ocurren en L , entonces L tiene índice m .
Por ejemplo, un cuadrado semilatino de orden 5 e índice 3 es:
1 0 2 2 1 0 0 1 2 2 0 1 2 0 1
Un cuadrado semilatino de orden n e índice m tendrá nm posiciones llenas. Surge la pregunta, ¿se puede completar un cuadrado semilatino en un cuadrado latino? Sorprendentemente, la respuesta es siempre.
Sea L un cuadrado semilatino de orden n e índice m , donde m <n . Entonces L se puede completar en un cuadrado latino.
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 || ser un rectángulo latino y S = || b ij || ser un cuadrado semilatino, entonces la equivalencia viene dada por
Por ejemplo, el rectángulo latino de 3 × 5
0 1 2 3 4 3 4 1 0 2 1 0 4 2 3
es equivalente a este cuadrado semilatino de orden 5 e índice 3:
0 2 1 2 0 1 0 2 1 1 0 2 1 2 0
ya que, por ejemplo, a 10 = 3 en el rectángulo latino entonces b 30 = 1 en el cuadrado semilatino.
Aplicaciones
En estadística , los rectángulos latinos tienen aplicaciones en el diseño de experimentos .
Ver también
Notas
Referencias
- Brualdi, Richard A. (2010), Introducción a la combinatoria (5.a ed.), Prentice Hall, ISBN 978-0-13-602040-0
- Colbourn, Charles J .; Dinitz, Jeffrey H. (2007), Manual de diseños combinatorios (2a 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 , MR 0351850
Otras lecturas
- 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
enlaces externos
- Weisstein, Eric W., "Latin Rectangle" , mathworld.wolfram.com , consultado el 12 de julio de 2020