Permutación

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 13 de noviembre de 2021; las comprobaciones requieren 6 ediciones .

Una permutación en combinatoria es un conjunto ordenado sin repeticiones de números , generalmente tratado como una biyección en el conjunto , que asocia el número con el -ésimo elemento del conjunto. El número se llama la longitud de la permutación [1] . ${\ estilo de visualización 1, \ 2, \ \ ldots, \ n,}$ ${\displaystyle \{1,\;2,\;\ldots,\;n\))$ $i$ $i$ $norte$

En teoría de grupos , una permutación de un conjunto arbitrario significa una biyección de este conjunto sobre sí mismo. Como sinónimo de la palabra "permutación" en este sentido, algunos autores utilizan la palabra sustitución . (Otros autores llaman sustitución a una forma visual de escribir una permutación. La diferencia más significativa es que una sustitución es una función en sí misma, mientras que una permutación es el resultado de aplicar esa función a los elementos de una secuencia).

El término "permutación" surgió porque al principio se tomaban objetos, se arreglaban de alguna manera, y otras formas de ordenar requerían reorganizar estos objetos. [2] .

Una permutación es un conjunto que consiste en el mismo número de elementos, que difieren solo en el orden de los elementos. [3]

Propiedades

El número de todas las permutaciones de elementos es igual al número de ubicaciones de by , es decir, el factorial [4] [5] [6] [7] : $norte$ $norte$ $norte$

P_{n}=A_{n}^{n}={\frac {n!}{(nn)!}}={\frac {n!}{0!}}=n!=1\ cdot 2\cdot \ldots \cdot n

La composición define la operación de producto sobre permutaciones de la misma longitud: Con respecto a esta operación, el conjunto de permutaciones de elementos forma un grupo , que se llama simétrico y se suele denotar . $(\pi \cdot \sigma)(k)=\pi (\sigma (k)).$ $norte$ $S_{n}$

Cualquier grupo finito de elementos es isomorfo a algún subgrupo del grupo simétrico ( teorema de Cayley ). En este caso, cada elemento está asociado a una permutación definida sobre los elementos por la identidad donde es una operación de grupo en . $norte$ $S_{n}$ $a \ en G$ $\pi _{a}$ $GRAMO$ $\pi _{a}(g)=a\circ g,$ $\circ$ $GRAMO$

Definiciones relacionadas

El portador de una permutación es un subconjunto del conjuntodefinido como $\pi \colon X\to X$ $X$ $\operatorname {suplemento} (\pi ):=\{x\in X\mid \pi (x)\neq x\}.$

Un punto fijo de una permutaciónes cualquier punto fijo de la aplicación, es decir, un elemento del conjuntoEl conjunto de todos los puntos fijos de una permutaciónes el complemento de su portador en. $\Pi$ $\pi \colon X\to X$ $\{x\in X\mid \pi (x)=x\}.$ $\Pi$ $X$

Una inversión en una permutaciónes cualquier par de índicestales quey. La paridad del número de inversiones en una permutación determina la paridad de la permutación . $\Pi$ ${\ estilo de visualización i, \ j}$ $1\leqslant i<j\leqslant n$ $\pi (i)>\pi (j)$

Tipos especiales de permutaciones

Una permutación idéntica es una permutaciónque cada elemento se asigna a sí mismo: $mi,$ $x\en X$ $e(x)=x.$
Una involución es una permutaciónque es la inversa de sí misma, es decir $\tau ,$ $\tau \cdot \tau =e.$
El desorden es una permutación sin puntos fijos .
Un ciclo de longitudes tal sustituciónque es idéntica en todo el conjuntoexcepto en el subconjuntoydenota. $\ana$ $\Pi ,$ $X,$ $\{x_{1},\;x_{2},\;\ldots,\;x_{\ell }\}\subconjunto X$ $\pi (x_{\ell })=x_{1},\ \pi (x_{i})=x_{i+1}.$ $(x_{1},\;x_{2},\;\ldots,\;x_{\ell }).$
Una transposición es una permutación de los elementos de un conjuntoque intercambia dos elementos. La transposición es un ciclo de longitud 2. $X$

Sustitución

Una permutación de un conjunto se puede escribir como una sustitución , por ejemplo: $\Pi$ $X$

