All the data you need.

Tag: Combinatorics

Up-down permutations
An up-down permutation of an ordered set is a permutation such that as you move from left to right the permutation alternates up and down. For example 1, 5, 3, 4, 2 is an up-down permutation of 1, 2, 3, 4, 5 because 1 < 5 > 3 < 4 …
Ruzsa distance
A few days ago I wrote about Jaccard distance, a way of defining a distance between sets. The Ruzsa distance is similar, except it defines the distance between two subsets of an Abelian group. Subset difference Let A and B be two subsets of an Abelian (commutative) group G. Then …
The 10th Dedekind number
The nth Dedekind number M(n) is the number of monotone Boolean functions of n variables. The 9th Dedekind number was recently computed to be M(9) = 286386577668298411128469151667598498812366. The previous post defines monotone Boolean functions and explicitly enumerates the functions for one, two, or three variables. As that post demonstrates, M(1) …
Computing Stirling numbers with limited integers
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 …
Hypergeometric distribution symmetry
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. …
Shuffle product
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. …
Design of experiments and design theory
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 …
Efficiently testing a black box
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 …
The original Room square
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 …
Costas arrays
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 …
Balanced tournament designs
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 …
Generating functions for polynomial sequences
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 …
Sampling with replacement until you’ve seen everything
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 …
Self-Orthogonal Latin Squares
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 …
Greco-Latin squares and magic squares
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 …
Latin squares and 3D chess
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 …
How many Latin squares are there?
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 …
Change of basis and Stirling numbers
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 …