Teaching Kids Programming: Videos on Data Structures and Algorithms

Introduction to Math Combination

Combinations count the ways to choose items when order does not matter. This guide builds intuition from a simple grid-walking example, introduces binomial notation, derives the formula, explains the recurrence , and connects everything to Pascal’s triangle.

Grid walking example — paths from bottom-left to top-right

Imagine you must move only Right (R) or Up (U). To go from the bottom-left to a point that requires three rights and two ups, every shortest path is a sequence of five moves containing three R’s and two U’s.

Each valid path is just a choice of which two positions (out of five) are U (the rest are R). So the number of such paths is “5 choose 2”, written (which equals ).

Example sequences:

R R U R U U R R R U R U R R U R R R U U U U R R R 

The binomial coefficient (combination) notation

The number of ways to choose items from items (order doesn’t matter) is written

or

Both mean “n choose m”.

Formula for combinations — the factorial derivation

First count ordered selections (permutations): the number of ordered lists of length from distinct items is

Each unordered set of items corresponds to ordered lists (the permutations of those ). Divide by to get combinations:

Apply the formula to the grid example

For total steps and ups:

So there are 10 distinct shortest paths.

Why the formula makes sense intuitively

• Viewpoint 1 — choose positions: choose the positions (out of ) where the U’s go; that’s .
• Viewpoint 2 — divide permutations by ordering: count all permutations of n moves then divide out reorderings of identical moves.

Pascal’s triangle and the recurrence

Write in rows to form Pascal’s triangle:

 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 

The entries satisfy the recurrence

Then, we can easily write a top-down dynamic programming implementation using @cache for memoized recursion:

from functools import cache

@cache
def C(n, m):
    if m == 0:
        return 1  # C(n, 0) = 1
    if m == n:
        return 1  # C(n, n) = 1
    return C(n-1, m-1) + C(n-1, m)

Of course, we can also implement it in a bottom-up manner:

def C_bottom_up(n, m):
    dp = [[0]*(m+1) for _ in range(n+1)]
    for i in range(n+1):
        dp[i][0] = 1  # C(i, 0) = 1
        for j in range(1, min(i, m)+1):
            if j == i:
                dp[i][j] = 1  # C(i, i) = 1
            else:
                dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
    return dp[n][m]

This bottom-up implementation accumulates from smaller subproblems to larger ones, avoiding the overhead of recursion and easily extending to compute the entire Pascal’s triangle.

The bottom-up Dynamic Programming for combinations can be further optimized using a one-dimensional array, leveraging the rolling array principle, since each row only depends on the previous row. The key is to update from right to left to avoid overwriting data that hasn’t been used yet.

Here’s an example implementation:

def C_one_dim(n, m):
    dp = [0] * (m+1)
    dp[0] = 1  # C(i, 0) = 1

    for i in range(1, n+1):
        # Update from right to left to avoid overwriting previous row data
        for j in range(min(i, m), 0, -1):
            dp[j] = dp[j] + dp[j-1]
    
    return dp[m]

Example:

print(C_one_dim(5, 2))  # Output: 10

✅ Advantages:

• Space complexity: O(m)
• Time complexity: O(n*m)
• Can easily be extended to compute an entire row or column of combination numbers

Combinatorial proof — picking apples

Want to pick apples from apples. Consider the last apple (#n):

If you pick it, you must choose the remaining from the first : ways.

If you skip it, you must choose all from the first : ways.

These two disjoint cases cover all possibilities, so

(That identity is exactly what builds Pascal’s triangle.)

Grid interpretation of the recurrence

On the grid, look at the last step of any path to a certain point: it is either R or U. Paths ending in R come from one earlier grid point, and paths ending in U come from another. Counting those two groups reproduces the same addition rule.

Common small values and remarks

(choose nothing).
(choose one).
(choose all).

Small table for :

C(5,0)=1
C(5,1)=5
C(5,2)=10
C(5,3)=10
C(5,4)=5
C(5,5)=1 

Final notes

Combinations appear in counting paths, binomial expansions (coefficients of ), probability, and selection problems. The factorial formula gives direct computation, while Pascal’s triangle and the recurrence provide inductive intuition and efficient building of values. The grid-walking example is a concrete way to visualize why “choose positions” equals “choose steps”, which is the heart of combinations.

–EOF (The Ultimate Computing & Technology Blog) —

See more 2264 words
Last Post: The Hidden Engine of Performance: It’s All About Where the Data Lives (Cache is the King)
Next Post: Why Parallelism Isn’t Infinite: Amdahl vs Gustafson Explained Simply