Combinations and Unordered Selections | Free Discrete Mathematics Lesson (4 College Credits) | UPI Study

UPI Study › Courses › Discrete Mathematics › Free lessons › Lesson 5.7 Free with a free account

Combinations and Unordered Selections

Discrete Mathematics · Chapter 5: Counting Methods and Basic ProbabilitySection 5.7 · lesson 33 of 879 min · free with a free account

← Circular PermutationsNext lesson: Probability of Combination Events →

Earn 4 college credits for Discrete MathematicsRecommended for credit by NCCRS · Math 230 · self-paced · one payment, lifetime access
Enroll in Discrete Mathematics · $250 →Download the syllabus (PDF)

In this lesson

Choosing r from n when order carries no information.

  • Derive the combination formula from permutations
  • Count unordered selections
  • Decide between a permutation and a combination
  • Generate combination counts with Pascal's Triangle

Transcript

Everything said in the video, section by section (1,203 words). Read along, or search it.

Counting Methods and Basic Probability

Combinations and Unordered Selections

Permutations count selections where order matters. This section builds the tool for selections where order carries no information at all. They're called combinations. We'll derive the formula directly from permutations, contrast the two tools side by side, and see a triangle of numbers that generates combination counts by simple addition.

The Opening Problem

Same Pool, Same 3 - Different Answers

A company's IT department needs to choose three employees, from a pool of ten IT staff, to receive elevated admin privileges. Does it matter which of the three is chosen first? No. Once they're selected, they either have admin access or they don't. There's no first, second, or third admin. But suppose instead the department were filling three different roles from that same pool. Primary admin, backup admin, and audit reviewer. Now order matters enormously. Being primary admin is a different outcome from being backup admin. Same ten people, same request for three of them. Yet two very different counting answers, depending on whether the three roles can be told apart. n P r, from section five point four, counts the ordered kind. This section supplies n C r, for the unordered kind.

5.7.1 When Order Stops Mattering

12 Ordered Pairs, 6 Selections

Take the small set A, B, C, D, and ask how many ways two letters can be selected. If order matters, that's four P two, four times three, which is twelve ordered pairs. They're all listed on the first line. But if order doesn't matter, A B and B A are the same selection, just written differently. Then the twelve ordered pairs collapse into only six unordered pairs. Every unordered pair accounts for exactly two ordered pairs. The pair A, B covers both A B and B A. And six times two is twelve, confirming nothing was lost or double-counted. That pattern, dividing the ordered count by the number of ways each group could be internally arranged, is exactly what the combination formula generalizes.

5.7.2 Deriving the Formula

Divide Out the Internal Orders

Every unordered selection of r items can itself be arranged in r factorial different orders. So the number of ordered selections, n P r, must equal the number of unordered selections, n C r, times the r factorial orderings each one produces. Solve for n C r. It's n P r divided by r factorial. And substituting n factorial over n minus r factorial for n P r gives the combination formula. n C r equals n factorial, over r factorial times n minus r factorial. That counts the ways to select r items from n distinct items, for r from zero to n, when order doesn't matter. Each such unordered selection is called a combination.

Worked Examples 5.7.1 and 5.7.2

Groups and Reading Lists

First, the admin privilege group. How many distinct three-person groups can be formed from ten IT staff, all receiving identical privileges? That's ten C three. Ten times nine times eight, over three times two times one. Seven hundred twenty over six, or one hundred twenty groups. Next, a student must choose four books to read this summer, from a required list of nine, with no distinction in which is read first. That's nine C four. Nine times eight times seven times six, which is three thousand twenty-four, over four factorial, twenty-four. That's one hundred twenty-six distinct sets of books.

5.7.3 Side by Side

Exactly 3! Times as Many

Now back to the opening, with exact numbers. Choosing three people from ten, for identical admin privileges, is ten C three, one hundred twenty. Choosing three from the same ten, to fill three distinct roles, is ten P three. Ten times nine times eight, which is seven hundred twenty. That's exactly six times as many. And six is three factorial, the number of ways any chosen trio could be assigned to the three distinct roles.

