Combinatorics

Six friends draw names for a gift exchange. How many draws send the gifts around in one unbroken loop?

Pick three vertices of a regular 12-gon. How many of the resulting triangles have all three angles acute?

In how many shuffles of 1 through 6 does the 2 come after both the 1 and the 3?

Five Americans and five Britons share a round table, and protocol demands they alternate.

How many distinct arrangements are there of the letters in MISSISSIPPI?

Pick as many numbers from 1 to 50 as you can, but no two of your picks may add up to a multiple of 7.

Four black beads and four white beads on a circle. Up to rotation, how many different necklaces can you form?

How many people need to be in a room before there is at least a 50% chance that two of them share a birthday?

Colour the eight corners of a cube black or white. Up to rotation, how many different patterns exist?

Snacks come only in boxes of 6, 9 or 20. Some orders can never be filled exactly. What is the largest such order?

Divide each central binomial coefficient by a power of 8 and add them all up. The total is a famous irrational number.

Join some of eight points on a circle in disjoint pairs so that no two chords cross. How many such drawings are possible?

Twelve edges, two colours, twenty-four rotations. How many essentially different edge colourings does a cube have?

How many functions from a 5-element set onto a 3-element set hit every element of the codomain?

Write out every integer from 1 to 1000. How many times do you write the digit 0? Leading zeros are the trap.

Three couples at a round table, and nobody is willing to be separated from their partner.

In a regular 12-gon with all diagonals drawn, many diagonals pass through the same points. How many distinct interior crossing points are there?

n letters are placed randomly into n addressed envelopes. As n → ∞, what does the probability that no letter ends up in its correct envelope approach?

Some numbers are the difference of two perfect squares and some are not. How many of 1 through 1000 are?

Write down every whole number from 1 up to 999,999 and add up every digit you wrote. What do you get?

Six-digit numbers like 112399, whose digits never step down. How many are there?

Draw any collection of diagonals in a convex heptagon, provided no two cross. How many collections are possible?

Write twenty as a sum of positive integers, order irrelevant, with no summand repeated. How many ways are there?

A 2 × 10 strip is to be covered using 1 × 2 dominoes and 2 × 2 squares. Count the tilings.

Mix 1 × 2 dominoes with L-shaped trominoes and tile a 2 × 8 strip. The count obeys a surprisingly short recurrence.

The 2 × n case gives Fibonacci numbers. What happens when the board is three squares tall and ten long?

Thirty-two dominoes cover an 8 × 8 chessboard. How many distinct ways are there to lay them?

In how many ways can 8 rooks be placed on a chessboard so that no two attack each other?

Words of length ten from a four-letter alphabet, but two of the letters must each appear an even number of times. How many words survive?

Add up every third entry of row 30 of Pascal's triangle. The answer is almost exactly a third of the row total, but not quite.

Stack the Fibonacci numbers into decimal places, each shifted one more place to the right, and the infinite sum is a surprisingly tidy fraction.

How many integers must you collect before you can always pick five of them whose sum is a multiple of 5?

Roll four dice that cannot be told apart. How many visibly different results are there?

There are 32768 labelled graphs on six vertices. How many remain once you forget the labels?

How many right/up paths cross an 8 × 8 grid from corner to corner?

How many numbers must you pick from {1, ..., 100} to guarantee two of them sum to 101?

Choose three numbers from 1 to 20. How often do they line up evenly spaced?

Every standard die has opposite faces summing to 7. Does that rule pin down a unique die, up to rotation?

A right triangle with legs 20 and 15 on the axes. How many lattice points lie strictly inside it?

How many different triangles have whole-number side lengths adding up to 30?

Eight friends bring gifts. Each one either keeps their own or trades with exactly one other friend. How many outcomes are possible?

L-shaped trominoes, rotated or flipped as you like, must exactly cover a 2 × 12 strip. How many tilings exist?

The circle of radius √325 centred at the origin passes through a surprising number of integer points. How many?

Five lines and five circles. What is the largest number of points where two of these curves cross?

A 4 by 4 array of points. How many distinct straight lines pass through at least two of them?

Cover a hexagon of side three with 60-degree rhombi. Seen the right way, every tiling is a pile of cubes in a corner.

A ticket is lucky when its first three digits add up to the same total as its last three. How many lucky tickets are there?

In how many ways can you make 25 cents from pennies, nickels, and dimes?

Join six points on a circle with all chords. The region counts 1, 2, 4, 8, 16 suggest 32 next; what is it really?

Split the numbers one through seven into groups so that no group contains two consecutive integers. How many ways?

Six ballots for Alice, four for Bob, counted one by one. In how many orders is Alice never trailing?

How many subsets of {1, ..., 10} contain no two consecutive integers?

Eight-letter words from a three-letter alphabet, with one rule: no letter may immediately repeat.

Binary strings of length twelve in which no symbol ever appears three times in a row. How many are there?

Ordered sums of ten in which neighbouring summands always differ. Count them.

Six people line up for a photo, but two of them each have one spot they refuse to take.

Shade the odd numbers in Pascal's triangle and a fractal appears. How many odd entries are in the first 64 rows?

