How to calculate sum over set of vectors $\sum\limits_{\vec q\in E}f(\vec q)$? Summation over integers is easy, since there are many rules that we can follow. For example,$$
\sum\limits_{i=1}^ni=\frac{n(n+1)}{2}.
$$
A summation can also be taken over a set of vector of integers $E\subset\mathbb{Z}_+^N$ as $\sum\limits_{\vec q\in E}f(\vec q)$. An example when $N=3$:\begin{align*}
\sum_{|\vec q|\le 2}|\vec q|&=|(0,0,0)|+|(1,0,0)|+|(0,1,0)|+|(0,0,1)|\\
&\quad +|(1,1,0)|+|(2,0,0)|+|(0,1,1)|+|(0,0,2)|+|(1,0,1)|+|(0,2,0)|=15.\end{align*} However this is much harder to find a close form, as here is an example from an algorithm that iterates on a set of vectors.
Let $\vec q=(q_1,q_2,\cdots,q_N)\in\mathbb{Z}_+^N\cup\{(0,\cdots,0)\}$. What is a close form of
$$\sum_{\{\vec q:|\vec q|\le M\}}|\vec q|\sum_{n=0}^M\sum_{\{\vec l:0\le\vec l\le\vec q,|\vec l|\ge n\}}1$$
in terms of $M$, $N$? Here $\vec l\le\vec q$ means every entry of $\vec l$ is less than or equal to that of $\vec q$. 
If an exact closed form is difficult, then a tight upper-bound or approximation is acceptable. If bounds are difficult, then only consider when $M<<N$ is acceptable.

If we replace $\{\vec l:0\le\vec l\le\vec q\}$ by $\{\vec l:0\le|\vec l|\le|\vec q|\}$, then by a stars-and-bars argument above is approximately
$$\sum_{|\vec q|=0}^M\begin{pmatrix}|\vec q|+N\cr N\end{pmatrix}|\vec q|\sum_{n=0}^M\sum_{|\vec l|=n}^{|\vec q|}\begin{pmatrix}|\vec l|+N\cr N\end{pmatrix}=\sum_{m=0}^M\begin{pmatrix}m+N\cr N\end{pmatrix}m\sum_{n=0}^M\sum_{k=n}^m\begin{pmatrix}k+N\cr N\end{pmatrix}$$
First, how to then get a closed form of this? Second, this is not a very good approximation because eventually it is hard to express$$
\sum_{n=0}^M\sum_{\{\vec l:0\le\vec l\le\vec q,|\vec l|\ge n\}}1$$
as a function of $|\vec q|$ instead of $\vec q$. A more precise calculation yields
$$\sum_{\{\vec q:|\vec q|\le M\}}|\vec q|\sum_{n=1}^M \left[\prod_{i=1}^Nq_i-\begin{pmatrix}N+n\cr N\end{pmatrix}\right].$$
Can anyone give a close form of this?
 A: 
We obtain
  \begin{align*}
\color{blue}{\sum_{{ 0\leq |\vec q|\le M}\atop{\vec q\geq \vec 0}}}&\color{blue}{|\vec q|\sum_{n=0}^M\sum_{{\vec 0\le\vec l\le\vec q}\atop{|\vec l|\ge n}}1}\\
&=\sum_{{0\leq n\leq |\vec l|\leq |\vec q|\leq M}\atop{\vec 0\leq \vec l\leq \vec q}}|\vec q|\tag{1}\\
&=\sum_{{0\leq |\vec l|\leq |\vec q|\leq M}\atop{\vec 0\leq \vec l\leq \vec q}}\left(|\vec l|+1\right)|\vec q|\tag{2}\\
&=\sum_{{0\leq |\vec l|\leq  M}\atop{\vec 0\leq \vec l}}\left(|\vec l|+1\right)\sum_{{|\vec l|\leq  |\vec q|\leq M}\atop{ \vec l\leq \vec q}}|\vec q|\tag{3}\\
&=\sum_{{0\leq |\vec l|\leq  M}\atop{\vec 0\leq \vec l}}\left(|\vec l|+1\right)
\sum_{{0\leq  |\vec{q^\prime}|\leq M-|\vec l|}\atop{\vec  0\leq \vec {q^\prime}}}\left(|\vec {q^\prime}|+|\vec l|\right)\tag{4}\\
&=\sum_{|\vec l|=0}^M\left(|\vec l|+1\right)\binom{|\vec l|+N-1}{|\vec l|}
\sum_{|\vec {q^{\prime}}|=0}^{M-|\vec l|}\left(|\vec {q^\prime}|+|\vec l|\right)\binom{|\vec {q^\prime}|+N-1}{|\vec {q^\prime}|}\tag{5}\\
&=\sum_{j=0}^M\left(j+1\right)\binom{j+N-1}{j}\sum_{k=0}^{M-j}\left(k+j\right)\binom{k+N-1}{k}\tag{6}\\
&=\sum_{j=0}^M\left(j+1\right)\binom{j+N-1}{j}\left(N\binom{N+M-j}{M-j-1}+j\binom{N+M-j}{M-j}\right)\tag{7}\\
&=N\sum_{j=0}^{M-1}\left(j+1\right)\binom{j+N-1}{j}\binom{N+M-j}{M-j-1}\\
&\qquad+\sum_{j=1}^Mj(j+1)\binom{N+M-j}{M-j}\\
&=N^2\sum_{j=1}^{M-1}\binom{j+N-1}{j-1}\binom{N+M-j}{M-j-1}+N\binom{2N+M}{M-1}\\
&\qquad+N\sum_{j=1}^M(j+1)\binom{j+N-1}{j-1}\binom{N+M-j}{M-j}\tag{8}\\
&=N^2\sum_{j=0}^{M-2}\binom{j+N}{j}\binom{N+M-j-1}{M-2-j}+N\binom{2N+M}{M-1}\\
&\qquad+N\sum_{j=0}^{M-1}(j+2)\binom{j+N}{j}\binom{N+M-j-1}{M-j-1}\\
&=N^2\binom{2N+M}{M-2}+N\binom{2N+M}{M-1}\\
&\qquad+N(N+1)\sum_{j=1}^{M-1}\binom{j+N+1}{j}\binom{N+M-j-2}{M-j-2}+2N\binom{2N+M}{M-1}\\
&=N^2\binom{2N+M}{M-2}+N\binom{2N+M}{M-1}\\
&\qquad+N(N+1)\binom{2N+M}{M-2}+2N\binom{2N+M}{M-1}\\
&\,\,\color{blue}{=N(2N+1)\binom{2N+M}{M-2}+3N\binom{2N+M}{M-1}}
\end{align*}

