Teaching Kids Programming – Pascal Triangle Algorithms and Applications

Teaching Kids Programming: Videos on Data Structures and Algorithms

The Pascal Triangle looks like this:

1
2
3
4
5
6
7
8

[1]
[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]
[1, 7, 21, 35, 35, 21, 7, 1]

[1]
[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]
[1, 7, 21, 35, 35, 21, 7, 1]

Each number is equal to the two numbers above it. Two edges are filled with ones.

Compute Pascal Triangle Numbers using Recurrsive Formula (Bottom Up)

The P(r, c) where r is the row, and c is the column can be expressed by:

and [math] P(0, c) = P(r, 0) = P(R, R) [math] where R is from [0, inf)

We can implement the recursion (Bottom Up approach) and use the hash set / dictionary (notebook) to avoid repeative calculation of intermediate Pascal Triangle values. With Python, we can use functools.lru_cach to cache the values automatically.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

from functools import lru_cache
 
@lru_cache(maxsize=None)
def f(r, c):
    if r == 0 or c == 0 or r == c:
        return 1
    return f(r - 1, c) + f(r - 1, c - 1)
 
# print the first 8 rows of a Pascal Triangle
for r in range(8):
    a = []
    for c in range(r + 1):
        a.append(f(r, c))
    print(a)

from functools import lru_cache

@lru_cache(maxsize=None)
def f(r, c):
    if r == 0 or c == 0 or r == c:
        return 1
    return f(r - 1, c) + f(r - 1, c - 1)

# print the first 8 rows of a Pascal Triangle
for r in range(8):
    a = []
    for c in range(r + 1):
        a.append(f(r, c))
    print(a)

Print Pascal Triangle using Top-Down Algorithm

We can print the first row, and then second row and this goes on printing all other rows of Pascal Triangle. This is a iterative top-down approach:

1
2
3
4
5
6
7
8
9
10
11

def pascal(rows):
    data = [0] * rows
    for r in range(rows):
        data[0] = 1  # first column
        data[r] = 1  # last column
        for c in range(r - 1, 0, -1):
            data[c] += data[c - 1]  # dynamic programming
        print(data[:r + 1])  # only print the lower half triangle
 
# print first 8 rows of a pascal triangle
pascal(8)

def pascal(rows):
    data = [0] * rows
    for r in range(rows):
        data[0] = 1  # first column
        data[r] = 1  # last column
        for c in range(r - 1, 0, -1):
            data[c] += data[c - 1]  # dynamic programming
        print(data[:r + 1])  # only print the lower half triangle

# print first 8 rows of a pascal triangle
pascal(8)

On each row, we update the values from right to the left, so that we can re-use the previous values (via Dynamic Programming)

Pascal Triangle Applications

Pascal Triangle has many interesting mathematics properties.

11’s time table

If you look carefuly, the first row is: 0 which is 11^0 (to the power of zero).
The second row 11 which is 11^1
The third row 121 which is 11^2
and this goes on

2’s time table for sum of each row’s digits

Sum of digits for first row 1 – which is 2^0
Sum of digits for the second row 2 – which is 2^1
Sum of digits for the third row 4 – which is 2^2
and this goes on

Combination Formula

There are C(N, M) ways to pick M items out of N total items, which corresponds to row M and column N (0 index) of a pascal triangle.

Pascal Triangle Implementations:

• Teaching Kids Programming – Pascal Triangle Algorithms and Applications
• Coding Exercise – Pascal Triangle II – C++ and Python Solution
• How to Print Pascal Triangle in C++ (with Source Code)
• Compute the Nth Row of a Pascal’s Triangle using Dynamic Programming Algorithm
• GoLang: Generate a Pascal Triangle

–EOF (The Ultimate Computing & Technology Blog) —