A couple days ago I wrote a post about a probability problem that involved calculating Stirling numbers. There are two kinds of Stirling numbers, creatively called “Stirling numbers of the first kind” and “Stirling numbers of the second kind.” The second kind come up more often in application, and so …

One of these days I’d like to read Feller’s probability book slowly. He often says clever things in passing that are easy to miss. Here’s an example from Feller [1] that I overlooked until I saw it cited elsewhere. Suppose an urn contains n marbles, n1 red and n2 black. …

The shuffle product of two words, w1 and w2, written w1 Ш w2, is the set of all words formed by the letters in w1 and w2, preserving the order of each word’s letters. The name comes from the analogy with doing a riffle shuffle of two decks of cards. …

March 14, 2023, 12:39 a.m.

Design of experiments is a branch of statistics, and design theory is a branch of combinatorics, and yet they overlap quite a bit. It’s hard to say precisely what design theory is, but it’s consider with whether objects can be arranged in certain ways, and if so how many ways …

Suppose you have a black box that takes three bits as input and produces one bit as output. You could think of the input bits as positions of toggle switches, and the output bit as a light attached to the box that is either on or off. Now suppose that …

A few days ago I wrote about Room squares, squares named after Thomas Room. This post will be about Room’s original square. You could think of a Room square as a tournament design in which the rows represent locations and the columns represent rounds (or vice versa). Every team plays …

Sept. 28, 2022, 1:55 p.m.

The famous n queens problem is to find a way to position n queens on a n×n chessboard so that no queen attacks any other. That is, no two queens can be in the same row, the same column, or on the same diagonal. Here’s an example solution: Costas arrays …

Sept. 18, 2022, 7:14 p.m.

Suppose you have an even number of teams that you’d like to schedule in a Round Robin tournament. This means each team plays every other team exactly once. Denote the number of teams as 2n. You’d like each team to play in each round, so you need n locations for …

Sept. 17, 2022, 2:16 p.m.

The previous post looked at a generating function for a specific polynomial sequence. This post will look at generating functions for polynomial sequences in general. (There’s an alternating term in the previous post that isn’t polynomial, but we’ll address that too.) The starting point for this post is a simple …

Suppose you have a standard deck of 52 cards. You pull out a card, put it back in the deck, shuffle, and pull out another card. How long would you expect to do this until you’ve seen every card? Here’s a variation on the same problem. Suppose you’re a park …

The other day I wrote about orthogonal Latin squares. Two Latin squares are orthogonal if the list of pairs of corresponding elements in the two squares contains no repeats. A self-orthogonal Latin square (SOLS) is a Latin square that is orthogonal to its transpose. Here’s an example of a self-orthogonal …

Suppose you create an n × n Latin square filled with the first n letters of the Roman alphabet. This means that each letter appears exactly once in each row and in each column. You could repeat the same exercise only using the Greek alphabet. Is it possible to find …

In a n×n Latin square, each of the numbers 1 through n appears exactly once in each row and column. For example, the 5 × 5 square below is a Latin square. If we placed a rook on each square numbered 1, the rooks would not attack each other since …

A Latin square is an n × n grid with a number from 1 to n in each cell, such that no number appears twice in a row or twice in a column. It’s not obvious that Latin squares exist for all n, but they do, and in fact there …

Polynomials form a vector space—the sum of two polynomials is a polynomial etc.—and the most natural basis for this vector space is powers of x: 1, x, x², x³, … But the power basis is not the only possible basis, and often not the most useful basis in application. Falling …

Here are three things about dominoes, two easy and one more advanced. Counting First, how many pieces are there in a set of dominoes? A domino corresponds to an unordered pair of numbers from 0 to n. The most popular form has n = 6, but there are variations with …

Stirling numbers are something like binomial coefficients. They come in two varieties, imaginatively called the first kind and second kind. Unfortunately it is the second kind that are simpler to describe and that come up more often in applications, so we’ll start there. Stirling numbers of the second kind The …

The nth Bell number is the number of ways to partition a set of n labeled items. It’s also equal to the following sum. You may have to look at that sum twice to see it correctly. It looks a lot like the sum for en except the roles of …