Die Druckversion wird nicht mehr unterstützt und kann Darstellungsfehler aufweisen. Bitte aktualisiere deine Browser-Lesezeichen und verwende stattdessen die Standard-Druckfunktion des Browsers.

Combinatorics

Introduction

Combinatorics is the mathematics of counting, arranging, selecting, and proving facts about finite structures. It gives you systematic ways to answer questions such as: How many passwords are possible under a rule? How many teams can be chosen from a class? How many shortest routes exist through a grid? How can you prove that some repetition is unavoidable? These questions connect directly to Probability, Discrete mathematics, Graph theory, Computer science, coding, scheduling, and data analysis.

At Grades 11–13, the key challenge is not simply to memorize formulas. You need to decide which counting model fits a situation, justify why there is no double counting, and explain how different formulas are connected. Throughout this aiMOOC, you will move from basic counting rules to permutations, combinations, repeated selections, inclusion–exclusion, the pigeonhole principle, binomial coefficients, lattice paths, and combinatorial proofs.

The animation above shows how Pascal's triangle grows. Each interior entry is formed by adding the two entries above it. Later you will see why the same numbers count subsets, coefficients in the Binomial theorem, and shortest lattice paths.

Learning Goals

By the end of this aiMOOC, you should be able to:

Use the sum and product rules: Break a counting problem into disjoint cases or successive stages and combine the counts correctly.
Model ordered selections: Distinguish full permutations from partial arrangements and recognize when repetition changes the count.
Model unordered selections: Use binomial and multinomial coefficients to count subsets and grouped arrangements.
Handle repeated selections: Translate distributions of identical objects into separator models.
Correct for overlap: Count unions without double counting.
Prove unavoidable repetition: Apply both the basic and generalized pigeonhole principles.
Connect formulas and structures: Relate Pascal's triangle, the binomial theorem, lattice paths, subsets, and complete graphs.
Prove identities by counting: Explain why two expressions are equal because they count the same set in different ways.
Apply combinatorics to probability: Count favorable and total outcomes in finite equally likely sample spaces.

Counting Foundations

Sets, Outcomes, and Cardinality

Combinatorics often begins with a finite set. The cardinality of a finite set $A$ , written $| A |$ , is the number of elements in it. A counting problem therefore asks you to describe a set of possible outcomes clearly and determine its cardinality.

A good model answers three questions before any formula is used: What exactly is one outcome? When are two outcomes considered different? Are all allowed outcomes represented exactly once? Many errors in combinatorics come from changing the meaning of an outcome halfway through a calculation.

For example, if you choose a president and a vice-president from a group, the pair Alice–Ben is different from Ben–Alice because the roles are different. If you merely choose a two-person committee, those two descriptions represent the same subset. This distinction between order matters and order does not matter drives much of elementary combinatorics.

The Sum Rule

Use the sum rule when the possibilities are divided into disjoint cases. If a task can be completed in one of several mutually exclusive ways, and the cases contain $a_{1}, a_{2}, \dots, a_{r}$ possibilities, then the total number is

$a_{1} + a_{2} + \dots + a_{r} .$

Suppose a school club chooses either one student from 12 Grade 11 students or one student from 15 Grade 12 students. If no student belongs to both grade groups, there are $12 + 15 = 27$ possibilities.

The word disjoint matters. If cases overlap, simple addition counts some outcomes more than once. That is why the Inclusion–exclusion principle is needed later.

The Product Rule

Use the product rule when a process has successive stages. If the first stage has $a_{1}$ choices, the second has $a_{2}$ choices for each first-stage choice, and so on, then the total number of complete outcomes is

$a_{1} a_{2} \dots a_{r} .$

A four-character code using one of 26 letters followed by three digits, each chosen from 10 possibilities, has $26 \cdot 1 0^{3} = 26,000$ possibilities if repetition is allowed. The important idea is not the formula itself but the structure: a complete code is built by making one choice at each stage.

This MIT OpenCourseWare lecture develops counting rules from set relationships and mappings. Use it to compare your own reasoning with a university-level treatment of the same core ideas.

Factorials

