Prueba: para cualquier entero$n$ con$n \ge 1$, el número de permutaciones de un conjunto con$n$ elementos es$n!$.

Question

Estoy tratando de usar la inducción matemática para demostrar el siguiente teorema:

Para cualquier entero $n$ con $n \ge 1$, el número de permutaciones de un conjunto con $n$ elementos es $n!$.

---

Prueba

Deje $P(n)$ ser la declaración anterior.

Tome el conjunto de elementos $\{ x_1, x_2, \dots, x_n \mid n \ge 1 \}$.

$P(1)$ sostiene debido a que el número de permutaciones de $1$ elemento es el tamaño de la $1$ e $1! = 1$.

Supongamos ahora que $P(n)$ es cierto para algunos $n = m \ge 1$.

$P(m + 1)$ significa que tenemos el conjunto de $\{ x_1, x_2, \dots, x_{m + 1} \}.$

No estoy seguro de cómo proceder a partir de aquí. Yo estaba pensando en usar la regla de la multiplicación, de alguna manera, pero he sido incapaz de progresar en este sentido.

También he sido capaz de encontrar ninguna de las pruebas de este teorema en línea.

Les agradecería mucho si la gente podría por favor ayudarme a probar esto.

---

EDITAR (Completado la Prueba):

Deje $P(n)$ ser la declaración anterior.

Tome el conjunto $X = \{ x_1, x_2, \dots, x_n \mid n \ge 1 \}$.

$P(1)$ sostiene debido a que el número de permutaciones de $1$ elemento es el tamaño de la $1$ e $1! = 1$.

Supongamos ahora que $P(n)$ es cierto para algunos $n = m \ge 1$.

Y supongamos que tenemos los conjuntos de $X = \{ x_1, x_2, \dots, x_m \}$ e $X' = \{ x_{m + 1} \}$.

Dejar de tarea $T$ representan las tareas de $T_1, T_2, \dots, T_m$, donde la tarea $T_k, k = 1, 2, \dots, m$, representa la tarea donde la $k$th elemento del conjunto $X$ es fijo y cada permutación del conjunto resultante de configuración se calcula.

Cada vez que arreglar uno de los elementos y encontrar todas las permutaciones del conjunto resultante, que deja una configuración de conjunto de que el siguiente juego no puede tener, ya que sería idéntico a una de las permutaciones de la configuración anterior. Esto es lo que se supone que para ser verdadero para un conjunto con $m$ elementos.

Dejar de tarea $T_{m + 1}$ ser la tarea donde se toma el conjunto de $X^* = X \cup X'$, fijar el elemento $x_{m + 1}$, y calcular todas las permutaciones del conjunto resultante de configuración. Desde allí se $m + 1$ elementos del conjunto $X^*$hay $m + 1$ maneras de solucionar $x_{m + 1}$ ($m + 1$ conjunto de configuraciones) y calcular todas las permutaciones. Por lo tanto, de acuerdo a la regla de la multiplicación, hay $(m!)(m + 1) = (m + 1)!$ formas de realizar las tareas de $T$ e $T_{m + 1}$. $$\tag*{$\blacksquare$}$$

---

Les agradecería mucho si la gente podría, por favor revise la prueba y proporcionar retroalimentación en cuanto a su exactitud.

Answer 1

La prueba de que parece correcto, pero (en mi opinión) es demasiado elaborado. Se oscurece la combinatoria simplicidad del argumento. Yo podría escribir lo siguiente:

Claramente, sólo hay uno (que es, $1!$) permutación de un conjunto que contiene un único elemento.

Supongamos ahora (para el propósito de la inducción) que hay a$m!$ permutaciones de un conjunto que contenga $m$ elementos. Buscamos para mostrar que no se $(m+1)!$ permutaciones de un conjunto que contenga $m+1$ elementos.

Podemos construir todas las permutaciones de el último de la siguiente manera:

1. Elija una permutación de la primera $m$ elementos.
2. Insertar el elemento final en la permutación.

