Combinations — Mathematics Knowledge System

Overview

A combination is a selection of items from a set such that the order of selection does not matter. Given three fruits — an apple, an orange, and a pear — there are three combinations of two that can be drawn: apple-pear, apple-orange, or pear-orange. More formally, a k-combination of a set S is a subset of k distinct elements of S; two combinations are identical exactly when they contain the same members, regardless of the order in which those members were chosen. If the set has n elements, the number of k-combinations, written C(n,k) or the binomial coefficient (n choose k), is n! / (k!(n-k)!). Combinations are the counting foundation for probability, the binomial theorem, and much of discrete mathematics.

Intuition

Suppose you're picking a 3-person committee from 5 candidates. Order doesn't matter — picking Alice, Bob, Carol is the same committee as Carol, Alice, Bob. Compare this to arranging 3 of the 5 candidates in a line for 1st/2nd/3rd place, where order does matter: that's a permutation. Every committee (combination) corresponds to exactly 3! = 6 different orderings (permutations), since each of its 3 members can be arranged 3! ways. So the number of committees is just the number of permutations divided by the number of orderings that collapse onto the same committee: P(n,k) / k!.

Formal Definition

Definition

A k-combination of an n-element set S is a k-element subset of S. The number of k-combinations of an n-element set is the binomial coefficient C(n,k):

\binom{n}{k} = C(n,k) = \frac{n!}{k!\,(n-k)!}, \quad 0 \le k \le n

The number of ways to choose an unordered subset of size k from a set of size n

Definition

\binom{n}{k} = \frac{P(n,k)}{k!} = \frac{n(n-1)\cdots(n-k+1)}{k!}

Equivalent form in terms of the number of k-permutations P(n,k)

Notation

Notation	Meaning
$C(n,k)$	The number of k-combinations of an n-element setAlso written: ₙCₖ, nCk
$\binom{n}{k}$	Binomial coefficient notation for the same quantity
$n!$	Factorial of n: the product 1·2·3···n, with 0! = 1

Derivation

Derive C(n,k) by relating combinations to permutations. Counting the k-permutations of an n-set (ordered selections of k distinct elements) in two ways gives the formula.

P(n,k) = n(n-1)(n-2)\cdots(n-k+1) = \frac{n!}{(n-k)!}

The number of ways to choose k elements from n IN ORDER (permutations).

\text{Each unordered k-subset corresponds to exactly } k! \text{ ordered arrangements.}

Fixing a k-element subset, every one of its k! internal orderings is counted separately in P(n,k).

P(n,k) = \binom{n}{k} \cdot k!

Grouping the k! permutations that share the same underlying subset.

\binom{n}{k} = \frac{P(n,k)}{k!} = \frac{n!}{k!(n-k)!}

Solve for the number of subsets — the combination formula.

Proofs

Pascal's Rule: C(n,k) = C(n-1,k-1) + C(n-1,k)

$\text{Fix an element } x \in S, |S| = n.$ (Single out one distinguished element to split the counting into cases.)
$\text{Case 1: subsets of size } k \text{ containing } x.$ (Choosing such a subset means choosing the remaining k-1 elements from the other n-1 elements: C(n-1,k-1) ways.)
$\text{Case 2: subsets of size } k \text{ not containing } x.$ (Such a subset is just any k-subset of the remaining n-1 elements: \binom{n-1}{k} ways.)
$\text{Every k-subset falls into exactly one case (x is in it or not).}$ (The two cases partition all k-subsets of S with no overlap.)
$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$ (Sum of the sizes of the two disjoint cases (addition principle).)

Symmetry: C(n,k) = C(n,n-k)

$\binom{n}{k} = \frac{n!}{k!(n-k)!}$ (Formula for C(n,k).)
$\binom{n}{n-k} = \frac{n!}{(n-k)!\,(n-(n-k))!} = \frac{n!}{(n-k)!\,k!}$ (Substitute n-k in place of k in the formula.)
$\binom{n}{k} = \binom{n}{n-k}$ (Both expressions are identical, since multiplication in the denominator commutes. Bijectively: choosing which k elements to INCLUDE is equivalent to choosing which n-k elements to EXCLUDE.)

Properties

Symmetry

\binom{n}{k} = \binom{n}{n-k}

Pascal's rule

\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}

Boundary values

