Permutations and Combinations
Count arrangements where order matters and selections where it does not. Find the selection count by dividing the arrangement count by the number of orders for each selection.
What a learner can do afterwards
- Choose between a permutation and a combination count from the wording of a problem
- Derive the combination formula from the permutation count by dividing out repeats
- Count arrangements of a multiset where some objects are identical
1 · Read
Use the product rule for ordered choices and the sum rule for disjoint cases. A permutation distinguishes orders; a combination distinguishes only the chosen group. Test the outcomes, not the word 'choose': choosing people for different posts still distinguishes order. Here P(n,r) and C(n,r) use n distinct objects, with none chosen twice. The integers satisfy 0 <= r <= n.
Nine students fill two different posts, with nobody holding both. There are 9 choices, then 8, giving 72 assignments. In general, P(n,r) multiplies r decreasing factors: n! / (n-r)!. For positive n, n! means n × (n-1) × ... × 1, and 0! = 1.
Each group of r distinct people has r! ordered listings. Divide by that number to count each group once: C(n,r) = P(n,r) / r! = n! / (r! × (n-r)!). For example, choosing 3 people from 8 gives (8 × 7 × 6) / (3 × 2 × 1) = 56. For an unordered pair, the two listings are A then B and B then A.
For a row using all n objects, identical copies cause repeated counting. If their type counts are a, b and so on, summing to n, divide n! by a! × b! × ... . Temporarily labelling the copies explains why: each visible row has that many labelled versions. MOM has two Ms and one O, giving 3! / 2! = 3 distinct rows.
A required increasing order leaves one listing for each chosen set, so use C(n,r), not P(n,r). Choosing r objects also determines the n-r left out: C(n,r) = C(n,n-r). If one named object must be included, fix it and choose the remaining members from the other n-1 objects. A required member of a pair leaves n-1 choices for its partner.
For an arrangement with a fixed first object, remove it before counting the remaining row. Update the type counts used in the divisor. For AABB with A fixed first, the remaining letters are ABB. They give 3! / 2! = 3 rows. The fixed first slot contributes one choice.
Distinguish outcomes first. Divide ordered selections by r! for groups, and full arrangements by the factorial of each identical type's count.
Lesson and practice text written for this dataset. Counting resources were consulted for mathematical facts and question-design study.
Readings and extra questions written for this dataset. Video links are credited to Khan Academy in the source catalog; their publisher terms are unverified.
More to read
Counting distinct assignments
Numbered positions let us tell ordered outcomes apart. Place different cards in three numbered slots without using any card twice. Each filled slot removes one option for the next slot. Multiplying those decreasing counts gives P(n,3). More generally, P(n,r) = n! / (n-r)!, where n distinct objects supply r positions. A factorial multiplies positive integers down to one, and 0! is defined as one. These formulas assume an object cannot be selected again. If reuse is allowed, count the available options at each stage instead.
How lists repeat a group
Suppose a list records r different members of a group. Rearranging the list gives r! listings of those same members. Every group has exactly that many listings, so C(n,r) = P(n,r) / r!. This counts selections from distinct objects with no repeated selection. A row made from identical copies needs a different divisor. Temporarily label those copies and count all n! labelled rows. Erasing the labels merges a! rows for a type appearing a times. Divide by the product of these factorials to count the visible rows.
Use the excluded group
Write down the objects excluded from a selection. That excluded group determines the selection, because every other available object was included. This gives a one-to-one correspondence between r-object selections and excluded groups of size n-r, proving C(n,r) = C(n,n-r). Counting the smaller group may take fewer factors. Another check uses P(n,r) = C(n,r) × r!. For valid selections without repetition, the combination count is strictly smaller when r is at least two. At r=0 or r=1, the two counts are equal.
Describe an outcome before counting
Decide what information an outcome records. A chair and a secretary have different roles, so exchanging their names changes the outcome. An equal-duty committee records only membership. A list required to be increasing also has one permitted order for each chosen set. These distinctions cannot be decided from the word 'choose' alone. When a row has a fixed first object, remove it before counting the remaining positions. For identical copies, use the multiplicities that remain after removing the fixed object.
Explore more
2 · Watch
به انگلیسیTake it off screen
Where it sits
Learn first
This opens up
14 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.