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 b_{k}=å_{i=0}^{k} C_{k}^{i} a_{i} 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 Bspline
polynomial curves) are used to describe the shape of geometric entities [23].
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:
b_{k}= 
k å
i=0

C_{k}^{i} a_{i}, b_{k}= 
n å
i=k

C_{i}^{k} a_{i}, b_{k}= 
k å
i=0

C_{ni}^{ki}a_{i}, ¼ (k=0, 1, ¼, n) 

where,
C_{n}^{i}= 
æ ç
è

 
ö ÷
ø

= 
n! (ni)! i!



are called the binomial coefficients. Assume a table of binomial
coefficients is given. Then, a straight forward method to compute, for example,
b_{k}=å_{i=0}^{k} C_{k}^{i} p_{i} (k=1,2,...,n) is to multiply p_{i} by C_{k}^{i}
and then add them together. However, even with the supply of binomial
coefficients, this simple method requires n(n1)/2 multiplications and the
same number of additions. In this paper, we shall derive an efficient
algorithm to compute b_{k}. Using our method, only n(n1)/2 additions are
needed to compute all b_{k}=å_{i=0}^{k} C_{k}^{i} p_{i} (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
wellknown algorithm to compute binomial coefficients. Some practical
applications of our methods are given in this paper.
2 Computing b_{k}=å_{i=0}^{k} C_{k}^{i} a_{i} and
b_{k}=å_{i=0}^{k} C_{k}^{i} a_{i}b^{i}
We start our discussion by considering computation of binomial coefficients.
It is taught in a high school that C_{n}^{i}=C_{n1}^{i1}+C_{n1}^{i}. 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, k1
c(k,i) = c(k1,i1) + c(k1,i)
enddo
enddo
This method is commonly known as the construction of Pascal triangle. It
is seen that only n(n1)/2 additions are needed to obtain all C_{k}^{i}
(k=1,2,¼,n; i=1,2,¼,k). When n=3, the Pascal triangle is given
by
We now consider computation of b_{k}=å_{i=0}^{k} C_{k}^{i} a_{i}. For n=3, we have

æ ç ç
ç ç è

 
ö ÷ ÷
÷ ÷ ø

= 
æ ç ç
ç ç è

 
ö ÷ ÷
÷ ÷ ø


æ ç ç
ç ç è

 
ö ÷ ÷
÷ ÷ ø

= 
æ ç ç
ç ç è

   a_{0}+3a_{1}+3a_{2}+a_{3} 

 
ö ÷ ÷
÷ ÷ ø

. 

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 b_{k}
Copy a(i) into b(i)
do k=1, n
do i=n, k, 1
b(i) = b(i) + b(i1)
enddo
This method requires only n(n1)/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 b_{k}=å_{i=0}^{k} C_{k}^{i} a_{i}b^{i}:
Copy a(i) into b(i)
do k=1, n
do i=n, k, 1
b(i) = b(i) * beta + b(i1)
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 [23]:
P(t)= 
n å
i=0

C_{n}^{i}(1t)^{ni}t^{i} p_{i}. 

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

C_{n}^{i}(1t)^{ni}t^{i}p_{i} = 
n å
i=0


ni å
j=0

(1)^{j}C_{n}^{i}C_{ni}^{j}p_{i}t^{i+j}. 

Then, we want to find b_{k} such that

n å
k=0

b_{k}t^{k}= 
n å
i=0


ni å
j=0

(1)^{j}C_{n}^{i}C_{ni}^{j}p_{i}t^{i+j}. 

Since the coefficients of the same degree terms at both sides should be equal,
we thus have
b_{k}= 
k å
i=0


ki å
j=ki

(1)^{j}C_{n}^{i}C_{ni}^{j}p_{i}t^{i+j} = 
k å
i=0

(1)^{ki}C_{n}^{i}C_{ni}^{ki}p_{i}. 

From the relation C_{n}^{i}C_{ni}^{ki}=C_{n}^{k}C_{k}^{i}, we obtain
b_{k}= 
k å
i=0

(1)^{ki}C_{n}^{k}C_{k}^{i}p_{i} = (1)^{k}C_{n}^{k} 
k å
i=0

(1)^{i}C_{k}^{i}p_{i}. 

To compute b_{k} efficiently, we first evaluate å_{i=0}^{k}(1)^{i}C_{k}^{i}p_{i}
using the above method, then multiply the results by (1)^{k}C_{n}^{k} (noting that
C_{n}^{k}=[(nk+1)/k]C_{n}^{k1}). 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(i1)
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 b_{k} by (1)^{k}C_{n}^{k} if one's system has a table of binomial
coefficients.
3 Compute b_{k}=å_{i=k}^{n} C_{i}^{k}a_{i},
b_{k}=å_{i=k}^{n} C_{i}^{k}a_{i}b^{ik}
In this section, we are concerned with efficient evaluation of
b_{k}=å_{i=k}^{n} C_{i}^{k}a_{i} with k=0,1,¼,n. For n=3, we have

æ ç ç
ç ç è

 
ö ÷ ÷
÷ ÷ ø

= 
æ ç ç
ç ç è

 
ö ÷ ÷
÷ ÷ ø


æ ç ç
ç ç è

 
ö ÷ ÷
÷ ÷ ø

= 
æ ç ç
ç ç è

 
ö ÷ ÷
÷ ÷ ø

. 

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 b_{k}=å_{i=k}^{n} C_{i}^{k}a_{i}:
Copy a(i) into b(i)
do k=0, n1
do i=n1, k, 1
b(i) = b(i) + b(i+1)
enddo
We may extend the above method to compute b_{k}=å_{j=k}^{n} C_{j}^{k}a_{j}b^{jk}:
Copy a(i) into b(i)
do k=0, n1
do i=n1, 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

a_{i} t^{i}, t Î [a, b] 

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

a_{i} a^{i}(b+u)^{i}. 

By the theorem of binomial expansion, we have
P(u)= 
n å
i=0


i å
j=0

a_{i}a^{i} C_{i}^{j} b^{j} u^{ij}. 

We want to find b_{k} such that

n å
k=0

b_{k} u^{k}= 
n å
i=0


i å
j=0

a_{i}a^{i} C_{i}^{j} b^{j} u^{ij}. 

Since the coefficients of the same degree terms on both side should be equal,
we have
b_{k}= 
n å
i=k


ik å
j=ik

a_{i}a^{i} C_{i}^{j} b^{j} = 
n å
i=k

a_{i}a^{i} C_{i}^{ik} b^{ik} = 
n å
i=k

C_{i}^{k}(a_{i}a^{i})b^{ik}. 

Therefore, an efficient method to compute b_{k} would be
b(0) = a(0)
temp = alpha
do i=1, n
b(i) = a(i) * temp
temp = temp * alpha
enddo
do k=0, n1
do i=n1, k, step=1
b(i) = b(i) + b(i+1) * beta
enddo
4 Compute b_{k}=å_{i=0}^{k} C_{ni}^{ki}a_{i},
b_{k}=å_{i=0}^{k} C_{ni}^{ki}a_{i}b^{ki}
In this section, we are concerned with efficient evaluation of
b_{k}=å_{i=0}^{k} C_{ni}^{ki}a_{i} with k=0,1,¼,n. For n=3, we have

æ ç ç
ç ç è

 
ö ÷ ÷
÷ ÷ ø

= 
æ ç ç
ç ç è

 
ö ÷ ÷
÷ ÷ ø


æ ç ç
ç ç è

 
ö ÷ ÷
÷ ÷ ø

= 
æ ç ç
ç ç è

 
ö ÷ ÷
÷ ÷ ø

. 

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 b_{k}:
Copy a(k) into b(k)
do k=0, n
do i=1, nk
b(i) = b(i) + b(i1)
enddo
This method can be extended to compute
b_{k}=å_{i=0}^{k} C_{ni}^{ki}a_{i}b^{ki}:
Copy a(k) into b(k)
do k=0, n
do i=1, nk
b(i) = b(i) + b(i1) * beta
enddo
To illustrate an application of the above method, we consider reparametrising a
vectorvalued 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 (a1)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=0}^{n}a_{k} t^{k}, where a_{k}=(x_{k},y_{k},z_{k},w_{k}) are
vectors in homogeneous coordinates. Replacing t in R(t) by t=t(u),
we have
R(u)= 
n å
i=0

