How to calculate sum over set of vectors $\sum\limits_{\vec q\in E}f(\vec q)$?

Question

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?

Answer 1

$\def\peq{\mathrel{\phantom{=}}{}}$Lemma 1: For any $a, b \in \mathbb{N}$, $a \geqslant 1$, the number of non-negative integer solutions to $\sum\limits_{k = 1}^ a x_k = b$ is $\dbinom{a + b - 1}{a - 1}$.

Lemma 2: For any $a, b, c \in \mathbb{N}$,$$ \sum_{k = 0}^c \binom{a + k}{a} \binom{b + c - k}{b} = \binom{a + b + c + 1}{a + b +1 }. $$

Proof of lemma: Define $\displaystyle f(a, b, c) = \sum_{k = 0}^c \binom{a + k}{a} \binom{b + c - k}{b}$. It is well-known that$$ f(a, 0, c) = \dbinom{a + c + 1}{a + 1}. $$ Note that\begin{align*} f(a, b, c + 1) - f(a, b, c) &= \sum_{k = 0}^{c + 1} \binom{a + k}{a} \binom{b + c + 1 - k}{b} - \sum_{k = 0}^c \binom{a + k}{a} \binom{b + c - k}{b}\\ &= \binom{a + c + 1}{a} + \sum_{k = 0}^c \binom{a + k}{a} \left( \binom{b + c + 1 - k}{b} - \binom{b + c - k}{b} \right)\\ &= \binom{a + c + 1}{a} + \sum_{k = 0}^c \binom{a + k}{a} \binom{b + c - k}{b - 1}\\ &= \sum_{k = 0}^{c + 1} \binom{a + k}{a} \binom{b + c - k}{b - 1} = f(a, b - 1, c + 1), \end{align*} then the conclusion follows by induction on $c$.