For a positive integer $n$ , the factorial is

$n! = n (n - 1) (n - 2) \dots 2 \cdot 1.$

By definition, $0! = 1$ . This convention makes formulas consistent and reflects the fact that there is exactly one way to arrange no objects, namely the empty arrangement.

Factorials grow extremely quickly. For instance, arranging 10 distinct books on a shelf gives $10! = 3,628,800$ orders. This rapid growth is one reason exhaustive search becomes impractical in many computer-science problems.

Permutations and Ordered Arrangements

Full Permutations

A permutation of $n$ distinct objects is a linear ordering of all of them. There are

$n!$

such permutations. The product rule proves this: there are $n$ choices for the first position, then $n - 1$ for the second, continuing down to one remaining object.

If six runners finish a race with no ties, the number of possible finishing orders is $6!$ . The same model appears when you order tasks, arrange books, rank candidates, or schedule distinct presentations.

Partial Permutations

If you choose and order only $k$ objects from $n$ distinct objects, then the number of ordered selections is

$P (n, k) = n (n - 1) \dots (n - k + 1) = \frac{n!}{(n - k)!} .$

For example, the number of ways to award gold, silver, and bronze medals to 12 finalists is

$P (12, 3) = 12 \cdot 11 \cdot 10.$

Order matters because each medal represents a different role.

The video above focuses on the permutation formula. As you watch, identify exactly where the decreasing factors come from and why dividing by $(n - k)!$ removes the unused tail of $n!$ .

Repetition in Ordered Sequences

If each of $k$ positions can independently contain any of $n$ symbols and repetition is allowed, then there are

$n^{k}$

sequences. A four-digit PIN has $1 0^{4}$ possibilities when leading zeros and repeated digits are allowed.

If repetition is forbidden, the model changes to $P (n, k)$ . Always read conditions such as “without replacement,” “distinct,” or “no repeated symbol” carefully.

Repeated Objects and Multinomial Counting

If some objects are indistinguishable, $n!$ overcounts arrangements. If $n$ positions contain $n_{1}$ objects of one type, $n_{2}$ of another, and so on, with $n_{1} + \dots + n_{r} = n$ , then the number of distinct arrangements is

$\frac{n!}{n_{1}! n_{2}! \dots n_{r}!} .$

For example, the letters of BANANA contain three As, two Ns, and one B, so the number of distinct strings is

$\frac{6!}{3! 2! 1!} = 60.$

This expression is a multinomial coefficient. It can also count ways to divide labeled objects into labeled groups of prescribed sizes.

Combinations and Unordered Selections

Choosing Subsets

A combination is a selection in which order does not matter. The number of $k$ -element subsets of an $n$ -element set is the binomial coefficient

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

Why divide by $k!$ ? First count ordered selections with $P (n, k)$ . Every unordered $k$ -element subset appears once for each of its $k!$ internal orders. Dividing removes this overcounting.

If a five-person committee is chosen from 12 students, there are $(\binom{12}{5})$ possible committees.

A useful test is to ask whether swapping two selected people creates a new outcome. For a committee, it does not. For president and vice-president, it does.

Symmetry of Binomial Coefficients

A fundamental identity is

$(\binom{n}{k}) = (\binom{n}{n - k}) .$

There is an algebraic reason: both factorial formulas simplify to the same expression. There is also a combinatorial reason: choosing the $k$ members who are included uniquely determines the $n - k$ members who are excluded.

This is your first example of a combinatorial proof: instead of manipulating symbols, you describe two ways of counting the same set of outcomes.

From Subsets to Graphs

A complete graph $K_{n}$ has one edge between every pair of distinct vertices. Since each edge is an unordered pair of vertices, the number of edges is

$(\binom{n}{2}) = \frac{n (n - 1)}{2} .$

For $K_{5}$ , the formula gives $(\binom{5}{2}) = 10$ edges. The same reasoning counts handshakes if every pair of people shakes hands exactly once.

Repetition and Stars and Bars

Combinations with Repetition

Suppose you choose $k$ items from $n$ types, repetition is allowed, and order is irrelevant. Equivalently, you seek nonnegative integer solutions of

