Usaremos las definiciones combinatorias de los factoriales aquí.
Recordemos que n! representa la cantidad de formas en que podemos permutar n objetos (ponerlos en orden) , entonces (n + 1)! es cómo podemos permutar n + 1 objetos.
Mira la respuesta 1 / (n + 1) como una razón. Lo que esto está diciendo es: por cada forma en que podemos permutar n objetos, hay n + 1 formas correspondientes en las que podemos permutar n + 1 objetos.
- ¿Cuáles son los requisitos previos (matemáticos, de programación, etc.) que uno debe tener para convertirse en ingeniero de control?
- ¿Por qué identificamos algoritmos que actúan en diferentes tamaños de entrada?
- ¿Qué literatura necesitas para resolver el problema P vs NP?
- ¿Cuál es la diferencia entre datos continuos y discretos?
- ¿Qué tan eficientemente la computadora Quantum puede resolver el problema P vs NP?
Encontremos esta correspondencia.
Primero, hagamos esto para n = 3 . Solo usaremos los números {1,2,3} como nuestros objetos.
Hay seis formas de permutar {1,2,3}:
1, 2, 3 // 1, 3, 2 // 2, 1, 3 // 2, 3, 1 // 3, 1, 2 // 3, 2, 1
Ahora, para cada una de estas formas, necesitamos encontrar 4 formas correspondientes en las que podamos permutar {1,2,3,4}. Para cada permutación P de {1,2,3}, que las permutaciones correspondientes de {1,2,3,4} sean aquellas en las que 1, 2 y 3, aparecen en el mismo orden que en P.
Entonces tenemos
1, 2, 3 → 4, 1, 2, 3 // 1, 4, 2, 3 // 1, 2, 4, 3 // 1, 2, 3, 4
1, 3, 2 → 4, 1, 3, 2 // 1, 4, 3, 2 // 1, 3, 4, 2 // 1, 3, 2, 4
2, 1, 3 → 4, 2, 1, 3 // 2, 4, 1, 3 // 2, 1, 4, 3 // 2, 1, 3, 4
2, 3, 1 → 4, 2, 3, 1 // 2, 4, 3, 1 // 2, 3, 4, 1 // 2, 3, 1, 4
3, 1, 2 → 4, 3, 1, 2 // 3, 4, 1, 2 // 3, 1, 4, 2 // 3, 1, 2, 4
3, 2, 1 → 4, 3, 2, 1 // 3, 4, 2, 1 // 3, 2, 4, 1 // 3, 2, 1, 4
Observe que cada uno de estos conjuntos de permutaciones de {1,2,3,4} divide las 24 permutaciones. Es decir, ninguna permutación de {1,2,3,4} aparece dos veces, y cada permutación se contabiliza exactamente una vez.
Por lo tanto, existe una correspondencia 1: 4 entre las permutaciones de {1,2,3} y las permutaciones de {1,2,3,4}.
Usando la misma lógica, puede mostrar que hay una correspondencia 1: n + 1 entre las permutaciones de {1,2, …, n} y {1,2, …, n + 1}
