What is combinatorics?

Combinatorics is the branch of mathematics that studies counting, arrangement, and selection of objects. It answers questions of the form 'in how many ways can this be done?' through a small set of logical principles -- the addition and multiplication rules, complementary counting, double counting, the pigeonhole principle, and inclusion-exclusion -- and a family of standard scenarios for permutations and combinations.

What is the difference between a permutation and a combination?

A permutation is an arrangement where order matters: ABC and CBA count as different permutations. A combination is a selection where order does not matter: the set {A, B, C} is the same combination regardless of how the items were chosen. Each combination of r items corresponds to exactly r! permutations, so C(n,r) = P(n,r) / r!.

What is the binomial coefficient?

The binomial coefficient C(n,k), read 'n choose k', counts the number of k-element subsets of an n-element set. Its formula is n! divided by k! times (n-k)!. The same coefficient also organizes polynomial expansions through the binomial theorem and governs the binomial probability distribution.

What is the inclusion-exclusion principle?

The inclusion-exclusion principle computes the size of a union of overlapping sets by alternately adding and subtracting the sizes of k-fold intersections. For two sets, |A union B| = |A| + |B| - |A intersect B|. The general n-set formula has 2^n - 1 terms with alternating signs, and produces the derangement count and the surjective function count in its complementary form.

Combinatorics Terms and Definitions

Q: What are the basic counting principles?

The basic counting principles are the addition rule (mutually exclusive cases sum), the multiplication rule (independent steps multiply), complementary counting (count what fails and subtract), double counting (count the same set two ways to produce an identity), the pigeonhole principle (more items than containers forces a repeat), and the inclusion-exclusion principle (systematic correction for overlapping sets).

About This Glossary

This glossary organizes 22 combinatorics terms into four categories that build from the foundational counting rules through arrangements, selections, and the algebraic structure of the binomial coefficient.

Counting Principles covers the 6 logical rules that govern how counts combine: the addition rule and multiplication rule (the foundational pair distinguished by "or" versus "and"), complementary counting (count the failures and subtract), double counting (count the same set two ways to produce an identity), the pigeonhole principle (more items than containers forces a repeat), and the inclusion-exclusion principle (the systematic correction for overlapping sets).

Permutations contains 8 entries on arrangements where order matters: factorial (the foundational operation

n!

), the general concept of permutation, and the five permutation scenarios (full, partial, with repetition, with identical items, and circular), plus derangements (permutations with no fixed point).

Combinations & Distributions covers 5 entries on selections and distributions where order does not matter: simple combination, partition into groups (distinct items into unlabeled subsets), weak composition (identical items into labeled bins, empties allowed), strong composition (identical items into labeled bins, no empties), and distribution into cells (distinct items into labeled containers).

Binomial Structure addresses 3 entries on the algebraic objects that organize combinatorial counts: the binomial coefficient

\binom{n}{k}

, its generalization to the multinomial coefficient, and Pascal's triangle as the visual organization of all binomial coefficients.

Each definition includes a precise formal statement, notation conventions, key properties, worked examples, and links to detailed lesson pages. Use the search bar or category filters above to navigate.

Binomial StructureCombinations & DistributionsCounting PrinciplesPermutations

Binomial Structure(3)

Combinations & Distributions(5)

Counting Principles(6)

Permutations(8)

22 of 22 terms

22 terms

Counting Principles

(6 items)

Addition Rule

The addition rule states that if a count splits into

k

mutually exclusive cases with

m_1, m_2, \ldots, m_k

outcomes each, the total number of outcomes is

m_1 + m_2 + \cdots + m_k

Addition Rule

See details

↑ Back to top

intuitionpropertiesexamplesrelated concepts

The addition rule applies whenever a choice is made by selecting one option from several disjoint groups. The linguistic marker is the word "or" — pick method 1 OR method 2 OR method 3. Each "or" between mutually exclusive cases contributes its own count to the sum.

In set-theoretic language, the rule is the cardinality identity

|A \cup B| = |A| + |B|

when

A \cap B = \emptyset

, generalized to any number of pairwise disjoint sets.

↑ Back to top

Multiplication Rule

The multiplication rule states that if an outcome is built from

k

independent steps with

m_1, m_2, \ldots, m_k

options each, the combined sequence has

m_1 \times m_2 \times \cdots \times m_k

possible outcomes.

Multiplication Rule

See details

↑ Back to top

intuitionpropertiesexamplesrelated concepts

The multiplication rule applies whenever an outcome requires completing a sequence of independent steps. The linguistic marker is the word "and" — choose step 1 AND step 2 AND step 3. Each "and" between independent steps multiplies the count.

In set-theoretic terms, the rule is the cardinality of the Cartesian product,

|A \times B| = |A| \cdot |B|

, extended to any finite number of factors.

↑ Back to top

Complementary Counting

Complementary counting computes the size of a set by subtracting the size of its complement from the universe: if

U

is the universe and

A \subseteq U

, then

|A| = |U| - |U \setminus A|

Complementary Counting

See details

↑ Back to top

intuitionpropertiesexamplesrelated concepts

Some counting problems are easier to solve in reverse. Counting the cases that fail a condition can be significantly simpler than counting the cases that satisfy it, especially when the condition has the form "at least one" — its negation, "none", often collapses into a single tractable count.

The strategy is: count the total, count the complement, subtract.

↑ Back to top

Double Counting

Double counting is a proof technique in which the same set is enumerated by two different strategies; the resulting expressions both equal the size of the set, so they equal each other: if

|S| = f(n)

by one argument and

|S| = g(n)

by another, then

f(n) = g(n)

Double Counting

See details

↑ Back to top

intuitionpropertiesexamplesrelated concepts

Double counting produces identities rather than numerical counts. A combinatorial object is counted in two genuinely different ways — typically by selecting members directly versus by partitioning the selection into stages — and the two expressions for the same total are equated.

Many binomial coefficient identities, including Vandermonde's identity and the hockey stick identity, are most naturally proved by double counting.

↑ Back to top

Pigeonhole Principle

The pigeonhole principle states that if

n

items are distributed among

k

containers and

n > k

, then at least one container holds at least two items. The generalized form: if

n

items are distributed among

k

containers, at least one container holds at least

\lceil n/k \rceil

items.

Pigeonhole Principle

See details

↑ Back to top

intuitionpropertiesexamplesrelated concepts

The pigeonhole principle does not count outcomes — it guarantees the existence of a particular kind of outcome. The statement is existential: it certifies that something must occur without identifying where.

The basic form is the case

n = k + 1

of the generalized form, which forces

\lceil n/k \rceil = 2

↑ Back to top

Inclusion-Exclusion Principle

The inclusion-exclusion principle computes the size of a union of

n

sets by alternately adding the sizes of

k

-fold intersections:

\left| \bigcup_{i=1}^{n} A_i \right| = \sum_{k=1}^{n} (-1)^{k+1} \sum_{1 \le i_1 < \cdots < i_k \le n} |A_{i_1} \cap \cdots \cap A_{i_k}|

Inclusion-Exclusion Principle

See details

↑ Back to top

intuitionpropertiesexamplesrelated concepts

The addition rule computes the size of a union by adding the sizes of its pieces — but only when those pieces are mutually exclusive. The moment two sets share elements, simply adding their sizes counts the shared elements twice.

Inclusion-exclusion is the systematic correction: add the sizes of individual sets, subtract pairwise intersections to remove double-counting, add back triple intersections to compensate for over-correction, and continue with alternating signs.

↑ Back to top

Permutations

(8 items)

Factorial

The factorial of a non-negative integer

n

, written

n!

, is the product of all positive integers from

1

up to

n

n! = n \cdot (n-1) \cdot (n-2) \cdots 2 \cdot 1

, with the convention

0! = 1

Permutations

See details

↑ Back to top

notationpropertiesexamplesrelated concepts

The exclamation mark

!

written after a non-negative integer denotes the factorial:

5! = 120

10! = 3{,}628{,}800

. The convention

0! = 1

is required for formulas such as

\binom{n}{0} = 1

to behave correctly.

↑ Back to top

Permutation

A permutation is an arrangement of objects in a definite order. The defining property is that order matters — different sequences of the same objects count as different permutations.

Permutations

See details

↑ Back to top

intuitionnotationrelated concepts

A permutation answers the question "in how many ways can these items be arranged in order?" Each distinct ordering is a separate permutation. Reordering the same items produces a different permutation, even though the underlying set of items is unchanged. This is the property that distinguishes permutations from combinations, where order is irrelevant.

Five scenarios refine the general concept depending on whether all items are used, whether repetition is allowed, whether some items are identical, and whether the arrangement is linear or circular: full permutation, partial permutation, permutation with repetition, permutation with identical items, and circular permutation.

↑ Back to top

Full Permutation

A full permutation is an arrangement of all

n

distinct items in a linear sequence, with each item appearing exactly once. The number of full permutations of

n

items is

P(n) = n!

Full Permutation

See details

↑ Back to top

propertiesexamplesrelated concepts

All items are used: no item is left out and no item is reused. Each item appears exactly once in the arrangement.

Order matters: rearranging items produces a different full permutation.

The count

n!

follows from the multiplication rule:

n

choices for the first position,

n-1

for the second, decreasing to

1

for the last position.

↑ Back to top

Partial Permutation

A partial permutation is a selection of

r

distinct items from

n

available items followed by their arrangement into a linear sequence, with no item reused. The number of partial permutations is

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

Partial Permutation

See details

↑ Back to top

notationpropertiesexamplesrelated concepts

Several notations are in use for the same count:

P(n,r)

{}_nP_r

A_n^r

, and

\text{nPr}

— the last is the form most calculator displays use.

↑ Back to top

Permutation with Repetition

A permutation with repetition is an arrangement of

r

positions where each position is filled independently from

n

available items, with the same item allowed to appear in multiple positions. The number of such arrangements is

P_{\text{rep}}(n, r) = n^r

Permutation with Repetition

See details

↑ Back to top

propertiesexamplesrelated concepts

Order matters and items may be reused. Each of the

r

positions is filled independently from the same pool of

n

items.

The count

n^r

follows from the multiplication rule: every one of the

r

positions has all

n

items available, so the total is the product of

r

factors of

n

.

This is the only permutation scenario where the count can exceed

n!

— the formula

n^r

grows without bound as

r

increases past

n

↑ Back to top

Permutation with Identical Items

A permutation with identical items is an arrangement of

n

objects in a linear sequence where some objects are indistinguishable from one another, counting only distinct orderings. If the objects split into groups of sizes

n_1, n_2, \ldots, n_k

with

n_1 + n_2 + \cdots + n_k = n

, the count is

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

Permutation with Identical Items

See details

↑ Back to top

notationpropertiesexamplesrelated concepts

\binom{n}{n_1, n_2, \ldots, n_k}

P(n; n_1, n_2, \ldots, n_k)

— both denote the same count, equal to the multinomial coefficient.

↑ Back to top

Circular Permutation

A circular permutation is an arrangement of

n

distinct items around a circle, where two arrangements are considered identical if one is a rotation of the other. The number of circular permutations is

P_{\text{circ}}(n) = (n-1)!

Circular Permutation

See details

↑ Back to top

propertiesexamplesrelated concepts

Order matters along the circle, but absolute position does not. Fixing the position of one item removes the rotational redundancy, leaving the remaining

n - 1

items to be arranged linearly in

(n-1)!

ways.

Equivalently: the

n!

linear arrangements of

n

items partition into groups of

n

rotationally equivalent versions, so dividing by

n

gives

\frac{n!}{n} = (n-1)!

.

Reflections (clockwise vs counterclockwise) are typically considered distinct in this definition. If reflections are also identified, the count becomes

\frac{(n-1)!}{2}

↑ Back to top

Derangement

A derangement is a permutation of a set in which no element appears in its original position. The number of derangements of an

n

-element set, written

!n

D_n

, is

!n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}

Derangements

See details

↑ Back to top

notationpropertiesexamplesrelated concepts

!n

— the subfactorial notation, with the exclamation mark preceding the number (in contrast to

n!

for the factorial).

D_n

— alternative notation common in older texts.

↑ Back to top

Combinations & Distributions

(5 items)

Combination

A combination is a selection of items from a collection where order does not matter. The number of ways to select

r

items from

n

distinct items is the binomial coefficient

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

Combinations

See details

↑ Back to top

notationkey distinctionexamplesrelated concepts

Several notations denote the same quantity:

\binom{n}{r}

— the standard modern form, read "

n

choose

r

C(n,r)

— common in introductory texts;

C_n^r

— an alternative form;

{}_nC_r

— the form most calculator displays use.

↑ Back to top

Partition into Groups

A partition into groups divides

n

distinct items into

k

unlabeled subsets where only the grouping matters, not the order within groups or names of the groups. When the group sizes

n_1, n_2, \ldots, n_k

are specified and distinct, the count is

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

Partition into Groups

See details

↑ Back to top

propertiesexamplesrelated concepts

Items are distinct, but groups are unlabeled — only which items share a group matters, not which group is called "Group 1" versus "Group 2".

