Combination
Countable subsets!

A combination of a set is a subset made from its elements. In combinatorics, it's often necessary to count the number of combinations that can be made from a set.

Since combinations are sets, the order of their elements does not matter, unlike permutations.

Contents

\(r\)-combination

An \(r\)-combination of a set is an \(r\)-sized subset of it. For example, \(\set{9, 5, 6}\) and \(\set{6, 1, 7}\) are both \(3\)-combinations of the set \(\set{9, 1, 6, 5, 7, 8}.\) However, \((6, 1, 7)\) would not be a \(3\)-combination of that set, because even though it has \(3\) elements, the parentheses \(()\) indicates that it is a sequence, in which order matters. The total number of \(3\)-permutations that can be made from that set of \(6\) elements is known to be \(P(6, 3) = \frac{6!}{(6 - 3)!} = \frac{6!}{3!} = 120.\) Let's define a function \(f\) that converts the \(3\)-permutations into \(3\)-combinations by just removing order. For example, \(f((6, 1, 7)) = \set{6, 1, 7}.\) Because there are \(3! = 6\) ways to arrange \(3\) elements, there will be \(6\) \(3\)-permutations for every \(3\)-combination, making \(f\) a \(6\)-to-\(1\) correspondence. Indeed, we can see that \((1, 6, 7)\), \((1, 7, 6)\), \((6, 1, 7)\), \((6, 7, 1)\), \((7, 1, 6)\), and \((7, 6, 1)\) will all map to the set \(\set{6, 1, 7}.\) By the \(k\)-to-\(1\) rule, with \(k = 3!\), the total number of \(3\)-combinations that can be made from that set is \(\frac{P(6, 3)}{3!} = \frac{120}{6} = 20.\) This method of counting can be generalized:

The number of \(r\)-combinations (subsets of size \(r\)) that can be made from a set of \(n\) elements, denoted \(\binom{n}{r}\), is: $$\binom{n}{r} = \frac{n!}{r!(n-r)!}$$
⚠ The formula above is a consequence of the \(r!\)-to-\(1\) correspondence that exists between the \(r\)-permutations and \(r\)-combinations of a set of size \(n.\) If you're still confused, think about the number of \(r\)-permutations that can be made from a single \(r\)-combination, which is \(P(r, r) = r!.\) With \(P(n, r)\) total \(r\)-permutations, there must be \(\frac{P(n, r)}{r!}\) total \(r\)-combinations.
⚠ \(\binom{n}{r}\) has its own special notation, but it could also be written as \(C(n, r)\) or \(nCr.\) All are read "\(n\) choose \(r.\)"
⚠ Again, it is assumed that \(n\) and \(r\) are always non-negative in these equations, and satisfy \(n \geq r.\)

Just like with \(r\)-permutations, there are also lots of problems that can be solved by counting \(r\)-combinations. How many ways are there to elect \(3\) representatives from \(6\) people? Unlike the question asked before with permutations, every person elected is a representative, meaning there is no order imposed on the roles of those elected. How many \(6\)-bit binary strings have exactly \(3\) \(1\)'s? The answer is the same as the answer to the previous question I asked about electing representatives. The overarching theme here seems to be that whenever what is "chosen" shares the same role as everything else that is being chosen, whether that role is being a representative in a group or a \(1\) in a binary string, you should know to count combinations, and not permutations.

⚠ Some problems can make you unsure about whether to count permutations or combinations. Lucky for you, there is a simple solution: look at what is being selected! Do the selected elements get assigned to distinct (different) roles? If so, then, during the selection process, you would need to know which role you're giving to each element as they are selected, which is a roundabout way of saying that the order of selection matters and that you therefore need to count permutations. I hope this explanation of when to use permutations is clearer than just vaguely saying "when order matters!" In the other case, where the selected elements are each assigned to identical roles such that it wouldn't matter if any two selected items traded roles, count combinations instead.

Curiously, an identity involving \(\binom{n}{r}\) can also be obtained by putting \(n - r\) in for \(r.\) You might like to think of \(\binom{n}{n-r}\) as counting the complements of the subsets that \(\binom{n}{r}\) is counting, given a universal set of size \(n.\) Actually, if you want, you could rigorously prove that a bijection exists between the \(r\)-sized subsets and the \((n - r)\)-sized subsets of any set of size \(n\), where each \(r\)-sized subset maps to the corresponding \((n - r)\)-sized subset that has the \((n - r)\) elements which the \(r\)-sized subset excludes. Here's the identity:

The number of subsets of size \((n - r)\) that can be made from a set of \(n\) elements is equal to the number of subsets of size \(r\) that can be made from a set of \(n\) elements: $$\binom{n}{n - r} = \binom{n}{r}$$
⚠ If all that talk about bijections is confusing you, let's bring in a familiar question. How many ways are there to elect \(5\) representatives from \(20\) people? Normally, to solve this problem, you would calculate \(\binom{20}{5}.\) However, it is just as valid to consider how many ways there are to have \(15\) people not be representatives in a group of \(20\) people, and calculate \(\binom{20}{15}\) instead. The result would be equivalent, as shown by the above identity.

Imagine you are at \((0, 0)\) on the coordinate plane. You want to reach the point \((7, 3)\), but can only move right or up exactly \(1\) unit at a time, which is considered a step. How many distinct paths (sequences of steps) can you take from \((0, 0)\) to \((7, 3)\)? Well, let's first convince ourselves that any successful path would consist of exactly \(10\) steps, \(7\) of which are right and \(3\) of which are up. Therefore, what makes a path distinct is the order in which those \(10\) steps are arranged. Since a step can only be either right or up, you can think of a path as being a \(10\)-bit binary string where the \(1\)'s represent right, and the \(0\)'s represent up. This is a bijection. So, the question is now: how many \(10\)-bit binary strings have exactly \(7\) \(1\)'s? Answering that would be the same as answering: how many \(10\)-step paths from \((0, 0)\) to \((7, 3)\) have exactly \(7\) steps to the right? The answer is \(\binom{10}{7}.\) Or, alternatively: \(\binom{10}{3}\), if we were choosing which \(3\) steps should be up. In general, the number of distinct paths you can take from \((0, 0)\) to \((x, y)\), given the same restrictions on movement, is \(\binom{x+y}{x}\), which is equal to \(\binom{x+y}{y}.\)

Logic & Proofs
Integer • Rational number • Inequality • Real number • Theorem • Proof • Statement • Proof by exhaustion • Universal generalization • Counterexample • Existence proof • Existential instantiation • Axiom • Logic • Truth • Proposition • Compound proposition • Logical operation • Logical equivalence • Tautology • Contradiction • Logic law • Predicate • Domain • Quantifier • Argument • Rule of inference • Logical proof • Direct proof • Proof by contrapositive • Irrational number • Proof by contradiction • Proof by cases • Summation • Disjunctive normal form
Set Theory
Set • Element • Empty set • Universal set • Subset • Power set • Cartesian product • String • Binary string • Empty string • Set operation • Set identity • Set proof
Functions
Function • Floor function • Ceiling function • Inverse function
Algorithms
Algorithm • Pseudocode • Command • Asymptotic notation • Time complexity • Atomic operation • Brute-force algorithm
Relations
Relation • Reflexive relation • Symmetric relation • Transitive relation • Relation composition • Equivalence relation • Equivalence class
Number Theory
Integer division • Linear combination • Division algorithm • Modular arithmetic • Prime factorization • Greatest common divisor • Least common multiple • Primality test • Factoring algorithm • Euclid's theorem • Prime number theorem • Euclidean algorithm
Induction
Proof by induction • Fibonacci sequence • Proof by strong induction • Well-ordering principle • Sequence • Factorial • Recursive definition
Combinatorics
Rule of product • Rule of sum • Bijection rule • Permutation • Combination • Complement rule • Experiment • Outcome • Sample space • Event • Probability • Probability distribution • Uniform distribution • Multiset • Sixfold way • Inclusion-exclusion principle • Pigeonhole principle
Graph Theory
Graph • Walk • Subgraph • Regular graph • Complete graph • Empty graph • Cycle graph • Hypercube graph • Bipartite graph • Component • Eulerian circuit • Eulerian trail • Hamiltonian cycle • Hamiltonian path • Tree • Huffman tree • Substring • Forest • Path graph • Star • Spanning tree • Weighted graph • Minimum spanning tree • Greedy algorithm • Prim's algorithm
Recursion
Recursion • Recursive algorithm • Correctness proof • Divide-and-conquer algorithm • Sorting algorithm • Merge sort