Combinations and Selection Problems
A combination is an unordered selection; nCr = n!/(r!(n-r)!) counts the r-subsets of an n-set.
What is Combinations and Selection Problems?
A combination is an unordered selection; nCr = n!/(r!(n-r)!) counts the r-subsets of an n-set.
Key formula / rule: nCr = nC(n-r) and the sum of all nCr over r equals 2n.
Key points
- Compute selection counts using combinations with constraints.
- Prove Pascal's rule combinatorially.
Common exam trap
Using a combination where the objects are actually arranged in order.
Definitions
- Term
Combinations and Selection Problems
- Meaning
A combination is an unordered selection; nCr = n!/(r!(n-r)!) counts the r-subsets of an n-set.
- Term
Combinations and Selection Problems — explanation
- Meaning
Dividing a permutation count by r! removes the ordering that a selection problem does not care about. Grouping, distribution and committee problems all reduce to combinations with constraints.
Learning objectives
Compute selection counts using combinations with constraints.
Prove Pascal's rule combinatorially.
Formulae
- Key point
nCr = nC(n-r) and the sum of all nCr over r equals 2n.
- Key point
Pascal's rule states nCr = (n-1)C(r-1) + (n-1)Cr.
- Key point
Selections with at least one constraint are handled by complementary counting.
Prerequisites
MAT-U1-PC-T1-S1-C1
Common mistakes
Using a combination where the objects are actually arranged in order.
Double counting when cases in a case split overlap.
Keywords
Combinations
Selection
Problems
Practice preview
How many ways can a committee of 3 members be selected from a group of 7 people?…
easy
A box contains 10 distinct balls. In how many ways can 2 balls be chosen from the box?…
easy
There are 10 points in a plane, no three of which are collinear. How many straight lines can be formed by joining any two of these points?…
medium