Comments:


*

*In (1) we rewrite the index region to better see what's going on.

*In (2) we respect the index $0\leq n\leq |\vec l|$ by the factor $|\vec l|+1$.

*In (3) we split the index region conveniently.

*In (4) we substitute $\vec{q^\prime} = \vec q - \vec l$ in order to start the summation of the inner sum from $\vec 0$.

*In (5) we use in both sums that the number of weak compositions is
\begin{align*}
\sum_{{\vec l\geq \vec 0}\atop{|\vec l|=M}}1=\binom{M+N-1}{M}\qquad\qquad \vec l\in \mathbb{N}_0^{N}
\end{align*} 

*In (6) we use the substitution $j=|\vec l|$ and $k=|\vec {q^{\prime}}|$. Note that in (5) integers only and no longer any $N$-tupel are used for summation.

*In (7) we multiply out the inner sum and use the binomial identities
\begin{align*}
\color{blue}{\sum_{j=0}^K\binom{j+N-1}{j}}&=\sum_{j=0}^K[z^j](1+z)^{j+N-1}\\
&=[z^0](1+z)^{N-1}\sum_{j=0}^k\left(1+\frac{1}{z}\right)^j\\
&=[z^0](1+z)^{N-1}\frac{\left(1+\frac{1}{z}\right)^{K+1}-1}{\left(1+\frac{1}{z}\right)-1}\\
&=[z^{-1}](1+z)^{N-1}\left(\left(1+\frac{1}{z}\right)^{K+1}-1\right)\\
&=[z^K](1+z)^{N+K}\\
&\,\,\color{blue}{=\binom{N+K}{K}}\\
\color{blue}{\sum_{j=0}^Kj\binom{j+N-1}{j}}&=N\sum_{j=1}^K\binom{j+N-1}{j-1}=N\sum_{j=0}^{K-1}\binom{j+N}{j}\\
&\,\,\color{blue}{=N\binom{N+K}{K-1}}
\end{align*}

*In (8) and in the following lines we use consequently two identities. The binomial identity
\begin{align*}
q\binom{p}{q}=(p-q+1)\binom{p}{q-1}
\end{align*}
and the Chu-Vandermonde Identity
in disguise:
\begin{align*}
\sum_{j=0}^K\binom{j+M}{j}\binom{N-j}{K-j}&=\sum_{j=0}^K\binom{-M-1}{j}(-1)^j \binom{-N+K-1}{K-j}(-1)^{K-j}\\
&= \binom{-M-N+K-2}{K}(-1)^K\\
&=\binom{M+N+1}{K}
\end{align*}
A: For each possible $m=|q|$, we can use stars-and-bars to count the partitions:
$$\sum_{m=0}^M  \binom{m+N-1}{m}$$
Notice each binomial term has the top and bottom values $1$ more than the previous term. Repeatedly using the fact that $$\binom{n+1}{k+1} = \frac{n+1}{k+1} \binom n k $$
We can derive the closed form 
$$\frac{M+1}{N} \binom{M+N}{M+1}$$
For example with $M=2, N=3$ we get $\binom 5 3 = 10$. 
