Recommended resources
The freely available resources this lesson will direct you to.
Hello! Last lesson, you counted arrangements of a fixed inventory, correcting for swaps of indistinguishable objects. Now the question changes: from distinct objects, you want to select , and the order in which you name them does not create a new selection.
We will derive the combination formula from the permutation rule you already know, then use it in several representations of the same counting problem. Allow about 35–40 minutes, including the video and reading.
From ordered lists to selections
Suppose eight distinct proposals are available and three will be selected for review. If you record first choice, second choice, third choice, you are counting ordered lists:
But if the outcome is just the set of three proposals, each set has been counted times. For example, choosing describes the same set as choosing . Thus the number of selections is .
The argument generalizes. An ordered selection of distinct objects from can be formed in
ways. Every unordered selection contains distinct objects, which can be listed in exactly orders. Crucially, this number is the same for every selection. Consequently, for ,
The notation , read “ choose ,” counts the -element subsets of an -element set. This is selection without replacement: an object either belongs to the subset or it does not.
Watch MIT OpenCourseWare’s L04.4 Combinations for a second derivation. Instead of describing the calculation as correcting an overcount, the lecturer counts the same ordered lists in two ways.
MIT OpenCourseWare’s L04.4 Combinations derives the combination formula by connecting subsets to ordered selections and checks its boundary cases.
Watch the definition for the meaning of a subset and the notation. In the derivation, follow the two counts of ordered lists: filling positions directly versus choosing the members first and then ordering them. Finish with boundary cases, especially what selecting none or all of the objects means.
In the video’s two-stage count, the number of ordered lists is . Setting this equal to gives the boxed formula. The two-stage argument and the overcounting argument are the same relationship viewed from opposite directions.
Which order is being ignored?
“Order does not matter” is useful shorthand, but it needs an object: the order of what? A selected set has no first or second member. An ordered list does. Meanwhile, the objects you select can still have distinct identities.
Read the discussion in Counting with Equivalence by Richard Grassl and Oscar Levin. It sharpens this distinction with examples where an outcome may have an apparent order, yet a combination is still the right count.
Read Grassl and Levin’s discussion of when order changes an outcome. It is a useful check against choosing a formula based only on words such as “select” or “arrange.”
In Subsection 2.3.2, “When does Order Matter?”, begin with the opening distinction. Then look at Activity 116(b), beginning increasing digits, and Activities 117–118, from bit strings onward. Focus on what counts as one outcome; you need not complete every activity in the subsection.
Consider five distinct digits chosen from . If you may arrange them freely into a five-digit number, different orders produce different numbers, giving . If the digits must appear in increasing order, each choice of five digits determines exactly one valid number, giving . The result is a written sequence in both cases. What changes is how many outcomes each selected set can produce under the stated rule.
A different caution concerns repeats. If you can select the same object more than once, you are not choosing a subset, and does not directly answer the question. First specify what makes two outcomes distinct; only then decide what to count.
Connections to the previous lesson
There is another way to see . Label positions, and put a in each of the selected positions and a in each of the others. Every -element subset determines exactly one such string, and every string with exactly ones determines exactly one subset. Hence also counts length- binary strings with exactly ones.
This agrees with last lesson’s multiset-arrangement formula: arranging identical ones and identical zeros gives
Here, the positions distinguish the strings, while exchanges among the ones—or among the zeros—do not. It is the same count expressed as a subset, a binary string, or a multiset arrangement.
Selecting objects also determines the objects left out. Pair each selected set with its complement. This gives the useful symmetry
For instance, selecting three of eight proposals is equivalent, for counting purposes, to specifying the five that will not be selected. At the boundaries, : there is one empty subset and one subset containing everything.
Counting with a specified composition
Combinations can be joined using the multiplication principle. Suppose five available proposals are in one category and four are in another. To select a three-proposal set containing exactly two from the first category, choose two of its five members and one of the four members in the second:
There is no extra : you have already specified a set, not an order for reviewing its members. Nor do you divide by : the two selected proposals in the first category are distinct objects, and has already removed the order in which they might be named.
A quick consistency check is available. There are unrestricted three-proposal sets across both categories, so the 40 sets with the specified composition must be fewer than 84. This kind of comparison is often helpful when a counting expression has acquired one factor too many.
The image below shows another counting relationship. In its highlighted entry, , or
Why does that addition work? Fix one particular object among seven, and count five-object subsets in two disjoint cases. If the object is included, choose the other four from the remaining six: . If it is excluded, choose all five from the remaining six: . Every five-object subset falls into exactly one case. This is Pascal’s identity in counting form:
It provides both a way to build the triangle and an independent check on small combination counts.
Key takeaways
Use when an outcome is an -element subset of distinct objects, chosen without replacement. The denominator removes the different orders in which the same selected objects could be listed. To check a model, state exactly what one outcome is and whether changing the order of its selected members changes it.
Next, you will extend this selection logic to placing distinct objects into labelled groups of prescribed sizes.