Combinations

Introduction to Combinations

Many everyday situations involve choosing objects or people from a larger group. For example, a teacher may select students for a committee, a coach may choose players for a team, or a customer may select toppings for a pizza.

In these situations, the order in which the objects are selected often does not matter.

A combination is a selection of objects from a larger set in which order does not matter.

For example, suppose three students—Alex, Ben, and Chloe—are selected for a science project.

Selecting Alex, Ben, and Chloe produces the same group as selecting Chloe, Alex, and Ben.

Although the order of the names changes, the members of the group remain the same.

Combinations provide a mathematical method for calculating the number of different groups that can be formed without listing every possibility.

Understanding Why Order Does Not Matter

The defining feature of a combination is that changing the order of selected objects does not create a new outcome.

Consider four students:

A, B, C, D

Suppose two students must be selected.

The possible combinations are:

• AB

• AC

• AD

• BC

• BD

• CD

There are six different combinations.

Notice that AB and BA are not counted separately because they contain the same two students.

Comparing Arrangements and Selections

If two students are selected for different positions, such as president and vice-president, order matters.

AB means A is president and B is vice-president.

BA means B is president and A is vice-president.

These are different permutations.

However, if A and B are simply selected for a committee, AB and BA represent the same combination.

This distinction is essential when deciding which counting method to use.

Combinations and Permutations

Permutations and combinations both involve selecting objects from a larger set.

The difference is whether order matters.

Worked Example: Selecting Two Students

Suppose five students are available.

Situation A: Choosing a captain and vice-captain

Order matters because the positions are different.

P(5, 2) = 5 × 4 = 20

There are 20 possible assignments.

Situation B: Choosing two students for a committee

Order does not matter.

C(5, 2) = 10

There are 10 possible committees.

The number of combinations is smaller because different arrangements of the same selected objects are counted only once.

The Combination Formula

The number of ways to select r objects from n distinct objects without repetition is:

C(n, r) = n!/[r!(n − r)!]

This is also written as:

nCr

or read as:

"n choose r"

where:

• n is the total number of available objects.

• r is the number of objects selected.

• ! represents factorial.

The formula applies when 0 ≤ r ≤ n and both are whole numbers.

Understanding Factorials

A factorial is the product of all positive integers from 1 to a given positive integer.

For example:

5! = 5 × 4 × 3 × 2 × 1 = 120

4! = 4 × 3 × 2 × 1 = 24

3! = 3 × 2 × 1 = 6

By definition:

0! = 1

Factorials allow combination calculations to be written efficiently.

Why the Combination Formula Works

The combination formula can be derived from the permutation formula.

Suppose we want to select three students from a group of five.

If order matters, the number of permutations is:

P(5, 3) = 5 × 4 × 3 = 60

However, each group of three students can be arranged in:

3! = 6 ways

For example, the group ABC can be arranged as:

ABC, ACB, BAC, BCA, CAB, CBA

All six arrangements represent the same combination.

Therefore, divide the number of permutations by 3!.

C(5, 3) = 60/6

C(5, 3) = 10

This gives the general relationship:

C(n, r) = P(n, r)/r!

Substituting the permutation formula:

C(n, r) = [n!/(n − r)!]/r!

Therefore:

C(n, r) = n!/[r!(n − r)!]

Calculating Combinations

To calculate a combination:

1. Identify the total number of objects, n.

2. Identify how many objects are selected, r.

3. Substitute into the combination formula.

4. Simplify the factorial expressions.

5. Calculate the result.

Worked Example: Choosing a Committee

A class has 8 students.

How many different committees of 3 students can be formed?

Step 1: Identify n and r.

n = 8

r = 3

Step 2: Apply the formula.

C(8, 3) = 8!/[3!(8 − 3)!]

Step 3: Simplify.

C(8, 3) = 8!/(3! × 5!)

C(8, 3) = (8 × 7 × 6)/(3 × 2 × 1)

Step 4: Calculate.

C(8, 3) = 336/6

