Contar de dos maneras: $m^3 = 6 {m \choose 3} + 6 {m \choose 2} + m \quad \forall m \in \mathbb{N}$

Question

Tengo un problema para contar de dos maneras. Cómo puedo hacer para probar:

$$m^3 = 6 {m \choose 3} + 6 {m \choose 2} + m \quad \forall m \in \mathbb{N}$$

Veo que sustituyendo las fórmulas y simplificando se conseguiría la igualdad. No estoy seguro de poder producir una prueba combinatoria (pero eso no es necesario para el curso en el que estoy).

Answer 1

Escoge $3$ elementos de un conjunto de $m$ elementos, las repeticiones permitidas y el seguimiento del orden del primer, segundo y tercer elemento.

El lado izquierdo cuenta claramente el número de formas de hacerlo. El lado derecho lo rompe eligiendo un conjunto desordenado y ordenándolo. (Hay una cosa más con el coeficiente del ${m \choose 2}$ término dejaré que averigües cuál es).

Answer 2

Utilizamos el hecho de que las potencias habituales pueden expresarse como una combinación de factoriales descendentes $x^{(k)}$ así como la relación $x^{(k)}=k!\binom{x}{k}$ para obtener la serie:

$$x^n=\sum_{j=0}^n \left\{n \atop j\right\}j!\binom{x}{j}$$

donde $\left\{n \atop j\right\}$ es un Número de subconjunto de Stirling . (Véase la página 262 de Matemáticas concretas para una justificación). Para $n=3$ entonces tenemos

$$\begin{align*}x^3&=0!\left\{3 \atop 0\right\}\binom{x}{0}+1!\left\{3 \atop 1\right\}\binom{x}{1}+2!\left\{3 \atop 2\right\}\binom{x}{2}+3!\left\{3 \atop 3\right\}\binom{x}{3}\\&=1\times0\times\binom{x}{0}+1\times1\times\binom{x}{1}+2\times3\times\binom{x}{2}+6\times1\times\binom{x}{3}\\&=x+6\binom{x}{2}+6\binom{x}{3}\end{align*}$$

y ¡listo!