
Pascal's Triangle
 Problem: Given n balloons. In how many ways can you pop
k of them?
 Let P(k,n) be the symbols used to denote this number.
For example, if n is 1 (1 balloon) and k is 1, there
is only one way to pop the single balloon. Therefore, P(1,1)
is 1. Observe also that P(0,1) (how many ways to pop no
balloons) is 1. Also observe that P(0,2) is 1,
P(1,2) is 2 (pop 1st or pop 2nd but not both) and
P(2,2) is 1. Also observe that P(0,n) is 1 for any
n (pop none) and P(n,n) is 1 for any n (pop
all). But how can we find P(k,n) in general?
 Sounds hard. But, if we know P(k,n) for all
0≤k≤n we can compute P(k,n+1) for all
0≤k≤n+1. Here is how. Observe that popping
n+1 balloons is the same as popping n balloons
except we have to account for the one extra balloon. Well, there are
two things that could happen to that balloon: we could pop it or we
can leave it alone. Suppose for the moment we will pop the last one.
Then the number of ways to pop k out of all n+1
balloons given that the last one is popped is exactly the same
as the number of ways to pop k1 out of the first n
balloons (since the last balloon is definitely popped in this case it
adds 1 to the count of the number of popped balloons). So, this
contribution to P(k,n+1) is P(k1,n). Now suppose
for the moment that we leave the last balloon alone. Then the number
of ways to pop k out of all n+1 balloons given
that the last one is not popped is exactly the same as the number
of ways to pop k out of the first n balloons (since
the last balloon is definitely not popped in this case it adds 0 to the
count of the number of popped balloons). So, in this case the
contribution to P(k,n+1) is P(k,n1). Therefore,
P(k,n+1) = P(k,n) + P(k1,n)
 How can you program this? You can use a for loop where iteration
n computes P(k,n) for 0≤k≤n. The
results are saved in an array called row and are used to
compute sums for P(k,n+1). The attached source code shows a
temporary array called accum which computes the new row
(except for the end cases) via
for (int k=1 ; k < row.length ; k++)
accum[k] = row[k] + row[k1];
To avoid arrayindexoutofbounds errors, the special end cases are
treated with the lines
accum[0] = 1;
accum[accum.length1] = 1;
For the next iteration, the row array becomes the temporary
array via
row = accum;
On each iteration the size of the row array increases by 1. Hence a
new array is created on each iteration using
accum = new int[row.length+1];
The old array then becomes garbage which is automatically collected by Java.
