DSA Combinatorics for Interviews

Combinatorics is the counting of choices and arrangements with exact whole numbers. Two rules do most of the work, and Pascal's triangle supplies the choice counts.

Multiply for "and"

An outfit picks one shirt and one pair of trousers. A nested loop counts every pairing directly.

count = 0
for shirt in ["red", "green", "blue"]:
    for trousers in ["black", "grey", "white", "tan"]:
        count += 1
print("outfits counted:", count)
print("3 shirts * 4 trousers =", 3 * 4)

Add for "or"

A trip takes one bus or one train, never both. The two route counts simply add.

buses = ["B1", "B2", "B3"]
trains = ["T1", "T2", "T3", "T4"]
print("routes:", len(buses) + len(trains))

Read a choice count from Pascal's triangle

Row 6 of the triangle holds the counts for picking from six items. The middle entries count the larger selections.

row = [1]
for _ in range(6):
    row = [1] + [row[i] + row[i + 1] for i in range(len(row) - 1)] + [1]
print("row 6:", row)
print("C(6, 2):", row[2])
print("C(6, 3):", row[3])

Example

def pascal_rows(last):
    rows = [[1]]
    for _ in range(last):
        prev = rows[-1]
        rows.append([1] + [prev[i] + prev[i + 1] for i in range(len(prev) - 1)] + [1])
    return rows

rows = pascal_rows(30)
for n in range(8):
    print("row", n, ":", rows[n])
print("C(10, 3) teams:", rows[10][3])
print("C(12, 5) committees:", rows[12][5])
print("C(20, 10) squads:", rows[20][10])
print("C(30, 15) draws:", rows[30][15])
print("symmetry C(12, 5) == C(12, 7):", rows[12][5] == rows[12][7])
print("row 20 sums to 2**20:", sum(rows[20]) == 2 ** 20)

Key points

Combinatorics counts choices and arrangements with exact whole numbers.
Choices joined by "and" multiply their counts together.
Choices joined by "or" add their counts together.
A combination is a selection where the order of picks does not matter.
The notation C(n, k) counts the ways to pick k items from n items.
Each Pascal row entry equals the sum of the two entries above it.
Python integers grow without overflow, so every count stays exact.

In this example, the triangle grows one row at a time. Each new entry adds the two entries above it. The first prints show the rows up to row 7. The later lines read exact counts straight from deeper rows. The last two lines check symmetry and a full row sum.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

def pascal_rows(last):
    rows = [[1]]
    for _ in range(last):
        prev = rows[-1]
        rows.append([1] + [prev[i] + prev[i + 1] for i in range(len(prev) - 1)] + [1])
    return rows

rows = pascal_rows(30)
for n in range(8):
    print("row", n, ":", rows[n])
print("C(10, 3) teams:", rows[10][3])
print("C(12, 5) committees:", rows[12][5])
print("C(20, 10) squads:", rows[20][10])
print("C(30, 15) draws:", rows[30][15])
print("symmetry C(12, 5) == C(12, 7):", rows[12][5] == rows[12][7])
print("row 20 sums to 2**20:", sum(rows[20]) == 2 ** 20)

Exercise

A menu offers 4 starters and 5 mains. How many starter-and-main pairs exist?

20 9 45 1