A combination is an unordered selection of objects — {A,B,C} and {B,A,C} are the same combination, unlike a permutation. The number of ways of choosing r objects (order irrelevant) from n distinct objects is denoted nCr ("n choose r").
Link to permutations. Every combination of r objects can itself be internally arranged in r! ways, so nPr=nCr×r!, giving
nCr=r!nPr=r!(n−r)!n!,0≤r≤n.
Permutation vs. combination, at a glance: a batting line-up of 11 from 15 players is a permutation (order = batting position matters); the team of 11 chosen from 15 is a combination (no roles attached). Distributing 3 distinct prizes is a permutation-style count; distributing 3 identical prizes is a combination-style count.
Standard identities (each provable directly from the r!(n−r)!n! formula):
- nC0=nCn=1; and nCr=r!n(n−1)⋯(n−r+1).
- Symmetry: nCr=nCn−r — choosing r to include is the same act as choosing n−r to exclude.
- Injectivity (up to symmetry): if nCx=nCy, then x=y or x+y=n.
- Pascal's rule: nCr+nCr−1=n+1Cr — the count of r-subsets of an (n+1)-set splits by whether a fixed element is included (nCr−1 ways, then fill the rest from the remaining n) or excluded (nCr ways).
- Reduction: nCr=rn×n−1Cr−1. …