<p>Our input is a $(n+1)\times (n+1)$ table filled with some value (integer) for each leftmost and bottom cell $l_i,b_i$ as in the figure. 
We wish to compute the value of all upper and rightmost cells $u_i$ and $r_i$ ($1\leq i\leq n$) 
when each cell of the table is filled recursively according 
to the equation $T(x,y)=T(x,y-1)+T(x-1,y)$ for each $x,y\geq 1$. 
<img src="https://i.sstatic.net/Ubuhd.jpg" alt="picture to illustrate problem input"></p>

<p>If we compute naively the $u_i,r_i$ by filling the table, or summing corresponding binomial coefficients, the complexity is $\Theta(n^2)$. 
Is this a lower bound for the problem or is there any way to compute all $u_i, r_i$ in $o(n^2)$? 
If so, does the technique extend to rectangular tables?</p>

CC BY-SA 3.0
2013-12-19T21:02:36.507Z
You can assume that you have just the upper left triangle and the values are on the diagonal without loss of generality. So this question is essentially the same problem as computing 
$$\sum_{0 \leq i \leq n} {n \choose i} a_i$$
Kaveh
CC BY-SA 3.0
2013-12-23T14:09:53.970Z
@kaveh:
Thanks. 
I suppose that the 'upper left triangle' means: we can consider independently the contribution originating from the $b_i$ and those from the $l_i$. Then indeed we only need to compute $O(n)$ sums of $O(n)$ binomial coefficients (I actually hinted at this in the question: 'summing binomial coefficients').  However, 

I do not see how to compute $\sum_{0 \leq i \leq j} {j \choose i} a_i$ for all 
$j\in \{1,...,n\}$ in $o(n^2)$.

Maybe this is because I did not understand the part about 'values are on the diagonal'?
Joseph Stack
<ds.algorithms><co.combinatorics><integer-lattice>
Complexity for computing weighted number of paths on integer lattice
Joseph Stack
# Complexity for computing weighted number of paths on integer lattice

(Asked by: username_0 on 2013-12-17)

Our input is a $(n+1)\times (n+1)$ table filled with some value (integer) for each leftmost and bottom cell $l\_i,b\_i$ as in the figure.
We wish to compute the value of all upper and rightmost cells $u\_i$ and $r\_i$ ($1\leq i\leq n$)
when each cell of the table is filled recursively according
to the equation $T(x,y)=T(x,y-1)+T(x-1,y)$ for each $x,y\geq 1$.
![picture to illustrate problem input](https://i.sstatic.net/Ubuhd.jpg)

If we compute naively the $u\_i,r\_i$ by filling the table, or summing corresponding binomial coefficients, the complexity is $\Theta(n^2)$.
Is this a lower bound for the problem or is there any way to compute all $u\_i, r\_i$ in $o(n^2)$?
If so, does the technique extend to rectangular tables?

**Tags:** ds.algorithms, co.combinatorics, integer-lattice

> **Comments:**
> **username_1**: You can assume that you have just the upper left triangle and the values are on the diagonal without loss of generality. So this question is essentially the same problem as computing  $$\sum_{0 \leq i \leq n} {n \choose i} a_i$$  
> **username_0**: @kaveh: Thanks.  I suppose that the 'upper left triangle' means: we can consider independently the contribution originating from the $b_i$ and those from the $l_i$. Then indeed we only need to compute $O(n)$ sums of $O(n)$ binomial coefficients (I actually hinted at this in the question: 'summing binomial coefficients').  However,   I do not see how to compute $\sum_{0 \leq i \leq j} {j \choose i} a_i$ for all  $j\in \{1,...,n\}$ in $o(n^2)$.  Maybe this is because I did not understand the part about 'values are on the diagonal'?  

---

## 0 answers

