Combinations Basics: A Comprehensive Guide

Combinations are a cornerstone of combinatorics, focusing on the number of ways to select items from a set where the order of selection does not matter. Unlike permutations, where the sequence defines distinct outcomes, combinations treat selections as identical regardless of arrangement. This distinction makes combinations ideal for problems involving groups, subsets, or choices where position is irrelevant.

Rooted in discrete mathematics, combinations have a rich history, from Pascal’s triangle in the 17th century to modern applications in probability and computer science. They provide a systematic way to count possibilities without overcomplicating the process with order considerations. This guide delves into the theory, formulas, examples, and applications of combinations, offering a thorough understanding enriched with equations and practical insights.

Combinations answer questions like "How many ways can I pick a team?" or "How many subsets exist?" By focusing on selection rather than arrangement, they simplify complex counting tasks, making them indispensable across various fields.

Combination Formulas and Variations

Combination formulas calculate the number of ways to select items under different conditions. Below, we explore the standard formula and its extensions, each tailored to specific scenarios.

Standard Combination Formula

The number of ways to choose \( k \) items from \( n \) distinct items (no repetition, order irrelevant):

\[ C(n, k) = \binom{n}{k} = \frac{n!}{k! (n - k)!} \]

Where \( n! = n \cdot (n-1) \cdot \ldots \cdot 1 \). For \( n = 5 \), \( k = 2 \):

\[ C(5, 2) = \frac{5!}{2! (5-2)!} \]
\[ = \frac{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{(2 \cdot 1) \cdot (3 \cdot 2 \cdot 1)} \]
\[ = \frac{120}{2 \cdot 6} = 10 \]

Properties: \( C(n, k) = C(n, n-k) \), \( C(n, 0) = 1 \), \( C(n, n) = 1 \).

Combinations with Repetition

Selecting \( k \) items from \( n \) types, allowing repetition (multisets, e.g., "stars and bars"):

\[ C(n + k - 1, k) = \binom{n + k - 1}{k} \]

3 scoops from 4 flavors:

\[ C(4 + 3 - 1, 3) = \binom{6}{3} \]
\[ = \frac{6!}{3! (6-3)!} = \frac{720}{6 \cdot 6} = 20 \]

Binomial Theorem Connection

Combinations appear in the binomial expansion:

\[ (x + y)^n = \sum_{k=0}^{n} \binom{n}{k} x^{n-k} y^k \]

For \( n = 4 \):

\[ (x + y)^4 = \binom{4}{0} x^4 + \binom{4}{1} x^3 y + \binom{4}{2} x^2 y^2 + \binom{4}{3} x y^3 + \binom{4}{4} y^4 \]
\[ = x^4 + 4 x^3 y + 6 x^2 y^2 + 4 x y^3 + y^4 \]

Total subsets of \( n \) items: \( \sum_{k=0}^{n} C(n, k) = 2^n \).

Combinations with Constraints

Selecting with restrictions (e.g., at least one item). Total subsets minus none:

\[ 2^n - 1 \]

For \( n = 3 \): \( 2^3 - 1 = 8 - 1 = 7 \).

Exactly \( m \) types from \( n \), each at least once:

\[ C(n, m) \]

Multinomial Combinations

Partition \( n \) items into groups of sizes \( k_1, k_2, \ldots, k_m \) (where \( k_1 + k_2 + \ldots + k_m = n \)):

\[ \frac{n!}{k_1! k_2! \ldots k_m!} \]

10 items into 3, 4, 3:

\[ \frac{10!}{3! 4! 3!} = \frac{3,628,800}{6 \cdot 24 \cdot 6} = 4,200 \]

Generating Function for Combinations

The generating function for \( C(n, k) \):

\[ (1 + x)^n = \sum_{k=0}^{n} \binom{n}{k} x^k \]

Coefficient of \( x^k \) is \( C(n, k) \).

Detailed Examples of Combinations

Let’s apply these formulas to diverse problems.

Example 1: Basic Selection

Choose 2 fruits from \{apple, banana, orange\}:

\[ C(3, 2) = \frac{3!}{2! (3-2)!} \]
\[ = \frac{6}{2 \cdot 1} = 3 \]

Selections: \{apple, banana\}, \{apple, orange\}, \{banana, orange\}.

Example 2: Committee Formation

Choose 4 from 10 people:

\[ C(10, 4) = \frac{10!}{4! (10-4)!} \]
\[ = \frac{10 \cdot 9 \cdot 8 \cdot 7}{4 \cdot 3 \cdot 2 \cdot 1} = 210 \]

Example 3: Repetition Allowed

5 candies from 3 types:

\[ C(3 + 5 - 1, 5) = \binom{7}{5} \]
\[ = \frac{7!}{5! (7-5)!} = \frac{5040}{120 \cdot 2} = 21 \]

E.g., (5,0,0), (4,1,0), (3,2,0), etc.

Example 4: Binomial Expansion

Coefficient of \( x^2 y^3 \) in \( (x + y)^5 \):

\[ C(5, 3) = \frac{5!}{3! (5-3)!} = \frac{120}{6 \cdot 2} = 10 \]

Term: \( 10 x^2 y^3 \).

Example 5: Subsets

Total subsets of 4 items:

\[ 2^4 = 16 \]

Non-empty: \( 16 - 1 = 15 \).

Example 6: Constrained Selection

Choose 3 from 6, including A:

\[ C(5, 2) = \frac{5!}{2! (5-2)!} = 10 \]

A fixed, pick 2 from 5 others.

Example 7: Multinomial

Split 8 students into 3, 2, 3:

\[ \frac{8!}{3! 2! 3!} = \frac{40,320}{6 \cdot 2 \cdot 6} = 560 \]

Applications of Combinations

Combinations are pivotal in practical and theoretical contexts.

Lottery Odds

Pick 6 from 49:

\[ C(49, 6) = \frac{49!}{6! (49-6)!} \]
\[ = \frac{49 \cdot 48 \cdot 47 \cdot 46 \cdot 45 \cdot 44}{6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1} = 13,983,816 \]

Odds: \( \frac{1}{13,983,816} \).

Team Selection

5 players from 12:

\[ C(12, 5) = \frac{12!}{5! (12-5)!} = 792 \]

Statistical Sampling

Sample 3 from 20 items:

\[ C(20, 3) = \frac{20 \cdot 19 \cdot 18}{3 \cdot 2 \cdot 1} = 1,140 \]

Probability

Poker hands (5 from 52):

\[ C(52, 5) = 2,598,960 \]

Royal flush: \( \frac{4}{2,598,960} \approx 0.00000154 \).

Computer Science

Subsets for testing (6 components):

\[ 2^6 = 64 \]

Biology

Gene combinations (3 from 10):

\[ C(10, 3) = 120 \]