Modified Multinomial formula

I am trying to compute an explicit formula using Mathematica for the following multinomial expression:

$$\sum_{n_{1}+n_{2}+...+n_{M}=N}^{M} {N \choose n_{1},n_{2},...,n_{M }} \cdot n_{i} = ?$$

where $i={1,2,...,M}$ and using

multinomial[n__] := (Plus @@ {n})!/Times @@ (#! & /@ {n})


but I don't know how make the sumatoria over all the index $n_{k}$.

In fact I know the following:

$$\sum_{n_{1}+n_{2}+...+n_{M}=N}^{M} {N \choose n_{1},n_{2},...,n_{M }} = M^{N}$$

but I think that this previous results can not be used in order to obtain the result at the first equation, it's the reason why I am asking for a code in Mathematica that tries to compute this thing in an analytical way.

example:

Taking for example M=N=2 and $i=1$ then I have to obtain:

$$\sum_{n_{1}+n_{2}=2}^{2} {2 \choose n_{1},n_{2}} \cdot n_{1} = {2 \choose 2,0} \cdot 2+{2 \choose 0,2} \cdot 0+{2 \choose 1,1} \cdot 1$$

In fact I I take $i=2$ i would obtain the same:

$$\sum_{n_{1}+n_{2}=2}^{2} {2 \choose n_{1},n_{2}} \cdot n_{2} = {2 \choose 2,0} \cdot 0+{2 \choose 0,2} \cdot 2+{2 \choose 1,1} \cdot 1$$

• Where is your try in Mathematica? – zhk Feb 18 '17 at 17:01
• the problem is that I don't know how make the sumatoria over all the index for an arbitrary M – Joe Feb 18 '17 at 17:05
• Use $\sum_{n_{1}+n_{2}+...+n_{M}=N}^{M} {N \choose n_{1},n_{2},...,n_{M }} x_1^{n_1}\ldots x_N^{n_N} = ( x_1+x_2+\ldots x_N)^{N}$, differentiate over $x_1$ and set all $x_i$ to 1. – yarchik Feb 18 '17 at 17:21
• I think that your comment is incorrect. In my case n_{i} takes different values inside the summatoria, which are precisely the values for the different index – Joe Feb 18 '17 at 17:32
• Based @yarchik's comment, the answer is N M^(N-1). Agrees with Mr.Wizards answer 4 3^(4-1) == 108 (although he had m and n switched). Also agrees with your M=N=2 example. – Carl Woll Feb 18 '17 at 18:40

Given that it doesn't matter which index ($i$) one picks, here's a brute force algebraic approach:

\begin{align*} \sum_{n_1+n_2+\cdots+n_M=N}n_1\binom{N}{n_1,n_2,\cdots,n_M}&=\sum_{n_1=0}^N n_1 \sum_{n_2+n_3+\cdots+n_M=N-n_1}\binom{N}{n_1,n_2,\cdots,n_M}\\ &=\sum_{n_1=0}^N n_1 \sum_{n_2+n_3+\cdots+n_M=N-n_1}\frac{N!}{n_1! n_2!\cdots n_M !}\\ &=\sum_{n_1=0}^N n_1 \sum_{n_2+n_3+\cdots+n_M=N-n_1}\frac{N!}{n_1! n_2!\cdots n_M !}\frac{(N-n_1)!}{(N-n_1)!}\\ &=\sum_{n_1=0}^N n_1 \binom{N}{n_1} \sum_{n_2+n_3+\cdots+n_M=N-n_1}\frac{(N-n_1)!}{n_2!\cdots n_M !}\\ &=\sum_{n_1=0}^N n_1 \binom{N}{n_1}(M-1)^{N-n_1}\\ &=\sum_{n_1=0}^N n_1 \binom{N}{n_1}1^{n_1}(M-1)^{N-n_1}\\ &=N M^{N-1} \end{align*}

And, yes, I know, this doesn't use Mathematica.

• I enjoyed your exposition +1 :) – ubpdqn Mar 31 '17 at 4:54
• Still some niche for us humanoids left. Invigorating (+1). :) – gwr Mar 31 '17 at 6:01
• @gwr It sounds like you watched youtube.com/watch?v=7Pq-S557XQU recently. ;^) – Mr.Wizard Mar 31 '17 at 6:06
• @Mr.Wizard No, I had not, but have now. Maybe we need to implement some Turing test here? I am waiting for Mathematica to tell me, it does not feel like working for me today. Brave new world... :) – gwr Mar 31 '17 at 6:58
• @ubpdqn Good. My approach was simple brute force but yarchik's approach is much more elegant and useful for many situations. I hope it gets fleshed out in Mathematica terms and posted. – JimB Mar 31 '17 at 16:34

Following Carl Woll's comment, correcting $m$ and $n$, and providing a more efficient form:

n = 17;
m = 9;

p = IntegerPartitions[n, {m}, Range[0, n]];

Sum[Total[Permutations[x][[All, 1]] * Multinomial @@ x], {x, p}]

n m^(n - 1)

31501343210481297

31501343210481297


Solved, it would seem.

• Thanks, but the point is try to obtain an analitic expresion, I am not interested in the numerical evaluation – Joe Feb 18 '17 at 18:27
• You could use Multinomial instead. – Carl Woll Feb 18 '17 at 19:07
• @CarlWoll lol -- I missed that completely; the OP said modified multinomial and I just assumed there was a variation, and my memory was too poor to recall the formula without checking. – Mr.Wizard Feb 19 '17 at 4:07