Twelve customers buy five-dollar tickets, half paying with tens. The cashier starts with a single five. How likely is she never stuck?

Paint each face of a cube red, white or blue. Up to rotation, how many genuinely different cubes can you make?

Twelve pentagonal faces, three colours, sixty rotations. How many essentially different painted dodecahedra are there?

Four colours, four faces, repeats allowed. How many different painted tetrahedra can you make, counting rotations as the same?

Four-digit palindromes like 3443 or 9009. How many of them are multiples of 7? One factorisation does all the work.

An ordered sum of twenty that reads the same backwards as forwards. How many are there?

In how many ways can a 5-element set be split into any number of nonempty unlabeled blocks?

Order does not matter and repetition is allowed. In how many ways can fifteen be written as a sum of positive integers?

How many lattice paths from (0,0) to (10,10) never rise above the diagonal? The answer is a famous sequence in disguise.

Five horses race and dead heats are possible. How many different official results could the stewards announce?

A four-digit PIN whose digits add to 20. The upper limit of 9 per digit is what makes it interesting.

How many diagonals does a convex 12-sided polygon have?

Some two-colour necklaces repeat a shorter pattern; others have no rotational symmetry at all. With twelve beads, how many are primitive?

Five paints, and faces that share an edge must differ. Up to rotation, how many different cubes can be painted?

Shade any of the nine cells of a 3 by 3 tile. If the tile can be turned but not flipped, how many different tiles are there?

Choose half of the numbers from 1 to 14. How many of these choices have a sum that is a multiple of 7?

Paint a cube with six different colours, one per face. How many distinguishable cubes result?

Divide the numbers 1 through 12 into two teams with equal totals. In how many ways can it be done?

How many perfect squares divide 12! exactly? Read the answer straight off the prime factorisation.

How many nonnegative integer solutions does x₁ + x₂ + x₃ + x₄ = 10 have?

Straight 1 × 3 bars must exactly cover a board three squares tall and twelve long. How many tilings are there?

On a ten-step staircase you may take strides of any length you like. How many ways are there to reach the top?

Of the 1024 subsets of {1, ..., 10}, how many have a sum divisible by 11? A clean roots-of-unity argument gives it exactly.

Write down the smallest element of every 3-element subset of {1,...,10}, then add them all up.

Ten circles, every pair crossing twice, no three through a common point. How many regions of the plane result?

Draw ten straight lines across the plane, as generically as possible. Into how many pieces do they cut it?

A lab of ten must split into five unlabelled lab-partner pairs. How many pairings are possible?

Slice space with ten planes in general position. How many pieces does space fall into?

A staircase-shaped diamond of 40 squares is to be covered with dominoes. The count turns out to be startlingly clean.

Candidate A gets 60 votes, Candidate B gets 40. What is the probability A was strictly ahead throughout the entire count?

One step of a twelve-step staircase is rotten and cannot bear weight. How many ways remain to climb it in strides of one or two?

Eight knights at a round table, two of whom cannot stand the sight of each other at close range.

A frog hops along a row of lily pads, always jumping exactly two or three pads forward. In how many ways can it land on pad twenty?

At a party of 20 people, everyone shakes hands with everyone else exactly once. How many handshakes?

A king crosses a 6 × 6 grid of points moving only east, north, or northeast. How many routes reach the far corner?

100 people stand in a circle and every second person is eliminated until one remains. Which position survives?

Remove two opposite corners from a chessboard. Can 31 dominoes tile the remaining 62 squares?

Two cubes with relabelled faces roll every total exactly as often as ordinary dice do. What number do they need?

In how many distinct ways can 8 people sit around a circular table, counting rotations as the same?

Paint a cube using three colours, each on exactly two faces. Up to rotation, how many different cubes can you get?

Six beads on a loose loop, each one of three colours. A bracelet can be turned or flipped over. How many truly different bracelets are there?

How many integers from 1 to 1000 are divisible by 3 or 5?

How many ways can a 2 × 10 board be tiled with 1 × 2 dominoes?

A 5 by 5 array of dots. Count every square whose corners are dots, including the tilted ones.

How many zeros does 100! end in?

Draw every side and diagonal of a convex hexagon. How many triangles, of every size, can be traced in the figure?

Cut an equilateral triangle of side 6 into unit triangles. Counting all sizes, pointing up or down, how many triangles are in the figure?

Sixteen points in a square grid. How many triangles of positive area have all three corners among them?

Draw non-crossing diagonals until a convex octagon is cut entirely into triangles. How many different triangulations are possible?

Two queens on a chessboard, placed so that neither can capture the other.

Six guests, two identical round tables, nobody left without company of a table. How many seatings are there?

Place two identical tokens on a chessboard. If rotating or reflecting the board does not count as different, how many placements are there?

How many distinct necklaces of 6 black-or-white beads exist, counting rotations as the same?

In how many ways can 1/12 be written as the sum of two unit fractions, if order matters?

Arrange one through seven so the sequence rises, falls, rises, falls, all the way along. How many arrangements work?

Stand at the origin and look out over a 10 by 10 orchard of lattice-point trees. How many trees can you actually see?