# Combinations

[https://www.youtube.com/watch?v=0iMtlus-afo\&list=TLPQMjQxMDIwMjBfeWCl0eYdng\&index=30](https://www.youtube.com/watch?v=0iMtlus-afo\&list=TLPQMjQxMDIwMjBfeWCl0eYdng\&index=30) [https://en.wikipedia.org/wiki/Pascal%27s\_triangle](https://en.wikipedia.org/wiki/Pascal's_triangle) [https://en.wikipedia.org/wiki/Binomial\_theorem](https://en.wikipedia.org/wiki/Binomial_theorem) [https://en.wikipedia.org/wiki/Binomial\_distribution](https://en.wikipedia.org/wiki/Binomial_distribution) [https://rosettacode.org/wiki/Combinations\_and\_permutations](https://rosettacode.org/wiki/Combinations_and_permutations) [https://en.wikipedia.org/wiki/Combination](https://en.wikipedia.org/wiki/Combination) [https://en.wikipedia.org/wiki/Permutation](https://en.wikipedia.org/wiki/Permutation) [https://rosettacode.org/wiki/Gamma\_function](https://rosettacode.org/wiki/Gamma_function) [https://rosettacode.org/wiki/Evaluate\_binomial\_coefficients](https://rosettacode.org/wiki/Evaluate_binomial_coefficients) [https://en.wikipedia.org/wiki/Twelvefold\_way](https://en.wikipedia.org/wiki/Twelvefold_way) [https://en.wikipedia.org/wiki/Multiset](https://en.wikipedia.org/wiki/Multiset) [https://en.wikipedia.org/wiki/Partition\_of\_a\_set](https://en.wikipedia.org/wiki/Partition_of_a_set) [https://en.wikipedia.org/wiki/Partition\_(number\_theory](https://en.wikipedia.org/wiki/Partition_\(number_theory))

**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

[https://en.wikipedia.org/wiki/Partition\_(number\_theory](https://en.wikipedia.org/wiki/Partition_\(number_theory)) [https://artofproblemsolving.com/wiki/index.php/Partition\_(combinatorics](https://artofproblemsolving.com/wiki/index.php/Partition_\(combinatorics))

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
