- Describe the defining properties of a set.
- Apply the sum and product rules to counting problems.
- Distinguish permutations, variations, circular arrangements, and combinations.
- Count arrangements with repeated elements and selections with repetition.
- Use Pascal's identity, the binomial theorem, the pigeonhole principle, inclusion-exclusion, and derangements.
- Whole-number multiplication and division
- Basic algebraic notation
- Familiarity with powers and simple sets
Sets as Mathematical Containers
A set is a well-defined, unordered collection of distinct elements with no fixed size limit.
Picture a bag holding a marble, a photograph, and a pen. Mathematics calls the bag a set and the objects inside it elements. This simple container idea gives us a way to organize mathematical objects.
- Orderless: rearranging the elements does not change the set, so {1, 2, 3} and {3, 2, 1} are equal.
- Unbounded: a set may contain any number of elements, including infinitely many.
- Distinct: repetition does not matter; membership matters only once, so {🍎, 🍎, 🍌} is the same set as {🍎, 🍌}.
- Well-defined: it must be possible to decide whether an object belongs. “Tall people” is vague, while “people taller than 6 ft” gives a clear rule.
How does an unordered set differ from an everyday arrangement in which position matters? Give one example whose order matters in ordinary use but not when its objects are treated as set elements.
Two Basic Counting Rules
Multiply choices joined by “and”; add mutually exclusive choices joined by “or.”
Permutations: Using Every Object in Order
A permutation counts ordered arrangements that use all available distinct objects.
Consider the ten heart cards from ace through ten. To draw all ten in sequence, we may think either of selecting cards one after another or assigning cards to ten fixed positions.
- Selection model: the successive numbers of choices are 10, 9, 8, and so on down to 1.
- Allocation model: the first position accepts any of 10 cards, the second any of the remaining 9, and the pattern continues.
For the cards, 10! = 3,628,800. This is a permutation because every card is used and its position matters.
Variations: Ordered Choices from Part of a Set
A variation keeps order important but uses only some of the available objects.
Arrangements Around a Circle
Rotations represent the same circular arrangement, and mirror images may also be identified.
Permutations When Some Elements Repeat
Divide the full factorial count by the internal permutations of each identical group.
Begin as if every object were distinct. Swapping identical copies produces no visible change, so those duplicate counts must be removed by division.
Combinations: Selecting Without Order
A combination records which objects were selected, not the sequence of selection.
Suppose three toppings are chosen from ten without repetition. Cheese, mushrooms, and olives make the same pizza regardless of the order in which they were picked. That is why combinations ignore order.
An ordered selection of p objects from n has n!/(n−p)! possibilities. Each chosen group is represented by p! different orders, so combinations × p! = variations.
Two Useful Combination Identities
Selecting p objects determines the n−p objects left out, so the two counts are equal.
To justify Pascal's identity, designate one target object. If it is excluded, choose all p objects from the other n−1. If it is included, choose the remaining p−1 from those n−1 objects. The cases cannot occur together, so their counts are added.
Building Pascal's Triangle
- Row 0: 1, because (\binom{0}{0}=1).
- Row 1: 1, 1.
- Row 2: 1, 2, 1.
- Continue by making each entry the sum of the two entries above it.
The row totals are 1, 2, 4, 8, 16, 32, 64, and so on: the powers of two.
Combinations Inside Binomial Expansions
Binomial coefficients count how many expansion choices produce each term.
Expanding a power such as (a+b)⁵ directly is lengthy. Each bracket contributes either a or b, so combination counts provide the coefficients efficiently.
Dividing Objects Among Several Groups
Choose each group's objects in sequence and combine the counts with the product rule.
Ordered and Unordered Selection with Repetition
Unlimited supplies change ordered counts to powers and unordered counts to a divider problem.
If repetition is allowed and order matters, every one of p positions has n choices. The number of ordered results is therefore nᵖ.
Guaranteeing a Crowded Category
The pigeonhole principle proves that some category must contain a minimum number of objects.
More generally, distributing k×n+1 pigeons among n holes forces at least one hole to hold at least k+1 pigeons.
Correcting Counts for Overlapping Sets
Inclusion-exclusion alternates addition and subtraction so shared elements are counted exactly once.
Adding both set sizes counts their shared elements twice, so one copy of the overlap must be subtracted.
The continuing pattern alternates: add single sets, subtract pairwise overlaps, add triple overlaps, and proceed in the same way.
Derangements: Every Object in the Wrong Place
A derangement is a permutation with no fixed object, derived through inclusion-exclusion.
Take n letters and their n matching envelopes, placing one letter in each envelope. A derangement is an arrangement in which no letter enters its corresponding envelope. Its count is written !n.
- Start with all n! permutations.
- Subtract arrangements with a selected correct letter: (\binom{n}{1}(n-1)!).
- Add arrangements with a selected pair of correct letters: (\binom{n}{2}(n-2)!).
- Continue alternating subtraction and addition through the case where all n letters are fixed.
Common misconceptions
Watch out: Changing the order of a set's elements creates a different set.
Instead: A set is unordered, so rearranging the same elements does not create a new set.
Watch out: Zero factorial must equal zero.
Instead: By definition, 0! = 1 because doing nothing is the single arrangement of zero objects.
Watch out: Choosing the same objects in another sequence makes a new combination.
Instead: A combination ignores selection order; only the chosen objects matter.
Watch out: The size of overlapping sets can be found by simply adding their individual sizes.
Instead: Shared elements would be counted repeatedly, so inclusion-exclusion must correct the total.
Lesson recap
- Sets organize elements as unordered, unbounded, distinct, and well-defined collections.
- The product rule multiplies choices made together; the sum rule adds alternative choices.
- Permutations use every distinct object and care about order: n!.
- Variations use p of n objects in order: n!/(n−p)!.
- Circular arrangements identified under rotation have (n−1)! forms.
- For repeated elements, divide n! by the factorial of every repeated-group size.
- Combinations ignore order: n!/[(n−p)!p!].
- Pascal's triangle and the binomial theorem connect combination counts with binomial coefficients.
- Multiple-group selection uses successive combinations and has the same factorial pattern as repeated-element permutations.
- With unlimited repetition, ordered selections number nᵖ and unordered selections number (\binom{p+n-1}{n-1}).
- The pigeonhole principle proves that some category must reach a guaranteed occupancy.
- Inclusion-exclusion counts overlapping sets by alternating addition and subtraction.
- Derangements place every object incorrectly and make up approximately 36.8% of all permutations for sufficiently large n.
When a problem asks how many ways something can happen, first decide whether order matters, whether all or only some objects are used, whether repetition is allowed, whether the arrangement is linear or circular, and whether any elements are identical. Those decisions point toward the appropriate counting formula.