{\begin{pmatrix}x_{1}&x_{2}&x_{3}&\ldots &x_{n}\\y_{1}&y_{2}&y_{3}&\ldots &y_{n}\ fin{pmatrix}},

donde y . $\{x_{1},\;\ldots,\;x_{n}\}=\{y_{1},\;\ldots,\;y_{n}\}=X$ ${\ estilo de visualización \ pi (x_ {i}) = y_ {i}}$

Los productos del ciclo y el signo de permutación

Cualquier permutación puede descomponerse en un producto ( composición ) de ciclos disjuntos de longitud , y de forma única hasta el orden de los ciclos en el producto. Por ejemplo: $\Pi$ ${\ estilo de visualización \ ell \ geqslant 2}$

{\begin{pmatrix}1&2&3&4&5&6\\5&1&6&4&2&3\end{pmatrix}}=(1,\;5,\;2)(3,\;6).

También se suele suponer que los puntos fijos de una permutación son ciclos independientes de longitud 1 y complementan con ellos la expansión del ciclo de la permutación. Para el ejemplo anterior, tal descomposición aumentada sería . El número de ciclos de diferentes longitudes, a saber, el conjunto de números , donde es el número de ciclos de longitud , determina la estructura cíclica de la permutación. En este caso, el valor es igual a la longitud de la permutación y el valor es igual al número total de ciclos. El número de permutaciones de elementos con ciclos viene dado por el número de Stirling sin signo de primera clase . ${\ estilo de visualización (1, \; 5, \; 2) (3, \; 6) (4)}$ $(c_{1},\;c_{2},\;\ldots)$ ${\displaystyle c_{\ell ))$ $\ana$ $1\cdot c_{1}+2\cdot c_{2}+\ldots$ $c_{1}+c_{2}+\ldots$ $norte$ $k$ ${\begin{bmatriz}n\\k\end{bmatriz))$

Cualquier ciclo se puede descomponer en un producto de transposiciones (no necesariamente disjuntas) . En este caso, un ciclo de longitud 1 (que es esencialmente una permutación idéntica ) se puede representar como un producto vacío de transposiciones o, por ejemplo, como un cuadrado de cualquier transposición: un ciclo de longitud se puede descomponer en un producto de transposiciones como sigue: $mi$ ${\ estilo de visualización (1, \; 2) (1, \; 2) = (2, \; 3) (2, \; 3) = e.}$ ${\ estilo de visualización \ ell \ geqslant 2}$ ${\ estilo de visualización \ ell -1}$

(x_{1},\;\ldots,\;x_{l})=(x_{1},\;x_{\ell })(x_{1},\;x_{\ell -1 })\puntos (x_{1},\;x_{2}).

Cabe señalar que la descomposición de ciclos en un producto de transposiciones no es única:

(1,\;2,\;3)=(1,\;3)(1,\;2)=(2,\;3)(1,\;3)=(1,\; 3)(2,\;4)(2,\;4)(1,\;2).

Así, cualquier permutación se puede descomponer en un producto de transposiciones. Aunque esto se puede hacer de muchas maneras, la paridad del número de transposiciones es la misma en todas esas descomposiciones. Esto permite definir el signo de una permutación ( paridad de permutación o firma de permutación ) como: $\Pi$

{\ estilo de visualización \ varepsilon _ {\ pi} = (-1) ^ {t},}

donde es el número de transposiciones en alguna expansión de . En este caso, llaman a una permutación par si y a una permutación impar si . $t$ $\Pi$ $\Pi$ ${\ estilo de visualización \ varepsilon _ {\ pi} = 1}$ ${\ estilo de visualización \ varepsilon _ {\ pi} = -1}$

De manera equivalente, el signo de una permutación está determinado por su estructura de ciclo: el signo de una permutación de elementos, que consta de ciclos, es igual a $\Pi$ $norte$ $k$

{\ estilo de visualización \ varepsilon _ {\ pi} = (-1) ^ {nk}}

El signo de la permutación también se puede determinar en términos del número de inversiones en : $\Pi$ $N(\pi)$ $\Pi$

{\ estilo de visualización \ varepsilon _ {\ pi} = (-1) ^ {N (\ pi)})

Permutaciones con repetición

Considere elementos de diferentes tipos, y en cada tipo todos los elementos son iguales. Entonces las permutaciones de todos estos elementos, hasta el orden del mismo tipo de elementos, se llaman permutaciones con repetición . Si es el número de elementos del tipo th, entonces el número de permutaciones posibles con repeticiones es igual al coeficiente multinomial $norte$ $metro$ $k_i$ $i$ $k_{1}+k_{2}+\ldots +k_{m}=n$ $\textstyle {\binom {n}{k_{1},\;k_{2},\;\ldots,\;k_{m))}={\frac {n!}{k_{1} !k_{2}!\ldots k_{m}!}}.$

Una permutación con repeticiones también se puede considerar como una permutación multiconjunto de cardinalidad . $\{1^{k_{1}},\;2^{k_{2}},\;\ldots,\;m^{k_{m}}\}$ $k_{1}+k_{2}+\ldots +k_{m}=n$

Permutación aleatoria

Una permutación aleatoria es un vector aleatorio, cuyos elementos toman valores naturales de 1 a y la probabilidad de que dos elementos coincidan es 0. ${\ estilo de visualización \ xi = (\ xi _ {1}, \; \ ldots, \; \ xi _ {n}),}$ $norte,$

Una permutación aleatoria independiente es una permutación aleatoria de este tipo , para la cual: $\xi$

P\{\xi =\sigma \}={\frac {p_{{1\sigma (1)}}\ldots p_{{n\sigma (n)))}{\sum \limits_{{\pi \in S_{n}}}p_{{1\pi (1)}}\ldots p_{{n\pi (n)}}}}

para algunos tales que: $p_{{ij}},$

\forall i\ (1\leqslant i\leqslant n)\colon p_{i1}+\ldots +p_{in}=1

\sum \limits _{{\pi \in S_{n}}}p_{{1\pi (1)))\ldots p_{{n\pi (n))))>0.

Si al mismo tiempo no dependen de , entonces la permutación se llama igualmente distribuida . Si no hay dependencia de , es decir, se llama homogéneo . $p_{{ij}}$ $i$ $\xi$ $j$ $\forall i,\;j\ (1\leqslant i,\;j\leqslant n)\colon p_{ij}=1/n,$ $\xi$

Véase también

Notas

↑ Evgeny Vechtomov, Dmitry Shirokov. Matemáticas: Lógica, Conjuntos, Combinatoria . Libro de texto para bachillerato académico. - 2ª ed. - Litros, 2018-03-02. - S. 145-146. — 244 págs. Archivado el 7 de abril de 2022 en Wayback Machine .
↑ Libro de texto de matemáticas para SPO / M. I. Bashmakov, grados 10-11. - página 67
↑ Teoría de la probabilidad y elementos de las estadísticas matemáticas . Archivado el 1 de febrero de 2022 en Wayback Machine .
↑ Vilenkin N. Ya. Capítulo III. Combinatoria de tuplas y conjuntos. Asignaciones con repeticiones // Combinatoria popular . - M. : Nauka, 1975. - S. 80. - 208 p.
↑ Teoría de la configuración y Teoría de la enumeración . Fecha de acceso: 30 de diciembre de 2009. Archivado desde el original el 23 de enero de 2010. (indefinido)
↑ Capítulo 3. Elementos de combinatoria Archivado el 4 de enero de 2010 en Wayback Machine . // Conferencias sobre la teoría de la probabilidad.
↑ Donald E. Knuth - El arte de la programación. Volumen 1. Algoritmos básicos. 1.2.5. Permutaciones y factoriales

Literatura

Donald Knuth . El arte de la programación informática, volumen 3. Clasificación y búsqueda = El arte de la programación informática, vol.3. Clasificación y búsqueda. - 2ª ed. - M. : "Williams" , 2007. - S. 824. - ISBN 0-201-89685-0 .
Kostrikin A.I. Introducción al álgebra. Fundamentos de Álgebra . - M .: Fizmatlit , 1994. - S. 59 -71. — 320 s. — ISBN 5-02-014644-7 .
Serguéi Mélnikov. Permutaciones, combinaciones, ubicaciones: derivación de todas las permutaciones // Delphi y Turbo Pascal con ejemplos entretenidos. - BHV-Petersburgo, 2012. - 448 p. - ISBN 978-5-94157-886-3 .

Enlaces

Arangeman // Diccionario enciclopédico de Brockhaus y Efron : en 86 volúmenes (82 volúmenes y 4 adicionales). - San Petersburgo. , 1890-1907.