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}

$\endgroup$
8
  • $\begingroup$ Where is your try in Mathematica? $\endgroup$
    – zhk
    Feb 18, 2017 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, 2017 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, 2017 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, 2017 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, 2017 at 18:40

2 Answers 2

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.

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

$\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, 2017 at 18:27
  • 2
    $\begingroup$ You could use Multinomial instead. $\endgroup$
    – Carl Woll
    Feb 18, 2017 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, 2017 at 4:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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