1
$\begingroup$

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?

$\endgroup$
7
  • $\begingroup$ 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? $\endgroup$
    – Symeof
    Nov 10, 2015 at 16:31
  • $\begingroup$ 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. $\endgroup$
    – Carlos Bribiescas
    Nov 10, 2015 at 17:33
  • $\begingroup$ Okay. So it could be any subset of $[0, r-1]$ not just a sub-interval, right? $\endgroup$
    – Symeof
    Nov 10, 2015 at 17:39
  • $\begingroup$ Actually, I had a subinterval in mind, but if you could do any subset then you could do a subinterval $\endgroup$
    – Carlos Bribiescas
    Nov 10, 2015 at 18:35
  • 1
    $\begingroup$ 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? $\endgroup$
    – David K
    Nov 10, 2015 at 22:07

1 Answer 1

Reset to default
0
$\begingroup$

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)]

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .