Combinatorics Basics: Counting Rules and Scenarios

Counting Principles

When Counts Overlap: Inclusion–Exclusion

Permutations and Combinations

Standard Scenarios

The Binomial Coefficient

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

A lunch menu has 3 soups and 4 salads. How many different lunches are there?

The answer depends on the deal: either a soup or a salad, or one soup and one salad together.

Side by side, "or" gives 7 lunches and "and" gives 12.

lunch deal	how one lunch is built	number of lunches	rule
a soup or a salad	one choice from two separate groups	3 + 4 = 7	addition
a soup and a salad	one choice at each of two stages	3 · 4 = 12	multiplication

With "or", each lunch is one of the

3

soups or one of the

4

salads. With "and", each of the

3

soups can be paired with each of the

4

salads.

Alternatives add; stages multiply.

Which of the two rules applies depends on how an outcome is built. When a single choice is made from one of several separate groups, the groups are alternatives and each option belongs to exactly one of them. When an outcome needs one choice at each of several stages, every option at one stage can be combined with every option at the next. The linking word in the problem often shows which structure is present: "or" joins alternatives, "and" joins stages.

The definition

The counting principles are the rules for combining counts: the addition rule for mutually exclusive alternatives and the multiplication rule for successive choices, with three further rules built on these two.

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.

So "soup or salad" gives

3 + 4 = 7

lunches and "soup and salad" gives

3 \cdot 4 = 12

These rules are the basic tools behind every count in combinatorics.

Permutations, combinations and the binomial coefficient, later on this page, all come from using the multiplication and addition rules over and over. Each rule is treated in full on the counting principles page.

Using the wrong rule is the commonest counting mistake.

Pitfall: Adding counts of sequential choices

Counting outfits of one shirt from

5

and one pair of trousers from

3

5 + 3 = 8

treats the two choices as alternatives. Each shirt goes with each pair, so there are

5 \cdot 3 = 15

outfits.

Alternatives that overlap need a correction to the addition rule, set out in when counts overlap.

The rest of the page covers inclusion-exclusion, permutations and combinations, standard scenarios, the binomial coefficient and the binomial theorem.

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:

Inclusion-Exclusion Principle (Two Sets)

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

Learn more about this formula: Inclusion-Exclusion Principle (Two Sets) →

Browse all combinatorics formulas →

Pitfall: Dropping the triple intersection

Counting

1

30

divisible by

2

3

5

15 + 10 + 6 - 5 - 3 - 2 = 21

loses

30

, which is added three times and subtracted three times. Adding back the triple term gives

21 + 1 = 22

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 — the factorial and arrangement marks are unpacked in permutation notation. Selecting and arranging

r

items from

n

gives

Permutations and Combinations

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.

Fact: A shuffled deck is almost surely new

A deck has

52! \approx 8 \times 10^{67}

orders. Even a billion shuffles a second since the Big Bang would deal fewer than

10^{27}

decks, so a well-shuffled deck is almost certainly in an order no deck has ever had.

Factorials grow faster than any exponential

c^n

. Each item added to a row multiplies the number of arrangements by the new length of the row:

5! = 120

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

, and

20!

is already above

2 \times 10^{18}

. A standard deck of cards is a row of

52

distinct items, and every shuffle produces one of its

52!

orders.

A combination is an unordered selection of items. Choosing

r

items from

n

without regard to order gives

Combination

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

Learn more about this formula: Combination →

Browse all combinatorics formulas →

Pitfall: Using a permutation for a selection

Counting committees of

3

from

10

people as

P(10,3) = 720

treats each order of the same three members as a new committee. A committee has no order, so the count is

\binom{10}{3} = 120

The two formulas are closely linked. Every unordered selection of

r

items can be lined up in

r!

different orders, so each combination stands for exactly

r!

permutations, and

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

. Which count a problem needs depends on whether two outcomes with the same items in a different order are treated as different outcomes.

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

All of these formulas are built from a handful of combinatorial symbols — the factorial

n!

, the arrangement count

P(n,r)

, the binomial coefficient

\binom{n}{r}

— each listed in the symbols reference with the LaTeX code that produces it, and the mathematical keyboard lets you type them directly.

To evaluate the factorials in these formulas, use the factorial calculator.

DownloadPNG2×PDF

One question first

Selecting

r

items from

n

distinct items: whether the order of the selected items matters decides which count applies.

Selecting r from n

r

items from

n

split by whether order matters

Case 1

order matters

Permutation

an ordered arrangement; see permutations

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

Case 2

order does not matter

Combination

an unordered selection

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

Variants

Each family has variants: repetition, identical items, circular arrangements and constraints for permutations; groups, distributions and compositions for combinations.

Permutation or combination: does order matter?·/combinatorics/basicsLearn Math Class

Whether order matters splits every counting formula in two: arrangements count each order, selections divide the orders out.

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 come first and combination scenarios after them, 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, cells allowed empty:

r^n

Pitfall: Swapping base and exponent

Counting ways to drop

3

distinct letters into

4

mailboxes as

3^4 = 81

has each mailbox choosing a letter. Each letter chooses a mailbox, so the count is

4^3 = 64

Two of the formulas above are powers, and both come from the multiplication rule. In a permutation with repetition, each of the

r

positions is filled from the

n

choices, giving one factor of

n

per position. In a distribution into cells, each of the

n

items is sent to one of the

r

cells, giving one factor of

r

per item.

To count arrangements and selections for your own numbers in each of these scenarios, use the combinatorics calculator.

DownloadPNG2×PDF

Before you read

Ten templates for counting problems

Almost every counting problem matches one of ten standard scenarios. The first split is whether the order of the chosen items matters.

L0Standard counting scenariosten templates
- L1Permutation scenariosorder matters
  - L2Full permutationarrange n distinct items in a rown!
  - L2With identical itemsn items, n₁ … nₖ of each typen!/(n₁!…nₖ!)
  - L2Partial, no repetitionarrange r chosen from nn!/(n−r)!
  - L2With repetitionfill r positions from n choicesnʳ
  - L2Circulararrange n items in a circle(n−1)!
- L1Combination scenariosorder does not matter
  - L2Simple combinationchoose r items from nC(n, r)
  - L2Partition into groupssplit n items into labeled groupsmultinomial
  - L2Weak compositionn identical items into r bins, empty allowedC(n+r−1, r−1)
  - L2Strong compositionn identical items into r bins, none emptyC(n−1, r−1)
  - L2Distribution into cellsn distinct items into r labeled cellsrⁿ

Takeaway

Find the template, then the formula

Decide whether order matters, then whether items repeat or are identical; the matching scenario hands you the formula.

Ten standard counting scenarios·/combinatorics/basicsLearn Math Class

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,

The Binomial Coefficient

\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.

C(4,2) = C(3,1) + C(3,2)

The highlighted entry is the sum of the two directly above it, which is Pascal’s rule read off the array instead of out of the formula. Every interior entry is built the same way, so the whole triangle can be generated from its edges of 1s without evaluating a single factorial. Focus any entry and watch its two parents light up on the Pascal’s triangle visualizer.

Seen that way the binomial coefficient is not only an answer to a counting question but an entry in a structure, and the identities above are statements about where it sits in that structure.

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:

Binomial Theorem

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

Learn more about this formula: Binomial Theorem →

Browse all combinatorics formulas →

Pitfall: Forgetting the power on b

Taking the

x^2

term of

(x + 2)^4

\binom{4}{2} x^2 \cdot 2 = 12x^2

leaves the

2

without its power. With

b^k = 2^2 = 4

, the term is

6 \cdot 4\, x^2 = 24x^2

Each term of the expansion has three parts: the coefficient

\binom{n}{k}

, the power

a^{n-k}

and the power

b^k

, with the two exponents always adding up to

n

. When

a

b

is a number, or a variable with a coefficient, its power is a number too, and it multiplies into the coefficient of the term. Only for

(x + y)^n

are the coefficients read directly from a row of Pascal's triangle.

The theorem generalizes — the multinomial theorem expands

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

using multinomial coefficients.

Common Pitfalls

Five mistakes come up again and again in basic counting problems. Each is marked where it happens in the sections above; here each is worked through in full, with the wrong and the right working side by side.

DownloadPNG2×PDF

1Adding counts of sequential choices

An outcome is built in stages, one choice at each stage, but the counts of the stages are added as if they were alternatives. The sum counts the options at the stages, not the ways to combine them.

Wrong turn

Error here

An outfit is one of

5

shirts and one of

3

pairs of trousers, so there are

5 + 3 = 8

outfits.

Right path

Every shirt can be worn with every pair of trousers. The multiplication rule gives

5 \cdot 3 = 15

outfits.

Why it happensBoth rules start from the same numbers, and "5 shirts and 3 pairs of trousers" reads like a list of things to total. The addition rule fits only when exactly one option is picked from one of the groups.

How to checkList the outcomes for a single shirt. It already gives

3

outfits, one with each pair of trousers, so

5

shirts give

5

groups of

3

2Dropping the triple intersection

With three sets, the pairwise intersections are subtracted and the calculation stops there. Elements that lie in all three sets were added three times and subtracted three times, so they are no longer counted at all.

Wrong turn

Error here

For the numbers

1

30

divisible by

2

3

5

|A| = 15

|B| = 10

|C| = 6

|A \cap B| = 5

|A \cap C| = 3

and

|B \cap C| = 2

, so the count is

15 + 10 + 6 - 5 - 3 - 2 = 21

Right path

The triple intersection holds the multiples of

30

, so

|A \cap B \cap C| = 1

and

|A \cup B \cup C| = 21 + 1 = 22