a_{i} 
æ ç
è

au bu+1

ö ÷
ø

i

= 
1 (bu+1)^{n}


n å
i=0

a_{i}(au)^{i}(bu+1)^{ni}. 

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

a_{i}(au)^{i}(bu+1)^{ni}. 

By the binomial expansion theorem we obtain
R(u)= 
n å
i=0


ni å
j=0

a_{i}a^{i}C_{ni}^{j}b^{j} u^{i+j}. 

We now want to find b_{k} such that

n å
k=0

b_{k}u^{k}= 
n å
i=0


ni å
j=0

a_{i}a^{i} C_{ni}^{j}b^{j} u^{i+j}. 

Since the same degree terms at both side should be equal, we can then derive
b_{k}= 
k å
i=0


ki å
j=ki

a_{i}a^{i}C_{ni}^{j}b^{j} = 
k å
i=0

a_{i}a^{i}C_{ni}^{ki}b^{ki}. 

Let [`(a_{i})]=a_{i}a^{i}. Then,
b_{k}=å_{i=0}^{k} C_{ni}^{ki}[`(a_{i})]b^{ki} (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 b_{k}=å_{i=0}^{k} C_{k}^{i} a_{i},
b_{k}=å_{i=k}^{n} C_{i}^{k} a_{i}, etc. Applications of these methods in
computational geometry and approximation were also discussed. Although not all
possible combinations of the binomial coefficients and a_{i} 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