Skip to content
Tutorials Center
My learning

Topics

Lesson 1 of 36 ยท Getting Started

What Is Combinatorics?

Meet combinatorics, the mathematics of counting. Learn the four basic questions, why counting gets hard fast, and how Python can check your answers.

Combinatorics is the mathematics of counting. How many different passwords are possible? In how many ways can eight people sit at a table? How many handshakes happen at a party? Each question asks "how many?", and the answer is a number you can reason out without listing every case.

That sounds easy until the numbers explode. There are more ways to shuffle a deck of cards than there are atoms on Earth, so listing is hopeless. Combinatorics gives you the tools to find such numbers with a few lines of reasoning, and this course also shows you how to confirm every formula with real code.

The four questions

Almost every counting problem is a variation of four questions. You choose some items from a collection, and you ask:

  1. Does the order of the chosen items matter?
  2. Can an item be repeated?
  3. Are some items identical to each other?
  4. Are there restrictions (this person must not sit next to that one)?

Answering these four tells you which tool to pick. Throughout the course you will meet the tools by name: the sum and product rules, permutations, combinations, inclusion-exclusion, and later recurrences, generating functions, partitions and more.

Four questions to ask

Order? ABC differs from CBA
Repeats? Can you pick twice
Identical? Two red balls look alike
Restrictions? Some choices forbidden

Answer these before you reach for a formula.

1 / 2

A first example, counted two ways

A pizza shop offers 3 sizes and 4 toppings. How many different single-topping pizzas can you order? You can list them all, or you can notice that each size pairs with each topping, so there are 3 x 4 = 12. The second way does not care if the menu grows to 300 sizes.

The code below counts the same thing both ways. When the two numbers agree, you have good evidence that your reasoning is right. We will do this check over and over.

Python Counting pizzas by listing and by multiplying

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Why counting is hard

Small counts are easy to verify by listing. The trouble is growth. A password of length 8 over 62 characters (letters and digits) has 62^8 possibilities, about 218 trillion. No loop should visit them all. Meanwhile, a smart formula gives the number instantly.

Here is the same idea on a smaller scale. The code compares a formula with a brute-force count and shows how quickly brute force becomes impractical.

Python Formula versus brute force

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice that the brute-force time grows with the answer, while the formula takes the same time for every length. That gap is the whole reason combinatorics exists.

Counting versus listing versus structure

Combinatorics asks three kinds of questions about a finite collection:

  • Enumeration: how many objects are there? (this course starts here)
  • Existence: is there at least one object with a given property? (the pigeonhole principle is a famous tool; a later chapter covers it)
  • Construction and optimization: how do you build one, or find the best one?

You will mostly count, but the same ideas power algorithms, probability and cryptography.

You do not need advanced math. If you can multiply, add and read a short Python loop, you are ready. Everything else is built from scratch.

How this course works

Each lesson has the same shape: an idea, a worked example, runnable code that checks the formula, a short quiz and a summary. The code runs right in your browser using Python, so you can change numbers and watch the answer change. The libraries math and itertools are enough for almost everything; later lessons also use sympy for symbolic work.

A good habit: before you run a formula, predict the answer on paper. When your prediction and the code disagree, one of them has a bug, and finding it teaches you more than any lecture.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which of these is a counting question?

    Counting asks how many objects fit a description. PIN codes are objects, and we want their number.
  2. 2. A menu has 5 starters and 6 mains. If you pick one of each, how many meals are possible?

    Each starter pairs with each main, so 5 x 6 = 30.
  3. 3. Which is NOT one of the four basic questions?

    Parity of the answer is unrelated. The four questions concern order, repetition, identical items and restrictions.
  4. 4. Why is brute-force listing a poor strategy for large problems?

    Counts such as 62^8 are far too large to enumerate, while a formula returns instantly.

Summary

  • Combinatorics is the mathematics of counting, existence and construction.
  • Four questions guide you: order, repetition, identical items, restrictions.
  • Counts grow explosively, so formulas beat brute force.
  • Python lets you check every formula against a small brute-force count.

Next: Sets and Counting Notation