Combinations

INTRODUCTION TO UNORDERED SELECTIONS

In combinatorics, combinations represent a way of selecting elements from a given set where the order does not matter. This means that selections like {A, B, C} and {C, B, A} are considered the same combination. Combinations are often used to count possibilities in cases where order is irrelevant – for example, when drawing lottery numbers, selecting people for a group, or choosing dishes from a menu.

If we select k elements from a set of n distinct elements, where the order does not matter and elements are chosen without repetition, we are talking about combinations without repetition.

COMBINATIONS WITHOUT REPETITION

The number of all such combinations is denoted by C(n,k) or (kn​), which is calculated by the formula:

C(n,k)=n!/[k!∗(n−k)!]

This formula accounts for all possible arrangements (n!/(n−k)!) and then divides them by the number of possible orderings of the k chosen elements (k!), since we are not interested in the order.

Example: Calculating Combinations Without Repetition

How many different 3-person teams can be formed from 5 people? n=5 (total people), k=3 (team members)

C(5,3)=5!/(3!∗2!)=120/(6∗2)=10

There are 10 different 3-person teams that can be formed from 5 people.

COMBINATIONS WITH REPETITION

If we allow repetition of elements in the selection, we use combinations with repetition, denoted as C′(n,k). The formula is:

C′(n,k)=C(n+k−1,k)=(n+k−1)!/[k!∗(n−1)!]

This means we have more possibilities since the same element can be chosen multiple times.

Example: Calculating Combinations With Repetition

How many ways are there to choose 4 fruits (k=4) from 3 different types of fruit (n=3), if repetition is allowed?

C′(3,4)=C(3+4−1,4)=C(6,4)=15

There are 15 ways to choose 4 fruits from 3 different types when repetition is allowed.

COMBINATIONS VS. VARIATIONS: KEY DIFFERENCES

Understanding the distinction between combinations and variations is fundamental in combinatorics:

• Combinations: The order of selected elements does not matter.
• Variations: The order of selected elements does matter.

Both types also have forms with and without repetition.

Illustrative Example from the Set {A, B, C}:

Let's consider choosing k=2 elements from the set {A, B, C}:

• Combinations (k=2): AB, AC, BC → 3 possibilities (Note: BA is the same as AB)
• Variations (k=2): AB, BA, AC, CA, BC, CB → 6 possibilities (Note: BA is different from AB)

PRACTICAL USES OF COMBINATIONS

Combinations are applied in various real-world scenarios, including:

• Lottery draws: Calculating the probability of winning based on selecting numbers where order doesn't matter.
• Forming committees, teams, or groups: Where the arrangement of individuals within the group is not relevant.
• Choosing items where sequence is unimportant: Such as picking toppings for a pizza or selecting books from a shelf.
• Probability calculations: Especially in scenarios involving sampling without replacement where the sequence of selection doesn't affect the outcome.

CONCLUSION: MASTERING COMBINATORIAL COUNTING

Combinations are a foundational counting method for cases where we select without considering order. The number of all combinations is always less than the number of variations from the same set, as permutations within the same group are counted as a single instance. Knowing the differences between combinations, permutations, and variations is crucial for accurate counting in various combinatorial situations.