Course contentsShow
← Computer Science
Lesson 100 of 2,8722. Discrete Mathematics for CSFree lesson

Combinations: Selections Without Order

Master unordered selections using the binomial coefficient C(n,r) and understand when order doesn't matter.

Combinations: Selections Without Order

What you'll learn: How to count selections when the order doesn't matter, like choosing team members or pizza toppings.

The Core Idea

When you studied Permutations: Arrangements Without Repetition (the previous lesson), order mattered—ABC was different from BAC. But what if you're simply choosing 3 students out of 10 to form a study group? Alice-Bob-Carol is the same group as Carol-Alice-Bob. This is a combination: selecting items where order is irrelevant.

Why Combinations Are Different

Think of permutations as arranging books on a shelf (order matters), and combinations as grabbing books to put in a bag (order doesn't matter). Since permutations count every arrangement, they overcount combinations by a factor equal to the number of ways to rearrange the selected items.

The Binomial Coefficient Formula

We write combinations as C(n, r) or nCr, also called the binomial coefficient:

C(n, r) = n! / (r! × (n - r)!)

  • n = total items available
  • r = items to select
  • The division by r! removes the overcounting from order

Example

How many ways can you choose 2 toppings from 4 options (pepperoni, mushrooms, olives, onions)?

C(4, 2) = 4! / (2! × 2!) = 24 / (2 × 2) = 6

The six combinations: {pepperoni, mushrooms}, {pepperoni, olives}, {pepperoni, onions}, {mushrooms, olives}, {mushrooms, onions}, {olives, onions}.

Notice: We'd have 12 permutations (P(4,2) = 12), but only 6 combinations because order doesn't matter.

Key Takeaway: Use combinations C(n, r) = n! / (r! × (n - r)!) when selecting items and order doesn't matter—essential for counting subsets, committee formations, and many algorithmic problems.