9 votos

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

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.

12voto

N. Shales Puntos 51

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.

9voto

Foobaz John Puntos 276

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.

6voto

Harish Puntos 153

¿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.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X