Gersonides’ counting formulas

Levi ben Gershon’s 1321 Maaseh Hoshev proved by induction that n objects can be arranged in n! orders, that k of them can be arranged in n!/(n-k)! ways, and that k can be chosen in n!/(k!(n-k)!) ways. This example checks each formula against brute-force enumeration.

import matplotlib.pyplot as plt

from mathematicskit.combinatorics import combinations_count, generate_combinations, generate_permutations, permutations_count

Formula against enumeration

items = "ABCDE"
n = len(items)
print(f"arrangements of {n} objects: formula {permutations_count(n)}, listed {len(generate_permutations(items))}")
for k in range(n + 1):
    ordered = permutations_count(n, k)
    unordered = combinations_count(n, k)
    listed = len(generate_combinations(items, k))
    print(f"k = {k}: P(n,k) = {ordered:3d}, C(n,k) = {unordered:2d} (listed {listed}), P/C = k! = {ordered // unordered}")

arrangements of 5 objects: formula 120, listed 120
k = 0: P(n,k) =   1, C(n,k) =  1 (listed 1), P/C = k! = 1
k = 1: P(n,k) =   5, C(n,k) =  5 (listed 5), P/C = k! = 1
k = 2: P(n,k) =  20, C(n,k) = 10 (listed 10), P/C = k! = 2
k = 3: P(n,k) =  60, C(n,k) = 10 (listed 10), P/C = k! = 6
k = 4: P(n,k) = 120, C(n,k) =  5 (listed 5), P/C = k! = 24
k = 5: P(n,k) = 120, C(n,k) =  1 (listed 1), P/C = k! = 120

Arrangements grow much faster than selections

ks = range(0, 11)
fig, ax = plt.subplots()
ax.semilogy(list(ks), [permutations_count(10, k) for k in ks], "o-", label="ordered: P(10, k)")
ax.semilogy(list(ks), [combinations_count(10, k) for k in ks], "s-", label="unordered: C(10, k)")
ax.set_xlabel("k")
ax.set_ylabel("count")
ax.legend()
ax.set_title("Choosing k of 10 objects")

Text(0.5, 1.0, 'Choosing k of 10 objects')