$x_{1} + x_{2} + \dots + x_{n} = k .$

The stars and bars method represents the $k$ chosen items by stars and separates the $n$ types with $n - 1$ bars. The total number is

$(\binom{n + k - 1}{k}) = (\binom{n + k - 1}{n - 1}) .$

For example, distributing 8 identical tokens among 3 labeled boxes allows zero tokens in a box and gives

$(\binom{8 + 3 - 1}{8}) = (\binom{10}{8}) = 45.$

The method changes when each box must receive at least one token. Give one token to every box first, then distribute the remainder with the nonnegative model.

Translating Word Problems into Equations

Stars and bars is powerful only when the modeling conditions match. The objects must be identical with respect to the distribution, the boxes or categories must be distinguishable, and the constraints must be expressible as conditions on integer variables.

If there are upper bounds such as $x_{i} \leq 4$ , the simple stars-and-bars formula may count forbidden solutions. You may then need inclusion–exclusion, generating functions, or a case split.

Inclusion–Exclusion

Correcting Double Counting

For two finite sets $A$ and $B$ ,

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

The intersection is subtracted because elements belonging to both sets were counted twice by $| A | + | B |$ .

For three sets,

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

The alternating pattern continues for more sets.

The diagram helps you track how overlap is corrected. For complicated counting problems, it is often easier to count the complement: count all outcomes first, then subtract those that violate at least one condition.

This second MIT OpenCourseWare counting lecture includes inclusion–exclusion and subset-based counting. Use it when you are ready to connect formulas with more formal set arguments.

Example: Divisibility Conditions

How many integers from 1 through 100 are divisible by 2 or 5? Let $A$ be the multiples of 2 and $B$ the multiples of 5. Then

$| A | = 50, | B | = 20, | A \cap B | = 10$

because the intersection consists of multiples of 10. Therefore

$| A \cup B | = 50 + 20 - 10 = 60.$

Notice that the calculation is short only after the sets have been defined precisely.

The Pigeonhole Principle

Basic Principle

The pigeonhole principle states that if more than $m$ objects are placed into $m$ boxes, at least one box contains at least two objects. The language of “pigeons” and “holes” is metaphorical: the objects could be students, numbers, birthdays, files, or graph vertices.

A simple example: among 13 people, at least two were born in the same month, because there are only 12 months.

Generalized Principle

If $N$ objects are placed into $m$ boxes, then some box contains at least

$⌈ \frac{N}{m} ⌉$

objects.

This form is stronger because it quantifies the unavoidable crowding. For example, if 100 files are stored in 9 folders, at least one folder contains at least $⌈ 100 / 9 ⌉ = 12$ files.

In harder problems, the main work is identifying the right “pigeons” and “holes.” A clever choice can turn a difficult existence proof into a short counting argument.

Binomial Coefficients and Pascal's Triangle

Pascal's Recurrence

Pascal's identity is

$(\binom{n}{k}) = (\binom{n - 1}{k - 1}) + (\binom{n - 1}{k}) .$

A combinatorial proof is immediate. Fix one particular element, say Alex, in an $n$ -element set. Every $k$ -element subset either contains Alex or does not. The subsets containing Alex are formed by choosing the remaining $k - 1$ elements from $n - 1$ others. The subsets not containing Alex are formed by choosing all $k$ elements from those $n - 1$ others. The two cases are disjoint, so the sum rule applies.

This recurrence generates Pascal's triangle, with boundary values $(\binom{n}{0}) = (\binom{n}{n}) = 1$ .

The Binomial Theorem

For a nonnegative integer $n$ ,

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

The coefficient $(\binom{n}{k})$ appears because to obtain a term containing exactly $k$ factors of $y$ , you choose which $k$ of the $n$ factors contribute $y$ ; the remaining factors contribute $x$ .

Setting $x = y = 1$ gives the identity

$\sum_{k = 0}^{n} (\binom{n}{k}) = 2^{n} .$

Combinatorially, both sides count all subsets of an $n$ -element set: the left side groups subsets by their size, while the right side gives each element two choices, included or excluded.

