# Closed form of to calculate variation of Pascal's triangle

So if you have Pascal's triangle, I know you can calculate any value in closed form.

   1
1 1
1 2 1
1 3 3 1
....


If we let R be the row number, then we can generate that triangle like this

         C(R,0)
C(R,0) C(R,1)
C(R,0) C(R,1) C(R,2)
C(R,0) C(R,1) C(R,2) CR,3)


with the choose function Choose(row#,column#) but I have a variation on this that looks like this

                     C(R,0)*C(N,0)
C(R,0)*C(N,0) C(R,1)*C(N,1)
C(R,0)*C(N,0) C(R,1)*C(N,1) C(R,2)*C(N,2)
C(R,0)*C(N,0) C(R,1)*C(N,1) C(R,2)*C(N,2) C(R,2)*C(N,3)
....


So at point in Pascals triangle instead of C(N,Column#) you have C(R,Column#)*C(N,Column#). Where R > Column#.

So we can calculate any single value in closed form, but if I wanted to calculate a whole row or subset of a row, is there a closed form for that?

• So you want a function that takes a row number and an interval $[a,b]$ for $a,b\in \mathbb{N}, a \leq b$ and returns a list of numbers? – Symeof Nov 10 '15 at 16:31
• A function that takes a row number r and an interval integer range R that is a subset of [0,r-1] and returns the sum of the terms of R from the variation of pascals triangle. – Carlos Bribiescas Nov 10 '15 at 17:33
• Okay. So it could be any subset of $[0, r-1]$ not just a sub-interval, right? – Symeof Nov 10 '15 at 17:39
• Actually, I had a subinterval in mind, but if you could do any subset then you could do a subinterval – Carlos Bribiescas Nov 10 '15 at 18:35
• Technically, I think $C(n,k)$ is considered not to be a closed form. You can use some form of Stirling's formula to approximate it if $n$ and $k$ are large, or you can compute it by some kind of iterative method, such as multiplying out the factorials or building part of Pascal's triangle. For the sum of a (partial) row of your triangle you can use a similarly iterative method. How big are values of $n$ and $r$ you need to work with? – David K Nov 10 '15 at 22:07

## 1 Answer

To my knowledge there is no [known] closed-form formula to your problem (this link gives a bound to a similar problem: https://mathoverflow.net/questions/17202/sum-of-the-first-k-binomial-coefficients-for-fixed-n).

But we know that $\sum_{k=0}^{n} {n \choose k} = 2^n$, so if your interval is large, you can deduce the sum of the terms that you don't want to $2^n$ and compute the answer more quickly.

[Also, you can use the fact that the triangle is symmetric to speed up computation, by only considering one side and multiplying it by 2 (plus the middle term, if the row has an odd number of terms)]

• I think you misunderstood, let me try to clarify – Carlos Bribiescas Nov 10 '15 at 21:43
• And I mean not that you misunderstood completely, but I could have done a better job of explaining – Carlos Bribiescas Nov 10 '15 at 21:54