¿Por qué dividimos las Permutaciones para llegar a las Combinaciones?

Question

Me está costando mucho razonar la fórmula de las combinaciones $ \frac {n!}{k! \left (n-k \right )!}$ . Entiendo la razón de la fórmula de las permutaciones y sé que para las combinaciones que dividimos por $k!$ para ajustar los casos repetidos, ya que el orden no importa. ¿Pero qué sucede exactamente cuando dividimos el conjunto de permutaciones por $k!$ ?

Sé que esto puede parecer una pregunta tonta... No puedo darlo por sentado, no sea que pierda la oportunidad de aplicarlo correctamente. ¿Puedes describir lo que está sucediendo aquí paso a paso, algo así como la depuración de un script?

Answer 1

Tal vez, mirando un ejemplo aclare esto mejor:

Tienes $20$ objetos y tienen que elegir $5$ de ellos. ¿Cuántas posibilidades hay?

Tienes $20,19,18,17,16$ opciones que explican cómo $ \frac {20!}{15!}$ entra en la obra.

Ahora cada combinación puede aparecer en $5!$ posibles órdenes que corresponden a la misma combinación. Por lo tanto, tenemos que dividir por $5!$ para encontrar el número de combinaciones.

Esto puede generalizarse a los números arbóreos que explican cómo surge el coeficiente binomial.

Answer 2

Agrupemos las permutaciones que tienen el mismo contenido. Cada clase de equivalencia resultante tiene $k!$ miembros. Por lo tanto, el número de tales clases es $k!$ veces más pequeño que el número de permutaciones. Una combinación es sólo una clase de equivalencia o, si lo prefiere, un elemento nominado de la misma.

Answer 3

Asume que quieres saber el número de combinaciones de $k$ elementos fuera de $n$ elementos. Una forma de elegir tal combinación es la de organizar todos $n$ elementos en cualquier orden arbitrario (hay $n!$ formas de hacerlo) y elegir la primera $k$ de ellos como "su selección". Como el resto $n-k$ los elementos pueden ser dispuestos en cualquier orden, cada selección ordenada de la primera $k$ elementos aparece $(n-k)!$ veces en el conjunto de todas las permutaciones de la $n$ elementos, así que tienes que dividir $n!$ por $(n-k)!$ para contar las diferentes "selecciones" (ordenadas) de $k$ elementos. Ahora, como no está interesado en el orden de los $k$ elementos, todos $k!$ Las permutaciones de una "selección" representan la misma combinación así que todavía tienes que dividir el número por $k!$ que hace un total de $ \frac {n!}{k!(n-k)!}$ combinaciones. Así que, en resumen, este dividiendo "elimina el orden" al contar (aquí: el orden de la primera $k$ elementos y el orden de los restantes $n-k$ elementos).

Answer 4

Deje que $X$ ser un conjunto finito de tamaño $n$ . Supongamos que queremos saber el número de combinaciones de tamaño $k$ . Primero una definición:

A combinación es un subconjunto de $X$

Así que preguntémonos: ¿Cómo podemos construir una combinación? Sugiero que lo hagamos construyendo una permutación. Usemos esta definición:

A subpermutación de $X$ es un subconjunto de $X$ con algún pedido adjunto.

Hay dos formas de proceder. Esta se llama adelante :

¿Cómo construimos una subpermutación? Bueno, tiene que ser ordenado, así que vamos a elegir el primer elemento. Hay $n$ y podemos dividir el conjunto de permutaciones por la elección del primer elemento, así que no nos hemos perdido nada todavía con esta elección y no hemos contado dos veces nada. Así que continuamos y eventualmente nos detenemos después $k$ elementos y concluyen que hay $ \frac {n!}{(n-k)!}=n(n-1) \cdots (n-k+1)$ subpermutaciones de tamaño $k.$

Dada una subpermutación podemos olvidarnos del orden para obtener una combinación. Sin embargo, como hay múltiples subpermutaciones con el mismo conjunto y diferentes órdenes, hemos contado la misma combinación varias veces llegando a ella de diferentes maneras. Si dividimos por el número de formas de llegar a cada combinación, no estaremos contando las cosas varias veces. Entonces, ¿cuántas formas de llegar a una combinación? Bueno, ese es el número de maneras de tener un orden diferente en una subpermutación sin cambiar el conjunto. ¿Cuántas de ellas? Bueno, hay $k$ opciones para la primera, $k-1$ para el segundo, y así sucesivamente, así que $k!$ total, por lo que dividimos por $k!.$

---

Este es el al revés camino:

Supongamos que sabemos que hay $C$ combinaciones de tamaño $k$ y queremos calcular $P,$ el número de subpermutaciones de tamaño $k$ . Aquí hay un algoritmo:

1. Elija una combinación de tamaño $k$
2. Elija algunos pedidos de esa combinación

Y hay $C$ formas de hacer la parte 1, y $k!$ formas de hacer la parte 2, así que hay $Ck!$ formas de hacer una subpermutación de tamaño $k.$ No hemos contado doblemente porque no contamos doblemente en el paso 1 o 2 y dos subpermutaciones necesitan el mismo conjunto y el mismo orden para ser iguales. Por lo tanto $P=Ck!$ pero resulta que sabemos $P$ y no $C$ así que podemos deducir $C= \frac P{k!}$

Answer 5

En lugar de tratar de averiguar directamente por qué debemos dividir las permutaciones por $k!$ Intentemos pensar en ello desde la otra dirección:

Dado $n$ objetos distintos, hay varias maneras de elegir una combinación de $k$ de aquellos objetos en los que el orden de los objetos en la lista final de $k$ no importa. No nos preocupemos todavía por cómo calcular exactamente ese número; es suficiente para saber que existe. (Podríamos, por ejemplo, hacer una lista de todos los las combinaciones por fuerza bruta con una cuidadosa revisión de los duplicados). Para cualquier $n$ y cualquier $k,$ deja $C(n,k)$ representan el número de combinaciones.

Consideremos ahora una de esas combinaciones de $k$ artículos. Si queremos contar las permutaciones (donde el orden importa), esta única combinación puede ser arreglada en $k!$ permutaciones distintas. Ninguna de esas permutaciones es igual a cualquier permutación derivada de cualquier otra combinación de $k$ artículos. Así que si revisamos las combinaciones una por una, cada una de ellas añade $k!$ nuevas permutaciones al total. Pero hay $C(n,k)$ combinaciones. Así que $P(n,k),$ definido como el número total de permutaciones de $k$ los artículos seleccionados de $n$ elementos distintos, obedece a la ecuación $$ P(n, k) = C(n, k) \times k!.$$

Ahora es una simple operación aritmética para dividir por $k!$ en ambos lados, con el resultado $$ C(n, k) = \frac {P(n, k)}{k!}.$$

Y es por eso que dividimos el número de permutaciones por $k!.$