$$\sum_{k_1 + \cdots +k_m =n} \frac{n!}{k_1!\cdots k_m!}. (k_1 + 1).(k_2 + 1)\cdots(k_m + 1) $$
We are given N = M - 2
I read about Multinomial Theorem, this one looks similar to it, are there any ways to calculate this in a easier way. Can this be further generalised?
Hint
The multinomial theorem states $$ (x_1+x_2+\dots+x_m)^n=\sum_{k_1+\dots+k_m=n}\frac{n!}{k_1!\cdots k_m!}x_1^{k_1}\cdots x_m^{k_m} $$ Multiply both sides by $x_1x_2\cdots x_m$: $$ x_1x_2\cdots x_m(x_1+x_2+\dots+x_m)^n=\sum_{k_1+\dots+k_m=n}\frac{n!}{k_1!\cdots k_m!}x_1^{k_1+1}\cdots x_m^{k_m+1} $$ Now, partial differentiate both sides with respect to $x_1$. Note that the $x_1^{k_1+1}$ on the right is replaced with $(k_1+1)x_1^{k_1}$; we have a $k_1+1$ now, which is what you want. Therefore, you should partial differentiate with respect to all the other variables as well. After plugging in $x_1=x_2=\dots=x_m=1$, the RHS is then exactly what you want. All the remains is to compute what the partial differentiating does to the LHS, which will probability get a little messy but should be OK.
It appears that the result of the differentiations is $$ \sum_{S\subseteq \{1,2,\dots,m\}}\left(\prod_{i\in S}x_i\right)\binom{n}{|S|}(|S|)!(x_1+\dots+x_m)^{n-|S|} $$ which after substituting one for all variables implies the summation is $$ \sum_{j=0}^m \binom{m}j\binom{n}jj!\cdot m^{n-j}. $$ This is based on seeing a pattern after trying this for $m=2,3$, so you still need to prove that this actually is correct.