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. [1]
Un rectángulo latino n × n se llama cuadrado latino .
Un ejemplo de un rectángulo latino de 3 × 5 es: [2]
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. [3] [4]
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 [5]
Un rectángulo latino de 2 × n corresponde a una permutación sin puntos fijos . Estas permutaciones se han denominado permutaciones discordantes . [3] 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 cambio cíclico de la otra, se conoce como problème des ménages reducido . [3]
El número de rectángulos latinos normalizados, L ( k , n ) , de tamaños pequeños viene dado por [5]
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, dado que los rectángulos latinos están normalizados, no hay elecció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 extendido de forma única 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 . [6]
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 . [7]
Por ejemplo, un cuadrado semilatino de orden 5 e índice 3 es: [7]
1 0 2 2 1 0 0 1 2 2 0 1 2 0 1
Un cuadrado semilatino de orden ny í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
Una forma de probar 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 [8]
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: [8]
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
- ^ Colbourn y Dinitz 2007 , p. 141
- ^ Brualdi 2010 , p. 385
- ↑ a b c Denes y Keedwell , 1974 , p. 150
- ^ Algunos autores, en particular J. Riordan, no requieren que la primera columna esté en orden y esto afectará la validez de algunas fórmulas que se mencionan a continuación.
- ↑ a b Colbourn y Dinitz , 2007 , p. 142
- ^ Brualdi 2010 , p. 386
- ↑ a b c Brualdi , 2010 , p. 387
- ↑ a b Brualdi , 2010 , p. 388
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