Permutations
A permutation (also called arrangement) is the number of sequences we can make in selecting elements from a set.
Conditions:
-
selected elements are ordered
-
no element occurs more than once
-
it is not necessary to select all elements from the set
Example: we have 4 numbered balls. If we select 2 of them, how many different ordered sequences can we do?
Combinations
Combinations are similar to permutations except that order doesn’t matter. In other words, $(a,b)$ counts as the same combination as $(b,a)$. We thus adjust the above formula in removing the number of possible permutations in the selected sequence:
\[C^n_k = \begin{pmatrix}n \\ k\end{pmatrix} = \frac{P^n_k}{P^k_k} = \frac{\frac{n!}{(n-k)!}}{\frac{k!}{0!}} = \frac{n!}{(n-k)!k!} \text{ where } k \leq n\]Example (Time’s up): we have 15 names. If I select 5 names, what is the total number of possible combinations? (Answer: $C_5^{15} = 3003!!$)
Example (NLP): say we want to analyze headlines from news feeds. In order to remove duplicate-likes (= sentences that are closely matching) in the list of headlines, we look for closely matching pairs. We thus need to compare pairs of headlines looking at similarities. The order doesn’t matter here, i.e. $similarity(headline1, headline2) = similarity(headline2, headline1)$. Below is the implementation.
import itertools
headline_list = [
"Apple is facing difficulties",
"Microsoft shows profitability",
"Microsoft is profitable according to analysts",
"Amazon is risky according to analysts"
]
headline_combinations = list(itertools.combinations(headline_list, 2))
# len(headline_combinations) = C_2^len(headline_list)
Example (cheers): when celebrating an event, the number of “cheers” that can be made between pairs of people is $C_2^n$ with $n$ the number of people around the table.
Rule of product
The rule of product states that if there are $a$ ways of doing something and $b$ ways of doing another thing, then there are $a*b$ ways of performing both actions.
Example (code): a code composed of 4 digits. How many possibilities are there? It’s like we draw 4 times one 0-9 digit number. To get the total number of possibilities we use the rule of product: The total number of combinations is thus $C_1^{10} C_1^{10} C_1^{10} C_1^{10} = 10^4$.
Example (bits): using the rule of product, the number of combinations with $n$ binary digits is $C_1^{2}C_1^{2}…C_1^{2}$. It’s like we draw $n$ times one 0-1 digit number. Hence, the largest number a 64-bits computer can handle is $(C_1^{2})^{63}-1 = 2^{63}-1$ ($\approx 10^{19}$).
Note: we use 63 since the first bit is used for the sign. -1 is used to take into account of the 0.
Graphical representations
When the possibilities are binary (e.g. include or not include something), the number of possibilities is typically $2$ raised to a certain power. All combinations can be represented in a power set as done in the context of machine learning explainability with Shapley values (we want to evaluate a model when we include or remove one feature):
All combinations can also be represented in a tree as done in brute-force 0/1 knapsack problem:
