Connecticut College
MICHAEL AVIDON
New London, CT 06320
RICK MABRY
Louisiana State University in Shreveport
PAUL SISSON
Shreveport, LA 71115
To appear in
Mathematics Magazine
© 2000 The Mathematical Association of America
Introduction A classic problem in beginning Finite or Discrete Mathematics courses reads as follows: A photographer wants to arrange N men and N women in a line so that men and women alternate. In how many ways can this be done?
This problem nicely illustrates the use of factorials and has a simple solution, though students often neglect the factor of two in the answer 2 (N!)2. This omission can be instructive, as it leads naturally to generalizations of the problem: How does the answer change if there are N men and N-1 women? What if men outnumber women by 2 or more? What if a sexist photographer insists that the lineup start with a man?
These variations are all easily dealt with, and illustrate some of the possible subtleties encountered in counting problems. Another variation of the problem is not, however, so easily handled. The setting (or sitting) must change slightly: A pet photographer must pose C cats, D dogs, and E emus in a line, with no two animals of the same species adjacent. In how many ways can this be done?
Skirting the issue of whether emus can in fact be considered pets, we quickly discover many interesting features in this variation of the problem. For example, C, D, and E can differ by more than 1 and still admit nonzero solutions. We also discover that the new problem is quite a bit harder than the original. Dating back to 1966 ( [6]), it is often called Smirnov's problem and it has practical applications in such areas such as queuing, transportation flow, sequential analysis and multivariate order statistics (see, e.g., [1,5]). The problem has been solved in a variety of ways (some of which we mention at the end of this note) but unlike those methods, what is presented here is entirely elementary and could be discussed in a first course in discrete mathematics or combinatorics.
Two ways of counting Consider any arrangement of a row of C cats, D dogs and E emus, distinguishable only by species. Let A(C,D,E) be the set of all such arrangements. As an example, consider the member of A(4,2,3) represented by the string cccdeeecd. Obviously this arrangement is not of the sort we are trying to count, as some adjacent seats are occupied by the same species. On the other hand, the arrangement cdcecedec in A(4,2,3) is the kind we want. Let L(C,D,E) denote the set of all such legal arrangements in A(C,D,E). We need to find the cardinality of L(C,D,E), which we denote by L(C,D,E). Now since these critters are pets, they should all be considered distinct! In that case we simply multiply L(C,D,E) by C!D!E! to account for the permuting of the animals within each species. But the crux of the problem is to find a formula for L(C,D,E), and so we will henceforth, unless otherwise stated, neglect the individuality of the creatures within each species.
Now let A and L denote, respectively, the set of all arrangements and legal arrangements, of any size. Define a map from A into L as follows: For a given arrangement in A, replace any run of identical species with a single member of that species (e.g., cccdeeecd ® cdecd). Then a member of A(C,D,E) will be mapped to some member of L(C¢,D¢,E¢), with 1 £ C¢ £ C, 1 £ D¢ £ D, and 1 £ E¢ £ E. In particular, an arrangement is legal iff it is mapped to itself.
We now seek the number of members of A(C,D,E) that will be mapped to a fixed member of L(C¢,D¢,E¢). This is a familiar type of pigeonhole problem, as we are asking for the number of ways that C cats can be distributed among C¢ compartments, and similarly for the dogs and emus. Many readers will recognize that the answer is
| (1) |
Lemma 1. The number of ways of distributing N indistinguishable items among N¢ nonempty compartments is
|
Proof. Consider a line of N "stars". From among the N-1 spaces between the stars, there are
|
|
Applying this lemma to each species in turn and invoking the multiplication principle produces formula (1).
Since L(C¢,D¢,E¢) stands for the number of legal arrangements of C¢ cats, D¢ dogs, and E¢ emus, it is clear that
|
| (2) |
Inverting the formula Our goal is to invert (2) to determine L(C,D,E). Fortunately, the inversion is easily accomplished due to the nature of the much-studied coefficients in front of the function L.
To begin, we define two matrices (of unspecified size, for the moment) A = (ai,j) and B = (bi,j), where
|
|
|
Lemma 2. Assume the sizes of A and B (resp. B and A) are such that the matrix product AB (resp. BA) is defined. Then åjai,jbj,k = di,k (resp. åjbi,jaj,k = di,k).
Proof. Let n equal the number of columns of A (and hence the number of rows of B). We will prove that åjai,jbj,k = di,k. (The proof of the second claim is similar.)
Let C = AB, and note that if we let C = (ci,k), then ci,k = 0 for i < k. For i ³ k, observe that
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Note, then, that if f and g are arbitrary functions defined on the natural numbers, each of the equations f(i) = åjai,j g(j) and g(i) = åjbi,j f(j) implies the other. A proof of one implication follows, with the other proved in identical fashion. Assuming the former equation holds, we have
|
| (3) |
We are now ready to isolate the function L from equation (2).
Theorem.
|
Proof. The formula follows immediately upon applying the observation in equation (3) to equation (2). Note that we are, in effect, "peeling off" the binary coefficients one at a time from the left-hand side of (2), with the result that they appear on the right-hand side along with the appropriate power of -1.
This finally reveals the photographer's conundrum. Once we acknowledge the individuality of the pets, the number of different seatings of the C cats, D dogs, and E emus is L(C,D,E)C! D! E!.
Just how bad is the situation for the photographer? We list below some values of special interest, namely, when C = D = E. Asymptotic estimates for L are known [1,5]. In particular, L(N,N,N) is asymptotic to a constant multiple of 8N/N.
| N | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| L(N,N,N) | 6 | 30 | 174 | 1092 | 7188 | 48852 | 339720 | 2403588 | 17236524 |
Some sophisticated methods Having presented an elementary approach to the problem, we offer a few tantalizing glimpses at some methods known to specialists. (Our problem can be viewed in many other frameworks. For example, L(C,D,E) is the number of different ways a labeled chain of C+D+E vertices can be properly colored (in the usual graph-theoretic sense) with three colors 1, 2, and 3, each used C, D, and E times, respectively. Or it can be viewed as the number of words that can be formed from the alphabet {c,d,e}, without adjacencies, and with the letter c being used C times, etc.)
|
|
|
|
It is also instructive to apply symbolic software, such as Mathematica, to explore all four methods of calculating L(C,D,E). Be forewarned, however, that the first two methods above will require significant computing time for all but small values of C, D and E.
Generalizations The problem can, of course, be generalized. In one direction, each of the formulas presented for L(C,D,E) can easily be extended to handle more species. For example, the number of legal arrangements of C cats, D dogs, E emus, and F frogs is
|
The formula can also be restricted to the original simple problem. If only cats and dogs are present, the obvious changes lead to a double summation formula for L(C,D). Of course, we already knew L(C,D): it must be either two, one, or zero, depending on whether C = D, |C-D| = 1, or |C-D| ³ 2, respectively. It is an interesting exercise to verify that the formula in the case of two species really does simplify in this manner.
Further generalizations are left to the reader to explore. For example, one of our students asked for the number of arrangements such that no member of a species is trapped between two other members of the same species. Or perhaps the photographer will permit blocks of up to k members of a given species, but no more. Other variations might concern circular arrangements or two-dimensional grid arrangements of seats. (The latter problem belongs to a class of more general problems concerning the enumeration of n-colorings of labeled graphs with specified numbers of each color, already very difficult for n = 2.)
Acknowledgment. The authors thank E. Rodney Canfield, Ira Gessel, Carl Pomerance, and an anonymous reviewer for their help in relating the problem to standard enumeration (emu-neration?) techniques, and for providing references to those methods.