Pascal's Triangle

PG: These are projects and should be listed as projects. Nice enough suggestions, but optional. And why are "simple ones" after all the (implicitly and, I think, really) hard stuff? It would be great to have a collection of puzzles, like the ones Parisa hands out, for kids to sink their teeth into, but /they/ already knew how to program recursively. I don't think we've provided what is needed for our kids to master that.

MF: I want to review/revise.

Pages or lab needs renaming so they aren't duplicative. --MF, 6/15/20

In Pascal's Triangle, each number is the sum of the two numbers above it. The numbers at the ends of each row are always 1.

The HTML in this triangle needs to be cleaned up. --MF

Row 1:    1  1
Row 2:    1  2  1
Row 3:    1  3  3  1
Row 4:    1  4  6  4  1
Row 5:    1  5  10  10  5  1
Row 6:    1  6  15  20  15  6  1
                ︙

For example, each 15 in Row 6 is the sum of the 5 and 10 just above it.

  1. Write out Row 7 of Pascal's Triangle.
  2. Write a next row block that takes a row of Pascal's Triangle as its input, and reports the next row as its output:
    next row(list{1,4,6,4,1}) reporting {1,5,10,10,5,1}

To refer to a specific number in Pascal's Triangle, you need to know its row and column. Rows are simple; columns are more complicated because of the triangle's orientation. Here is Pascal's Triangle, aligned in columns:

The alignment here is still a little messy. Some sort of tabular environment could get it more precisely right. I removed the "blockquote" environment since it italicized everything. I can't figure out how to "center" this as a block while still keeping its visible alignment. -BK
  1. I would fix this, but I'm not clear what's intended... -MF

1   1
1   2   1
1   3   3    1
1   4   6    4    1
1   5  10  10   5   1
1   6  15  20  15  6   1

By convention (because it turns out to be useful), the columns in Pascal's Triangle are named starting from 0, not 1. For example, the number in row 4, column 1 of Pascal's Triangle is 4, not 1.
  1. What number is in row 6, column 2 of Pascal's Triangle?
  2. Two numbers in row 5 are added to produce the number in row 6, column 2. What are their locations?
  3. To determine the number in row 14, column 5 of Pascal's Triangle, you would need to know two numbers from row 13. In which columns in row 13 are those numbers?

Pascal's Triangle counts the number of ways to pick a collection from larger collection. For more about Pascal's Triangle and its uses, see About Pascal's Triangle page.

What are the base cases? The work in earlier problems should help you figure out the recursion. Try more examples if you're not sure.
  1. Write a pascal block that takes two numbers as input, row and column, and reports the value in that row and column of Pascal's Triangle.