Efficient Computation of Binomial Coefficients and Applications

Abstract

Binomial coefficients can be computed very efficiently by the construction of Pascal triangle. Analogous to this construction, we shall derive efficient methods to compute bk=i=0k Cki ai etc. Practical applications of such methods include polynomial basis conversion, reparametrisation, and subdivision.

1  Introduction

In interpolation and approximation, polynomials are employed for data fitting [1]. In computational geometry, polynomial curves (e.g., Bézier and B-spline polynomial curves) are used to describe the shape of geometric entities [2-3]. For the purpose of evaluating or manipulating a polynomial, it is often required to convert a polynomial of one basis to another or subdivide an interval over which a polynomial is defined. Accordingly, we shall need to compute the following coefficients:

bk= k

i=0 
Cki ai,    bk= n

i=k 
Cik ai,    bk= k

i=0 
Cn-ik-iai    (k=0, 1, , n)
where,

Cni=

n
i


= n!
(n-i)! i!
are called the binomial coefficients. Assume a table of binomial coefficients is given. Then, a straight forward method to compute, for example, bk=i=0k Cki pi (k=1,2,...,n) is to multiply pi by Cki and then add them together. However, even with the supply of binomial coefficients, this simple method requires n(n-1)/2 multiplications and the same number of additions. In this paper, we shall derive an efficient algorithm to compute bk. Using our method, only n(n-1)/2 additions are needed to compute all bk=i=0k Cki pi (k=0, 1, ..., n) in the absence of a table of binomial coefficients.

Our methods are derived analogously to the construction of Pascal triangle, the well-known algorithm to compute binomial coefficients. Some practical applications of our methods are given in this paper.

2  Computing bk=i=0k Cki ai and bk=i=0k Cki aibi

We start our discussion by considering computation of binomial coefficients. It is taught in a high school that Cni=Cn-1i-1+Cn-1i. From this property, we can derive an efficient algorithm to compute binomial coefficients
   c(0,0) = 1
   do k=1, n
      c(k,0) = 1
      c(k,k) = 1
      do i=1, k-1
         c(k,i) = c(k-1,i-1) + c(k-1,i)
      enddo
   enddo

This method is commonly known as the construction of Pascal triangle. It is seen that only n(n-1)/2 additions are needed to obtain all Cki (k=1,2,,n; i=1,2,,k). When n=3, the Pascal triangle is given by

1
1
1
1
2
1
1
3
3
1
We now consider computation of bk=i=0k Cki ai. For n=3, we have






b0
b1
b2
b3





=




1
0
0
0
1
1
0
0
1
2
1
0
1
3
3
1










a0
a1
a2
a3





=




a0
a0+a1
a0+2a1+a2
a0+3a1+3a2+a3





.
It is noted that the transformation matrix resembles the property of Pascal triangle. Therefore, analogous to the construction of Pascal triangle, we may derive the following method to compute bk

   Copy a(i) into b(i)
   do k=1, n
   do i=n, k, -1
      b(i) = b(i) + b(i-1)
   enddo

This method requires only n(n-1)/2 additions. For verification, we look at the case where n=3:
   (k = 1)              (k = 2)                   (k = 3)
   b3=b3+b2=a3+a2       b3=b3+b2=a3+2a2+a1        b3=b3+b2=a3+3a2+3a1+a0
   b2=b2+b1=a2+a1       b2=b2+b1=a2+2a1+a0
   b1=b1+b0=a1+a0 

We may extend the above method to compute bk=i=0k Cki aibi:

   Copy a(i) into b(i)
   do k=1, n
   do i=n, k, -1
      b(i) = b(i) * beta + b(i-1)
   enddo

We now consider the application of the above method. In computational geometry, a Bézier polynomial is commonly used to describe the shape of geometric entity. A Bézier polynomial of degree n may be represented in terms of Bernstein polynomials [2-3]:

P(t)= n

