Probar una igualdad que involucra composiciones de un entero

Question

Vamos a considerar las diversas representaciones de un número natural $n \geq 4$ como suma de enteros positivos, en los que el orden de los sumandos es importante (es decir, composiciones). La tarea es demostrar el número de $3$ aparece en total $n2^{n-5}$ veces en todos ellos.

Sé que hay $2^{n-1}$ composiciones de $n$. Sin embargo, no tengo ni idea de cómo contar sólo aquellos que involucran a los número(s) $3$. No puedo pensar en cualquier sensato generar función de esta. Tal vez hay un buen combinatoria interpretación de la fórmula, lo que no puedo entender? Alguien podría prestarme una mano con el manejo de este problema?

Answer 1

El número de $k$plazo composiciones de $n$${n-1} \choose {k-1}$$k \le n$.
Habrá ${n-4} \choose {k-2}$ apariciones de $3$ como el primer término de una $k$-plazo de la composición (es decir, el número de $k-1$plazo composiciones de $n-3$). Pero dado que cualquier permutación de una composición es una composición, por $1 \le j \le k$ el número de ocurrencias de $3$ como el $j$'el plazo de un $k$plazo la composición de $n$${n-4} \choose {k-2}$. Por lo que el número total de apariciones de $3$ $k$plazo composiciones de $n$$k {{n-4} \choose {k-2}}$. Ahora se suma esta de$k = 1$$n-2$.

Answer 2

Aunque es posible hacerlo usando las funciones de generación, que no es el mejor método. (A menos que haya sido específicamente pedido hacer esto mediante la generación de funciones!)

Si usted ha aprendido acerca de las composiciones hay una buena probabilidad de que usted ha aprendido acerca de los puntos y las barras en representación de ellos. Una composición de $n$ puede ser representado por $n$ puntos, con barras de separación de las piezas. Por ejemplo, podemos representar la composición de la $10 = 2 + 4 + 3 + 1$

$$ \cdot \cdot | \cdot \cdot \cdot \cdot | \cdot \cdot \cdot | \cdot $$

Cualquier composición de 10 puede ser escrito como 10 $\cdot$s; cada una de las 9 posiciones entre dos puntos puede contener un $|$ o no, dando una prueba de que no se $2^9$ composiciones de $10$. (Por supuesto, esto se generaliza; en general hay $2^{n-1}$ composiciones de $n$.)

Esta composición puede ser escrito como (algunas partes que suman 6) + 3 + (algunas partes que suman 1). Cuántas de estas composiciones hay? Lo que sobre para las otras posiciones en las que la parte $3$ podría ocurrir?

Answer 3

Parece que la generación de la función de enfoque es bastante simple aquí. Tenemos por parte de la inspección, que el bivariado de generación de función de composiciones con el número tres marcado es $$M(z, u) = \sum_{q\ge 1}\left(\frac{z}{1-z} - z^3 + uz^3\right)^q.$$ Por lo tanto, la generación de la función de el número total de ocurrences es $$\left.\frac{d}{du} M(z, u)\right|_{u=1} = \left. \sum_{q\ge 1} p \left(\frac{z}{1-z} z^3 + uz^3\right)^{p-1} \times z^3 \right|_{u=1} \\= z^3 \sum_{q\ge 1} p \left(\frac{z}{1-z}\right)^{p-1} = z^3 \frac{1}{(1-z/(1-z))^2} = z^3 \frac{(1-z)^2}{(1-2z)^2} \\ = z^3 \left(\frac{1}{1-2z} + \frac{z^2}{(1-2z)^2}\right).$$ A la conclusión de extracto de los coeficientes de llegar $$[z^{n-3}] \left(\frac{1}{1-2z} + \frac{z^2}{(1-2z)^2}\right) = 2^{n-3} + [z^{n-5}] \frac{1}{(1-2z)^2} \\ = 2^{n-3} + (n-4) 2^{n-5} = 4 \times 2^{n-5} + (n-4) 2^{n-5} = n 2^{n-5}.$$