Skip to main content

Combinatorics

LinearCircularNon-Ordinal
Non-RepetitivePkn=n!(n−k)!P^n_k = \frac{n!}{(n-k)!}n!k⋅(n−k)!\frac{n!}{k \cdot (n-k)!}Ckn=n!k!⋅(n−k)!C_{k}^{n}={\frac{n!}{k!\cdot (n-k)!}}
RepetitiveUkn=nkU^n_k = n^k∑r∣k(r⋅φ(r)⋅nkr)k\frac{\sum_{r \vert k}(r \cdot \varphi (r) \cdot n^{\frac{k}{r}})}{k}Hkn=(n+k−1)!k!⋅(n−1)!H_{k}^{n}={\frac{(n+k-1)!}{k!\cdot (n-1)!}}

Permutation​

Pkn=n!(n−k)!P^n_k = \frac{n!}{(n-k)!}

Counting​

import math

def permutation(n, k):
    return math.factorial(n) // math.factorial(n - k)

Example:

print(permutation(4, 2)) # 12

Generation​

itertools.permutations("ABCD", 2)
# [('A', 'B'),
#  ('A', 'C'),
#  ('A', 'D'),
#  ('B', 'A'),
#  ('B', 'C'),
#  ('B', 'D'),
#  ('C', 'A'),
#  ('C', 'B'),
#  ('C', 'D'),
#  ('D', 'A'),
#  ('D', 'B'),
#  ('D', 'C')]

Product​

Ukn=nkU^n_k = n^k

Counting​

def product(n, k):
    return n ** k

Example:

print(product(4, 2)) # 16

Generation​

itertools.product("ABCD", repeat=2)
# [('A', 'A'),
#  ('A', 'B'),
#  ('A', 'C'),
#  ('A', 'D'),
#  ('B', 'A'),
#  ('B', 'B'),
#  ('B', 'C'),
#  ('B', 'D'),
#  ('C', 'A'),
#  ('C', 'B'),
#  ('C', 'C'),
#  ('C', 'D'),
#  ('D', 'A'),
#  ('D', 'B'),
#  ('D', 'C'),
#  ('D', 'D')]

Combination​

Ckn=n!k!⋅(n−k)!C_{k}^{n}={\frac{n!}{k!\cdot (n-k)!}}

Counting​

import math

def combination(n, k):
    return math.factorial(n) // (math.factorial(k) * math.factorial(n - k))

Example:

print(combination(4, 2)) # 6

Generation​

itertools.combinations("ABCD", 2)
# [('A', 'B'),
#  ('A', 'C'),
#  ('A', 'D'),
#  ('B', 'C'),
#  ('B', 'D'),
#  ('C', 'D')]

Counting multisets​

Hkn=(n+k−1)!k!⋅(n−1)!H_{k}^{n}={\frac{(n+k-1)!}{k!\cdot (n-1)!}}

tip

Multiset can be used to calculate the number of combinations of non-negative integers that sum to a given number.

E.g. The number of ways to sum 3 non-negative integers to 4 is H43=C26=15H^3_4 = C^6_2 = 15.

Counting​

import math

def counting_multisets(n, k):
    return math.factorial(n + k - 1) // (math.factorial(k) * math.factorial(n - 1))

Example:

print(counting_multisets(4, 2)) # 10

Generation​

itertools.combinations_with_replacement("ABCD", 2)
# [('A', 'A'),
#  ('A', 'B'),
#  ('A', 'C'),
#  ('A', 'D'),
#  ('B', 'B'),
#  ('B', 'C'),
#  ('B', 'D'),
#  ('C', 'C'),
#  ('C', 'D'),
#  ('D', 'D')]

Reference​