i=0 
Cni(1-t)n-iti pi.
For efficient evaluation of Bézier polynomial and its derivatives, we often convert it into a canonical polynomial so that Horner method can be employed. By the binomial expansion theorem, we have

n

i=0 
Cni(1-t)n-itipi = n

i=0 
n-i

j=0 
(-1)jCniCn-ijpiti+j.
Then, we want to find bk such that

n

k=0 
bktk= n

i=0 
n-i

j=0 
(-1)jCniCn-ijpiti+j.
Since the coefficients of the same degree terms at both sides should be equal, we thus have

bk= k

i=0 
k-i

j=k-i 
(-1)jCniCn-ijpiti+j = k

i=0 
(-1)k-iCniCn-ik-ipi.
From the relation CniCn-ik-i=CnkCki, we obtain

bk= k

i=0 
(-1)k-iCnkCkipi = (-1)kCnk k

i=0 
(-1)iCkipi.
To compute bk efficiently, we first evaluate i=0k(-1)iCkipi using the above method, then multiply the results by (-1)kCnk (noting that Cnk=[(n-k+1)/k]Cnk-1). The pseudo code is given as follows:

  do i=0, n, 2
     b(i) = a(i)
  enddo
  do i=1, n, 2
     b(i) = -a(i)
  enddo

  do k=1, n
  do i=n, k, -1
     b(i) = b(i) + b(i-1)
  enddo

  temp = 1.0
  do i=1, n
     temp = -(n + 1 - i) * temp / i
     b(i) = b(i) * temp
  enddo

It should be noted that the third block may be replaced by directly multiplying bk by (-1)kCnk if one's system has a table of binomial coefficients.

3  Compute bk=i=kn Cikai, bk=i=kn Cikaibi-k

In this section, we are concerned with efficient evaluation of bk=i=kn Cikai with k=0,1,,n. For n=3, we have






b0
b1
b2
b3





=




1
1
1
1
0
1
2
3
0
0
1
3
0
0
0
1










a0
a1
a2
a3





=




a0+a1+a2+a3
a1+2a2+3a3
a2+3a3
a3





.
From this special case, we can see that the transpose of a transformation matrix resembles the property of Pascal triangle. Therefore, analogous to the construction of Pascal triangle we can derive the following algorithm to compute bk=i=kn Cikai:

   Copy a(i) into b(i)
   do k=0, n-1
   do i=n-1, k, -1
      b(i) = b(i) + b(i+1)
   enddo

We may extend the above method to compute bk=j=kn Cjkajbj-k:
   Copy a(i) into b(i)
   do k=0, n-1
   do i=n-1, k, -1
      b(i) = b(i) + b(i+1) * beta
   enddo

To demonstrate an application of the above method, we consider reparametrising a canonical polynomial

P(t)= n

i=0 
ai ti,       t [a, b]
by t=[(b+a)+(b-a)u]/2 such that P(u) is defined over [-1,1]. Let a = (b-a)/2 and b = (b+a)/(b-a). Then, t=a(b+u). Therefore,

P(u)= n

i=0 
ai ai(b+u)i.
By the theorem of binomial expansion, we have

P(u)= n

i=0 
i

j=0 
aiai Cij bj ui-j.
We want to find bk such that

n

k=0 
bk uk= n

i=0 
i

j=0 
aiai Cij bj ui-j.
Since the coefficients of the same degree terms on both side should be equal, we have

bk= n

i=k 
i-k

j=i-k 
aiai Cij bj = n

i=k 
aiai Cii-k bi-k = n

i=k 
Cik(aiai)bi-k.
Therefore, an efficient method to compute bk would be

    b(0) = a(0)
    temp = alpha
    do i=1, n
       b(i) = a(i) * temp
       temp = temp * alpha
    enddo

    do k=0, n-1
    do i=n-1, k, step=-1
       b(i) = b(i) + b(i+1) * beta
    enddo

