What is combinatorics?

Combinatorics is the branch of mathematics that deals with counting, arrangement, and selection of objects. It answers questions about how many ways something can be done, providing the foundation for probability, graph theory, number theory partitions, and many algorithmic problems.

What are the basic counting principles?

The five core counting principles are the addition rule (for mutually exclusive cases), the multiplication rule (for sequential independent steps), complementary counting, double counting, and the pigeonhole principle. Every counting formula in combinatorics is built from these rules.

What is the difference between permutations and combinations?

Permutations are ordered arrangements where sequence matters, counted by n!/(n-r)! for choosing r from n. Combinations are unordered selections where only membership matters, counted by C(n,r) = n!/(r!(n-r)!). The structural question 'does order matter' is what separates the two families.

What is the binomial coefficient?

The binomial coefficient C(n,k), read 'n choose k', equals n!/(k!(n-k)!). It counts the number of k-element subsets of an n-element set and also appears as the coefficient of a^(n-k)·b^k in the expansion of (a+b)^n. Pascal's triangle organizes all binomial coefficients into rows.

What does the binomial theorem state?

The binomial theorem states that (a+b)^n equals the sum from k=0 to n of C(n,k)·a^(n-k)·b^k. The expansion has n+1 terms, and the coefficients are exactly the entries of row n of Pascal's triangle. The multinomial theorem generalizes this to sums of more than two terms.

Combinatorics

Counting Principles

When Counts Overlap: Inclusion–Exclusion

Permutations and Combinations

Standard Scenarios

The Binomial Coefficient

The Binomial Theorem

Related Concepts

Combinatorics: The Art of Counting

Combinatorics is the branch of mathematics that deals with counting, arrangement, and selection of objects. At its core, it answers fundamental questions: "In how many ways can this be done?" and "How many possibilities exist?" This field transforms seemingly simple counting problems into powerful mathematical tools that reveal hidden patterns and structures.

Combinatorics serves as a bridge connecting multiple mathematical disciplines. It provides the foundation for probability theory, where calculating favorable outcomes requires systematic counting techniques. The field draws heavily from set theory when dealing with collections and their intersections, while its applications extend into graph theory through network analysis and path counting. Number theory benefits from combinatorial methods in partition problems and divisibility questions, and linear algebra uses combinatorial principles in matrix theory and vector spaces.

The problems combinatorics solves range from practical applications—like determining optimal seating arrangements or analyzing computer algorithms—to abstract mathematical questions about infinite structures. Whether you're calculating lottery odds, designing efficient networks, or exploring mathematical proofs, combinatorics provides the essential counting framework.

In this section, we'll explore the fundamental counting principles, dive into permutations and combinations, and tackle real-world combinatorial scenarios that demonstrate the power and elegance of this mathematical art.

Counting Principles

Five logical rules govern how counts combine:

• Addition rule — when options are mutually exclusive, the counts add.

m

ways for one method and

n

ways for another, with no overlap, gives

m + n

total.
• Multiplication rule — when choices are sequential and independent, the counts multiply.

m

outcomes for step 1 and

n

outcomes for step 2 give

m \cdot n

combined outcomes.
• Complementary counting — reframes "at least one" problems by counting their negation (the "none" case) and subtracting from the total.
• Double counting — proves identities by counting the same set in two different ways and equating the two expressions.
• Pigeonhole principle — guarantees that when more items are distributed than there are containers, at least one container must hold a repeat.

The first two are foundational; the other three extend or apply them.

When Counts Overlap: Inclusion–Exclusion

The addition rule has a quiet requirement — the options must be mutually exclusive. The moment two sets share elements, simply adding their sizes counts the shared elements twice.

The inclusion–exclusion principle is the systematic correction. For two sets:

|A \cup B| = |A| + |B| - |A \cap B|.

For three sets the pattern continues — add singles, subtract pairwise intersections, add the triple intersection. For

n

sets the signs alternate down the line, with one term for every non-empty subset of the sets involved.

