Dado un conjunto, A, de n elementos, ¿de cuántas maneras se pueden elegir x elementos del conjunto A, siempre que pueda elegir el mismo elemento muchas veces?

Answer 1

Esencialmente, solo nos importa la cantidad de veces que [math] y_i [/ ​​math] ese elemento [math] i \ in A [/ math] (he decidido numerar elementos 1,2,3 .. etc.) es elegido, entonces simplemente contamos los vectores de solución [matemática] (y_1, y_2, \ cdots, y_n) [/ matemática] a la ecuación

[matemáticas] y_1 + y_2 + \ cdots + y_n = x [/ matemáticas]

Entonces simplemente necesitamos contar los arreglos de [matemática] n-1 [/ matemática] “+” sy [matemática] x [/ matemática] “1” s.

Por ejemplo, para [matemática] x = 6, \, n = 3 [/ matemática] podemos escribir un vector solución [matemática] (y_1, y_2, y_3) = (2,3,1) [/ matemática] como

[matemáticas] 2 + 3 + 1 = 6 [/ matemáticas]

que tiene la disposición de 2 “+” sy 6 “1” s

[matemáticas] 1 \, 1 \, + \, 1 \, 1 \, 1 \, + \, 1 \, = 6 [/ matemáticas]

El número de vectores de solución es igual al número de dichos arreglos, hay

[matemáticas] \ dfrac {(n + x-1)!} {(n-1)! \, x!} \ qquad \ blacksquare [/ math]

de estos por combinatoria elemental. Esto, puedes reconocerlo como

[matemáticas] \ dbinom {n + x-1} {n-1} \ qquad \ blacksquare [/ math]

Para mi ejemplo de [matemáticas] x = 6, \, n = 3 [/ matemáticas] hay [matemáticas] \ binom {3 + 6-1} {3-1} = \ binom {8} {2} = \ frac {8 \ cdot 7} {2} = 28 [/ math] vectores de solución.

Para su ejemplo con [matemáticas] x = 3, \, n = 3 [/ matemáticas] tenemos [matemáticas] \ binom {3 + 3-1} {3-1} = \ binom {5} {2} = \ frac {5 \ cdot 4} {2} = 10 [/ math] vectores de solución.

Editar : Disculpas, mi [matemáticas] x [/ matemáticas] fue originalmente su [matemáticas] n [/ matemáticas] y viceversa, ahora he editado para que coincida con la pregunta.

Answer 2

Piénselo de esta manera, tiene elementos [matemática] x [/ matemática] que puede seleccionar entre las opciones [matemática] n [/ matemática] pero que permiten la repetición. Esto es lo mismo que contar el número de formas de dividir [matemática] x [/ matemática] (idénticas) bolas en [matemática] n [/ matemática] contenedores donde cada contenedor puede contener [matemática] 0, 1, \ ldots, x [/ matemáticas] bolas.

¿Por qué son iguales? Bueno, los contenedores son los elementos del conjunto [math] A [/ math] y el número de bolas en cada bin correspondería al número de copias de ese elemento que vas a seleccionar.
Por ejemplo, si tenemos [matemáticas] n = 3, x = 3 [/ matemáticas] y
Bin [matemática] A = 0 [/ matemática] bolas, Bin [matemática] B = 1 [/ matemática] pelota, Bin [matemática] C = 2 [/ matemática] bolas, esto corresponde a elegir [matemática] BCC [/ matemática ]

Ahora, ¿cómo calculamos el número de formas de poner bolas [matemáticas] x [/ matemáticas] en contenedores [matemáticos] n [/ matemáticos], si permitimos contenedores vacíos?
Considere tener cuadrados [math] n + x – 1 [/ math] y seleccione [math] x-1 [/ math] de ellos. El número de cuadrados vacíos entre los cuadrados seleccionados es el número de bolas de cada grupo que van en cada contenedor.

Para el ejemplo anterior (eligiendo [math] BCC [/ math]) tenemos
[matemáticas] \ blacksquare, \ square, \ blacksquare, \ square, \ square [/ math]
Dado que hay [math] 0 [/ math] cuadrados vacíos antes del primer cuadrado negro, hay bolas [math] 0 [/ math] en el primer bin. Luego está [math] 1 [/ math] cuadrado vacío, por lo que hay [math] 1 [/ math] bola en el segundo contenedor, y finalmente hay [math] 2 [/ math] cuadrados vacíos, lo que significa que hay [matemáticas] 2 [/ matemáticas] bolas en el contenedor final.

Otros ejemplos serían
[matemáticas] \ blacksquare, \ square, \ square, \ square, \ blacksquare [/ math]
que corresponde a [math] 3 [/ math] bolas en el segundo contenedor (o elegir [math] BBB [/ math])
O
[matemáticas] \ cuadrado, \ cuadrado, \ blacksquare, \ blacksquare, \ square [/ math]
que corresponde a [matemáticas] 2 [/ matemáticas] bolas en el contenedor [matemáticas] A [/ matemáticas] y 1 pelota en el contenedor C (o elegir [matemáticas] AAC [/ matemáticas])
Y
[matemáticas] \ cuadrado, \ blacksquare, \ cuadrado, \ blacksquare, \ cuadrado [/ math]
que corresponde a [matemática] 1 [/ matemática] bola en cada contenedor (o elegir [matemática] ABC [/ matemática])

Ahora, finalmente, tenemos que la forma de seleccionar [matemática] x-1 [/ matemática] cuadrados de [matemática] n + x-1 [/ matemática] posibles es

[matemáticas] \ dbinom {n + x-1} {x-1} [/ matemáticas]

que también se conoce como una composición débil

Para el caso en la descripción, donde [matemática] n = 3, x = 3 [/ matemática] tenemos [matemática] \ binom {5} {2} = 10 [/ matemática]

Answer 3

Asumiré que cada uno de estos n elementos es distinto. Considere el conjunto {0,1,2,3,4,5,6,7,8,9}. Le pregunto cuántas cadenas de longitud 4 puede componer, dado que cada elemento del conjunto es distinto. Usted dice, ‘bueno, obviamente, 10000 ya que puedo crear todos los números 0000 a 9999’. Y estarías en lo cierto. Pero para muchos la pregunta original necesitamos entender cómo funciona esto.

Es fácil resolver esto intuitivamente, pero hay una forma formulada de lograr el resultado correcto para cualquier conjunto de elementos distintos. Veamos nuestro primer artículo en nuestra tienda en el ejemplo anterior. ¿Cuántos valores posibles puede tener? Contando el número de artículos en nuestro conjunto, obtenemos 10. Bien, entonces, para cada una de estas 10 opciones, ¿cuántas opciones tenemos para el siguiente artículo? Como no podemos repetir valores, nuevamente tenemos 10. Continuando podrá obtener 10 opciones para cada uno de los cuatro elementos, y por lo tanto hay 10 × 10 × 10 × 10 = 10 ^ 4 = 10000.

¿Ves el patrón? Teníamos 10 elementos distintos y una longitud de cuatro cuerdas, lo que resultó en 10 ^ 4 combinaciones. Mirando otros ejemplos, pronto verá que dado un conjunto, A, de n elementos distintos, puede formar n ^ x cadenas de longitud x si los elementos pueden repetirse.

EDITAR:

Esta respuesta ya no es correcta debido a una modificación de la pregunta.