\binom{n}{0} = \binom{n}{n} = 1, \quad \binom{n}{1} = n

Sum over all k (subset count)

\sum_{k=0}^{n} \binom{n}{k} = 2^n

Binomial theorem

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

Vandermonde's identity

\binom{m+n}{k} = \sum_{i=0}^{k} \binom{m}{i}\binom{n}{k-i}

Theorems

Theorem 1: Binomial Theorem

(x+y)^n = \sum_{k=0}^{n} \binom{n}{k} x^{n-k} y^k \text{ for any non-negative integer } n.

Corollaries

Follows from Binomial Theorem

\text{Setting } x = y = 1 \text{ gives } \sum_{k=0}^n \binom{n}{k} = 2^n \text{, the total number of subsets of an } n\text{-element set}

Applications

Combinations count the number of possible hands, subsets, or feature-selections in algorithms — e.g. evaluating C(52,5) poker hands or subset-sum search spaces.

Formula Explorer

Worked Examples

n = 3, k = 2. Apply the formula.
$\binom{3}{2} = \frac{3!}{2!\,1!} = \frac{6}{2} = 3$

Answer: 3 combinations: {apple,orange}, {apple,pear}, {orange,pear}.

Practice Problems

Difficulty 2/10

Compute C(6,2).

Difficulty 3/10

Which is equal to C(10,7)?

C(10,3)C(7,10)C(3,10)P(10,7)

Difficulty 5/10

A pizza shop offers 10 toppings. How many different 4-topping pizzas can you order (no repeated toppings, order doesn't matter)?

Common Mistakes

Common Mistake

Confusing combinations with permutations — using n!/(n-k)! when order shouldn't matter.

If rearranging the selected items produces a 'different' result you care about, use permutations P(n,k). If not (e.g. choosing a committee, a hand of cards, a subset), divide by k! to get combinations C(n,k).

Common Mistake

Thinking C(n,k) is undefined or zero when k > n.

C(n,k) = 0 for k > n by convention (and by the formula, since you can't choose more elements than exist), which is consistent and often used in summation identities.

Common Mistake

Forgetting that C(n,0) = 1, not 0.

There is exactly one way to choose nothing — the empty subset. So C(n,0) = C(n,n) = 1 always.

Quiz

Flashcards

1 / 4

Historical Background

Combinatorial counting appears in ancient Indian and Chinese mathematics — the Chandaḥśāstra (c. 2nd century BCE) discusses binomial coefficients in the context of poetic meter, and Pingala's rules anticipate Pascal's triangle by nearly two thousand years. In the Islamic world, al-Karaji and later al-Tusi (13th century) worked out systematic properties of binomial coefficients and induction-style arguments. In Europe, Blaise Pascal's Traité du triangle arithmétique (1654), written in correspondence with Pierre de Fermat while the two were founding probability theory, gave combinations their modern systematic treatment and cemented the notation and recursive structure now called Pascal's triangle.

c. 2nd century BCE
Pingala's Chandaḥśāstra implicitly tabulates binomial coefficients for counting poetic meters
Pingala
c. 1050
Al-Karaji develops the binomial theorem and Pascal's-triangle-style recursions
al-Karaji
1654
Pascal's Traité du triangle arithmétique systematizes combinations while corresponding with Fermat on games of chance
Blaise Pascal, Pierre de Fermat
1666
Leibniz gives one of the first uses of the term 'combinatorics' in his Dissertatio de Arte Combinatoria
Gottfried Wilhelm Leibniz

Summary

A combination is an unordered selection of k elements from a set of n — order does not matter.
C(n,k) = n!/(k!(n-k)!), derived by dividing the permutation count P(n,k) by k! to remove order.
Key identities: symmetry C(n,k)=C(n,n-k), and Pascal's rule C(n,k)=C(n-1,k-1)+C(n-1,k).
The binomial theorem (x+y)ⁿ = ∑ C(n,k)xⁿ⁻ᵏyᵏ ties combinations directly to algebraic expansion.
Combinations underlie probability (counting equally likely outcomes), cryptography, and statistical mechanics.

References

BookRosen, K.H. Discrete Mathematics and Its Applications, 8th ed. Ch. 6.
BookGraham, Knuth, Patashnik. Concrete Mathematics, 2nd ed. Ch. 5 (Binomial Coefficients).
WebsiteWikipedia — Combination