How many distinct sum of products are possible? Given a $k{\times}k$ matrix P, how many distinct sum of product values are possible for $\sum\limits_{i=1}^{k}\sum\limits_{j=1}^{k} i{\times}j{\times} P(i,j)$.
Conditions: elements in P are integers that lie in the range $[0,n]$ and $\sum\limits_{i=1}^{k}\sum\limits_{j=1}^{k} P(i,j) = n$.
 A: A possible approach:
The minimum is $n$ achieved when $P(1,1)=n$, and the maximum is $k^2n$ achieved when $P(k,k)=n$. The range of integers including these extremes has $(k^2-1)n+1$ integers.  
If $n$ is big enough compared with $k$, I think that you cannot achieve any number 


*

*strictly between $k^2n-k$ (when $P(k,k)=n-1$ and $P(k,k-1)=1$) and $k^2n$, or 

*strictly between $k^2n-2k+1$ (when  $P(k,k)=n-1$ and  $P(k-1,k-1)=1$) and  $k^2n-k$, or  

*strictly between $k^2n-3k+2$  (when  $P(k,k)=n-1$ and  $P(k-1,k-2)=1$) and  $k^2n-2k$ (when $P(k,k)=n-2$ and $P(k,k-1)=2$), 


and you continue this pattern.  For example $k^2n-3k+1$ is achievable when $P(k,k)=n-2$,   $P(k,k-1)=1$ and $P(k-1,k-1)=1$.   
If you continue this pattern, at first glance you seem to be excluding $(k-1)+(k-2)+(k-3)+\cdots = \frac{k(k-1)}{2}$ terms, leaving $k^2n-n-\frac{k^2}{2}+ \frac{k}{2}+1$ terms.   
I have not checked this, but it seems to give the correct answers when $n=1$ and $k=1$, when $n=2$ and $k=1$, and when $n=2$ and $k=2$, but not when $n=1$ and $k=2$.
