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$
  • $\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 '15 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 '15 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 '15 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 '15 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 '15 at 22:07
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$
  • $\begingroup$ I think you misunderstood, let me try to clarify $\endgroup$ – Carlos Bribiescas Nov 10 '15 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 '15 at 21:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.