4  Compute bk=i=0k Cn-ik-iai, bk=i=0k Cn-ik-iaibk-i

In this section, we are concerned with efficient evaluation of bk=i=0k Cn-ik-iai with k=0,1,,n. For n=3, we have






b0
b1
b2
b3





=




1
0
0
0
3
1
0
0
3
2
1
0
1
1
1
1










a0
a1
a2
a3





=




a0
3a0+a1
3a0+2a1+a2
a0+a1+a2+a3





.
From this special case, we can see that the transpose of a transformation matrix resembles the property of Pascal triangle. Therefore, analogous to the construction of Pascal triangle, we give the following method to compute bk:

   Copy a(k) into b(k)
   do k=0, n
   do i=1, n-k
      b(i) = b(i) + b(i-1)
   enddo

This method can be extended to compute bk=i=0k Cn-ik-iaibk-i:
   Copy a(k) into b(k)
   do k=0, n
   do i=1, n-k
      b(i) = b(i) + b(i-1) * beta
   enddo

To illustrate an application of the above method, we consider reparametrising a vector-valued rational curve r(t)=(x(t),y(t),z(t)) by t=t(u) such that

r(u)=r(t),    r(u)|u=0 = ar(t)|t=0.
Such reparametrisation is required whenever we want change the derivatives at the end points without affecting the geometric shape of the curve. In addition to the requirement of modifying the derivative at t=0, we also want to keep the degree of curve and the parameter interval unchanged. To meet all these requirements, the following bilinear transformation is a choice

t= au
(a-1)u+1
= au
bu+1
       (u [0,1], t [0,1]).
By the chain rule of differentiation we have r(u)=r(t)t(u). Then, it is readily checked that r(u)|u=0=ar(t)|t=0.

We denote r(t)=(x(t),y(t),z(t)) in homogeneous coordinate system by R(t)=(X(t),Y(t),Z(t),W(t)) and write R(t) in the canonical form R(t)=k=0nak tk, where ak=(xk,yk,zk,wk) are vectors in homogeneous coordinates. Replacing t in R(t) by t=t(u), we have

R(u)= n

i=0 
ai

au
bu+1


i

 
= 1
(bu+1)n
n

i=0 
ai(au)i(bu+1)n-i.
Since R(u) is represented in homogeneous coordinates, the common factor 1/(bu+1)n can be discarded. Therefore, we have

R(u) = n

i=0 
ai(au)i(bu+1)n-i.
By the binomial expansion theorem we obtain

R(u)= n

i=0 
n-i

j=0 
aiaiCn-ijbj ui+j.
We now want to find bk such that

n

k=0 
bkuk= n

i=0 
n-i

j=0 
aiai Cn-ijbj ui+j.
Since the same degree terms at both side should be equal, we can then derive

bk= k

i=0 
k-i

j=k-i 
aiaiCn-ijbj = k

i=0 
aiaiCn-ik-ibk-i.
Let [`(ai)]=aiai. Then, bk=i=0k Cn-ik-i[`(ai)]bk-i (k=0,1,,n), which can be computed very efficiently using the method we discussed earlier.

5  Conclusions

Binomial coefficients can be computed very efficiently by the construction of Pascal triangle. Based on an observation of this construction, we derived efficient methods to compute bk=i=0k Cki ai, bk=i=kn Cik ai, etc. Applications of these methods in computational geometry and approximation were also discussed. Although not all possible combinations of the binomial coefficients and ai were considered in this paper, one can analogously derive a respective method to meet his own requirement.

References

Davis, P.J. (1975), Interpolation & Approximation, Dover Pub., Inc.
Hoschek, J. and Lasser, D. (1993), Computer Aided Geometric Design, A.K. Peters, Ltd.
Faux, I.D. and Pratt, M.J. (1979), Computational Geometry for Design and Manufacture, Ellis Horwood Ltd., London.

RETURN