De cuántas maneras existen para elegir los 10 objetos de 6 tipos distintos de...

Question

(a) los objetos son ordenados y la repetición no está permitido?

(b) los objetos son ordenados y la repetición es permitido?

(c) los objetos son desordenadas y la repetición no está permitido?

(d) los objetos son desordenadas y la repetición es permitido?

No estoy realmente seguro de lo que significa para los objetos a ser "ordenado" y la repetición de ser "permitido". Puede alguien explique brevemente lo que sucede en cada caso, y cómo esto se puede generalizar a otros problemas del mismo tipo?

Answer 1

Digamos que los seis tipos a, B, C, D, E, y F. vas a elegir diez de ellos. Voy a empezar con las preguntas que permiten la repetición, lo que significa que usted puede seleccionar más de un objeto de un tipo determinado.

Decir que usted escoja $3$ a, una B, $4$ D y $2$ F. Si no están ordenadas, la lista de $\langle 3,1,0,4,0,2\rangle$, dando el número de elementos de cada tipo, le dice todo lo que hay que saber sobre el conjunto. Contando el número de desordenada conjuntos de $10$ objetos es el mismo como el conteo del número de $6$-tuplas $$\langle n_A,n_B,n_C,n_D,n_E,n_F\rangle$$ that could describe such a set, where $n_A$ is the number of objects of type A in the set, $n_B$ is the number of objects of type B in the set, and so on. It's not hard to see that the numbers $n_A,\dots,n_F$ must be non-negative integers, and they must sum to $10$: queremos que el número de enteros soluciones del sistema

$$\begin{align*} &n_A+n_B+n_C+n_D+n_E+n_F=10\\ &n_A,n_B,n_C,n_D,n_E,n_F\ge 0\;. \end{align*}$$

Esto es lo que se llama a veces una de las estrellas-y-bares problema; el artículo vinculado da la fórmula, de la que podemos encontrar que hay

$$\binom{10+6-1}{6-1}=\binom{15}5=3003$$ solutions and therefore $3003$ ways of picking an unordered set of $10$ los objetos, si la repetición es permitido. El artículo también proporciona una bastante decente explicación de la fórmula, y usted puede encontrar otra explicación en este sitio si usted busca para las estrellas y barras.

Ahora supongamos que no sólo se preocupan acerca de cómo muchos de los objetos de cada tipo tenemos, pero también sobre el orden en que los hemos recogido. Si vas a hacer un test de elección múltiple que ha $10$ preguntas, cada una con $6$ opciones, claramente la elección de las respuestas en el orden AAABDDDDFF se va a dar un puntaje diferente de la elección de los mismos en el orden ADFDDBAFAD! El cálculo apropiado es en realidad mucho más simple. Hay $6$ maneras de escoger el tipo del primer objeto. No importa la opción que elija, hay $6$ maneras de escoger el tipo del segundo objeto, por lo que hay $6\cdot6=36$ formas para elegir los tipos de los primeros dos objetos, así como hay $6\cdot6=36$ resultados posibles al tirar un dado rojo y un verde morir. El mismo razonamiento muestra que hay $6^3$ formas posibles para elegir los tipos de los primeros tres objetos, y en general $6^k$ formas para elegir los tipos de la primera $k$ objetos, por lo que hay $$6^{10}=60,466,176$$ ways to choose the types of all $10$ objetos.

Ahora supongamos que la repetición no está permitido. Eso simplemente significa que usted puede elegir a más de un objeto de cada tipo. En particular, en este problema significa que no hay manera de elegir a $10$ objetos sin repetición, si usted se preocupa por el orden de elección o no. Eso es fácil, pero no va a ayudar mucho con los problemas en los que el número de objetos elegido no es mayor que el número de tipos, así que vamos a modificar el problema y pedir $4$-elemento sets sin repetición.

Si están desordenadas, todos nos importa es que de los seis tipos están representados. El coeficiente binomial $$\binom64=\frac{6!}{4!(6-4)!}=\frac{6!}{4!2!}=\frac{6\cdot5}{2\cdot1}=15$$ gives the number of $4$-element subsets of a $6$-element set, and that's exactly what we want. More generally, the number of $k$-element subsets of an $n$-element set is $$\binom{n}k=\frac{n!}{k!(n-k)!}=\frac{\overbrace{n(n-1)(n-2)\ldots(n-k+1)}^{k\text{ factors}}}{k!}\;.\tag{1}$$

Finalmente, el numerador de $(1)$ da la respuesta a la última pregunta: hay

$$n(n-1)(n-2)\ldots(n-k+1)=\binom{n}k\cdot k!$$

ordenado de las formas para elegir a $k$ distintos elementos de un conjunto de $n$ elementos, es decir, no sólo para elegir lo que $k$ elementos en nuestra serie, sino también el orden en el que tenemos una lista de ellas. En el ejemplo, $n=6$$k=4$, por lo que hay

$$\binom64\cdot 4!=15\cdot24=360$$

estos conjuntos.

Answer 2

