Busque en Wikipedia en Estrellas y barras. La discusión allí es bastante clara. Las barras corresponden a sus cruces.
Tu problema es un poco diferente del descrito allí. Para su $M$ se puede plantear el problema de la siguiente manera. Usted tiene $w$ caramelos idénticos, y desea distribuir algunos (incluyendo la posibilidad de $0$ ) o todos ellos entre $s$ (¡no idénticos!) hijos. A continuación, $|M|$ cuenta el número de formas de hacerlo. El problema tratado en Wikipedia prevé regalar todos los caramelos. Pero esto se puede solucionar añadiendo un nuevo "niño" abstracto que obtendrá el resto de los $w$ caramelos, si los niños de verdad no se los llevan todos.
O bien, en términos de ecuaciones y desigualdades, $|M|$ cuenta el número de soluciones $(x_1,\dots, x_s)$ de la desigualdad $x_1+\cdots +x_s\le w$ en enteros no negativos. Esto es lo mismo que el número de soluciones de la ecuación ecuación $x_1+\cdots+x_s+y=w$ en enteros no negativos. Aunque es de ecuaciones de lo que trata el artículo de Wikipedia, su tratamiento se puede trasladar a tu entorno de desigualdades.
Con la forma anterior de tratar $\le w$ el resto debería ser directamente "Estrellas y Barras". Siguiendo con la analogía de los caramelos, el número de formas de distribuir $w$ caramelos entre $n$ niños, con algunos niños recibiendo posiblemente $0$ caramelos, es el mismo que el número de formas de distribuir $w+n$ caramelos entre $n$ niños, con cada niño recibiendo al menos $1$ . (Distribuya el $w+n$ caramelos, al menos $1$ a cada niño. Luego quita $1$ caramelos de cada niño).
Adenda: Describimos una biyección explícita $\varphi$ de $M$ a $N$ . La comprobación de que $\varphi$ es efectivamente una biyección es rutinario, ¡pero haremos todos los detalles! El inconveniente es que la presentación es algo larga, y hace que un procedimiento intuitivamente claro (digamos uno descrito en términos de caramelos y niños) parezca más difícil de lo que realmente es.
Sea $(n_1,n_2,\dots,n_s) \in M$ . Defina $\varphi(n_1,n_2,\dots,n_s)$ por $$\varphi(n_1,n_2,\dots,n_s)=(n_1+1,n_2+1,\dots,n_s+1, w+1 -(n_1+n_2+\cdots+n_s)). \qquad\qquad(\ast)$$ Tenga en cuenta que $\varphi(n_1,n_2,\dots,n_s)$ es un $(s+1)$ -tupla. Dado que $n_1,n_2,\dots, n_s$ están en $\mathbb{N}_0$ Eso es, $\ge 0$ se deduce que $n_1+1,n_2+1,\dots,n_s+1$ son todos $\ge 1$ es decir, están en $\mathbb{N}$ . ¿Y el último componente? $w+1-(n_1+n_2+\cdots+n_s)$ de $\varphi(n_1,n_2,\dots,n_s)$ ? La suma $n_1+n_2+\cdots+n_s$ es $\le w$ ya que $(n_1,n_2,\dots,n_s)\in M$ Así que $w+1-(n_1+n_2+\cdots+n_s) \ge 1$ .
Tenemos que demostrar que $\varphi(n_1,n_2,\dots,n_s)\in N$ . Esto significa que tenemos que demostrar que $$(n_1+1)+(n_2+1)+\cdots +(n_s+1) +(w+1-(n_1+n_2+\cdots+n_s))=w+s+1.$$ Tenga en cuenta que el $n_i$ cancelar. Obtenemos $s$ $1$ de la primera $s$ términos, más $w+1$ del último trimestre, para un total de $w+s+1$ .
A continuación demostramos que $\varphi$ es inyectiva. Supongamos que $\varphi(a_1,a_2,\dots,a_s)=\varphi(b_1,b_2,\dots,b_s)$ . Tenemos que demostrar que $(a_1,a_2,\dots,a_s)=(b_1,b_2,\dots,b_s)$ . Así que sabemos que el $(s+1)$ -tupla $$(a_1+1,a_2+1,\dots ,a_s+1, w+1-(a_1+a_2+\cdots+a_s))$$ es el mismo que el $(s+1)$ -tupla $$(b_1+1,b_2+1,\dots ,b_s+1, w+1-(b_1+b_2+\cdots+b_s)).$$ Es inmediato que $a_1=b_1$ , $a_2=b_2$ y así sucesivamente $(a_1,a_2,\dots,a_s)=(b_1,b_2,\dots,b_s)$ .
Por último, demostramos que $\varphi$ es suryectiva. Supongamos que el $(s+1)$ -tupla $(c_1,c_2,\dots, c_s,c_{s+1})\in N$ . Defina $(a_1,a_2,\dots,a_s)$ por $a_i=c_i-1$ . Así que $c_i=a_i+1$ .
Desde el $c_i$ son por definición $\ge 1$ El $a_i$ son $\ge 0$ . Desde $c_1+c_2+\cdots+c_s+c_{s+1}=w+s+1$ tenemos $c_1+c_2+\cdots+c_s\le w+s$ y, por lo tanto $a_1+a_2+\cdots+a_s \le w$ . Por fin, $$c_{s+1}=w+s+1-(c_1+c_2+\cdots+c_s)=w+1-(a_1+a_2+\cdots+a_s),$$ y por lo tanto por la definición $(\ast)$ de $\varphi$ tenemos $$\varphi(a_1,a_2,\dots,a_s)=(c_1,c_2,\dots, c_s, c_{s+1}).$$