Por la hipótesis inductiva, el Paso 1 se puede completar en $m!$ maneras. Paso 2 puede ser completado en $m+1$ maneras, ya que hay $m+1$ lugares en los que el elemento final puede ser insertado. Por lo tanto, tenemos (por el principio) que el número de permutaciones de un $m+1$ elemento del conjunto es igual a $m! \cdot (m+1)$, que es el que desee $(m+1)!$.

Answer 2

Cuando se nos da $m+1$ artículos, nos separamos un artículo especial de la otra $m$ artículos. Se ordena la $m$ artículos y fijar su orden, que nos dan $m!$ opciones.

Ahora tenemos $m+1$ posiciones para elegir nuestros artículos especiales y ninguno de ellos se repite.

Por lo tanto, tenemos $m! \cdot (m+1)= (m+1)!$

Answer 3

Considerar todas las $m!$ permutaciones de las $m$ primeros elementos e inserte el $m+1^{th}$ en todos los lugares posibles. Como hay $m+1$ posibles lugares por permutación, obtenemos un total de $(m+1)m!$.

Sigue siendo para demostrar que no nos hemos olvidado de cualquier nueva permutación ni repetir ninguna.

1. por hipótesis, empezamos con todas las permutaciones de la primera $m$; una permutación de las $m+1$ es forzosamente una permutación de las $m$ con la $m+1^{th}$ insertado en algún lugar. Hemos probado todos los puntos de inserción, nada se pierde.

2. todas las permutaciones de $m$ son distintos. Todas las permutaciones obtenidas mediante la inserción de un nuevo elemento en la posición $k$ son distintos el uno del otro, y distinta de todas las $k$. Por lo tanto todas las nuevas permutaciones son distintos.

Answer 4

Si $X$ es un conjunto, entonces $S_X$ se denota el conjunto de todas las permutaciones de $X$ (es decir, de todos bijections de $X$ a $X$). Quieres demostrar que todo conjunto finito $X$ satisface $\left|S_X\right| = \left|X\right|!$. (Tenga en cuenta que esto es perfectamente cierto cuando $X$ está vacía.)

---

Si quieres un riguroso prueba por escrito en todos los detalles, a continuación, un lugar donde usted puede encontrar que es Corolario 8.81 en mis Notas sobre la combinatoria fundamentos de álgebra, 7 de noviembre de 2018. Esta prueba puede ser resumido de la siguiente manera:

• Si $X$ es un conjunto, y si $x$ e $y$ son dos elementos de la $X$, luego la dejamos $t_{x, y}$ ser la permutación de $X$ swaps $x$ con $y$ , dejando el resto de elementos de $X$ sin cambios. (Este es el mapa de identidad cuando se $x = y$, y de lo contrario, es una transposición.)

• Ahora vamos a $n$ ser un entero no negativo, y establezca $\left[n\right] := \left\{1,2,\ldots,n\right\}$. Demostrar (Ejercicio 5.9 en op. cit.) que cada permutación $\sigma$ de $\left[n\right]$ puede ser escrita en la forma $\sigma = t_{1, i_1} \circ t_{2, i_2} \circ \cdots \circ t_{n, i_n}$ para un único $\left(i_1, i_2, \ldots, i_n\right) \in \left[1\right] \times \left[2\right] \times \cdots \times \left[n\right]$. A grandes rasgos, esto significa simplemente que $\sigma$ puede convertirse en la identidad de permutación por primera intercambio de $n$ con su imagen, entonces el intercambio de $n-1$ con su imagen (en virtud de la resultante de permutación), y así sucesivamente, hasta que todos los números de $n, n-1, \ldots, 1$ están en sus lugares apropiados. Yo formalizar esto como un argumento de inducción.

• La afirmación anterior puede ser interpretado como un bijection entre el conjunto de $\left[1\right] \times \left[2\right] \times \cdots \times \left[n\right]$ y el conjunto de $S_{\left[n\right]}$ de todas las permutaciones de $\left[n\right]$. El ex establecer claramente tiene el tamaño de $n!$; por lo tanto, también lo hace el segundo. Por lo tanto, el conjunto de $S_X$ de todas las permutaciones de cualquier $n$-element set $X$ tiene el tamaño de $n!$ (para probar esto, corregir algunos bijection entre $X$ e $\left[n\right]$, y utilizarlo para construir un bijection de $S_X$ a $S_{\left[n\right]}$).

