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 …

Most basic combinatorial problems can be solved in terms of multiplication, permutations, and combinations. The next step beyond the basics, in my experience, is counting selections with replacement. Often when I run into a problem that is not quite transparent, it boils down to this. Examples of selection with replacement …