¿Cuántas combinaciones de$3$ números naturales hay que suman$30$?

Question

¿Cuántas combinaciones de$3$ números naturales hay que suman$30$?

La respuesta es$75$ pero necesito el enfoque.

Aunque sé que podemos usar$_{(n-1)}C_{(r-1)}$, es decir,$_{29}C_2 = 406$, pero esto es cuando$a, b, c$ son distinguibles, lo cual no es el caso aquí.

Por favor explique.

EDITAR tres ejemplos de este tipo:
$\begin{align} 1+1+28 \\ 10+10+10 \\ 1+2+27 \\ ... \end {align}$

Answer 1

Las ideas de este método es conocido como burnsides lema en teoría de grupos.

Como usted ha señalado, el número de enteros positivos soluciones a $a+b+c=30$ ${29 \choose 2}=406$ por las estrellas y barras. Sin embargo, más de la cuenta el total debido a que los números son indistinguibles.

¿Cuántas veces es más contar? Si todos los números son los mismos, I. e. $a=b=c$, entonces solo hay una manera.

Si dos números son iguales, entonces se $2a+c=30$, y hay 14 formas correspondientes a $a=1$ 14. No obstante, debemos doble recuento $a=b=c$, por lo que hay 13 maneras. Cada uno de estos 13 maneras llevaría a 39 formas si los números eran indistinguibles.

Ahora, de los 406 distinguidas maneras, permite restar fuera de la $1+39=40$ distinguido formas mencionadas anteriormente, lo que nos da 366. Estos corresponden a distintos a, b, c valores. Cada una de estas formas se cuentan 6 veces. Por lo tanto, hay $366/6=61$ indiferente maneras.

Ahora añadimos de nuevo el 13 de distinción de los dos mismos una diferente, y el 1 de distinción de tres de los mismos, y llegamos $61+13+1=75$

Answer 2

Si queremos que la respuesta a un pequeño problema como este, podemos enumerar de forma sistemática y contar.

Solo se tiene en cuenta el número de particiones de $30$ a $3$ partes. La misma idea puede ser utilizado para producir una fórmula explícita para el número de particiones de $n$ a $3$ partes. Para uno de los avisos de un patrón simple. Si queremos $4$ partes, una idea similar obras. En principio, lo que utilizamos a continuación es una recurrencia, por la facilidad de $2$ partes al menos fáciles de $3$ partes.

Hacemos una lista por el elemento más pequeño en la partición:

Más pequeño $10$: $1$ camino

Más pequeño $9$: $2$ maneras.

Más pequeño $8$: $4$ maneras (en un próximo es$8$$11$)

Más pequeño $7$: $5$ formas

Más pequeño $6$: $7$ formas (próxima $6$$12$)

Más pequeño $5$: $8$ formas

Más pequeño $4$: $10$ maneras.

Más pequeño $3$: $11$ formas

Más pequeño $2$: $13$ formas

Más pequeño $1$: $14$ formas (próxima $1$$14$)

Nota el buen patrón de aumento de los números. Ahora agregue.

De otra manera: El siguiente es otro directo del enfoque computacional. Deje $f(n)$ el número de particiones de $n$ a $3$ partes. La parte más pequeña puede ser (i) mayor que $1$ o (ii) igual a $1$.

En el Caso (i), mediante la eliminación de una $1$ de cada parte, tenemos una partición de $n-3$, y tenemos todas las particiones de $n-3$ de esta manera.

Para contar el Caso (ii) posibilidades, tenga en cuenta que debemos partición $n-1$ en dos partes. Si $n-1$ es impar , esto se puede hacer en $(n-2)/2$ maneras. Si $n-1$ es incluso puede hacerse en $(n-1)/2$ maneras.

Así hemos obtenido la recurrencia $f(n)=f(n-3)+(n-2)/2$ si $n$ es aún, y $f(n)=f(n-3)+(n-1)/2$ si $n$ es impar.

Armado con esta recurrencia, se puede a $n=30$ rápidamente por $3$'s de la base de casos $n=3$.