Why it happensThe two-set formula ends with a subtraction, and the three-set version is remembered as "add the sets, subtract the overlaps" without its last term.

How to checkCount the complement. The numbers from

1

30

divisible by none of

2

3

and

5

are

1, 7, 11, 13, 17, 19, 23, 29

. There are

8

of them, and

30 - 8 = 22

3Using a permutation for a selection

A problem that asks only which items are chosen is counted with

P(n,r)

, the formula for ordered arrangements. Each selection is then counted once for every order of its items.

Wrong turn

Error here

A committee of

3

from

10

people is counted as

P(10,3) = 10 \cdot 9 \cdot 8 = 720

Right path

A committee has no first, second or third member, so order does not matter:

\binom{10}{3} = \frac{720}{3!} = \frac{720}{6} = 120

Why it happensPicking the members one after another feels like a sequence of choices, and the multiplication rule naturally produces

10 \cdot 9 \cdot 8

How to checkSwap two chosen items. If Ann, Ben, Cat and Cat, Ben, Ann describe the same committee, order does not matter and the ordered count must be divided by

r!

4Swapping base and exponent

In a power formula such as

r^n

for a distribution into cells, the number of items and the number of cells trade places. The count then answers a different question.

Start

3

distinct letters are dropped into

4

mailboxes, and a mailbox may stay empty.

Wrong turn

Error here

The count is given as

3^4 = 81

Right path

Each of the

3

letters chooses one of the

4

mailboxes, so the count is

4 \cdot 4 \cdot 4 = 4^3 = 64

Why it happensThe two power formulas on the page,

n^r

and

r^n

, look alike, and the letters

n

and

r

stand for different things in the two scenarios.

How to checkTry a single letter. It can go into any of the

4

mailboxes, which

4^1 = 4

gives and

1^4 = 1

does not.

5Forgetting the power on b

A term of the binomial expansion is written with its coefficient

\binom{n}{k}

and the power of the variable, but the number in the binomial is not raised to its power.

Wrong turn

Error here

The

x^2

term of

(x + 2)^4

has

k = 2

, and it is written as

\binom{4}{2} x^2 \cdot 2 = 6 \cdot 2\, x^2 = 12x^2

Right path

The term is

\binom{4}{2} x^2 \cdot 2^2 = 6 \cdot 4\, x^2 = 24x^2

. The full expansion is

(x + 2)^4 = x^4 + 8x^3 + 24x^2 + 32x + 16

Why it happensIn

(a + b)^n

with letters,

b^k

looks like bookkeeping for the variables, and when

b

is a number its power is easy to lose.

How to checkSet

x = 1

. The expansion must equal

(1 + 2)^4 = 81

, and

1 + 8 + 24 + 32 + 16 = 81

; with

12x^2

in place of

24x^2

the sum is only

69

Common pitfalls in basic counting·/combinatorics/basicsLearn Math Class

Each slip uses the right numbers in the wrong rule. Independent choices multiply, a selection without order divides the ordered count by

r!

, the exponent counts the choices made, the triple intersection goes back in, and the binomial term raises

b

to the power

k

. Trying a small case such as one shirt or one letter, counting the complement, or setting

x = 1

catches each slip.

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.

Combinatorics FAQ

What is combinatorics actually used for?

Counting things that are too numerous to list. It underpins probability, where you need the size of a sample space, and appears throughout cryptography, network design, scheduling, and algorithm analysis. Anywhere a question asks how many arrangements, selections, or configurations exist, combinatorics supplies the method for answering it without enumeration.Read more →

How do you tell whether order matters in a counting problem?

Ask whether swapping two chosen items produces a different outcome. Assigning first and second place gives different results when swapped, so order matters. Picking two people for a committee does not, since the same pair results either way. This single test decides which family of formulas applies before any arithmetic starts.Read more →

Why are combinatorics problems hard even when the formulas are simple?

Because the difficulty is recognition, not calculation. The formulas are short, but choosing among them requires deciding whether order matters, whether repetition is allowed, and whether the items are distinguishable. Two problems with almost identical wording can need entirely different approaches, which is why practice focuses on classifying rather than computing.Read more →

Has a shuffled deck of cards ever been in the same order before?

Almost certainly not, if the shuffle is thorough. A deck of

52

cards has

52! \approx 8 \times 10^{67}

possible orders. Even a billion shuffles a second since the Big Bang would have dealt fewer than

10^{27}

decks, a tiny fraction of that total, so a well-shuffled deck is almost surely in an order no deck has ever had.Read more →

Do factorials grow faster than exponentials?

Yes. Going from

n!

(n+1)!

multiplies by

n + 1

, while each step of

c^n

multiplies by the same

c

, so once

n + 1

is larger than

c

the factorial gains at every step and must overtake. It passes

2^n

n = 4

, where

24 > 16

, and

10^n

only at

n = 25

, but it always gets there. Already

20!

is above

2 \times 10^{18}

.Read more →