Table 5.7.1

Permutations Versus Combinations

This table lays the two tools side by side. A permutation asks how many ordered sequences of r items can be formed from n. A combination asks how many ways r items can be selected from n, ignoring order. The formulas differ by exactly one factor, r factorial, in the denominator. The real-world cue for a permutation is distinct roles, ranks, or ordered positions, where swapping two choices changes the outcome. For a combination, it's a group, a set, or a subset, with no internal distinction. Swapping two choices changes nothing. And they're related directly. Each unordered group of r items corresponds to exactly r factorial ordered sequences.

Worked Example 5.7.3

Diagnose, Then Solve

A photography club has twelve members. It wants to do two things. First, select four members to feature in a gallery, with no ranking among them. The four aren't ranked or distinguished, so that's a combination. Twelve C four is twelve times eleven times ten times nine, eleven thousand eight hundred eighty, over twenty-four. That's four hundred ninety-five ways. Second, select a president, vice-president, secretary, and treasurer. The four roles are distinct, so that's a permutation. Twelve P four, eleven thousand eight hundred eighty ways. As a check, eleven thousand eight hundred eighty, over four hundred ninety-five, is twenty-four. That's four factorial, the ways any four chosen members could fill the four roles.

5.7.4 Pascal's Rule

Include X, or Exclude It

The formula isn't the only way to find combination counts. They also satisfy an addition pattern called Pascal's rule. n C r equals n minus one C r minus one, plus n minus one C r. There's a direct counting explanation. Fix one particular item, call it X. Every r-item selection either includes X, or excludes it, never both. If X is included, the other r minus one items come from the remaining n minus one items. If X is excluded, all r items come from the remaining n minus one. The two cases are mutually exclusive, and together they cover every selection exactly once. So by the addition rule, they sum to n C r.

Figure 5.7.1

Pascal's Triangle, Rows 0 to 6

Arrange the combination counts row by row, for n equal to zero, one, two, and so on. That gives Pascal's triangle. Row n lists n C zero, through n C n. And every interior entry is the sum of the two entries diagonally above it. The highlighted entries show the rule in action. Four C one, which is four, plus four C two, which is six, gives ten. And that's five C two. The triangle is convenient for small n, generating combination counts with simple addition instead of factorials. But it gets impractical quickly. Finding ten C three, by building ten full rows by hand, would take far longer than the direct formula.

Takeaways

Does a Swap Change Anything?

To summarize. n C r, equal to n factorial over r factorial times n minus r factorial, counts the ways to choose r items from n when order doesn't matter. It comes from dividing n P r by r factorial, the number of orders each unordered group could be arranged in. The reliable test is whether swapping two chosen items makes a meaningfully different outcome. If yes, use n P r. If no, use n C r. And Pascal's triangle generates combination counts by addition, though it's impractical by hand for large n. Here's something to think about. A pizza with three toppings chosen from eight is a combination. There's no first topping. But a three-digit code using three different digits, entered in order, is a permutation. What specifically about the code introduces order? Try to state, in one sentence, a test you could apply to any choose r from n scenario, before doing any arithmetic.

About Discrete Mathematics at UPI Study

Discrete Mathematics (Math 230) is a self-paced online course of 87 video lessons in 13 chapters, from logic and proof to counting, probability, graph theory and trees. It carries a NCCRS credit recommendation for 4 semester credits.

Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Enroll now → Course details Download the syllabus Every course with PRO →

Why take it here

Why students take Discrete Mathematics with UPI Study

The math behind computer scienceDiscrete Mathematics is the mathematics of computer science: logic, proofs, sets, counting, probability and graphs underpin algorithms, data structures, cryptography and databases. Completing it now lets you qualify for those courses at your university.
Credit at a fraction of the priceThe same 4 credits can cost $750 or more at a US college. Here it is one payment, self-paced, with lifetime access.
Finish your degree soonerTransfer credits reduce the courses you still owe, so you can graduate earlier or lighten a heavy semester.
Strengthen an applicationA completed college-level course on an official transcript shows admissions and scholarship committees you can do the work.
Study on your own scheduleNo start dates, no deadlines. Watch the lessons, practice, and take the final when you are ready.
130,000+students helped with college creditsACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Where the credit goes