When groups of equal size are present, the formula divides further by the factorial of the count of equal-sized groups to remove the redundancy of interchangeable group labels.

The formula coincides with the multinomial coefficient when the groups are treated as labeled by their size signature.

↑ Back to top

Weak Composition

A weak composition is a distribution of

n

identical items into

r

labeled containers where some containers may remain empty. The number of weak compositions is

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

Weak Composition

See details

↑ Back to top

notationpropertiesexamplesrelated concepts

\left(\!\binom{n}{r}\!\right)

— the double-parenthesis notation specifically indicating a weak composition. The same count is also written

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

as an ordinary binomial coefficient.

↑ Back to top

Strong Composition

A strong composition is a distribution of

n

identical items into

r

labeled containers where every container must receive at least one item. The number of strong compositions is

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

Strong Composition

See details

↑ Back to top

notationpropertiesexamplesrelated concepts

\left\langle \binom{n}{r} \right\rangle

— the angle-bracket notation specifically indicating a strong composition. The same count is also written

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

as an ordinary binomial coefficient.

↑ Back to top

Distribution into Cells

A distribution into cells assigns each of

n

distinct items to one of

r

labeled containers, producing a mapping from items to containers. The number of distributions is

r^n

Distribution into Cells

See details

↑ Back to top

propertiesexamplesrelated concepts

Items are distinct and containers are labeled. Each item independently chooses one of the

r

containers, and containers may receive any number of items including zero.

The count

r^n

follows from the multiplication rule: each of the

n

items has

r

choices, so the total is

r \cdot r \cdots r = r^n

.

Equivalently, a distribution into cells is a function from an

n

-element domain to an

r

-element codomain. Counting functions:

r^n

.

This differs from permutation with repetition only in framing — the formula is the same with the roles of the parameters swapped.

↑ Back to top

Binomial Structure

(3 items)

Binomial Coefficient

The binomial coefficient

\binom{n}{k}

, read "

n

choose

k

", is the number of

k

-element subsets of an

n

-element set. For non-negative integers

n

and

k

with

0 \le k \le n

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

Binomial Coefficient

See details

↑ Back to top

notationpropertiesexamplesrelated concepts

\binom{n}{k}

— the standard modern form, used throughout mathematics.

C(n,k)

— common in introductory texts.

C_n^k

C_k^n

— used in some European traditions; the position of the subscript and superscript varies by source.

{}_nC_k

— the form most calculator displays use.

↑ Back to top

Multinomial Coefficient

The multinomial coefficient counts the number of ways to partition

n

distinct items into

r

labeled groups of specified sizes

k_1, k_2, \ldots, k_r

with

k_1 + k_2 + \cdots + k_r = n

. Its value is

\binom{n}{k_1, k_2, \ldots, k_r} = \frac{n!}{k_1! \, k_2! \cdots k_r!}

Multinomial Coefficient

See details

↑ Back to top

propertiesexamplesrelated concepts

The multinomial coefficient generalizes the binomial coefficient to more than two groups. The binomial case is

r = 2

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

.

Combinatorial interpretation: the count of distinct arrangements of

n

items in which

k_1

are of type 1,

k_2

are of type 2, and so on. This is the same count that arises in permutations with identical items — the two viewpoints (partitioning into labeled groups versus arranging with repetition of types) describe the same enumeration.

The multinomial coefficient is the coefficient of

x_1^{k_1} x_2^{k_2} \cdots x_r^{k_r}

in the expansion of

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

↑ Back to top

Pascal's Triangle

Pascal's triangle is the triangular array of binomial coefficients in which row

n

(indexed from

0

) contains the

n + 1

values

\binom{n}{0}, \binom{n}{1}, \ldots, \binom{n}{n}

, and each interior entry equals the sum of the two entries directly above it.

Pascal's Triangle

See details

↑ Back to top

propertiesexamplesrelated concepts

The recursive rule generating the triangle is Pascal's rule:

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

.

Symmetry: each row reads the same forwards and backwards, reflecting the identity

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

.

Row sums: the entries of row

n

sum to

2^n

, the number of subsets of an

n

-element set.

Diagonals: the first diagonal contains

1, 1, 1, \ldots

; the second contains the natural numbers

1, 2, 3, \ldots

; the third contains the triangular numbers

1, 3, 6, 10, \ldots

; the fourth contains the tetrahedral numbers

1, 4, 10, 20, \ldots

. Sums along shallow diagonals produce the Fibonacci numbers.

↑ Back to top