Permutación parcial

En matemáticas combinatorias , una permutación parcial , o secuencia sin repetición , en un conjunto finito S es una biyección entre dos subconjuntos específicos de S. Es decir, se define mediante dos subconjuntos U y V de igual tamaño y una función biyectiva de U a V. De forma equivalente, es una función parcial en S que puede extenderse a una permutación . ^{[ 1 ] [ 2 ]}

Es común considerar el caso en que el conjunto S es simplemente el conjunto {1, 2, ..., n } de los primeros n enteros positivos. 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 n.${\displaystyle n}$y los restantes de los cuales 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 dichas 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

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

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 el OEIS )

donde el n -ésimo elemento de la secuencia viene dado por la fórmula de sumatoria

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

en la 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 que no son agujeros. 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 en las que se omiten los elementos finales de cada conjunto:
2. ${\displaystyle P(n-1)}$permutaciones parciales donde los elementos finales de cada conjunto se corresponden entre sí.
3. ${\displaystyle (n-1)P(n-1)}$permutaciones parciales donde se incluye el último elemento del primer conjunto, pero no se corresponde con el último elemento del segundo conjunto.
4. ${\displaystyle (n-1)P(n-1)}$permutaciones parciales donde se incluye el último elemento del segundo conjunto, pero no se corresponde con el último elemento del primer conjunto.
5. ${\displaystyle -(n-1)^{2}P(n-2)}$, las permutaciones parciales incluidas en los recuentos 3 y 4, aquellas permutaciones en las que se incluyen los elementos finales de ambos conjuntos, pero no se corresponden entre sí.

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 permutan, para algún k . En el primer caso, una permutación parcial de longitud k de un conjunto de n elementos es simplemente una secuencia de k términos del conjunto de n elementos sin repetición. (En combinatoria elemental, a estos objetos a veces se les llama, de forma confusa, " k- permutaciones " del conjunto de n elementos).