Now back to the question.\begin{align*} &\peq \sum_{|q| \leqslant M} |q| \sum_{n = 0}^M \sum_{\substack{0 \preccurlyeq l \preccurlyeq q \\ |l| \geqslant n}} 1 = \sum_{|q| \leqslant M} \sum_{n = 0}^M \sum_{\substack{0 \preccurlyeq l \preccurlyeq q \\ |l| \geqslant n}} |q| = \sum_{|l| \leqslant M} \sum_{n = 0}^{|l|} \sum_{\substack{q \succcurlyeq l \\ |q| \leqslant M}} |q|\\ &= \sum_{|l| \leqslant M} \left( \sum_{n = 0}^{|l|} 1 \right) \Biggl( \sum_{\substack{q \succcurlyeq l \\ |q| \leqslant M}} |q| \Biggr) = \sum_{|l| \leqslant M} (|l| + 1) \smash[b]{\sum_{\substack{q \succcurlyeq l \\ |q| \leqslant M}}} |q|\\ &= \sum_{|l| \leqslant M} (|l| + 1) \sum_{m = |l|}^M \sum_{\substack{q \succcurlyeq l \\ |q| = m}} |q| = \sum_{|l| \leqslant M} (|l| + 1) \sum_{m = |l|}^M m \sum_{\substack{q \succcurlyeq l \\ |q| = m}} 1. \tag{1} \end{align*} Because by Lemma 1,$$ \sum_{\substack{q \succcurlyeq l \\ |q| = m}} 1 = \sum_{\substack{q' \succcurlyeq 0 \\ |q'| = m - |l|}} 1 = \binom{m - |l| + N - 1}{N - 1}, $$ then\begin{align*} (1) &= \sum_{|l| \leqslant M} (|l| + 1) \sum_{m = |l|}^M m \binom{m - |l| + N - 1}{N - 1}\\ &= \sum_{j = 0}^M \sum_{|l| = j} (|l| + 1) \sum_{m = |l|}^M m \binom{m - |l| + N - 1}{N - 1}\\ &= \sum_{j = 0}^M (j + 1) \sum_{m = j}^M m \binom{m - j + N - 1}{N - 1} \sum_{|l| = j} 1\\ &= \sum_{j = 0}^M (j + 1) \binom{j + N - 1}{N - 1} \sum_{m = j}^M m \binom{m - j + N - 1}{N - 1}, \tag{2} \end{align*} where the last step again uses Lemma 1. Because by Lemma 2 with $b = 0$,\begin{align*} \sum_{m = j}^M m \binom{m - j + N - 1}{N - 1} &= \sum_{m = j}^M (m - j) \binom{m - j + N - 1}{N - 1} + \sum_{m = j}^M j \binom{m - j + N - 1}{N - 1}\\ &= N \sum_{m = j + 1}^M \binom{m - j + N - 1}{N} + j \sum_{m = j}^M \binom{m - j + N - 1}{N - 1}\\ &= N \sum_{m = 0}^{M - j - 1} \binom{m + N}{N} + j \sum_{m = 0}^{M - j} \binom{m + N - 1}{N - 1}\\ &= N \binom{M + N - j}{N + 1} + j \binom{M + N - j}{N}, \end{align*} then\begin{align*} (2) &= N \sum_{j = 0}^{M - 1} (j + 1) \binom{j + N - 1}{N - 1} \binom{M + N - j}{N + 1} + \sum_{j = 0}^M j(j + 1) \binom{j + N - 1}{N - 1} \binom{M + N - j}{N}\\ &= N \sum_{j = 0}^{M - 1} j \binom{j + N - 1}{N - 1} \binom{M + N - j}{N + 1} + N \sum_{j = 0}^{M - 1} \binom{j + N - 1}{N - 1} \binom{M + N - j}{N + 1}\\ &\peq + \sum_{j = 1}^M j(j - 1) \binom{j + N - 1}{N - 1} \binom{M + N - j}{N} + \sum_{j = 1}^M 2j \binom{j + N - 1}{N - 1} \binom{M + N - j}{N}\\ &= N^2 \sum_{j = 1}^{M - 1} \binom{j + N - 1}{N} \binom{M + N - j}{N + 1} + N \sum_{j = 0}^{M - 1} \binom{j + N - 1}{N - 1} \binom{M + N - j}{N + 1}\\ &\peq + N(N + 1) \sum_{j = 2}^M \binom{j + N - 1}{N + 1} \binom{M + N - j}{N} + 2N \sum_{j = 1}^M \binom{j + N - 1}{N} \binom{M + N - j}{N}\\ &= N^2 \sum_{j = 0}^{M - 2} \binom{j + N}{N} \binom{M + N - j - 1}{N + 1} + N \sum_{j = 0}^{M - 1} \binom{j + N - 1}{N - 1} \binom{M + N - j}{N + 1}\\ &\peq + N(N + 1) \sum_{j = 0}^{M - 2} \binom{j + N + 1}{N + 1} \binom{M + N - j - 2}{N} + 2N \sum_{j = 0}^{M - 1} \binom{j + N}{N} \binom{M + N - j - 1}{N}\\ &= N^2 \binom{M + 2N}{2N + 2} + N \binom{M + 2N}{2N + 1} + N(N + 1) \binom{M + 2N}{2N + 2} + 2N \binom{M + 2N}{2N + 1}\\ &= N(2N + 1) \binom{M + 2N}{2N + 2} + 3N \binom{M + 2N}{2N + 1}, \end{align*} where the last but one step again uses Lemma 2. Therefore,$$ \sum_{|q| \leqslant M} |q| \sum_{n = 0}^M \sum_{\substack{0 \preccurlyeq l \preccurlyeq q \\ |l| \geqslant n}} 1 = N(2N + 1) \binom{M + 2N}{2N + 2} + 3N \binom{M + 2N}{2N + 1}. $$

---

If the expression $\sum\limits_{\substack{0 \preccurlyeq l \preccurlyeq q \\ |l| \geqslant n}} 1$ is defined to be $1$ when $\{l \mid 0 \preccurlyeq l \preccurlyeq q,\ |l| \geqslant n\} = \varnothing$, note that$$ \{l \mid 0 \preccurlyeq l \preccurlyeq q,\ |l| \geqslant n\} = \varnothing \Longleftrightarrow n \geqslant |q| + 1, $$ then the result will increase by\begin{align*} &\peq \sum_{|q| \leqslant M} |q| \sum_{n = |q| + 1}^M 1 = \sum_{|q| \leqslant M} |q| (M - |q|) = \sum_{m = 0}^M \sum_{|q| = m} |q| (M - |q|)\\ &= \sum_{m = 0}^M m(M - m) \sum_{|q| = m} 1 = \sum_{m = 0}^M m(M - m) \binom{m + N - 1}{N - 1}\\ &= -\sum_{m = 0}^M m(m - 1) \binom{m + N - 1}{N - 1} + (M - 1) \sum_{m = 0}^M m \binom{m + N - 1}{N - 1}\\ &= -N(N + 1) \sum_{m = 2}^M \binom{m + N - 1}{N + 1} + (M - 1)N \sum_{m = 1}^M \binom{m + N - 1}{N}\\ &= -N(N + 1) \sum_{m = 0}^{M - 2} \binom{m + N + 1}{N + 1} + (M - 1)N \sum_{m = 0}^{M - 1} \binom{m + N}{N}\\ &= -N(N + 1) \binom{M + N}{N + 2} + (M - 1)N \binom{M + N}{N + 1}. \end{align*}

Answer 2

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$.

Answer 3

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*}