Unit 15: Counting Without Listing

Multiply the choices

Three shirts and four hats make twelve outfits. Choices that do not interfere multiply — that is the whole of counting, and everything else is a special case.

Ordering n things: n choices, then n - 1, then n - 2. That is n factorial, which unit 2 already watched explode.

Choosing k from n, when the order does not matter

Line up k of them in order — n * (n - 1) * ... ways — then divide by the k! orders that are the same handful.

Written this way it never leaves whole numbers, because after i + 1 steps the product is always divisible by i + 1.

Python

def choose(n, k):
    result = 1
    for i in range(k):
        result = result * (n - i) // (i + 1)
    return result

print(choose(5, 2))
print(choose(10, 3))
print(choose(52, 5))

It prints

10
120
2598960

Two facts to keep in your head

Choosing k is the same as choosing which n - k to leave out, so choose(n, k) equals choose(n, n - k).

And adding up a whole row of them gives 2 ** n — because choosing any subset is what the row counts.

Python

def choose(n, k):
    result = 1
    for i in range(k):
        result = result * (n - i) // (i + 1)
    return result

print(choose(10, 3), choose(10, 7))
print(sum(choose(10, k) for k in range(11)), 2 ** 10)

It prints

120 120
1024 1024

Each number is the two above it added together

To choose k from n, either the last item is in your group — then choose k - 1 from the rest — or it is not, and you choose k from the rest.

So choose(n, k) is choose(n-1, k-1) + choose(n-1, k), which is a table you fill in row by row.

Python

rows = 6
table = [[1] * (r + 1) for r in range(rows)]
for r in range(2, rows):
    for c in range(1, r):
        table[r][c] = table[r - 1][c - 1] + table[r - 1][c]

for row in table:
    print(row)

It prints

[1]
[1, 1]
[1, 2, 1]
[1, 3, 3, 1]
[1, 4, 6, 4, 1]
[1, 5, 10, 10, 5, 1]

Why bother, when the formula is shorter?

Two reasons a contest cares about. The table needs only addition, so it works under any modulus, prime or not — no inverses required.

And it hands you every value at once, which is what a dynamic programming solution usually wants.

Python

MOD = 1000
rows = 10
table = [[1] * (r + 1) for r in range(rows)]
for r in range(2, rows):
    for c in range(1, r):
        table[r][c] = (table[r - 1][c - 1] + table[r - 1][c]) % MOD

print(table[9])

It prints

[1, 9, 36, 84, 126, 126, 84, 36, 9, 1]

The cost of each way

The table is n * n — fine for n up to a few thousand, hopeless at a hundred thousand.

Factorials with inverses are n to build and constant per question, which is why unit 14 finished where it did. Pick by the size of n, not by taste.

How many numbers up to 100 divide by 2, 3 or 5?

50 divide by 2, 33 by 3, 20 by 5 — but that is 103, and there are only 100 numbers. Everything divisible by 6 has been counted twice.

So take the pairs off. That takes the multiples of 30 off three times having added them three times, so put them back. This is inclusion and exclusion.

Python

print(100 // 2, 100 // 3, 100 // 5)
print(100 // 6, 100 // 10, 100 // 15)
print(100 // 30)
print(50 + 33 + 20 - 16 - 10 - 6 + 3)

It prints

50 33 20
16 10 6
3
74

Every subset of the conditions, with a sign

Odd number of conditions: add. Even number: subtract. That is a loop over bitmasks, straight out of unit 3, and it handles ten conditions as easily as three.

bin(mask).count("1") counts the bits; the sign is whether that count is odd.

Python

limit = 100
divisors = [2, 3, 5]
total = 0

for mask in range(1, 1 << len(divisors)):
    product = 1
    bits = 0
    for i in range(len(divisors)):
        if (mask >> i) & 1:
            product *= divisors[i]
            bits += 1
    if bits % 2 == 1:
        total += limit // product
    else:
        total -= limit // product

print(total)

It prints

74

Checking it the slow way

For a hundred numbers you can simply count. Do it — a counting argument that disagrees with a loop is wrong, and it is always the argument.

For a limit of a thousand million the loop is impossible and the argument is instant, which is the point.

Python

count = 0
for n in range(1, 101):
    if n % 2 == 0 or n % 3 == 0 or n % 5 == 0:
        count += 1

print(count)

It prints

74

How many ways can brackets be balanced?

With three pairs there are five: ((())), (()()), (())(), ()(()), ()()().

That 5 is a Catalan number, and the same sequence — 1, 1, 2, 5, 14, 42 — counts mountain ranges, binary trees, and ways to cut a polygon into triangles.

Python

def balanced(open_left, close_left, so_far, found):
    if open_left == 0 and close_left == 0:
        found.append(so_far)
        return
    if open_left > 0:
        balanced(open_left - 1, close_left, so_far + "(", found)
    if close_left > open_left:
        balanced(open_left, close_left - 1, so_far + ")", found)

found = []
balanced(3, 3, "", found)
print(found)
print(len(found))

It prints

['((()))', '(()())', '(())()', '()(())', '()()()']
5

Split on where the first bracket closes

The opening bracket must close somewhere. Inside it is a balanced string, and after it is a balanced string, and every way of splitting the remaining pairs between the two gives a different answer.

So c[i] is the sum over j of c[j] * c[i - 1 - j]. Listing them all would be hopeless by 20 pairs; this loop is not.

Python

def catalan(n):
    c = [0] * (n + 1)
    c[0] = 1
    for i in range(1, n + 1):
        for j in range(i):
            c[i] += c[j] * c[i - 1 - j]
    return c

print(catalan(10))

It prints

[1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796]

And there is a closed form

choose(2n, n) divided by n + 1 gives the same numbers. It counts every string of n opens and n closes and then throws away the ones that go negative somewhere.

Under a modulus, that division needs the inverse from unit 14 — which is the moment the whole chain of this unit and the last one clicks together.

Python

def choose(n, k):
    result = 1
    for i in range(k):
        result = result * (n - i) // (i + 1)
    return result

print([choose(2 * n, n) // (n + 1) for n in range(11)])

It prints

[1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796]

Two ways to the same numbers is the whole trick

The loop and the formula agree on all eleven values, and the brute force agrees on the small ones. Three routes, one answer.

That is how you check a counting argument you are not sure of: build the small cases by force, and see whether your clever formula says the same thing.