Lattice Paths

A shortest path on a rectangular grid from $(0, 0)$ to $(r, u)$ using only right and up steps has $r + u$ moves. Every path is determined by choosing which $r$ positions contain right moves, so the number of shortest paths is

$(\binom{r + u}{r}) = (\binom{r + u}{u}) .$

This is another reason Pascal's triangle appears throughout combinatorics: moving through a grid produces the same addition rule as Pascal's recurrence. Lattice-path models also lead to more advanced objects such as Catalan numbers when paths must stay on one side of a boundary.

Double Counting and Combinatorial Proof

Count the Same Set in Two Ways

A double-counting argument proves an identity by describing one set of objects and counting it in two different ways. The equality of the two expressions follows because both counts describe exactly the same set.

For example, count the number of ways to choose a committee of $k$ people from $n$ people and then choose a chair from within the committee.

First choose the committee, then the chair:

$(\binom{n}{k}) k .$

Alternatively, choose the chair first, then choose the remaining $k - 1$ committee members:

$n (\binom{n - 1}{k - 1}) .$

Therefore,

$k (\binom{n}{k}) = n (\binom{n - 1}{k - 1}) .$

The proof explains why the identity is true rather than merely confirming it through algebra.

Bijections

A bijection is a one-to-one correspondence between two sets. If you can construct a bijection between finite sets $A$ and $B$ , then $| A | = | B |$ .

For instance, taking the complement maps every $k$ -element subset of an $n$ -element set to a unique $n - k$ -element subset. This bijection proves $(\binom{n}{k}) = (\binom{n}{n - k})$ without any factorial manipulation.

Bijections are among the most powerful ideas in combinatorics because they can reveal that two apparently unrelated problems have the same answer.

Combinatorics in Probability and Computing

Finite Probability Spaces

If a finite experiment has equally likely outcomes, then for an event $E$ ,

$P (E) = \frac{| E |}{| Ω |},$

where $Ω$ is the sample space. Combinatorics supplies the numerator and denominator.

Suppose five cards are drawn from a standard 52-card deck and order does not matter. The total number of hands is $(\binom{52}{5})$ . Counting hands with a specified pattern then becomes a combinations problem. The counting model must match the probability model: if outcomes are not equally likely, the simple ratio of counts is not valid.

This example video connects permutations and combinations directly to a probability calculation.

Counting in Algorithms and Security

Combinatorics helps you estimate the size of a search space. If a password uses 12 positions and each position allows 62 symbols, the unrestricted space has $6 2^{12}$ strings. Such counts help explain why key length and allowed symbol sets matter in security, although real security also depends on guessing strategies, implementation, and user behavior.

In algorithms, the number of subsets of an $n$ -element set is $2^{n}$ , and the number of permutations is $n!$ . Algorithms that examine every subset or every permutation can therefore become infeasible even for moderate $n$ . Counting is a first step toward analyzing computational complexity.

Advanced Extensions

Recurrences and Generating Functions

Some counting sequences are defined recursively. A recurrence relates later terms to earlier ones, as Pascal's triangle does. More advanced combinatorics often encodes sequences in a generating function, a formal power series whose coefficients store the numbers being counted.

You do not need generating functions for every Grades 11–13 problem, but they provide a bridge to university-level discrete mathematics. They are especially useful for restricted distributions, recurrence solving, and identities involving sequences.

When No Single Formula Works

Not every combinatorial problem has a one-line closed formula. You may need a case split, a recurrence, a complement, inclusion–exclusion, a bijection, or even careful enumeration for small cases. A strong solution is not the one with the most advanced formula; it is the one that models the outcomes correctly and gives a transparent justification.

A productive habit is to test a proposed formula on a tiny case that you can list by hand. Small examples often expose hidden overcounting or a mistaken assumption about order.

Strategy Guide

When you face a new counting problem, ask the following questions:

Define the outcome: What exactly counts as one complete outcome?
Check order: Does changing the order create a new outcome?
Check repetition: Can an object or symbol be used more than once?
Identify constraints: Are there required elements, forbidden patterns, lower bounds, or upper bounds?
Choose a structure: Is the problem naturally a sum of disjoint cases, a product of stages, a permutation, a combination, stars and bars, inclusion–exclusion, a pigeonhole argument, or a recurrence?
Check for overcounting: Does every valid outcome appear exactly once in your count?
Test a small case: Can you list a smaller version and compare it with your formula?

Interactive Tasks

Quiz: Test Your Knowledge

Which rule is most appropriate for a process built from successive choice stages? (Product rule) (!Sum rule) (!Pigeonhole principle) (!Complement rule)

How many full orderings of seven distinct objects are there? (Seven factorial) (!Seven squared) (!Seven choose two) (!Two to the seventh)

Which model fits choosing a four-person committee from twelve students? (Combination) (!Permutation) (!Ordered sequence) (!Pigeonhole argument)

What changes when three medals are awarded to three different finalists? (Order matters) (!Repetition is required) (!All choices are identical) (!Inclusion exclusion is automatic)

What does inclusion exclusion correct? (Overlapping cases) (!Factorial growth) (!Ordered positions) (!Identical objects)

What does the pigeonhole principle usually prove? (Some repetition is unavoidable) (!Every box has equal size) (!Every arrangement is unique) (!Order never matters)

Which expression counts subsets of a fixed size? (Binomial coefficient) (!Factorial alone) (!Geometric sequence) (!Arithmetic mean)

What does the stars and bars method count in its basic form? (Nonnegative integer distributions) (!Only ordered permutations) (!Only graph colorings) (!Continuous probabilities)

Why are the rows of Pascal's triangle important in combinatorics? (They contain binomial coefficients) (!They list prime numbers only) (!They contain factorials only) (!They measure angles)

What is the main idea of a combinatorial proof? (Count the same objects in two ways) (!Approximate every count numerically) (!Assume the desired identity) (!Replace counting with geometry)

Memory Game

Product rule	Multiply the numbers of choices in successive stages.
Permutation	An ordered arrangement of distinct objects.
Combination	An unordered selection from distinct objects.
Inclusion-exclusion	A method that corrects overlap among counted sets.
Pigeonhole principle	A guarantee that crowding occurs when objects outnumber containers.
Bijection	A one-to-one correspondence that proves two finite sets have equal size.

Drag and Drop

Match the correct terms.	Topic
Permutation without repetition	Ordered selection from distinct available objects
Combination without repetition	Unordered selection from distinct available objects
Sequence with repetition	Independent symbol choice at every position
Stars and bars	Distribution of identical objects among labeled categories
Inclusion exclusion	Counting a union while correcting overlap

...

Crossword Puzzle

Factorial	What operation multiplies all positive integers up to a given positive integer?
Permutation	What is an ordered arrangement of distinct objects called?
Combination	What is an unordered selection from distinct objects called?
Pigeonhole	Which principle proves unavoidable crowding when objects outnumber containers?
Binomial	What type of coefficient counts subsets of a fixed size?
Complement	What set contains the outcomes outside a chosen event within the sample space?

LearningApps

Cloze Text

When a counting process consists of successive stages, the

tells you to multiply the numbers of choices. If a selection is ordered and uses distinct objects, a

is often the right model. If order does not matter, you usually use a

. The formula for choosing a fixed-size subset is a

. When simple addition counts overlapping cases more than once,

corrects the total. The

proves that some container must receive multiple objects when there are too many objects for the available containers. Pascal's triangle is generated by a recurrence that adds two neighboring

. A one-to-one correspondence between two finite sets is called a

. In an equally likely finite sample space, combinatorial counts can be used to compute a

.

Open-Ended Tasks

Easy

Counting Photo Hunt: Photograph or sketch four everyday situations that can be modeled by the sum rule, product rule, permutations, or combinations, and write one sentence explaining the model for each image.
Permutation Experiment: Arrange five distinct cards or objects in as many orders as you can, compare your list with the factorial prediction, and explain how you know whether your list is complete.
Committee Survey: Ask classmates to create examples where order matters and where order does not matter, then classify the examples and explain one disputed case.
Pascal Triangle Poster: Produce a labeled image or poster of Pascal's triangle through at least eight rows and annotate symmetry, Pascal's recurrence, and one row sum.