---

Esta no es la menor prueba. El post de @CopyPasteIt sugiere un argumento diferente, pero confunde es algo en mi opinión, así que aquí es un boceto de cómo iba a hacerlo:

• Proceder por inducción en $\left|X\right|$. La base de la inducción ($\left|X\right| = 0$) es obvia. Para la inducción de paso, usted necesita demostrar que si $X$ es un conjunto finito y $x \in X$ es arbitrario, entonces $\left|S_X\right| = \left|X\right| \cdot \left|S_{X \setminus \left\{x\right\} }\right|$.

• Así que vamos a arreglar un conjunto finito $X$ y algunos $x \in X$. Deje $W$ ser el conjunto de todas las permutaciones $\tau \in S_X$ satisfacción $\tau\left(x\right) = x$. No es difícil ver que hay un bijection de $S_{X \setminus \left\{x\right\} }$ a $W$. (De hecho, esto se deduce de la Proposición 5.57 en op. cit., aplicado a $Y = X \setminus \left\{x\right\}$; pero realmente debería probar esto, ya que es un simple formalización de una declaración clara: Una permutación de $X$ que corrige $x$ es "realmente" sólo una permutación de $X \setminus \left\{x\right\}$. Al formalizar la "realidad", se obtiene una muy natural bijection.) Por lo tanto, $\left|W\right| = \left|S_{X \setminus \left\{x\right\} }\right|$.

• Si $\sigma \in S_X$ es cualquier permutación, entonces existe un único $y \in X$ satisfacción $t_{x, y} \circ \sigma \in W$ (es decir, esta $y$ es $\sigma\left(x\right)$). Por lo tanto, cada una de las $\sigma \in S_X$ puede ser escrito como $t_{x, y} \circ w$ para un único par de $\left(y, w\right) \in X \times W$. En otras palabras, el mapa de $X \times W \to S_X,\ \left(y, w\right) \mapsto t_{x, y} \circ w$ es un bijection. Por lo tanto, $\left|S_X\right| = \left|X \times W\right| = \left|X\right| \cdot \left|W\right| = \left|X\right| \cdot \left|S_{X \setminus \left\{x\right\} }\right|$ (desde $\left|W\right| = \left|S_{X \setminus \left\{x\right\} }\right|$). Esto completa el paso de inducción.

---

Las cosas se ponen un poco más fácil una vez que te acostumbras a la combinatoria y darse cuenta de que las permutaciones de un número finito de $n$-element set $X$ están en bijection con la $n$-tuplas $\left(x_1, x_2, \ldots, x_n\right)$ de los elementos distintos de a$X$. De hecho, la confusión, el último $n$-tuplas son a menudo se llama permutaciones de $X$ , aunque en general no canónica bijection entre estos dos tipos de permutaciones (vea nota 5.4 en op. cit.). Esta confusión de lado, no es difícil ver por algunas versiones del producto de la ley que el número de $n$-tuplas $\left(x_1, x_2, \ldots, x_n\right)$ de los distintos elementos de una $n$-element set $X$ es $n!$; de hecho, más en general, para cualquier entero no negativo $m$, el número de $m$-tuplas $\left(x_1, x_2, \ldots, x_m\right)$ de los distintos elementos de una $n$-element set $X$ es $n\left(n-1\right)\left(n-2\right)\cdots\left(n-m+1\right)$. Esto le da a la tal vez más corta pruebas de su demanda, teniendo la ventaja de que usted realmente no tiene que lidiar con las permutaciones (una vez que han demostrado que están en bijection con estas tuplas).

Answer 5

Cualquier rigurosa prueba de que implica la inducción ha de desarrollar de forma rudimentaria teoría para el conjunto de todas las permutaciones de un conjunto. El hecho de que el resultado es tan bien conocido y puede ser directamente demostrado el uso de la regla del producto no significa que la prueba de los detalles puede ser paliada.

---