"El fin es permitido" significa permutaciones diferentes de los mismos objetos son considerados diferentes.

Por ejemplo, el número de maneras de escoger 2 objetos de $\{a,b,c\}$ con "el fin de permitir" incluirá $\{ab, ba, bc, cb, ac, ca\}$. Una buena manera de entender el "orden permitidos, pero la repetición no se permite" el problema es pensar que están recogiendo a los seis objetos de uno en uno, de los diez objetos. Por ejemplo, en mi ejemplo, $ab$ representa a recoger $a$ en la primera selección y recolección de $b$ en el segundo.

La manera de contar con "el fin de permitidos, pero la repetición no permitido" es ver cómo muchas opciones que usted tiene en cada recogida y multiplicarlas. Para mi ejemplo, yo tenía tres opciones para la selección de primera viz. $a,b,c$ , y para mi segunda selección, tengo dos opciones a la izquierda. Por lo que el número total de maneras en que se $3 \times 2 = 6$ cual es el número total de posibilidades en nuestra enumeración viz. $\{ab, ba, bc, cb, ac, ca\}$

---

"Repeticiones son permitidos" por lo general significa que un elemento puede recogido en otro momento, aunque haya sido elegido una vez antes.

Una buena manera de entender el "orden permitía y la repetición permitido" en su problema es el de pensar que se están recogiendo los seis objetos de una en una pero coloca el objeto en la bolsa después de tomar nota de lo que has elegido. Por ejemplo, en mi ejemplo, $aa$ representa a recoger $a$ en el primer pick y ponerlo de nuevo y, a continuación, recoger $a$ más en la segunda.

Por ejemplo, el número de maneras de escoger 2 objetos de $\{a,b,c\}$ con "el fin de los permitidos y repetición permitido" incluirá $\{aa, bb, cc, ab, ba, bc, cb, ac, ca\}$. ¿Ves cómo $aa$ se incluye ahora? Esto representa la posibilidad de llegar a la $a$ en ambas selecciones.

La manera de contar con "el fin de los permitidos y repetición permitido" es ver cómo muchas opciones que usted tiene en cada recogida y multiplicarlas. Para mi ejemplo, yo tenía tres opciones para la selección de primera viz. $a,b,c$ , y para mi segunda elegir, yo todavía tiene tres opciones. Por lo que el número total de maneras en que se $3 \times 3 = 9$ cual es el número total de posibilidades en nuestra enumeración viz. $\{aa, bb, cc, ab, ba, bc, cb, ac, ca\}$

---

Si "el Fin no está permitido", entonces permutaciones diferentes de los mismos objetos son considerados mismo.

Por ejemplo, el número de maneras de escoger 2 objetos de $\{a,b,c\}$ con "el fin no se permite y no se permite la repetición" incluirá $\{ab, bc, ac\}$. ¿Ves cómo $ba$ no está incluido? Esto es debido a que $ab$ ha sido incluido. Los diferentes ordenamientos de $ab$ es irrelevante ahora.

Una buena manera de entender "el fin no se permite y no se permite la repetición" en su problema es el de pensar que se están recogiendo los seis objetos de todos a la vez. Por ejemplo, en mi ejemplo, $ab$ representa a escoger dos objetos en uno, donde tomé $a$$b$, Claramente este experimento no conteo de permutaciones de $ab$ como diferentes. Todo lo que importa es que el objeto que usted recibió.

La manera de contar con "el fin no se permite y no se permite la repetición" es el uso de $\binom{n}{r}$ fórmula. Esto representa el número total de formas de no-repitió la recogida de los 'r' objetos $n$ objetos de manera desordenada. Por lo que el número total de maneras en que se $\binom{3}{2} = 3$ cual es el número total de posibilidades en nuestra enumeración viz. $\{ab, bc, ac\}$

---

Los más difíciles caso es el último. Este es el caso donde las repeticiones son permitidos, pero la orden no está permitido.

Por ejemplo, el número de maneras de escoger 2 objetos de $\{a,b,c\}$ con "el fin no se permite la repetición permitido" incluirá $\{aa, ab, ac, bb, bc, cc\}$.Creo que no hay más explicación que se necesita para la anterior enumeración.

Una buena manera de entender "el fin no se permite la repetición y permitió que" el problema es pensar que se están distribuyendo $6$ idénticos objetos en $10$ distintas urnas. En mi ejemplo, dos objetos idénticos tienen que ser distribuidos en las urnas etiquetados $a,b,c$. Por ejemplo, $ab$ en la enumeración representa la distribución de uno de mis objetos en una urna etiquetados $a$ y otro objeto en una urna etiquetados $b$.

La manera de contar con "el fin no se permite la repetición permitido" es el uso de $\binom{n + r - 1}{r}$ fórmula. Esto representa el número total de no negativo soluciones a la ecuación de $x_1 + x_2 + \cdots + x_r = n$. Por lo que el número total de maneras en que se $\binom{3+2-1}{2} = 6$ cual es el número total de posibilidades en nuestra enumeración viz. $\{aa, bb,cc, ab, bc, ac\}$