¿Cuántas formas hay de elegir 3 monedas?

Question

Lo siento, no conozco los términos matemáticos correctos aquí, no he tenido una clase de matemáticas en algún tiempo. Probablemente por eso tengo problemas para encontrar una pregunta existente como esta. Digamos que hay 4 tipos diferentes de monedas: centavo (P), níquel (N), diez centavos (D) y cuarto (Q). ¿Cuántas formas puedes tener 3 monedas? Dado que hay 3 monedas y 4 posibilidades para cada una, mi primer pensamiento fue 4x4x4, o 64, pero eso no es correcto. 2 centavos y un níquel siguen siendo solo 2 centavos y un níquel, ya sea que sea PPN, PNP o NPP. El orden no importa. Enumeré todas las posibilidades y las conté, pero ¿cuál es la fórmula correcta para usar aquí?

 1. PPP
 2. PPN
 3. PPD
 4. PPQ
 5. PNN
 6. PND
 7. PNQ
 8. PDD
 9. PDQ
10. PQQ
11. NNN
12. NND
13. NNQ
14. NDD
15. NDQ
16. NQQ
17. DDD
18. DDQ
19. DQQ
20. QQQ

Answer 1

Tienes tres bolas, y quieres ponerlas en cuatro cubetas, llamadas $P$, $N$, $D$ y $Q. Esta es una aplicación clásica de estrellas y barras, y la respuesta es $$\left(\dbinom{4}{3}\right) = \dbinom{4+3-1}{3} = \dbinom{6}{3} = 20.$$

Answer 2

Es correcto que la respuesta es ${6 \choose 3} = 20$. Puedes usar el método de estrellas y barras para resolver esto.

Esto es equivalente a elegir cuatro enteros no negativos que sumen 3, que son la cantidad de peniques, monedas de cinco centavos, dimes y cuartos respectivamente. Cada posible suma se puede escribir colocando tres estrellas (*) y tres barras (|) que los separan. Hay ${6 \choose 3}$ de esas disposiciones, que lucen así $$*||*|*$$. Esto corresponde a la tupla de 4 elementos (1, 0, 1, 1), o sea un penique, cero monedas de cinco centavos, un dime y un cuarto.

Answer 3

Aquí hay una solución utilizando un método mucho más general, el lema de Pólya-Burnside.

Consideramos las tres opciones de monedas como un objeto único con tres espacios que deben ser llenados. Los tres espacios son indistinguibles, por lo que cualquier permutación de ellos se considera una simetría de este objeto; por lo tanto, su grupo de simetría es $S_3$, el grupo simétrico de tres elementos.

Supongamos que hay $N$ opciones de monedas para cada espacio. El lema de Pólya-Burnside dice que para encontrar la cantidad de formas de llenar todos los espacios, ajustadas por simetría, es encontrar la cantidad de llenados que son dejados invariables por cada una de las seis simetrías, y promediar esos seis números.

Las seis simetrías caen en tres clases de conjugación:

1. La simetría de identidad, con tres órbitas
2. Las tres simetrías que intercambian dos espacios y dejan uno fijo, con dos órbitas cada una
3. Las dos simetrías que permutan los espacios cíclicamente, con una órbita cada una

En cada clase de conjugación, la cantidad de formas de asignar monedas a los espacios de modo que la asignación sea dejada invariable por esa simetría es $N^k$ donde $k$ es el número de órbitas y $N$ es el número de tipos de monedas. La simetría de identidad contribuye con $N^3$ formas; las tres simetrías de tipo 2 contribuyen con $N^2$ formas cada una para un total de $3N^2$, y las dos simetrías de tipo 3 contribuyen con $N$ formas cada una para un total de $2N$. Al promediar estos encontramos que la cantidad de formas de asignar $N$ tipos de monedas a los tres espacios es siempre $$\frac{N^3+3N^2 + 2N}6$$ y tomando $N=4$ encontramos que la respuesta particular es $$\frac{4^3+3\cdot4^2+2\cdot 4}6 = \frac{120}{6} = 20.$$

También podemos observar que $$\frac{N^3+3N^2 + 2N}6 = \frac{N(N+1)(N+2)}{3!} = \binom{N+2}{3},$$ lo cual concuerda con la solución encontrada por el método de estrellas y barras descrito en otro lugar de este hilo.

Este es un gran martillo para usar en un problema pequeño, pero creo que es instructivo como un ejemplo simple de cómo utilizar el lema de Pólya-Burnside.