En matemática combinatoria , una permutación parcial , o secuencia sin repetición , en un conjunto finito S es una biyección entre dos especificados subconjuntos de S . Es decir, que se define por dos subconjuntos U y V de igual tamaño, y un mapeo uno a uno de U a V . De manera equivalente, es una función parcial en 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 enteros. En este caso, una permutación parcial puede estar representada por una cadena de n símbolos, algunos de los cuales son números distintos en el rango de 1 ay 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 cuerda 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í misma y asigna 3 a 2. [3] Las siete permutaciones parciales en dos elementos son
- ◊◊, ◊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 n- ésimo elemento de la secuencia viene dado por la fórmula de suma
en el que el i- ésimo término 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 agujeros. Alternativamente, se puede calcular mediante una relación de recurrencia
Esto se determina de la siguiente manera:
- permutaciones parciales donde se omiten los elementos finales de cada conjunto:
- permutaciones parciales donde los elementos finales de cada conjunto se mapean entre sí.
- permutaciones parciales donde se incluye el elemento final del primer conjunto, pero no se asigna al elemento final del segundo conjunto
- permutaciones parciales donde se incluye el elemento final del segundo conjunto, pero no se asigna al elemento final del primer conjunto
- , las permutaciones parciales incluidas en los 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 ve obligado a constar de los primeros k elementos del conjunto de n elementos que se permuta, para algunos k . En el primer caso, una permutación parcial de la longitud k de un n -set es solo una secuencia de k términos del n -set sin repetición. (En combinatoria elemental, estos objetos a veces se denominan confusamente " k -permutaciones " del conjunto n ).
Referencias
- ^ 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.
- ^ Ku, CY; Líder, I. (2006), "Un teorema de Erdős-Ko-Rado para permutaciones parciales", Matemáticas discretas , 306 (1): 74-86, doi : 10.1016 / j.disc.2005.11.007 , MR 2202076.
- ^ a b 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): Documento 25, 41, MR 2770130.
- ^ Burstein, Alexander; Lankham, Isaiah (2010), "Clasificación de paciencia restringida y evitación de patrones prohibidos", Patrones de permutación , London Math. Soc. Lecture Note Ser., 376 , Cambridge: Cambridge Univ. Prensa, págs. 233-257, arXiv : math / 0512122 , doi : 10.1017 / CBO9780511902499.013 , MR 2732833.