The principle also has a complementary form, counting elements that belong to none of the listed sets. This is the form behind the derangement count and other "at least one" or "none" results.

Permutations and Combinations

A permutation is an ordered arrangement of items. Arranging

n

distinct items in a row gives

n!

permutations. Selecting and arranging

r

items from

n

gives

P(n,r) = \frac{n!}{(n-r)!}.

Variants of the basic problem cover arrangements with repetition allowed, arrangements containing identical items, circular arrangements, and arrangements with positional constraints.

A combination is an unordered selection of items. Choosing

r

items from

n

without regard to order gives

\binom{n}{r} = \frac{n!}{r!(n-r)!}.

Variants cover partitioning items into groups, distributing identical items into labeled cells, and weak and strong compositions.

Standard Scenarios

Within the two families, problems reduce to ten standard templates — five permutation scenarios and five combination scenarios. Each scenario asks a distinct structural question and has a known formula. Permutation scenarios appear on the left, combination scenarios on the right, with each scenario paired with its counterpart on the opposite side.

Permutation Scenarios

• Full permutation — arrange

n

distinct items in a row:

n!

• Permutation with identical items — arrange

n

items where

n_1, n_2, \ldots, n_k

are identical of each type:

\dfrac{n!}{n_1!\, n_2! \cdots n_k!}

• Partial permutation without repetition — arrange

r

items chosen from

n

distinct:

\dfrac{n!}{(n-r)!}

• Permutation with repetition — fill

r

positions from

n

choices with repetition allowed:

n^r

• Circular permutation — arrange

n

items in a circle:

(n-1)!

Combination Scenarios

• Simple combination — choose

r

items from

n

\binom{n}{r}

• Partition into groups — split

n

items into labeled groups of sizes

k_1, k_2, \ldots, k_r

\binom{n}{k_1, k_2, \ldots, k_r}

• Weak composition — distribute

n

identical items into

r

bins, bins allowed empty:

\binom{n+r-1}{r-1}

• Strong composition — distribute

n

identical items into

r

bins, no bin empty:

\binom{n-1}{r-1}

• Distribution into cells — distribute

n

distinct items into

r

labeled cells with specified sizes: multinomial coefficient

The Binomial Coefficient

The combination formula

\binom{n}{r}

counts how many

r

-element subsets exist in an

n

-element set. The same expression keeps appearing in other contexts — in permutation formulas, in algebraic identities, in probability distributions — so it is worth examining as a mathematical object in its own right rather than only as a counting answer.

The coefficient satisfies relations that are not visible from the counting interpretation. The symmetry

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

follows immediately from the definition. Pascal's rule,

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

arranges all binomial coefficients into Pascal's triangle, where each interior entry is the sum of the two directly above. Further identities organize entire row sums and diagonal patterns.

The coefficient also generalizes to the multinomial coefficient

\binom{n}{k_1, k_2, \ldots, k_r}

, which counts arrangements of items partitioned into multiple groups of identical types.

The Binomial Theorem

The binomial coefficient's algebraic side becomes explicit in the expansion of

(a+b)^n

. Multiplying out the product distributes into terms of the form

a^{n-k} b^k

. The number of times each such term appears equals the number of ways to choose

k

of the

n

factors to contribute a

b

— which is exactly

\binom{n}{k}

. The result is the binomial theorem:

(a+b)^n = \sum_{k=0}^{n} \binom{n}{k} \, a^{n-k} b^k.

The theorem generalizes — the multinomial theorem expands

(x_1 + x_2 + \cdots + x_r)^n

using multinomial coefficients.

Related Concepts

• Probability — counting favorable outcomes against total outcomes is the bridge from combinatorics into probability.

• Set Theory — the formal language of unions, intersections, and partitions on which the counting principles are stated.

• Algebra — binomial and polynomial expansions, and the algebraic identities that arise from combinatorial counts.

• Linear Algebra — combinatorial structures appear in matrices and in permutations as transformations.