Las cuatro fórmulas combinatorias básicas?

Question

Hay 4 fórmulas combinatorias básicas al elegir$k$ elementos entre$n$

Tenemos repetición permitida o no, y el orden importa o no importa.

Cuando el orden importa y la repetición no está permitida, la llamamos permutación.

Cuando el orden no importa y no se permite la repetición, lo llamamos una combinación.

¿Cuáles son los nombres de los dos desaparecidos y cuáles son las fórmulas para cada uno?

Answer 1

Tenemos los siguientes casos para el número de subconjuntos de tamaño $k$ elegido de un conjunto de elementos distintos de $n$:

• reemplazo y ordenado, "permutación con repetición" $$n^k$ $
• no hay reemplazo y ordenado, «k-permutaciones de n» $$\frac{n!}{(n-k)!}$ $
• no hay reemplazo y desordenado, "combinaciones" $$\binom{n}k$ $
• reemplazo y desordenado, "combinación con repeticiones" $$\binom{n+k-1}k$ $

Answer 2

Cuando el orden de los asuntos y la repetición es permitido, usted obtiene todas las funciones de $\{1,2, \cdots, k\}$ a su conjunto $S$ $n$ elementos. Cada función corresponde a una única opción, y cada decisión que le permite construir una función mediante el establecimiento $f(r)$ $r^{th}$ elemento elegido. La fórmula de estos es más simple, sólo se $n^k,$ porque tenemos un total $n$ independiente de decisiones que tomar, $k$ veces en una fila.

Tal vez el más complicado de los cuatro es cuando la repetición es permitido, pero no importa el orden. Esos son llamados multisets. No hay una fórmula explícita para $n$ multichoose $k$ $\left( {n \choose k}\right) = {n+k-1 \choose k}.$