Final answer:

56 different committees

Worked Example: Choosing Books

A student has 10 different books but can take only 4 on a trip.

How many different groups of 4 books can be selected?

n = 10

r = 4

C(10, 4) = 10!/(4! × 6!)

C(10, 4) = (10 × 9 × 8 × 7)/(4 × 3 × 2 × 1)

C(10, 4) = 5040/24

Final answer:

210 possible selections

The order in which the books are chosen does not matter.

Using a Calculator to Find Combinations

Many scientific calculators include a function labeled:

nCr

This function calculates combinations directly.

For example, to calculate:

C(8, 3)

enter:

8 nCr 3

The calculator returns:

56

This method is particularly useful when working with large numbers.

However, students should understand the formula and why it works rather than relying only on a calculator.

Important Properties of Combinations

Combinations have several useful mathematical properties.

Selecting Zero Objects

There is exactly one way to select no objects from a set.

Therefore:

C(n, 0) = 1

Selecting Every Object

There is exactly one way to select all n objects.

Therefore:

C(n, n) = 1

Selecting One Object

There are n ways to select one object from n available objects.

Therefore:

C(n, 1) = n

Symmetry Property

An important property is:

C(n, r) = C(n, n − r)

For example:

C(8, 3) = C(8, 5)

Both equal 56.

Why Does This Work?

Choosing 3 students from a group of 8 automatically determines which 5 students are not chosen.

Every selection of 3 students corresponds to exactly one group of 5 students who remain.

Therefore, the number of ways to select 3 students equals the number of ways to leave out 3 students, or equivalently select the remaining 5.

This property can simplify calculations.

Pascal's Triangle and Combinations

Combinations are closely connected to Pascal's Triangle.

Pascal's Triangle is a triangular arrangement of numbers in which each interior number is the sum of the two numbers directly above it.

For example, the row:

1, 4, 6, 4, 1

represents:

C(4, 0) = 1

C(4, 1) = 4

C(4, 2) = 6

C(4, 3) = 4

C(4, 4) = 1

Pascal's Identity

The relationship between adjacent rows is expressed by:

C(n, r) = C(n − 1, r − 1) + C(n − 1, r)

This identity is useful in probability, algebra, and combinatorics.

Combinations and the Binomial Theorem

Combinations also appear in the expansion of binomial expressions.

For example:

(a + b)² = a² + 2ab + b²

The coefficients are:

1, 2, 1

These correspond to the second row of Pascal's Triangle.

Similarly:

(a + b)³ = a³ + 3a²b + 3ab² + b³

The coefficients are:

1, 3, 3, 1

For a positive integer n, the Binomial Theorem states:

(a + b)ⁿ = Σ C(n, r)a^(n−r)bʳ

where the sum runs from r = 0 to n.

This demonstrates an important connection between counting selections and algebraic expansion.

Solving Selection Problems

Some combination problems involve restrictions or multiple groups.

These problems may require both the combination formula and the Fundamental Counting Principle.

Worked Example: Selecting Boys and Girls

A class contains:

• 6 boys

• 5 girls

A committee must contain exactly:

• 2 boys

• 2 girls

How many committees are possible?

Step 1: Choose the boys.

C(6, 2) = 15

Step 2: Choose the girls.

C(5, 2) = 10

Step 3: Multiply.

15 × 10 = 150

Final answer:

150 possible committees

The multiplication is used because each selection of boys can be paired with each selection of girls.

Worked Example: At Least One Girl

A class contains 5 boys and 4 girls.

A committee of 3 students must contain at least one girl.

How many committees are possible?

Method: Complementary Counting

First calculate the total number of committees:

C(9, 3) = 84

Next calculate committees containing only boys:

C(5, 3) = 10

Subtract:

84 − 10 = 74

Final answer:

74 possible committees

This method is often easier than counting every acceptable case separately.

Combinations with Restrictions

Some problems require particular objects to be included or excluded.

Worked Example: A Particular Student Must Be Included

A group contains 10 students.

A committee of 4 must include Alex.

How many committees are possible?

Since Alex is already included, only 3 additional students must be selected.

There are 9 remaining students.

C(9, 3) = 84

Final answer:

84 possible committees

Worked Example: Two Students Cannot Be Selected Together

A group contains 8 students.

A committee of 3 is selected.

Alex and Ben cannot both be on the committee.

Step 1: Count all possible committees.

C(8, 3) = 56

Step 2: Count committees containing both Alex and Ben.

If both are selected, one more student must be chosen from the remaining 6.

C(6, 1) = 6

Step 3: Subtract.

56 − 6 = 50

Final answer:

50 possible committees

Combinations with Repetition

In some selection problems, the same type of object may be chosen more than once.

For example, suppose an ice cream shop offers 4 flavours.

A customer chooses 3 scoops, and flavours may be repeated.

If the order of the scoops does not matter, this is a combination with repetition.

The formula is:

C(n + r − 1, r)

where:

• n is the number of available types.

• r is the number of objects selected.

Worked Example: Choosing Ice Cream Scoops

There are 4 flavours and a customer chooses 3 scoops.

Repetition is allowed.

C(4 + 3 − 1, 3)

= C(6, 3)

= 20

Final answer:

20 possible flavour combinations

This includes selections such as:

• Vanilla, vanilla, vanilla

• Vanilla, chocolate, strawberry

• Chocolate, chocolate, mint

The order of the scoops is not counted.

Important Distinction

Combinations without repetition:

C(n, r) = n!/[r!(n − r)!]

Combinations with repetition:

C(n + r − 1, r)

These formulas apply to different situations.

Practical Applications of Combinations

Choosing Sports Teams

A coach has 15 players and must select 5 for a starting team.

Assuming all players are eligible and positions do not matter:

C(15, 5) = 3,003

There are 3,003 possible teams.

Lottery Numbers

Suppose a lottery requires selecting 6 different numbers from 49.

The order of the numbers does not matter.

The number of possible selections is:

C(49, 6) = 13,983,816

There are 13,983,816 possible combinations.

This illustrates why matching all six numbers is unlikely when every combination is equally likely.

Choosing Pizza Toppings

A pizza restaurant offers 8 different toppings.

A customer chooses exactly 3 different toppings.

C(8, 3) = 56

There are 56 possible topping combinations.

Scientific Experiments

A scientist has 10 samples and must select 4 for testing.

If the order of testing does not matter:

C(10, 4) = 210

There are 210 possible groups of samples.

Computer Science and Data Analysis

Combinations are useful in:

• Selecting features for machine-learning models.

• Forming groups of data points.

• Testing subsets of variables.

• Designing experiments.

• Analyzing networks.

• Solving optimization problems.

For example, a researcher may need to determine how many different groups of variables can be selected from a larger dataset.

Choosing the Correct Counting Method

Before solving a counting problem, ask three important questions.

Does order matter?

If yes, use permutations.

If no, use combinations.

Is repetition allowed?

If yes, the counting method may need to account for repeated selections.

Are there restrictions?

If yes, divide the problem into cases, use complementary counting, or apply additional multiplication.

Summary of Counting Methods

Common Mistakes

Confusing combinations with permutations

Combinations do not consider order, while permutations do.

Using the permutation formula for selection problems

If order does not matter, the combination formula should usually be used.

Forgetting to divide by r!

The combination formula accounts for repeated arrangements of the same selected objects.

Using the wrong values for n and r

n represents the total number available, while r represents the number selected.

Ignoring restrictions

Conditions such as requiring particular members or excluding certain combinations must be included.

Assuming repetition is always allowed

The standard combination formula assumes objects are selected without repetition.

Confusing combinations with repetition and permutations with repetition

Selecting repeated items without regard to order is different from arranging repeated symbols in positions.

Adding when multiplication is required

When independent selections must be combined, such as choosing boys and girls for a committee, multiplication is often appropriate.

