2
$\begingroup$

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

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

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:

\begin{equation} \sum_{n_{1}+n_{2}+...+n_{M}=N}^{M} {N \choose n_{1},n_{2},...,n_{M }} = M^{N} \end{equation}

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:

\begin{equation} \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\end{equation}

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

\begin{equation} \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\end{equation}

Improve this question
$\endgroup$
8
  • $\begingroup$ Where is your try in Mathematica? $\endgroup$ – zhk Feb 18 '17 at 17:01
  • $\begingroup$ the problem is that I don't know how make the sumatoria over all the index for an arbitrary M $\endgroup$ – Joe Feb 18 '17 at 17:05
  • 3
    $\begingroup$ 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. $\endgroup$ – yarchik Feb 18 '17 at 17:21
  • $\begingroup$ 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 $\endgroup$ – Joe Feb 18 '17 at 17:32
  • 3
    $\begingroup$ 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. $\endgroup$ – Carl Woll Feb 18 '17 at 18:40
5
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ I enjoyed your exposition +1 :) $\endgroup$ – ubpdqn Mar 31 '17 at 4:54
  • 1
    $\begingroup$ Still some niche for us humanoids left. Invigorating (+1). :) $\endgroup$ – gwr Mar 31 '17 at 6:01
  • 1
    $\begingroup$ @gwr It sounds like you watched youtube.com/watch?v=7Pq-S557XQU recently. ;^) $\endgroup$ – Mr.Wizard Mar 31 '17 at 6:06
  • $\begingroup$ @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... :) $\endgroup$ – gwr Mar 31 '17 at 6:58
  • $\begingroup$ @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. $\endgroup$ – JimB Mar 31 '17 at 16:34
3
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Thanks, but the point is try to obtain an analitic expresion, I am not interested in the numerical evaluation $\endgroup$ – Joe Feb 18 '17 at 18:27
  • 2
    $\begingroup$ You could use Multinomial instead. $\endgroup$ – Carl Woll Feb 18 '17 at 19:07
  • $\begingroup$ @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. $\endgroup$ – Mr.Wizard Feb 19 '17 at 4:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.