Standard

Password Space Investigation: Design three fictional password policies, calculate each search-space size, and make a short infographic comparing how length, alphabet size, and repetition affect the count.
Stars and Bars Model: Use counters and dividers to model an identical-object distribution problem, photograph or film the model, derive the matching binomial coefficient, and explain every symbol in your formula.
Pigeonhole Interview: Interview a teacher, programmer, librarian, or organizer about a situation involving limited categories or slots, then translate the situation into pigeons and holes and state a justified conclusion.
Combinatorial Route Map: Draw a local grid-like route, campus map, or fictional city map, count shortest paths between two points, and create a short video explaining why a binomial coefficient appears.

Advanced

Inclusion Exclusion Project: Collect or invent data for three overlapping categories, create a Venn diagram, compute the size of the union using inclusion–exclusion, and explain why each subtraction and addition is necessary.
Combinatorial Proof Video: Produce a three-to-five-minute teaching video that proves a binomial identity by counting one set of objects in two different ways rather than by algebra alone.
Enumeration Algorithm: Write a small program that generates combinations or permutations without duplicates, compare the number of generated outputs with the theoretical formula, and analyze how the runtime grows as the input size increases.
Counting in a Public Place: Visit a library, museum, transit hub, school event, or other suitable place, identify a real selection or scheduling problem, model it combinatorially, document assumptions, and discuss where the simple model may fail.

Learning Assessment

Model Selection Assessment: Given a set of unfamiliar counting scenarios, classify each as a sum, product, permutation, combination, repeated-selection, inclusion–exclusion, or pigeonhole problem and justify every classification in words before calculating.
Error Analysis Assessment: Analyze three incorrect combinatorial solutions, identify exactly where overcounting or undercounting occurs, and repair each argument with a correct model.
Identity Proof Assessment: Prove at least two binomial identities in two ways, once algebraically and once through a combinatorial interpretation, and compare what each proof reveals.
Constraint Transfer Assessment: Solve a stars-and-bars problem, then modify it by adding lower or upper bounds and explain why the original formula does or does not still apply.
Probability Transfer Assessment: Build a finite probability problem involving cards, codes, routes, or committees, derive the favorable and total counts, and justify why the outcomes used in the ratio are equally likely.
Computation Assessment: Implement or manually design an enumeration procedure for a small combinatorial class, verify its output against a formula, and explain how you know there are no missing or duplicate outcomes.

Evidence of Learning

Strong evidence of learning should show more than correct numerical answers. It should demonstrate that you can model, justify, communicate, and transfer combinatorial reasoning.

Knowledge evidence includes accurate use of the sum and product rules, factorials, permutations, combinations, multinomial coefficients, stars and bars, inclusion–exclusion, the pigeonhole principle, Pascal's recurrence, the binomial theorem, and finite counting in probability.

Skill evidence includes defining an outcome space, deciding whether order and repetition matter, handling constraints, detecting overcounting, constructing bijections, building combinatorial proofs, checking small cases, and explaining why a formula applies.

Product evidence may include annotated diagrams, Pascal-triangle posters, route maps, Venn diagrams, short explanatory videos, interview reports, spreadsheets, programs that enumerate objects, or written proof portfolios.

Transfer evidence appears when you can apply the same ideas to a new context such as scheduling, network edges, password spaces, probability, data classification, algorithm analysis, or resource allocation without being told which formula to use.

OERs on the Topic

The English Wikipedia article provides a broad reference overview of combinatorics and links to many related topics:

For a deeper university-level extension, Discrete mathematics and Probability provide natural next steps, especially when you want to study graph counting, recurrences, generating functions, or probabilistic methods.

Linked Learning Areas

Combinatorics

Combinatorics connects especially strongly with Mathematics, Probability and statistics, Computer science, Graph theory, Set theory, Number theory, algorithm design, coding theory, and optimization. At Grades 11–13, these links help you see counting not as an isolated collection of formulas but as a common language for discrete structures.