Deje $X$ ser un conjunto finito que contiene $n$ elementos con el grupo simétrico $\text{Sym}(X)$, es decir, el conjunto de todas las permutaciones de $X$. Deje $x' \notin X$ y establezca $X' = X \cup \{x'\}$ , de modo que hay una inclusión natural $\text{Sym}(X) \subset \text{Sym}(X')$ - ampliar cualquier permutación $\rho$ a $X$ a todos los de $X'$ definiendo $\rho(x') = x'$.

Si tenemos un conjunto de permutaciones, podemos generar un conjunto más grande por tomar todos los posibles productos (es decir, composición funcional) de las permutaciones. Cada vez que nos generan estos 'algebraicas cierres de' tirar la asignación de identidad para la buena medida.

Proposición 1: Si $\text{Sym}(X)$ es generado por el conjunto de todos los relatos , a continuación, el conjunto de $\text{Sym}(X')$ también es generado por el conjunto de transposiciones.
Prueba
Deje $f \in \text{Sym}(X')$ y establezca $\tau = \left(\,x' \;\; f^{-1}(x')\,\right)$ e $g = f \circ \tau$. Es inmediato que $g(x') = x'$ , de modo que $g$ es un producto de transposiciones. Pero, a continuación, $f = g \circ \tau^{-1}$ es también la composición de los relatos, ya que $\tau^{-1} = \tau$. $\quad \blacksquare$

Nota: En la anterior prueba, $\tau$ puede representar la identidad. Así que estamos abusando de la notación utilizada para una transposición, pero esta es la conveniencia de que vamos a seguir implícitamente emplear en lo que sigue.

En general, las siguientes ecuaciones cierto para transposiciones:

\begin{align}(T1) \quad (ab)(ab)&=1_{Id}\\ (T2) \quad (ab)(cd)&=(cd)(ab)\\ (T3) \quad (ab)(ac)&=(bc)(ab)\\ (T4) \quad (ab)(bc)&=(bc)(ac)\end{align}

Si $f \in \text{Sym}(X')$ es un producto de transposiciones, busque el primero $\tau$ desde el lado izquierdo (si los hubiere) que swaps $x'$ con otro elemento y empezar a 'empujando' paso-por-paso para el extremo derecho de usar
$\text{(T1)}$ thru $\text{(T3)}$ . Cuando el uso de $\text{(T2)}$ o $\text{(T3)}$ avances como $\tau$ está más cerca de la derecha y ninguna de las transposiciones a la izquierda de $\tau$ swap $x'$. Si en algún paso $\text{(T1)}$ entra en juego, entonces la "cadena de composición' es reducido por $2$ transposiciones (progreso) y tienes que empezar de nuevo.

Cuando esta empujando el algoritmo ha terminado, podemos escribir

$\tag 1 f =g \circ \left(\,x' \;\; x\,\right) \, \text{ with } (x \in X) \;\land\; (g \in \text{Sym}(X))$.

Deje $\mathcal S$ ser la colección de todas las transposiciones en $\text{Sym}(X')$ intercambio de $x'$ con otro elemento. De nuevo, la conveniencia de la identidad es un miembro de $\mathcal S$ e lo $\text{#}(\mathcal S) = n + 1$.

Proposición 2: La asignación de $\left(g,\tau\right) \mapsto g \circ \tau$ define una correspondencia bijective

$\quad \text{Sym}(X) \times \mathcal S \equiv \text{Sym}(X')$.

Prueba
Ya hemos demostrado que la asignación es un surjection y la inyectividad es un argumento fácil. $\blacksquare$

Tan fácil consecuencia de la proposición 2 es que

$\quad \text{#}\left(\text{Sym}(X')\right) =\text{#} \left( \text{Sym}(X) \times \mathcal S \right)= \text{#} \left( \text{Sym}(X) \right) \times \text{#} \left(\mathcal S \right) = \text{#} \left( \text{Sym}(X) \right) \times (n+1) $

Los siguientes pueden ser obtenidos mediante la inducción y la teoría anterior:

Teorema 3: Si $X$ ha $n$ elementos, a continuación, $\text{Sym}(X)$ contiene $n!$ elementos.