Universities that work with NCCRS

Discrete Mathematics carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Thomas Edison State UniversityThomas Edison State UniversitySigned partnerUniversity of the PeopleUniversity of the PeopleSigned partnerCharter Oak State CollegeCharter Oak State CollegeSigned partnerStrayer UniversityStrayer UniversitySigned partnerColumbia Southern UniversityColumbia Southern UniversitySigned partnerIndiana TechIndiana TechSigned partnerPenn StatePenn StateWorks with NCCRSSouthern New Hampshire UniversitySouthern New Hampshire UniversityWorks with NCCRSSUNYSUNYWorks with NCCRS +many more cooperating universitiesFind my college →

Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.

FAQ

Questions students ask us

About Combinations and Unordered Selections

How do you derive the combination formula from permutations?
Divide the permutation count by r!, because each unordered group of r items can be arranged in r! orders. Since _nP_r = {}_nC_r \cdot r!, solving gives _nC_r = \frac{_nP_r}{r!} = \frac{n!}{r!\,(n-r)!}. For A,B,C,D taken two at a time, 12/2 = 6 unordered pairs.
How do you decide whether to use a permutation or a combination?
Ask whether swapping two chosen items changes the outcome. If it does, as with president and treasurer or a code entered in order, use a permutation _nP_r. If it does not, as with a committee or a set of pizza toppings, use a combination _nC_r. The two formulas differ only by a factor of r! in the denominator.
How many ways can you choose 4 books from a list of 9 if order doesn't matter?
There are 126 ways, because the order of reading is not distinguished. Compute _9C_4 = \frac{9\cdot 8\cdot 7\cdot 6}{4!} = \frac{3024}{24} = 126. The numerator is the ordered count _9P_4 = 3024, and dividing by 4! = 24 removes the repeated orderings of each set of four books.
How does Pascal's Triangle give combination counts?
Row n of Pascal's Triangle lists _nC_0 through _nC_n, and each interior entry is the sum of the two entries diagonally above it. This is Pascal's rule, _nC_r = {}_{n-1}C_{r-1} + {}_{n-1}C_r. For example, _4C_1 + {}_4C_2 = 4 + 6 = 10 = {}_5C_2. It is practical for small n but slow for large n.

About the Discrete Mathematics course

How many college credits is Discrete Mathematics?
Discrete Mathematics (Math 230) carries a NCCRS credit recommendation for 4 semester credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
How much does Discrete Mathematics cost and what is included?
$250, paid once, with lifetime access: all 87 video lessons, a practice quiz after each, the graded work and final exam, and an official transcript when you finish. Students who want several courses choose UPI Study PRO instead.
Which universities accept UPI Study credits?
UPI Study has signed partner agreements with universities such as Thomas Edison State University, University of the People and Charter Oak State College, and works with universities such as Penn State, SNHU and SUNY. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities. Use "Find my college" on this page to check yours.
How long does Discrete Mathematics take?
It is self-paced with no deadlines. The 87 lessons total about 13 hours of video; most students add reading and practice time and finish in a few weeks to a few months, on their own schedule.
How are the exams done?
Quizzes and assignments are online in the course. The final exam is taken online with proctoring; a person on the UPI Study team checks assignments, usually within two days.
How do my credits reach my college?
When the course shows 100% complete, request the official transcript from your dashboard. It is sent to the college you name, and you can send it to more than one. Check your college first with "Find my college" on this page, or ask Athena.

Ready for the full course? Earn 4 credits in Discrete Mathematics.

87 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.

Enroll in Discrete Mathematics →Download the syllabusEvery course with PRO →
Discrete Mathematics
4 credits · NCCRSEnroll →