De cuántas maneras existen para seleccionar elementos de un conjunto, sin reemplazo?

Question

La mayoría de los ejemplos que veo es que de permutaciones. Esta consulta es si hay un formal fórmula para una lista más completa de pedidos:

Por ejemplo:
El conjunto $\{1\}$ es ordenado como $\{1\}$. Solo una posibilidad.
El conjunto $\{1,2\}$ sólo puede ser ordenado como: $\{1\},\{2\},\{1,2\},\{2,1\}$. Cuatro posibilidades.
El conjunto $\{1,2,3\}$ puede ser ordenado como:
$\{1\},\{2\},\{3\},\{1,2\},\{2,1\},\{1,3\},\{3,1\},\{2,3\},\{3,2\},\{1,2,3\},\{1,3,2\},\{2,1,3\},\{2,3,1\},\{3,1,2\},\{3,2,1\}$. Quince posibilidades.

Ya que la secuencia es de 1,4 y 15, no estoy seguro de qué fórmula se aplicaría.

Estoy desarrollando un programa que genera aleatoriamente un par de números a partir de este conjunto, pero para conocer el total de posibilidades, yo estaba esperando una fórmula que podría predecir.

Answer 1

Como Bill Wallis publicado, usted está tomando la suma

$$\sum_{r=1}^{n}\frac{n!}{(n-r)!}\, ,$$

o

$$\sum_{r=0}^{n}\frac{n!}{(n-r)!}$$

si se incluye la selección vacía.

Otra forma de escribir esto es

$$\sum_{r=0}^{n}\frac{n!}{r!}\, .\tag{1}$$

Si ahora nos recuerde la expansión de $e^x$:

$$e^x=\sum_{r\ge 0}\frac{1}{r!}x^r\tag{2}$$

a continuación, la suma de $(1)$ se aproxima por poner $x=1$ $(2)$ y multiplicando por $n!$:

$$n!e=\sum_{r\ge 0}\frac{n!}{r!}\, .\tag{3}$$

Ahora, todo lo que queda es mostrar es que la diferencia entre el $(3)$ $(1)$ es de menos de $1$ (sugerencia: realizar un término por término de comparación con una serie geométrica) y tenemos

$$\lfloor n!e\rfloor = \sum_{r=0}^{n}\frac{n!}{(n-r)!}\, .$$

O, si se excluye a la selección vacía

$$\lfloor n!e\rfloor - 1 = \sum_{r=1}^{n}\frac{n!}{(n-r)!}\, .$$

La única referencia que tengo para un push-botón de bloqueo de la secuencia es la página 82 de Una Introducción a la Enumeración de Alan Camina y Barry Lewis. Por desgracia, hay páginas que faltan en la muestra.

Answer 2

Deje $f(n)$ el número de palabras posibles de cualquier longitud sobre el alfabeto $\{1,\dotsb, n\}$ donde cada letra aparece en más de una vez(incluyendo la palabra vacía). Entonces $$ f(n)=\sum_{i=0}^n\frac{n!}{(n-i)!}=n!\sum_{i=0}^n\frac{1}{i!} $$ Tenga en cuenta que $$ \begin{align} 0\leq en!-f(n)&=n!\left(\frac{1}{(n+1)!}+\frac{1}{(n+2)!}+\frac{1}{(n+3)!}\dotsb\right)\\ &=\frac{1}{(n+1)}+\frac{1}{(n+1)(n+2)}+\frac{1}{(n+1)(n+2)(n+3)}+\dotsb\\ &<\frac{1}{(n+1)}+\frac{1}{(n+1)^2}+\frac{1}{(n+1)^3}+\dotsb\\ &=1/n\leq1 \end{align} $$ Por lo $f(n)=\lfloor{en!}\rfloor$. Si desea excluir de la palabra vacía restar uno.

Answer 3

¿Desea contar el conjunto vacío $\{\}$ así? Si sí, entonces simplemente comenzar el índice de $i$ $0$ en lugar de $1$ en el siguiente resumen.

Hasta el momento, que estás haciendo $$ \sum_{i=1}^{n} {}^n\text{P}_{i} $$ para cada número natural $n \in \mathbb{N}$ donde ${}^n\text{P}_{i}$ es la permutación dada por la fórmula $$ {}^n\text{P}_{i} = \frac{n!}{(n-i)!}. $$ Por ejemplo, para obtener $15$ que estás haciendo $$ \frac{3!}{(3-1)!} + \frac{3!}{(3-2)!} + \frac{3!}{(3-3)!} = \frac{3!}{2!} + \frac{3!}{1!} + \frac{3!}{0!} = 3 + 6 + 6 = 15. $$ Yo se lo dejo a usted para ver cómo cada término corresponde a cada tipo de conjunto, y espero que usted pueda entender donde esta fórmula viene. Si no, yo estaría feliz para elaborar más tarde.