Permutación parcial

Selección en un orden particular

En matemáticas combinatorias , una permutación parcial , o secuencia sin repetición , sobre un conjunto finito S es una biyección entre dos subconjuntos especificados de S. Es decir, está definida por dos subconjuntos U y V de igual tamaño, y una función biunívoca de U a V. De manera equivalente, es una función parcial sobre S que puede extenderse a una permutación . ^{[1] [2]}

Representación

Es común considerar el caso en el que el conjunto S es simplemente el conjunto {1, 2, ..., n } de los primeros n números enteros. En este caso, una permutación parcial puede representarse mediante una cadena de n símbolos, algunos de los cuales son números distintos en el rango de 1 a y los restantes son un símbolo especial de "agujero" ◊. En esta formulación, el dominio U de la permutación parcial consiste en las posiciones en la cadena que no contienen un agujero, y cada una de esas posiciones se asigna al número en esa posición. Por ejemplo, la cadena "1 ◊ 2" representaría la permutación parcial que asigna 1 a sí mismo y asigna 3 a 2. ^[3] Las siete permutaciones parciales en dos elementos son ${\displaystyle n}$

◊◊, ◊1, ◊2, 1◊, 2◊, 12, 21.

Enumeración combinatoria

El número de permutaciones parciales en n elementos, para n = 0, 1, 2, ..., viene dado por la secuencia entera

1, 2, 7, 34, 209, 1546, 13327, 130922, 1441729, 17572114, 234662231, ... (secuencia A002720 en la OEIS )

donde el elemento n- ésimo de la secuencia se da mediante la fórmula de suma

${\displaystyle \sum _{i=0}^{n}i!{\binom {n}{i}}^{2}}$

en el que el término i cuenta el número de permutaciones parciales con soporte de tamaño i , es decir, el número de permutaciones parciales con i entradas sin huecos. Alternativamente, se puede calcular mediante una relación de recurrencia

${\displaystyle P(n)=2nP(n-1)-(n-1)^{2}P(n-2).}$

Esto se determina de la siguiente manera:

1. ${\displaystyle P(n-1)}$permutaciones parciales donde se omiten los elementos finales de cada conjunto:
2. ${\displaystyle P(n-1)}$permutaciones parciales donde los elementos finales de cada conjunto se asignan entre sí.
3. ${\displaystyle (n-1)P(n-1)}$permutaciones parciales donde se incluye el elemento final del primer conjunto, pero no se asigna al elemento final del segundo conjunto
4. ${\displaystyle (n-1)P(n-1)}$permutaciones parciales donde se incluye el elemento final del segundo conjunto, pero no se asigna al elemento final del primer conjunto
5. ${\displaystyle -(n-1)^{2}P(n-2)}$, las permutaciones parciales incluidas en ambos conteos 3 y 4, aquellas permutaciones donde los elementos finales de ambos conjuntos están incluidos, pero no se asignan entre sí.

Permutaciones parciales restringidas

Algunos autores restringen las permutaciones parciales de modo que el dominio ^[4] o el rango ^[3] de la biyección se vean obligados a consistir en los primeros k elementos del conjunto de n elementos que se están permutando, para algún k . En el primer caso, una permutación parcial de longitud k de un conjunto n es simplemente una secuencia de k términos del conjunto n sin repetición. (En la combinatoria elemental, estos objetos a veces se denominan, de manera confusa, " k -permutaciones " del conjunto n ).

Referencias

1. Straubing, Howard (1983), "Una prueba combinatoria del teorema de Cayley-Hamilton", Matemáticas discretas , 43 (2–3): 273–279, doi : 10.1016/0012-365X(83)90164-4 , MR  0685635.
2. Ku, CY; Leader, I. (2006), "Un teorema de Erdős-Ko-Rado para permutaciones parciales", Discrete Mathematics , 306 (1): 74–86, doi : 10.1016/j.disc.2005.11.007 , MR  2202076.
3. Claesson, Anders; Jelínek, Vít; Jelínková, Eva; Kitaev, Sergey (2011), "Evitación de patrones en permutaciones parciales", Electronic Journal of Combinatorics , 18 (1): Artículo 25, 41, MR  2770130.
4. Burstein, Alexander; Lankham, Isaiah (2010), "Clasificación de paciencia restringida y evitación de patrones bloqueados", Patrones de permutación , London Math. Soc. Lecture Note Ser., vol. 376, Cambridge: Cambridge Univ. Press, págs. 233–257, arXiv : math/0512122 , doi :10.1017/CBO9780511902499.013, MR  2732833.