It is well known that the number of ways to select k objects from a set of size n is given by the binomial coefficient
Implicit in the above statement is the restriction that an object can only be selected once. But what if we allow an object to be selected multiple times? For example, suppose we want to know how many ways a board of 12 people could select 5 officers. If no one can hold more than one office, the answer is given by the binomial coefficient (12, 5). But what if we allow the possibility that one person could hold more than one office?
Richard Stanley introduced the following symbol for the number of ways to select k things from a set of n with replacement.
There are several ways to think of what this symbol represents. The first is the number of ways to select k things from a set of n with replacement. A more concrete variation on the same idea is the number of ways to place k unlabelled balls into n labeled urns.
Where the binomial coefficient counts the number of subsets of size k drawn from a set of size n, Stanley’s symbol counts the number of multisets of size k than can be drawn from a set of size n. (A multiset is like a set, except elements are allowed to appear more than once.)
Another way to view Stanley’s symbol is the number of solutions to x1 + x2 + … + xn = n+k with positive integers. To see this, every xi corresponds to an urn. Initially every xi is set to 1, because we must have positive integer values. Then we have k 1’s to add to the variables, increasing the sum to n+k. The additional 1’s to add are analogous to balls.
As we will demonstrate below, Stanley’s symbol has a simple relation to binomial coefficients, namely
This may be why Stanley’s symbol is not well known: it’s always possible to represent values of his symbol in terms of the more familiar symbols. However, the advantage to Stanley’s symbol is that it directly represents the problem being solved. It is not at all obvious that the equivalent binomial coefficient is the solution to the combinatorial problem defining Stanley’s symbol.
Here are a couple examples to show how Stanley’s symbol comes up in applications. First, suppose people are classified into 6 demographic groups in a survey of 15 people. How many ways could the summary of the survey turn out when you only count the number of people in each group? Stanley’s symbol (6, 15). Think of each demographic category as an urn and each person as a ball.
Next, how many 3rd order partial derivatives does a smooth function of 5 variables have? Think of each variable as an urn, labeled x1 up through x5. We have three unlabeled balls. For every ball an urn gets, we take a partial derivative with respect to that variable. And so the number of distinct partial derivatives is Stanley’s symbol (5, 3).
(Since the function is smooth, the order of partial derivatives doesn’t matter. For example, differentiating with respect to x1 and then with respect to x3 gives the same result as differentiating in the opposite order. Otherwise, we could not have used the analogy with unlabeled balls. The balls would be labeled because the order in which they enter an urn would matter.)
Now we establish the equation above by using William Feller’s “stars and bars” argument given in his book Introduction to Probability.
Imagine the n urns as the spaces between n+1 vertical bars. Represent the balls as stars between the bars. For example, |*||***| gives an illustration of one way to assign four balls to three urns. There must be a bar in the first and last positions, but otherwise there are as many ways to assign k balls to n urns as there are ways to arrange the stars and bars. There are n-1 bars that we are free to move and k stars, for a total of n+k-1 symbols. Among the n+k-1 positions for these symbols, we choose k in which to put stars and fill the rest with bars. Thus the number of possibilities is the binomial coefficient (n+k-1, k) possibilities.
See also binomial coefficients.