Counting the same group more than once

Different selection orders do not create different combinations.

Key Terms

• Combination: A selection of objects in which order does not matter.

• Permutation: An arrangement of objects in which order matters.

• Selection: The process of choosing objects from a larger group.

• Factorial: The product of all positive integers from 1 to a given positive integer.

• Combination Formula: The expression C(n, r) = n!/[r!(n − r)!].

• Binomial Coefficient: Another name for C(n, r), often read as "n choose r."

• Fundamental Counting Principle: A rule used to calculate outcomes by multiplying choices across stages.

• Pascal's Triangle: A triangular arrangement of numbers containing binomial coefficients.

• Pascal's Identity: The relationship C(n, r) = C(n − 1, r − 1) + C(n − 1, r).

• Binomial Theorem: A rule for expanding powers of binomial expressions using combination coefficients.

• Repetition: The selection of the same object or type more than once.

• Combination with Repetition: A selection in which repeated types are allowed and order does not matter.

• Restriction: A condition that limits which selections are permitted.

• Complementary Counting: A method that subtracts invalid selections from the total number of selections.

• Mutually Exclusive Cases: Cases that cannot occur simultaneously.

• Sample Space: The set of all possible outcomes of an experiment.

• Combinatorics: The branch of mathematics concerned with counting, arrangements, and selections.

• Symmetry Property: The relationship C(n, r) = C(n, n − r).

• Committee Problem: A common counting problem involving the selection of group members.

• Probability: The mathematical study of the likelihood of events.

Key Takeaways

• A combination is a selection in which order does not matter.

• Changing the order of selected objects does not create a new combination.

• Combinations differ from permutations because permutations count arrangements.

• The standard combination formula is C(n, r) = n!/[r!(n − r)!].

• The combination formula can be derived by dividing permutations by r!.

• Factorials are used to calculate combinations efficiently.

• The number of ways to select zero objects or all available objects is always 1.

• The symmetry property states that C(n, r) = C(n, n − r).

• Pascal's Triangle contains combination values.

• Combinations are closely related to the Binomial Theorem.

• Selection problems with restrictions may require multiplication, addition, or complementary counting.

• Combinations with repetition use a different formula from combinations without repetition.

• Combinations are useful in team selection, committees, lotteries, scientific experiments, product choices, and computer science.

• Understanding combinations is an important foundation for probability, statistics, and advanced counting methods.

Check Your Understanding

Recall and Understanding

1. Define a combination and explain why order does not matter.

2. Explain the difference between a permutation and a combination.

3. State the combination formula and explain the meaning of n and r.

4. Why do we divide permutations by r! to calculate combinations?

5. Explain the symmetry property C(n, r) = C(n, n − r).

Application

6. Calculate C(6, 2).

7. A class has 10 students. How many committees of 3 students can be formed?

8. A student has 8 books and wants to select 4. How many selections are possible?

9. A pizza restaurant offers 7 toppings. How many ways can a customer select exactly 2 different toppings?

10. A sports team has 12 players. How many groups of 5 players can be selected?

Analysis and Challenge

11. A class contains 7 boys and 6 girls. How many committees containing exactly 2 boys and 3 girls can be formed?

12. A group contains 9 students. How many committees of 4 can be formed if one particular student must be included?

13. A group contains 10 students. How many committees of 3 can be formed if two particular students cannot both be selected?

14. An ice cream shop offers 5 flavours. How many different selections of 3 scoops are possible if flavours may repeat and order does not matter?

15. Explain how combinations are used in probability, and calculate the number of ways to select 5 different numbers from a set of 20.

Final Summary

Combinations provide a systematic method for counting selections in which the order of objects does not matter.

By using factorials and the combination formula, large numbers of possible groups can be calculated efficiently without listing every selection.

Understanding the difference between combinations and permutations is essential for choosing the correct counting method.

Combinations also connect to Pascal's Triangle, the Binomial Theorem, probability, statistics, and many practical applications involving group selection and decision-making.