stringtranslate.com

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]

Normalización

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.

Enumeración

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.

Extensibilidad

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]

Cuadrados semilatinos

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.

Aplicaciones

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

Véase también

Notas

  1. ^ Colbourn y Dinitz 2007, pág. 141.
  2. ^ Piedras 2010.
  3. ^ Braldi 2010, pág. 385
  4. ^ abc Dénes y Keedwell 1974, pag. 150
  5. ^ Algunos autores, especialmente J. Riordan, no requieren que la primera columna esté en orden y esto afectará la validez de algunas fórmulas mencionadas a continuación.
  6. ^ ab Colbourn y Dinitz 2007, pág. 142
  7. ^ Brualdi 2010, pág. 386
  8. ^ abc Brualdi 2010, pág. 387
  9. ^Ab Brualdi 2010, pág. 388

Referencias

Lectura adicional

Enlaces externos