> For the complete documentation index, see [llms.txt](https://mandober.gitbook.io/math-debrief/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mandober.gitbook.io/math-debrief/501-number-theory/630-combinatorics/combinations.md). # Combinations ) **Combinatorics** studies the problems concerning *counting* and *ordering*, such as *partitioning* and *enumerations*. The number of ways to select $$k$$ objects from the set containing $$n$$ objects is denoted and calculated by: $$ \displaystyle{ C(n,k) = \ \_nC\_k = {n \choose k} = {n \choose n - k} = \frac {n!} {k!(n - k)!} } $$ The expression $$n\choose k$$ is read "n choose k". This formula shows that the number of ways to select 3 elements from the 10-element set is the same as the number of ways to select 7: $$ \displaystyle{ {10 \choose 3} = {10 \choose 7} = \frac{10!}{3!7!} = \frac{10!}{7!3!} } $$ Each combination $$C(n,r)$$ has a certain *frequency* and *frequency ratio* and all frequency ratios sum up to 1. ## Combinations, Pascal's triangle, Powers of 2, Powerset, Binomial coefficient In combinations, the order in which we select objects is irrelevant. We're only interested in the subsets that we can form out of a given set and/or number of subsets. If a given set A contains 5 elements, A = {a,b,c,d,e}, we might as well imagine the set A as an opaque bag that contains 5 marbles (labelled with letters a-e). Then, we might be interested, for example, in finding out the number of ways we can pick 3 distinct elements from A (with the order in which the individual elements are picked is immaterial). These types of problems have their own form of expression, $$n\choose k$$ (read "n choose k"), with n being the total number of elements and k the number of elements we'd like to select. ## Partitions ) ) In combinatorics, `C(n,r)`, since r must be `0 <= r <= n`, we can consider all the cases of `C(n,r[i])` where `i` iterates from `0` to `n`. For example, `C(3,r)` can be *partitioned* into 4 partitions: `C(3,0)`, `C(3,1)`, `C(3,2)`, `C(3,3)`. Each partition has a certain *frequency*. Adding these frequencies together we get the total number of partitions possible for a set of `n` elements (with variable `r` i.e. variable partition size): `C(3,0)`=1 + `C(3,1)`=3 + `C(3,2)`=3 + `C(3,3)`=1 => 8 In set theory, powerset contains all possible subsets of some particular set. So the number 8 obtained above, is the number of elements in the powerset (of a set with 3 elements), $$2^n = 8$$, i.e. if a set has 3 elements, then the cardinality of its powerset is 8. A particular partition frequency can be divided by the number of all possible partitions to get the ratio of those combos accounted for by that particular partition. E.g. C(3,1)=3, so its frequency ratio is 3/8. Adding all freq. ratios amounts to 1. E.g. 1/8 + 3/8 + 3/8 + 1+8 = 1 ## Examples ### List all 2-element partitions of a 4-element set The number of 2-element partitions: C(4,2) = 4!/2!2! = 12/2 = 6 Let set A={a,b,c,d}, then there are 6 two-element subsets of P(A):\ ab, ac, ad, bc, bd, cd\ (incorrect but convenient notation) ### How many ways to choose 2 out of 4 $$n=4,\ \ r=2$$ $$ \frac{n!}{r!(n-r)!} \= \frac{4!}{2!(4-2)!} \= \frac{4!}{2!·2!} \= \frac{4·3·\not 2!}{2!·\not 2!} \= 6 $$ ### How may distinct pairs can be made with 4 elements $$ {n \choose k} = {4 \choose 2} = \frac{4!}{2!} = \frac{4·3·2!}{2!} = 6 $$ Check: X={a,b,c,d}\ n=4\ 6 pairs: ab, ac, ad, bc, bd, cd