Arithmetic and Array Ops
Previous    Next    Home    Source    Package

In the applet on the left click once for P(0,0), again for P(0,1) and P(1,1), again for P(0,2), P(1,2), and P(2,2), and so on where P(k,n) is explained on the right.

Pascal's Triangle
  1. Problem: Given n balloons. In how many ways can you pop k of them?
  2. 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?
  3. 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 k-1 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(k-1,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,n-1). Therefore,
       P(k,n+1) = P(k,n) + P(k-1,n)
    
  4. 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[k-1];
    
    To avoid array-index-out-of-bounds errors, the special end cases are treated with the lines
       accum[0] = 1;
       accum[accum.length-1] = 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.