# Combinations [https://en.wikipedia.org/wiki/Pascal%27s\_triangle](https://en.wikipedia.org/wiki/Pascal's_triangle) ) **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 --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://mandober.gitbook.io/math-debrief/501-number-theory/630-combinatorics/combinations.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.