Volume 13, Number 4, December 2007
Copyright � 2007 Society for Music Theory

KEYWORDS: combinatorics, enumeration, permutations, combinations, Pólya, pitch-class sets, set classes, twelve-tone rows

ABSTRACT: Many techniques in combinatorial mathematics have applications in music theory. Standard formulas for permutations and combinations may be used to enumerate melodies, rhythms, rows, pitch-class sets, and other familiar musical entities subject to various constraints on their structure. Some music scholars in the eighteenth century advocated elementary combinatorial methods, including dice games, as aids in composition. Problems involving the enumeration of set classes, row classes, and other types of equivalence classes are more difficult and require advanced techniques for their solution, notably Pólya’s Enumeration Theorem. Such techniques are applicable in a wide variety of situations, enabling the enumeration of diverse musical structures in scales of various cardinalities and under various definitions of equivalence relations.

Received August 2007

Editor's note: This article contains Greek letters, which may not display correctly in some web browsers. If you do not see the letter alpha here: α , please try a different browser.

---

“Can you do addition?” the White Queen asked.
“How much is one and one and one and one and one
and one and one and one and one and one?”
“I don’t know,” said Alice. “I lost count.”
“She can’t do addition,” the Red Queen interrupted.
                            —Lewis Carroll, Through the Looking Glass
 

[1] Table 1 gives the number of pitch-class sets and the number of Tn/TnI set classes of each cardinality from 0 through 12. The number of different pc-sets of cardinality k, appearing in the central row of the table, may be calculated by a well-known formula (to be reviewed below) for “the number of combinations of 12 things k at a time.” The set-class counts in the bottom row are familiar to music theorists not by means of a formula, but through the widespread use of tables enumerating all the set classes. Such tables appear, for example, in Forte 1973, Rahn 1980, Morris 1987 and 1991, and Straus 2005, among various other texts.

Table 1. Enumeration of mod-12 pitch-class sets and Tn/TnI set classes (click to enlarge)

[2] The formula giving the number of set classes—if indeed there is such a formula at all—is not an obvious one. On reflection, some aspects of these numbers may even seem somewhat counterintuitive. We might expect that when we count something governed by a high degree of symmetry, such as the number of different types of four-element subsets of a twelve-element set, we should end up with a “round” number—probably a number with many divisors, such as 24, 30, or 36. The fact that the number of tetrachord types turns out to be 29—a number not only odd but prime—challenges this intuition and suggests that the enumeration question may be deeper or more difficult than we imagined.

[3] Bernard 1997 and Nolan 2003 show that pitch-class sets and set classes have been effectively enumerated in various ways dating back at least to the late nineteenth century. In general, though, the music scholars who have carried out this exercise have not pursued mathematical explanations for the numbers appearing in the bottom row of Table 1. That is, they have not attempted to calculate the number of set classes except by exhaustively listing all of the set classes—a process akin to the White Queen’s way of “doing addition” in the quotation above.

[4] Beyond simple curiosity, a further motivation for exploring the mathematics behind set-class enumeration is its potential for generalization. If we develop a formula that explains why there are 29 tetrachords, that formula will likely be applicable in a variety of other situations: other cardinalities of set (besides 4), other cardinalities of the underlying scale (besides 12), other definitions of “set class” (besides the usual one based on T_n/T_nI equivalence), and perhaps enumeration problems of entirely different sorts, involving twelve-tone rows or rhythms, for example. Listing and counting all the mod-12 set classes is feasible but already somewhat unwieldy, as the multi-page lengths of the tabulations cited above reveal; it is not hard to devise similar problems for which the numbers involved are much larger and the exhaustive approach becomes impractical.

[5] This article is organized in two parts. Part I, which might be subtitled “What every music theorist should know about combinatorics,” offers a primer on standard techniques in classical combinatorial theory (including the “combinations” formula mentioned above) and offers some simple applications to music theory (including the enumeration of pitch-class sets) and historical notes (including a brief overview of the ars combinatoria that found its way into eighteenth-century musical discourse). The computational methods of Part I are familiar to every mathematician and will be familiar as well to many readers of this article. I believe it is useful to include this crash course here because, even though the mathematics involved is elementary, it has never become a part of the standard music theorist’s toolbox and has seldom if ever been given a unified presentation oriented toward musical applications. Moreover, the elementary techniques covered in Part I foreshadow certain aspects of the more difficult work of Part II, and therefore may form a pedagogically beneficial bridge to the advanced material.

[6] The general problem of set-class enumeration, as intimated above, turns out to require mathematical techniques of substantial power and sophistication. Some of the appropriate methodology was not developed until well into the twentieth century; the most important theoretical result, Pólya’s Enumeration Theorem, was first published in 1937. Part II is devoted to an exploration of some of these advanced techniques and their music-theoretic applications. Here at last the numbers in the bottom row of Table 1 will find their theoretical justification, and a variety of other musical problems amenable to the same techniques will be discussed.

[7] It should be acknowledged at the outset that most of the results in this article, even those in Part II, are not new. Applications of Pólya’s theorem to the set-class enumeration problem and other musical situations may be found in Reiner 1985, Fripertinger 1993 and 1999, Read 1997, Jedrzejewski 2006, and Benson 2007. Most music theorists, however, would likely find these sources impenetrable, as all of them demand considerable mathematical fluency of the reader. I hope in this article to provide an exposition that will be more readily accessible to the music theory community. The mathematical discourse will have to be ratcheted up a notch in Part II, where some basic group theory will be assumed, but on the whole the most important mathematical prerequisite for this article is a simple willingness to jump in and get one’s hands dirty.

I. Elementary Techniques

[8] 1.1. Combinatorics. If a five-person committee is to be appointed from a group of eleven people, how many different committees are possible? In how many different ways can the six faces of a cube be painted if each face is to be a solid color, four colors are available, and all possible rotations of one painted cube are considered the same? Given a map showing a network of intersecting roads across the state of Texas, in how many ways can one travel from Galveston to Amarillo without crossing one’s path? These are some of the questions addressed by the branch of mathematics known as combinatorics. Combinatorics is essentially the study of methods of counting—enumerating all the objects of a certain description, all the ways in which a certain task can be performed, or all possible outcomes of a certain series of actions.⁽²⁾

[9] The most obvious way to find out how many objects of a certain type there are is the White Queen’s method: count them, one by one by one. Of course, people have been counting things for thousands of years. Listing and counting a large number of possibilities, however, is inefficient, prone to error, and in many situations completely impractical (although of course computers have redefined what we mean by “practical”). Moreover, it is mathematically unrevealing. In comparison with a method that tells us that the answer to a certain problem is 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1, a procedure that gives a formula such as 2 · 5 or 5 · 4 / 2, or possibly 4 + 3 + 2 + 1, is likely to be both more reliable and more enlightening: it will not only tell us that the answer is 10, but will also offer some insight into why it should be 10 rather than 9 or 11, may convey a helpful visual interpretation of the calculation, and also may suggest answers or approaches to other similar problems. It may be said, therefore, that combinatorics is not so much the study of counting as the study of how to avoid counting: the search for more revealing and more efficient approaches to problems of enumeration that could, at least in principle, be solved by brute force.

[10] Not surprisingly, some of the earliest recorded mathematics involves questions of enumeration. Combinatorial problems are presented and solved (along with problems in algebra and simple arithmetic) in the Rhind Papyrus, an Egyptian document dating from about 1650 BCE but apparently copied from even older sources. Such problems also interested Pingala, an Indian mathematician of the third century BCE; Sun Zi (Sun Tzu), a Chinese mathematician of approximately the third century CE; and Leonardo of Pisa (Fibonacci), writing around 1200.⁽³⁾

[11] Problems in combinatorics are often easy to state and to understand but deceptively difficult to solve. Combinatorics has consequently attracted the attention of some of the greatest minds in mathematics, but has also exerted a powerful appeal on many mathematical amateurs. Such is the allure of the discipline that is has often been extolled as an art, known by the Latin name ars combinatoria. Ars combinatoria is, in fact, the name of a journal of combinatorics, and De arte combinatoria is the title of a 1666 treatise by Gottfried Wilhelm Leibniz (1646–1716), who is remembered especially for his pioneering work in calculus but who also spearheaded a renewed interest in combinatorial theory among leading European mathematicians in the seventeenth and eighteenth centuries. Among the parade of other celebrated mathematicians who devised powerful combinatorial techniques may be found Blaise Pascal (1623–62), forever associated with the triangle (discussed below) that bears his name, though he was not the first to construct it; Jacob Bernoulli (1654–1705), a follower of Leibniz and one of the most notable members of a family that was to produce no fewer than ten distinguished mathematicians; Leonhard Euler (1707–1783), whose astonishingly broad range of achievements not only forged connections between combinatorics and other branches of mathematics but even ventured into music (Euler constructed a version of what we now know as the Riemannian Tonnetz); and Pierre-Simon Laplace (1749–1827), who among his many and varied accomplishments pioneered the study of probability, which is intimately connected to combinatorics.

[12] Combinatorial problems typically involve small numbers of objects that give rise to large numbers of possible configurations through combinations of various kinds. Music offers a clear illustration: though there may be only a small number of notes and durations to work with, the variety of ways in which a composer may combine them into a musical composition is enormous. Loosely speaking, the main reason for the proliferation of possibilities is what we may call the multiplication principle: if several choices are made independently, or several events happen in succession, the numbers of possibilities at the various stages are multiplied (not added as beginning students of the subject sometimes mistakenly assume). This simple principle suffices to solve a wide variety of enumeration problems; we offer a few musical illustrations.

[13] 1.2. Example: simple melodies. Suppose we wish to write a melody using only the notes of one octave of a major scale: eight notes to choose from (including tonic at both ends of the scale). Even if we restrict ourselves to melodies six notes in length (to choose an arbitrary but manageable limit), and even if we ignore rhythmic considerations entirely, the number of possibilities is 8 · 8 · 8 · 8 · 8 · 8, which is 8⁶ (8 to the 6th power) or 262,144—more than a quarter-million possible melodies, far more than anyone would care to list and count by hand. (The fact that many of these melodies will not be of much musical interest is, of course, beside the point of the present all-inclusive calculation. At least in principle, the formula is subject to numerous possible refinements on the basis of various criteria for “musical interest.”)

[14] The above calculation enumerates the melodies that are exactly six notes long. If we wish to consider melodies that are no more than six notes long, then we may add the corresponding results for lengths 1 through 6, yielding

8¹ + 8² + 8³ + 8⁴ + 8⁵ + 8⁶ = 8 + 64 + 512 + 4,096 + 32,768 + 262,144 = 299,592.

This sum may be written more compactly in the form

(“the summation of 8^k as k ranges from 1 to 6”).

[15] This formula is a simple one, but a few further remarks are in order for the benefit of readers with little experience in such calculations. In light of our previous remarks about the multiplication principle, it is worth taking a moment to consider why the six powers of 8 have been added rather than multiplied. We did not set out to write a one-note melody and a two-note melody and a three-note melody, and so on through six successive independently constructed melodies; had that been our intent, we would have multiplied the numbers. (The resulting product, 8¹ · 8² · 8³ · 8⁴ · 8⁵ · 8⁶, is precisely 8²¹, which is as we should have suspected, since by making all the above choices in succession we would effectively have composed a 21-note melody.) Rather, the problem called for us to choose a one-note melody or a two-note melody or a three-note melody or ... . The difference between and and or is the difference between multiplication and addition. In making a single selection from several mutually exclusive sets of choices, the possibilities must be added, not multiplied.

[16] The number of melodies with no more than six notes (299,592) does not appear much larger than the number with exactly six notes (262,144). Another look at the summation above shows why. Each successive power of 8 is significantly larger than all the previous ones, so the sum is dominated by its last (and largest) term. All melodies of one through five notes are numerically insignificant compared with the melodies of six notes—but bumping the length limit up from six notes to seven would change the magnitude of the total dramatically.

[17] A detail-minded mathematician could claim that the above sum overlooks one melody of “no more than six notes,” namely the “empty melody” consisting of no notes at all. If we wish to account for this “melody of length zero,” we may do so with little difficulty. The 0th power of any positive number is 1 by definition,⁽⁴⁾ so adding 8⁰ at the beginning of the sum increases the total by 1; the revised total is

[18] Such formulas are reasonably compact and convenient, but the calculation of this sum of powers still entails several steps. Much of the work of the early combinatorists was devoted to the derivation of formulas by which such calculations could be simplified further. Precisely such a formula is applicable in this case, namely the “sum of a geometric series” given by

Substituting a = 8 and n = 6 in this equation, the right side reduces to

the same answer as before. Here the summation of six powers has been replaced by a single power calculation and a simple division—a gain in efficiency that becomes more pronounced as the numbers involved grow larger.

[19] 1.3. Example: twelve-tone rows. How many possible twelve-tone rows are there? At first glance this example resembles the previous one, but with twelve notes to choose from (rather than eight) and twelve notes in the melody (rather than six), so we might suppose that the answer should be 12¹². But there is a problem: a melody twelve notes in length can (and usually will) repeat one or more pitch classes, so not all of the 12¹² melodies are actually valid rows.

[20] The multiplication principle is still applicable to this problem, but it must be applied judiciously. Let us construct a twelve-tone row, one note at a time. Of course there are 12 choices for the first note. But whatever the first note is, it cannot be repeated, so there are only 11 possible choices for the second note (and therefore 12 · 11 = 132 possibilities for the first two notes in order, rather than 12 · 12 = 144). By the same reasoning, there are only 10 possibilities for the third note, 9 for the fourth, and so on, and the total number of possible rows is

12 · 11 · 10 · 9 · 8 · 7 · 6 · 5 · 4 · 3 · 2 · 1 = 479,001,600.

This product is traditionally known as “12 factorial,” abbreviated 12!. (In general, n! is the product of all the integers from 1 to n.) This is a very large number—almost half a billion—but it is nevertheless far smaller than 12¹², which is almost 9 trillion. (As n increases, n! grows very rapidly—but not as rapidly as nⁿ.)

[21] The last factor in the above product is the number 1. Multiplying by 1, of course, has no bearing on the result. This makes sense because once the first eleven notes of a twelve-tone row have been selected, the twelfth is automatically determined—there are no more choices to make. In a twelve-pc universe, the number of twelve-tone rows is the same as the number of eleven-tone rows.

[22] The above calculation gives the literal count of arrangements of the twelve pitch classes; it does not take into account the convention in serial theory by which rows related to each other by transposition, inversion, or retrogression are considered equivalent. We have counted rows, that is, not row classes. If all row classes consisted of exactly 48 rows, the number of row classes could be obtained by dividing the above total by 48. But there are some symmetrical rows (that of Berg’s Lyric Suite being a well-known example) whose classes contain only 24 rows rather than 48, so this calculation would be in error. The precise calculation of the number of row classes is a considerably more complex problem, and will be considered in Part II. (In fact, most row classes do comprise 48 distinct rows, so even the incorrect calculation outlined above would give a good estimate, differing from the actual count of row classes by less than 0.1 percent.)

[23] 1.4. Permutations. The enumeration of twelve-tone rows is an example of a permutation problem. A permutation is an ordered arrangement of objects. It should be evident from the above discussion that the number of permutations of n objects is n!. Occasionally it is useful to form a permutation of some subset of the available objects rather than of all of them; that is, there are n objects from which to choose, but we are to construct an ordered arrangement of only k of them, for some k < n. Such arrangements are referred to as “permutations of n objects k at a time,” and the number of these permutations is denoted P(n, k). By the above reasoning, P(n, k) may be calculated as a product n · (n – 1) · (n – 2) · · · (n – k + 1), similar to the calculation of n! but stopping after the first k factors. This product may be written more compactly in the form

In this formula the n – k “extra” factors (n – k) ^... 1 in n! in the numerator of the fraction are exactly canceled by the corresponding factors in (n – k)! in the denominator.

[24] 1.5. Example: melodies with no repeated notes. Suppose again that we wish to write a six-note melody from our one-octave diatonic scale, but now with the restriction that all six notes must be different. The number of ways to do this is P(8, 6), or 8 · 7 · 6 · 5 · 4 · 3, or 8!/2!, or 20,160. This figure represents a drastic reduction from the number 262,144 calculated previously when note repetitions were allowed: more than 92 percent of the six-note melodies enumerated in section 1.2 include at least one note repetition. This statistical generalization is surely reflected in compositional practice: apart from the occasional unidirectional scalar melody (“Joy to the World”), coherent melodic phrases in which no notes are repeated are rare.

[25] 1.6. Example: pitch-class sets. How many pitch-class sets are there? It may not be immediately obvious that the multiplication principle applies to this question: pc-sets are not permutations, and we do not ordinarily think of constructing a pc-set through an orderly selection process with an easily determined number of choices at each stage. But there is such a process, a very simple one in fact, and it illustrates the creative logic with which simple combinatorial principles can often be applied. A pc-set may be uniquely specified by considering each of the twelve pitch classes in turn, and answering for each one a yes-or-no question. Is C in the set? Is C-sharp in the set? Is D in the set? When all twelve questions have been answered, the set is determined. The number of pitch-class sets is the number of ways the questions can be answered, namely 2¹² = 4,096. This number appears at the right side of Table 1. The calculation accounts for both the empty set (the result of answering “no” to all questions) and the complete twelve-tone aggregate (“yes” to all questions), along with everything in between. By the same reasoning, the number of distinct subsets of any set with n elements is always precisely 2ⁿ.

[26] 1.7. Example: rhythms. How many different rhythms are possible within a 4/4 measure, given that there are no rests and that all durations are to be eighth notes or whole multiples thereof? This problem, too, is a simple one when viewed from the proper perspective. Such a rhythm may be represented as a string of eight eighth notes, with some adjacent notes joined by ties. Specifying a rhythm is tantamount to specifying a subset of the seven possible ties; the number of possibilities is therefore 2⁷ = 128. If sixteenth-note multiple durations are allowed, the number rises dramatically to 2¹⁵ = 32,768.

[27] 1.8. Example: pitch-class sets of specified cardinality; combinations. How many four-note pitch-class sets are there? The figure 4,096 calculated in section 1.6 gives the total number of pc-sets of all possible cardinalities in mod-12 space, but we have not yet shown how to calculate the number of pc-sets of any given size. There are P(12, 4) = 11,880 permutations of four pcs, but that is not the number of four-note pc-sets: the 11,880 permutations would, for instance, count C–D–E–G, C–D–G–E, and E–G–C–D as three separate permutations even though as pc-sets they are all the same. Permutations are ordered arrangements; unordered collections are known as combinations. In terminology more familiar in music theory, combinations are sets while permutations are segments or strings.

[28] The number of “combinations of n things k at a time” is denoted C(n, k); this is simply the number of different k-element subsets of a fixed n-element set. Clearly C(n, k) is a smaller number than P(n, k). How much smaller? In the case of four-note sets, the enumeration of the P(12, 4) permutations will count every combination many times—precisely 4! = 24 times, in fact, because the four notes of any such set can be permuted in 4! ways. It follows that C(12, 4) is exactly P(12, 4) divided by 24, which is 11,880/24 or 495. The general combinations formula is

[29] These combination numbers C(n, k) (for n = 12) are precisely the numbers in the central row of Table 1. This row is symmetrical from left to right, because C(n, k) = C(n, n – k). This is clear from the above formula, in which k and n – k are interchangeable; of course it is also clear because k-element sets are in one-to-one correspondence with their (n – k)-element complements.

[30] 1.9. Pascal’s triangle and the binomial theorem. The combination numbers turn up in many diverse mathematical contexts. These are, in fact, the numbers appearing in Pascal’s triangle, shown in Figure 1. The number C(n, k) may be found at the intersection of the nth row and the kth diagonal, as illustrated in the figure for n = 8 and k = 3. Each number in the interior of this triangle is the sum of the two numbers immediately above it. The preceding discussion explains why the triangle is symmetrical from left to right, and why the sum of all the numbers in the nth row is exactly 2n. [31] The combination numbers appear also in the well-known binomial theorem. If the algebraic expression x + y (a binomial) is raised to successive powers, the numbers appearing as coefficients in the various terms of the algebraic expansions are exactly the combination numbers C(n, k), and can, in fact, be read directly across the rows of Pascal’s triangle, as illustrated in Figure 2. The numbers C(n, k) are therefore often called binomial coefficients. A frequently used alternate notation for binomial coefficients is The symbol on the right is commonly pronounced “n choose k,” reflecting the number’s interpretation as an enumeration of combinations.

Figure 1. Pascal’s triangle (click to enlarge) Figure 2. The binomial theorem (click to enlarge)

[32] The relation between binomial expansions and enumeration is worth lingering over a bit longer, because it resembles, in a somewhat simplified form, the more advanced enumeration techniques to be explored in Part II. According to the binomial theorem, the expansion of the binomial (x + y)¹² is

(x + y)¹² = C(12, 0)x¹² + C(12, 1)x¹¹y + ^... + C(12, 11)xy¹¹ + C(12, 12)y¹²,

which may be calculated as

x¹² + 12x¹¹y + 66x¹⁰y² + 220x⁹y³ + 495x⁸y⁴ + 792x⁷y⁵ + 924x⁶y⁶
+ 792x⁵y⁷ + 495x⁴y⁸ + 220x³y⁹ + 66x²y¹⁰ + 12xy¹¹ + y¹².

The above expression is a polynomial in the two variables x and y; the polynomial is homogeneous of degree 12, meaning that in each term the exponents on x and y add up to 12. The variables x and y here do not represent any particular quantities; they serve only as algebraic placeholders to assist us in organizing our calculations involving the coefficients, which are our primary interest.

[33] These coefficients are, of course, the numbers from Table 1, enumerating pc-sets of each cardinality from 0 to 12. The binomial theorem therefore provides a method for calculating the pc-set counts: take the abstract binomial x + y, raise it to the power 12, do the algebra, and the desired numbers emerge. We may say that (x + y)¹² is an enumeration function for the pc-set counts. In this case, doing the calculation in this rather cumbersome way is quite unnecessary because we already know a simple formula for the combination numbers. But there is no simple formula for the set-class numbers in the bottom row of Table 1. When we calculate these numbers in Part II, we shall do so by exhibiting an enumeration function for them—a function more complex than a power of a binomial, but similar to the binomial theorem in its general strategy.

[34] 1.10. Example: intervals in pitch-class sets. Consider for a moment the numbers appearing in the k = 2 diagonal of Pascal’s triangle: 1, 3, 6, 10, 15, 21, 28, ... . These are the numbers C(n, 2) for n ≥ 2. The combinations formula in this case reduces to

The number C(n, 2) has a natural musical interpretation as the number of 2-note subsets—that is, intervals—within a pc-set of cardinality n. This observation explains why the sum of the entries in the interval-class vector of a pc-set is always 3 for a trichord, 6 for a tetrachord, 10 for a pentachord, and so on.

[35] 1.11. Ars combinatoria and eighteenth-century music. We conclude Part I with a few illustrations of ways in which elementary combinatorial principles such as those discussed above left their mark upon musical composition and scholarship in the eighteenth century. By this time, mathematical techniques and mechanistic explanations were infusing many aspects of life and art, and music was no exception. Many of the leading musical treatises of the day include careful enumerations of musical configurations of various kinds, as well as particularly methodical and exhaustive case-by-case analysis more or less in the spirit of ars combinatoria.⁽⁵⁾

[36] Among the most fervent advocates of combinatorial methods in music was Joseph Riepel, who applied such methods to a great many musical parameters with meticulous thoroughness. In his Grundregeln zur Tonordnung insgemein of 1755, Riepel takes a four-note figure and exhibits all 4! = 24 possible permutations. Turning his attention to chord structure, he considers all possible three- and four-note diatonic chords over a fixed bass note; this is a problem in combinations rather than permutations, and Riepel recognizes correctly that the possibilities for three-note chords number C(7, 2) = 21 and for four-note chords C(7, 3) = 35. Another opportunity for permutations arises when Riepel considers the order of keys within a composition: for a piece that starts and ends in C major, Riepel actually lists all the 5! = 120 possible permutations of the other five closely related keys that could occur in between. In a later publication Riepel even enumerates patterns of articulation and bowing. As Riepel sums up his attitude in the Grundregeln, �the unique art of permutations, by which one can uncover in a single day far more than 99 themes, is at least 99 times healthier for composition than the calculation of ratios.”⁽⁶⁾

[37] Riepel was a practical musician, and as his disparaging reference to the pitch-ratio calculations used by Rameau and others as justification for their harmonic theories attests, he abhorred some kinds of abstract mathematical calculation. He evidently believed, though, that the study of permutations was a useful aid in the production of effective compositions. After enumerating melodic permutations and chords as described above, he proceeds to display every one of them in a sensible musical context (except for a few of the four-note chords that he dismisses as unworkable). Another theorist who expressed a similar view and who may even have surpassed Riepel in his zeal for combinatorics was Francesco Galeazzi, who in his Elementi teorico-pratici di musica of 1791–96 defends his method of inventing melodic figures by combinatorial manipulation, saying that it is especially suitable for sparking the imaginations of those who are otherwise unable to invent their own:

We find many who can proceed with a given figure with little effort but who have insuperable difficulties when they have to invent new material. Here is something that can assist (in invention) with which one can discover a hundred, a thousand in the twinkling of an eye: it may appear puerile but first experiment with it and then judge.⁽⁷⁾

[38] 1.12. Dice games. Among the best-known examples of combinatorial activity in eighteenth-century music are the “dice games” that were in vogue roughly for the latter half of the century. These games offer a completely mechanical way to compose: as their authors almost invariably point out, one need not know any rules of music, only the rules of the game. The first such game appeared in 1757 as Johann Philipp Kirnberger’s first published work, Der allezeit fertige Polonaisen- und Menuettencomponist (“Every-Ready Polonaise and Minuet Composer”). Kirnberger’s method spawned a wealth of imitators, with more than a dozen similar games appearing in the following decades, including games attributed somewhat dubiously to Haydn and Mozart.⁽⁸⁾

[39] To play the game, one generally rolls a die (or rolls two dice, or spins a top, or generates a random number by some other means), then looks up the resulting number in a table to find a reference to a measure (more or less) of music, which one transcribes; then one rolls again, consults the next column of the table to find the next measure; and so on. After typically sixteen or thirty-two measures, one has a complete waltz, or minuet, or polonaise, or march, or organ prelude. The logic of the game is simple enough: all the possible outcomes for any given measure share a harmonic basis, so the broad tonal outline of the piece is fixed, independent of the rolls of the dice, though the melodic and rhythmic details are quite variable. The scrambled appearance of the numbers in the table is contrived to shield the player from the underlying logic, thereby making the reasonably coherent music that emerges seem downright magical.

[40] Because of the multiplication principle, the number of possible compositions that can result from even a short dice game is enormous. In the game attributed to Mozart, for example, two dice are rolled, so there are eleven possible outcomes for each measure (the numbers 2 through 12—not all of which, it may be noted, are equally likely). The number of possibilities for the sixteen measures of music should therefore be 11¹⁶, a 17-digit number. Careful scrutiny of the tables reveals, however, that all eleven versions of measure 8 are the same, as are all eleven versions of measure 16, so the actual number of possible compositions is 11¹⁴, which is “only” about 380,000,000,000,000. Of course the actual variety present in these compositions is far more limited than such a vast sum may suggest, because they share an underlying harmonic structure and are composed from a common pool of musical fragments. Nevertheless, Joel Lester and Leonard Ratner have pointed out that these games could have come to the aid of a host in need of a supply of dances with which to entertain his guests, or a small-town organist without ready access to large quantities of printed music (Lester 1992, 229; Ratner 1970, 357).

[41] Eighteenth-century dice games have been cited by David Cope as important precedents for his much-publicized “Experiments in Musical Intelligence” computer program, which composes music in various styles (Cope 2001), but such games may seem far removed from the usual compositional practices and artistic ideals of human composers such as Haydn, Mozart, and Beethoven. Ratner, however, discerns quasi-combinatorial processes at work in the music of all three of the Viennese masters (Ratner 1970, 359–62). Ratner observes, for instance, that the patchwork rearrangement of an eight-measure melody near the end of the Alla tedesca movement of Beethoven’s String Quartet, Op. 130, is a permutational process. A Mozartian brand of permutation is on display in the famous five-part counterpoint that brings the curtain down on the “Jupiter” Symphony: the five melodic figures are traded among the five string parts in a largely systematic sequence of permutations constructed to ensure that each part takes a turn at each figure.⁽⁹⁾ (It has been suggested that writing out the 5! = 120 permutations of this counterpoint by hand would constitute apt punishment for unruly theory students.) Haydn’s frequent rearrangements of themes in his recapitulations also represent a sort of permutation; in that light, even sonata form can be seen as a series of slots into which musical elements may be inserted through combinatorial play. In Ratner’s concluding words:

Ars combinatoria is not composition but a resource in its service; it is a rational, intellectual device that can help to spark musical feeling, to set the clockwork in motion, to stir the mechanical into life. (Ratner 1970, 361–62)

II. Advanced Techniques

[42] 2.1. Groups of equivalences. Enumerating set classes—the bottom row of numbers in Table 1—is not a simple exercise in permutations or combinations. Instead, the problem is to count equivalence classes under a given equivalence relation. The equivalence relation is defined by a group G of transformations⁽¹⁰⁾ acting on a set Z of configurations of some sort; two configurations are considered equivalent if some transformation in the group maps one to the other. For this reason we call G the group of equivalences for the enumeration problem under consideration. (In the usual conception of pc-sets and set classes, the configurations are pc-sets and the group of equivalences consists of all the transposition and inversion operators.) The problem is to enumerate not the configurations themselves but the equivalence classes, or orbits as they are commonly called. The orbit of a configuration z in the set Z consists of all the configurations g(z), as g ranges through the transformations in the group G. In many cases we are interested not only in a single count of all the orbits, but in sub-counts of orbits of certain types (such as set classes consisting of sets of certain specific cardinalities).

[43] Although this problem is not one of permutations as discussed in Part I, the word permutation is often employed in this context as well—a usage whose sense it is important to understand. The configurations under consideration typically consist of a fixed number N of objects arranged in some characteristic way, and a transformation typically acts on a configuration by rearranging, or permuting, the N objects. In Part I we described permutations as static arrangements of objects, but they may also be regarded more dynamically as mappings, or transformations, that map a set of objects to itself. A pitch-class operator such as T₄I may be regarded as a permutation of the twelve pitch classes, either as a mapping

or in static form as the arrangement 43210BA98765. The N! possible permutations of N objects form a group (commonly known as S_N, the symmetric group on N objects), and the group of equivalences G in any enumeration problem is typically a subgroup of S_N. Of course, G need not include every permutation in S_N. Indeed, if it does, then every configuration is deemed “equivalent” to every other, so they are all in the same orbit and there is nothing of interest to count. The twelve pitch classes theoretically admit 12! = 479,001,600 permutations, but most of these permutations jumble the pitch classes in musically nonsensical fashion; only 24 of them are members of the group of transposition and inversion operators.

[44] 2.2. Burnside’s Lemma. A single overall count of orbits can generally be calculated by means of a theorem that goes by the name of Burnside’s Lemma:⁽¹¹⁾

If a group G acts on a set Z of configurations, the number of orbits is

where |G| denotes the order (cardinality) of the group G; the sum is taken over all permutations g in the group G; and ψ(g) denotes the number of configurations fixed by the permutation g (that is, the number of configurations z in Z such that g(z) = z).

By adding up ψ(g) for the various permutations g in the group G and then dividing by the order of the group, as the above formula specifies, we are effectively calculating the average value of ψ(g). Burnside’s Lemma says, therefore, that the number of orbits is equal to the average number of configurations fixed by an element of the transformation group. Upon reflection, this formula should make intuitive sense. In the trivial case in which the only element of the group is the identity e, each configuration is an orbit by itself, so the number of orbits is the number of configurations, which is also ψ(e) since the identity fixes everything. If there are other transformations in the group that fix fewer things, then more things become equivalent, the number of orbits decreases, and the average value of ψ(g) decreases also.

[45] Before applying Burnside’s Lemma to the set-class problem, it is instructive to consider two simpler situations of types commonly encountered in the study of combinatorics, which we shall call the birthday-cake problem and the necklace problem.

Figure 3. Four configurations of candles on a birthday cake or beads in a necklace

(click to enlarge)

[46] 2.3. Example: birthday-cake problem. First suppose you wish to put four candles on a cake; you have four fixed positions in which to place candles, and you have supplies of candles of three different colors (red, blue, green). The number of configurations is 3⁴ = 81. But some of these are equivalent, because a birthday cake can be rotated. In Figure 3, for example, configurations (a) and (b) are equivalent; if you decorate the cake as at (a), you can easily turn it to look like (b). Neither configuration (c) nor (d), however, is equivalent to any of the others shown (even though all four use the same colors in the same quantities). The group of equivalences G is the cyclic group C₄ of order 4. The elements of this group are analogous to transpositions in pitch-class space, so we may designate them by the labels T₀, T₁, T₂, and T₃. T₀ is the identity transformation—the identity element of the group—and of course it fixes all 81 configurations, so ψ(T₀) = 81. T₁ is a 90-degree clockwise rotation; the only way a configuration can be unchanged by this rotation is if all four candles are the same color. The only possibilities for such a configuration are the three single-color candle arrangements (all red candles, all blue, or all green), so ψ(T₁) = 3. Likewise T₃, the 90-degree rotation in the opposite direction, fixes only these same three configurations, so ψ(T₃) = 3 also. For a configuration to be fixed by the 180-degree rotation T₂, the candles opposite each other must be the same color, but the two pairs of opposite candles need not match; there are 3² = 9 such configurations, so ψ(T₃) = 9. Burnside’s Lemma tells us, therefore, that the number of orbits—the number of distinguishable ways to decorate the birthday cake—is the average of these four values of ψ(g):

The reader may enjoy the not-too-difficult exercise of listing these 24 inequivalent configurations.

[47] 2.4. Example: necklace problem. The diagrams in Figure 3 could represent beads in a necklace as well as candles on a birthday cake. The group of equivalences is different in the necklace problem, however, because a necklace may be flipped over as well as rotated; configurations (c) and (d) in Figure 3 are equivalent in the necklace problem but not in the birthday-cake problem. The group is now the dihedral group D₄, which consists of eight transformations of the four-sided figure. Four of these are the rotations T₀, T₁, T₂, T₃ as before. The other four are reflections, which we may designate I (= T₀I), T₁I, T₂I, T₃I. The notation here pursues the analogy with familiar transformations of musical pitch-class space; I is understood to be a flip about the vertical axis in the diagram, and T_jI is the result of following the reflection I by the rotation T_j.

[48] To apply Burnside’s Lemma to the necklace problem, we must calculate the number of configurations fixed by each transformation in the group D4. For this purpose the graphic depictions of the actions of the transformations in Figure 4 may prove helpful, along with the tabulation in Table 2. Here the transformations are represented as permutations of the numbers 0, 1, 2, and 3. Figure 4 shows, for example, that T1 effects a 90-degree clockwise rotation of the initial configuration, mapping 0 to position 1, 1 to 2, 2 to 3, and 3 to 0; this action is represented in Table 2 by the chain of arrows 0→1→2→3→0. The reflection I leaves 0 and 2 unchanged (0→0, 2→2) while interchanging 1 and 3 (1→3→1). The reflection T1I behaves somewhat differently, exchanging the numbers in two pairs (0→1→0, 2→3→2).

Figure 4. The transformations in the dihedral group D4 (click to enlarge)

Table 2. Cycle structure of the permutations in the dihedral group D₄ (3-color necklace problem)

(click to enlarge)

[49] The calculations of ψ(g) for the various transformations g depend heavily on how the permutations break down into cycles. The three transformations just considered, in fact, have three different cycle structures. The rotation T₁ permutes the four numbers in a single cycle, described by the action 0→1→2→3→0 or the more compact cycle representation (0 1 2 3). (The closing parenthesis indicates the completion of the cycle—that is, the implied mapping of the last number listed to the first, in this case 3→0.) This is a cycle of four elements, or a 4-cycle. The reflection I, in contrast, breaks down into two 1-cycles and a 2-cycle, (0)(1 3)(2), while T₁I breaks down into two 2-cycles, (0 1)(2 3). (The order in which the cycles are listed in a permutation is of no consequence, and cyclic reorderings of the numbers within any one cycle are also possible; thus T₁I could equally well be represented in the form (3 2)(0 1), for example. We follow the convention of listing smaller numbers first whenever there is a choice.)

[50] A transformation always maps any element to the next element within its cycle. In order for a necklace configuration to be fixed by a transformation, therefore, all the elements within any one cycle must be the same color, but the colors for elements in different cycles may be chosen independently. So the number of configurations fixed by any transformation (still under the assumption that there are three available colors) is 3^k, where k is the number of distinct cycles in the cycle representation. These numbers are tabulated in Table 2. The numbers in the “Fixed configurations” column can then be plugged into the formula of Burnside’s Lemma to calculate that the number of orbits in the necklace problem—the number of distinguishable four-bead necklaces that can be constructed using beads of three colors—is

This number is, as we should expect, smaller than the corresponding result in the birthday-cake problem, which was 24: more transformations are allowable for necklaces, so more configurations are equivalent and the number of orbits is reduced. Recall that configurations (c) and (d) in Figure 3 belong to two different orbits in the birthday-cake problem but are subsumed in a single orbit when reflections are allowed in the necklace problem. The reduction from 24 orbits to 21 is a small one; in fact, the orbits of configurations (c) and (d), and two other similar orbit pairs involving two blue or two green beads, are the only orbits to be conflated in this way.

[51] 2.5. Cycle structure of permutations. The final two columns in Table 2 supply some additional information that will prove useful later in the general application of Pólya’s theorem. The cycle type is a shorthand accounting of the number of cycles of each length: 4¹ in the case of T₁ indicates a single 4-cycle, while 1²2¹ in the case of I indicates two 1-cycles and one 2-cycle. The cycle type is converted in a straightforward way to the cycle index, an algebraic expression in which abstract variables t₁, t₂, t₄ stand in for the corresponding cycle lengths. More precisely, the cycle index p_g of a permutation g of N objects is an expression potentially involving the N variables t₁, t₂, ..., t_N, namely

where λ_j(g) is the number of j-cycles in the cycle representation of g. The cycle index P_G of a permutation group G is a more complex polynomial in N variables, defined as the average of the cycle indices of all the permutations in G:

The variables t_j do not stand for anything in particular at this point, but later will be replaced by something more concrete.

[52] 2.6. Example: Tn/TnI set classes. The set-class problem in music theory is essentially the necklace problem with two modifications: more objects and fewer colors. The objects are the twelve pitch classes. A pc-set may be specified by coloring the pitch classes with two colors, called yes and no. That is, a pc either belongs to a given pc-set or it does not; the 212 colorings of the pitch classes uniquely determine each of the 212 pc-sets. The group of equivalences is the dihedral group D12 of order 24, consisting of twelve rotations (transpositions) and twelve reflections (inversions) of mod-12 pitch-class space. Table 3 displays the cycle structures of all 24 of these transformations. The cycle representations here reflect properties of the transformations that music theorists will recognize. The twelve transpositions display six different cycle types, while the twelve inversions are of only two types: even-numbered inversions that fix two pitch classes, and odd-numbered inversions that fix none. Adding up the numbers of configurations fixed by these transformations and dividing by 24, as specified by Burnside’s Lemma, yields 224, the total number of set classes appearing in the lower-right corner of Table 1.

Table 3. Cycle structure of the permutations in the dihedral group D12 (set-class problem) (click to enlarge)

[53] 2.7. Weighted colors. The complete solution of the set-class problem entails more than this single number: we must still show how to derive the numbers of set classes of the various cardinalities from 0 through 12. To this end, let us step back momentarily to a higher level of abstraction, a general setting involving configurations of N objects colored with k colors. We assign an algebraic symbol to each color; these symbols will be called the weights of the colors. In the birthday-cake or necklace problem, for example, we could assign the weights r, b, and g to the colors red, blue, and green. In the set-class problem we could assign weight x to the color no and weight y to the color yes. In the general setting in which there are k colors from which to choose, we shall write w₁, w₂, ..., w_k for the weights assigned to the colors.

[54] Define the weight of a configuration to be the product of the weights of the colors of its objects. The weight of a configuration thus describes the multiplicities of its colors. All four configurations shown in Figure 3, for example, are of weight r²bg. In the set-class problem the weight of any tetrachord is x⁸y⁴ (eight pitch classes colored no, four yes). The weight of a configuration is a property of the configuration itself, and does not depend on the group of equivalences. When a group is at hand, however, permuting the objects does not change the weight of a configuration, so equivalent configurations (in the same orbit) will always have the same weight. The converse is not true: configurations of the same weight need not be in the same orbit, as Figure 3 illustrates. Because configurations in the same orbit have the same weight, it makes sense to speak of the weight of an orbit—that is, the common weight of all the configurations in the orbit. The problem is now to calculate the number of different orbits of any given weight.

[55] To do this, as was suggested in Part I, we shall exhibit an enumeration function. An enumeration function for the birthday-cake or necklace problem will be a polynomial in the variables r, b, and g, homogeneous of degree 4 (the number of colored objects in any configuration), in which the coefficient of r²bg or any other such term is the number of distinct orbits of that weight. An enumeration function for the set-class problem will be a polynomial in the variables x and y, homogeneous of degree 12 (the total number of “colored” pitch classes), in which the coefficient of x⁸y⁴ is the number of orbits of tetrachords (and similarly for the other terms). The reader may recall from Part I that the binomial theorem provided a formula of exactly this sort, but the numbers appearing there enumerated actual sets rather than set classes. (In fact, that formula may be considered a special case of the general orbit-counting formula we are now seeking—namely, the special case in which the group G consists of the identity permutation only, so that every pc-set defines its own orbit.)

[56] 2.8. Pólya’s Enumeration Theorem. The enumeration function we are seeking is given explicitly by Pólya’s Enumeration Theorem:⁽¹²⁾

Suppose a transformation group G acts on configurations of N objects colored with k colors. Let the weights assigned to the colors be w₁, w₂, ..., w_k, and define

Let P_G be the cycle index of the group G. Then the sum of the weights of all the orbits, counting each orbit once, is P_G(α₁, α₂, ..., α_N).

[57] The cycle index of the group G, it will be recalled, is a polynomial in N variables, P_G(t₁, t₂, ..., t_N), calculated by averaging together the cycle indices of the various permutations in the group. Pólya’s theorem instructs us to substitute α₁, α₂, ..., α_N for the variables t₁, t₂, ..., t_N in this expression. Because α₁, α₂, ..., α_N are defined as sums of powers of the weights w₁, w₂, ..., w_k, the resulting expression P_G(α₁, α₂, ..., α_N) is ultimately a polynomial in w₁, w₂, ..., w_k; it is known as the Pólya polynomial. The theorem says that the Pólya polynomial is the enumeration function: by calculating this polynomial in full, we will see the number of orbits of each weight as the coefficient of the appropriate term.

[58] 2.9. Example: birthday-cake problem, revisited. Let us consider in detail how Pólya’s theorem applies to the birthday-cake problem described previously, with N = 4 and k = 3. The group G is a cyclic group C₄, consisting only of the rotations T₀, T₁, T₂, T₃, whose cycle indices were presented in the top half of Table 2. These formulas involve the variables t₁, t₂, and t₄ (t₃ happens not to appear), for which we must now substitute α₁, α₂, and α₄, defined as α₁ = r + b + g, α₂ = r² + b² + g², and α₄ = r⁴ + b⁴ + g⁴. We consider each of the rotations T_j in turn.

[59] The cycle index of T₀, as given in Table 2, is

The contribution of T₀ to the Pólya polynomial is therefore

This expression appears rather unwieldy; there are, however, well-known formulas (analogous to the binomial theorem) for raising an expression such as r + b + g to any given power. Computationally, the most cumbersome part of the calculation of a Pólya polynomial is usually the step involving the identity element of the group (T₀ in this case). This odd state of affairs arises because the point of the calculation is to enumerate the configurations fixed by each transformation, and the identity fixes everything—more than any other transformation. The above polynomial in fact enumerates the weights of all 81 configurations in the birthday-cake problem, all of which, of course, are fixed by T₀.

[60] The calculations involving T₁ and T₃ are much simpler. Both have cycle index t₄¹, so the Pólya polynomial has two terms of the form

The only configurations fixed by T₁ and T₃ are the three single-color configurations, and the above expression is simply the sum of their weights.

[61] Finally, T₂ is a permutation of cycle index t₂², so it contributes the term

This polynomial represents the sum of the weights of the nine configurations fixed by T₂.

[62] The complete Pólya polynomial for the birthday-cake problem is therefore

which reduces to

The coefficients in this formula (including several suppressed 1’s) give the number of orbits of each weight. For instance, the term 3r²bg tells us that there are exactly three inequivalent configurations of weight r²bg. These are represented by configurations (a), (c), and (d) of Figure 3. (Configuration (b), it will be recalled, is equivalent to (a) and is therefore not counted separately.) Readers should be able to convince themselves that there are no others: any arrangement of two red candles, one blue, and one green can be rotated to look like (a), (c), or (d).

[63] Two further remarks about the above formula are in order. First, the Pólya polynomial is homogeneous of degree 4: every term involves a product of exactly four factors r, b, and g in some combination. In general, a Pólya polynomial is homogeneous of degree N, the number of objects in each configuration. (Indeed, the polynomial must be homogeneous of degree N if it is to enumerate the weights properly.) Second, the coefficients in the above formula sum to 24, which we calculated in section 2.3 to be the total number of orbits in the birthday-cake problem. The previous calculation was based on Burnside’s Lemma and did not involve weights; the weighted method given by Pólya’s theorem is simply a refinement of the same idea, showing exactly how the 24 orbits are distributed among the various weights.

[64] 2.10. Example: necklace problem, revisited. The application of Pólya’s theorem to the necklace problem begins like that for the birthday-cake problem, but requires additional terms for the transformations I, T₁I, T₂I, and T₃I in the dihedral group D₄. As Table 2 shows, two of these are permutations of cycle index t₂², so there are two more terms of the form α₂², identical to the term for T₂ displayed above. The other two are of cycle index t₁²t₂¹, and give rise to two terms of the form

When these four new terms are added to the four calculated previously and the result is divided by 8 (not 4) and simplified, the resulting formula is

which is identical to the formula for the birthday-cake problem except that the terms involving r²bg, rb²g, and rbg² now carry the coefficient 2 instead of 3, indicating (as observed previously in conjunction with Figure 3) that there are only two distinct necklace configurations of each of these weights rather than three.

[65] 2.11. Example: T_n/T_nI set classes, revisited. We are finally in a position to realize our original objective: that is, to verify the set-class counts from Table 1. Here N = 12 and k = 2. The Pólya polynomial for enumerating the set classes involves the quantities α₁ = x + y, α₂ = x² + y², ..., α₁₂ = x¹² + y¹². There are 24 terms to be added, corresponding to the cycle structures of the transformations T_n and T_nI, as enumerated in Table 3 above. The calculation is rather lengthy, but is simplified somewhat by the numerous repetitions among these cycle types. The Pólya polynomial is

which reduces to

The coefficients exactly match the numbers of set classes in Table 1.

[66] 2.12. Example: T_n set classes. Having developed the general technique of set-class enumeration, we may now readily apply it in a variety of alternative situations. We may, for instance, choose to consider only transpositional equivalence, so that inversionally related sets such as major and minor triads are no longer considered to belong to the same set class. This is the system called SG1 in Morris 2001; it is analogous, in the world of twelve pcs and two colors, to stepping back from the necklace problem to the birthday-cake problem. The group of equivalences in this situation is the cyclic group C₁₂ rather than the dihedral group D₁₂; we need only consider the terms associated with the transpositions T_n (the top half of Table 3) in the above calculation. The resulting Pólya polynomial is

which reduces to

As usual, the number of inequivalent pc-sets of each cardinality may be read directly from the coefficients in this formula. Comparison with the previous formula developed under the assumption of T_n/T_nI equivalence shows that the number of set classes increases when inversional equivalence is disregarded. This is as we should expect, of course; each asymmetrical set class of the T_n/T_nI variety splits into two set classes of the T_n variety. There are now 43 tetrachords rather than 29, because 14 asymmetrical tetrachord types have split. The total number of T_n set classes of all cardinalities, obtained by summing all the coefficients, is 352, compared with 224 in the T_n/T_nI situation.

[67] 2.13. Example: T_n/I/M set classes. If we create more ways for pc-sets to be equivalent, then the number of set classes will decrease. One way to do this is to adjoin the operator M (multiplication by 5 mod 12) to the group of equivalences, as in Morris (1987, 1991, 2001; the T_n/I/M system is called SG3 in Morris 2001). The group is now of order 48, and includes transformations of the forms T_nM and T_nMI in addition to the previous T_n and T_nI. The reader may verify that the transformation M is of cycle type 1⁴2⁴ and therefore of cycle index t₁⁴t₂⁴; the various transformations T_nM and T_nMI are of several different types, including t₂⁶, t₄³, t₆², t₁⁴t₂⁴, t₁⁶t₂³, and t₃²t₆¹. The Pólya polynomial reduces to

which represents a considerable reduction in set-class counts in comparison with the previous two examples, reflecting the broader understanding of equivalence that arises when M is included. Note in particular that the number of “interval classes” (set classes of two-element pc-sets) has dropped from six to five; this is because the usual ic1 and ic5 are related to each other by M (while the other interval classes are preserved under M). The total number of T_n/I/M set classes is only 158.

[68] 2.14. Example: T_n/T_nI set classes in a 19-note scale. Scales with 19 notes to the octave have received attention for their considerable acoustic and structural similarities with the familiar twelve-note system (Mandelbaum 1961). If N = 19 rather than 12, there are 38 pc-set operations of the forms T_n and T_nI. Although the transformation group is larger than in the twelve-note case, the fact that 19 is a prime number simplifies the cycle structure of the transformations considerably. In fact, there are only three different cycle types: the identity (T₀) is of cycle index t₁¹⁹; the transpositions T₁, ..., T₁₈ are all of type t₁₉¹ (each permuting the nineteen pcs in one large cycle); and the inversions I, T₁I, ..., T₁₈I are all of type t₁¹t₂⁹ (each fixing one pc while exchanging the others in pairs). The Pólya polynomial is therefore simply

which, when expanded, becomes

The numbers have increased greatly relative to the twelve-note situation. There are 120 tetrachords, almost 2500 nine-note set classes, and 14,310 set classes altogether.

[69] 2.15. Example: diatonic set classes. Moving in the direction of smaller rather than larger scale systems, let us consider the diatonic scale, for which N = 7. In the mod-7 system, the identity (T₀) is of cycle index t₁⁷; the transpositions T₁, ..., T₆ are all of type t₇¹; and the inversions I, T₁I, ..., T₆I are all of type t₁¹t₂³. The Pólya polynomial is therefore

which reduces to

If inversion is not considered, the calculation is even simpler:

In the diatonic world there are only 18 set classes if inversion is considered, and only two additional ones if it is not. These diatonic set classes are listed in Clough 1979.

[70] 2.16. Some general formulas. We have thus far skirted the question of whether it is actually possible to write down a single formula for the number of k-note set classes (either T_n classes or T_n/T_nI classes) in an N-note scale system. In fact, there is such a formula, but it is not simple.⁽¹³⁾ To derive it one first needs a general formula for the cycle index of the cyclic group C_N or the dihedral group D_N, as appropriate. Such formulas can be found in the combinatorial literature (e.g., Riordan 1958, 149–50) and will be given here without proof.

[71] The cycle index formulas involve Euler’s φ function: for any positive integer n, φ(n) is defined to be the number of positive integers m ≤ n that are coprime to n (that is, for which the greatest common divisor of m and n is 1).⁽¹⁴⁾ Specifically, the cycle index of C_N is

where the sum is taken over all positive divisors j of N. The cycle index of D_N is

where Φ_N is the cycle index of the cyclic group from the previous formula.

[72] We must then exhibit a formula for the coefficient of x^N–ky^k when α_j = x^j + y^j is substituted for t_j in each of these equations, as Pólya’s theorem specifies. In the cyclic case, the coefficient of x^N–ky^k—the number of T_n classes of k-note sets in an N-note scale—is given by

where the sum is taken over all common divisors j of N and k. The quantity in the large parentheses on the right is a binomial coefficient, the number of combinations of N/j things taken k/j at a time. The corresponding coefficient in the dihedral case—the number of T_n/T_nI classes—is

Again, the quantities in the large parentheses are binomial coefficients; denotes the largest integer less than or equal to x.

[73] Ambitious readers may use the above formulas to verify some of the results discussed previously. For example, in the usual 12-note system there are 43 T_n classes of tetrachords (ζ₁₂(4) = 43) and 29 T_n/T_nI classes of tetrachords (ξ₁₂(4) = 29), while in the 19-note system the number of T_n/T_nI classes of tetrachords is 120 (ξ₁₉(4) = 120). It will be noted that the sums appearing in the formulas for Φ_N and ζ_N(k) involve many terms when the number N has many divisors but are much simpler if N is a prime number; this is consistent with the relative complexity of our previous calculations in the 12- and 19-note cases.

[74] The above formulas have been used to produce Tables 4 and 5, which enumerate the T_n and T_n/T_nI classes, respectively, of k-note sets in an N-note scale for all values of N from 7 to 24. To save space, values are shown only for k ≤ 12; this is sufficient because the number of k-note set classes is the same as the number of (N – k)-note set classes. (In a 19-note scale, for instance, the number of 15-note set classes does not appear in the table, but it is the same as the number of 4-note set classes, which does appear.) The final column gives the total number of set classes of all cardinalities for each value of N.

Table 4. Values of ζN(k), the number of Tn classes of k-note chords in an N-note scale   (click to enlarge)

Table 5. Values of ξN(k), the number of Tn/TnI classes of k-note chords in an N-note scale (click to enlarge)

[75] These tables illustrate in dramatic fashion how set classes proliferate as N increases. In the quarter-tone system (N = 24), there are more than 350,000 T_n/T_nI classes and almost 700,000 T_n classes. The latter number is almost twice the former; indeed, as N increases, the ratio of T_n classes to T_n/T_nI classes approaches 2, because symmetrical sets become statistically scarcer. Without venturing too far into the somewhat contentious question of the “privileged” nature of the mod-12 system, we may at least note that the usual 224 T_n/T_nI classes, in comparison with the counts in other lines of the tables, are sufficient to provide a rich variety of set types while remaining a manageable number from the perspective of classification and aural recognition.⁽¹⁵⁾

[76] 2.17. Example: beat-class sets. Similarities between pitch and rhythmic structures have been widely noted. For example, Cohn 1992 and Roeder 2003 employ beat-class sets, the rhythmic counterpart of pitch-class sets, to study Steve Reich’s phase techniques. Indeed, calculations involving the distribution of k attacks in a measure of N beats are completely analogous to calculations involving k-note subsets of an N-note system. Rhythmic rotations play the role of transpositions, and retrogrades the role of inversions. If rotations (but not retrogrades) of a rhythm are considered equivalent, the number of ways to place four notes and eight rests (or vice versa) in a twelve-beat measure is ζ12(4) = ζ12(8) = 43 as calculated above. If retrogrades are also considered equivalent, the number drops to ξ12(4) = ξ12(8) = 29. Reich’s Clapping Music in fact consists of rotations of a twelve-beat rhythm with eight attacks. Haack 1991 applies combinatorial techniques to this piece, considering some of the properties of the particular rhythm chosen by Reich and exploring how many other rhythms might have been equally suitable.

[77] 2.18. Example: twelve-tone rows, revisited. In section 1.3 we observed that the total number of twelve-tone rows is 12!, and that the number of row classes in classical serial theory is approximately, but not exactly, 1/48 of that number. We now consider ways to make the latter calculation precise.⁽¹⁶⁾ The group of equivalences is of order 48, consisting of all transposition, inversion, and retrograde operations. It is possible to calculate how many of the 12! rows are fixed by each of these 48 transformations, and thereby to calculate the number of orbits using Burnside’s Lemma. The process can be simplified considerably, however, because the twelve transpositions of a row are always distinct: no rows are fixed by T_j for j ≠ 0. Because of this observation, transposition can be effectively eliminated from the calculation. Instead of considering the 12! rows acted upon by a group of order 48, we consider only the 11! T_n classes of rows acted upon by a group of order 4 consisting of T₀ (the identity), I, R, and RI (= IR). Each T_n class consists of exactly twelve rows, and may be represented by a single row that starts with 0. The number of orbits of the T_n classes in this simplified setting is the same as the number of orbits of rows in the original situation.

[78] To apply Burnside’s Lemma we must determine how many T_n classes are fixed by each of the four transformations in the group. Clearly T₀ fixes all 11! T_n classes, and I fixes none (an inverted form of a row can never be a transposition of the original row). For a T_n class represented by a row (0, a₁, a₂, ..., a₁₁) to be fixed by R, the retrograde (a₁₁, a₁₀, ..., a₁, 0) must be some transposition T_j of the row. That is, for some j, the twelve equations

0 + j = a₁₁, a₁ + j = a₁₀, ..., a₁₁ + j = 0

all hold (mod 12). The first equation says that j = a₁₁; then the last equation implies that j = a₁₁ = 6. (It cannot be 0, since 0 is the first note of the row and a₁₁ is the last.) Retrograde symmetry, therefore, is possible only at the tritone transposition T₆. The second note a₁ may be chosen freely from the remaining ten pcs (besides 0 and a₁₁ = 6), but then a₁₀ = a₁ + 6 is determined. Continuing in this way, there are eight choices for the third note, six for the fourth, four for the fifth, and two for the sixth, and the second half of the row is determined by these choices. The number of T_n classes fixed by R, therefore, is 10 · 8 · 6 · 4 · 2 = 3840. These classes represent only a tiny fraction of the 11! possible T_n classes, but the rows of Berg’s Lyric Suite and Webern’s Symphony, Op. 21 are of this type.

[79] Finally, if a T_n class represented by (0, a₁, ..., a₁₁) is fixed by RI, the equations become

0 + a₁₁ = j, a₁ + a₁₀ = j, ..., a₅ + a₆ = j

for some j. Even values of j are impossible: indeed, if j = 2i, then the pitch class i can have no partner with which to sum to j, as the equations require. For any of the six odd values of j, however, the situation is similar to that in the previous paragraph: a₁₁ is determined; a₁ can then be chosen from ten options, thereby determining a₁₀; and so on. The number of T_n classes fixed by RI is therefore 6 · 10 · 8 · 6 · 4 · 2 = 23,040. These classes are theoretically six times as numerous as the R-invariant classes but still rare among all T_n classes; the rows of Webern’s String Quartet, Op. 28, Cantata, Op. 29, and Variations, Op. 30 are all of this type.⁽¹⁷⁾

[80] By Burnside’s Lemma, then, the total number of row classes is

It is not difficult to show, using methods similar to the above, that the number of row classes in an N-note scale is

[81] 2.19. Further examples and conclusions. Fripertinger (1993, 5) shows that if N is even, the number of self-complementary N/2-note set classes may be calculated as P_G(0, 2, 0, 2, ...)—that is, by alternately substituting 0 and 2 for the variables t_j in the cycle index of the group of equivalences (which as usual may be either C_N or D_N). One can use this formula together with the cycle index formulas given previously to verify that for N = 12 the number of self-complementary hexachords is 8 if the group of equivalences is C_N (that is, eight T_n types of hexachords are related to their complements by some T_n), or 20 if the group is D_N (twenty T_n/T_nI types of hexachords are related to their complements by some T_n and/or T_nI).

[82] Fripertinger 1993 and Read 1997 give many additional examples of advanced calculations. Among the phenomena for which Fripertinger devises methods of enumeration are k-note row classes mod N (pp. 11–12); all-interval rows (pp. 13–17); “motifs” involving both pitch and rhythm (pp. 18–20); and Hauer’s tropes (pp. 20–21). Read (1997, 547) enumerates row classes if the group of equivalences is expanded to include rotations. (For N = 12 in this situation, the group is of order 48 · 12 = 576, and the number of row classes is 836,017. As we should expect, this number is slightly more than 1/12 of the number calculated in the previous section: the size of the group has increased by a factor of exactly 12, but the number of row classes is not precisely divided by 12 because a small number of the original row classes are fixed by some nonzero rotation.)

[83] In what may be the most Herculean feat of music-theoretic enumeration on record, Read (1997, 548–51) takes on Stockhausen’s Klavierstück XI, in which the performer is asked to make successive random choices among 19 fragments of music subject to certain constraints. Through several pages of work with enumeration functions, Read calculates the number of different possible performances of the piece to be no less than

17,423,935,148,332,958,167,310,127,282,862,901,334,594.

Perhaps of more practical interest than this vast number are Read’s observations about the lengths of the possible performances. The rules imply that the longest possible performance consists of 39 fragments; it turns out that most of the possible performances are close to this maximum length, and in fact the average length of all the possible performances is just over 38 fragments. (This situation recalls a much simpler observation from section 1.2, where we noted that of the melodies with no more than six notes, the great majority have exactly six notes. As was the case there, an enumeration of configurations of variable size is dominated by the configurations of the largest possible size.)

[84] The extravagance of such a calculation recalls the work of Riepel and Galeazzi, who saw immense numbers of possibilities as potential stimuli for musical creativity. Whether one subscribes to this view or not, the recent resurgence in applications of combinatorics to music theory at least aids our understanding of music in several ways. Combinatorial methods offer ways to understand simple and not-so-simple numerical patterns that arise naturally in the discipline, and provide answers to a wide variety of enumeration questions. Familiar concepts are seen in new light, as for instance when a tedious brute-force listing is superseded by an elegant (if esoteric) enumeration procedure, or when early attempts at pc-set classification are reconsidered in the context of groups of equivalences and the corresponding enumeration problems. The methodology employed in these calculations ranges from elementary observations to recent techniques of considerable sophistication, but all of it reaffirms and strengthens the long-standing bond between music and mathematics.

Return to beginning of article

---

Julian Hook
Jacobs School of Music
Indiana University
Bloomington, IN 47405
juhook@indiana.edu 

Return to beginning of article

---

Bibliography

Benson, David J. 2007. Music: A Mathematical Offering. Cambridge, UK: Cambridge University Press.

Bernard, Jonathan W. 1997. “Chord, Collection, and Set in Twentieth-Century Theory.” In Music Theory in Concept and Practice, ed. James M. Baker, David W. Beach, and Jonathan W. Bernard (Rochester: University of Rochester Press), 11–51.

Christensen, Thomas. 1993. Rameau and Musical Thought in the Enlightenment. Cambridge, UK: Cambridge University Press.

Cohen, Daniel I. A. 1978. Basic Techniques of Combinatorial Theory. New York: John Wiley & Sons.

Cohn, Richard. 1992. “Transpositional Combination of Beat-Class Sets in Steve Reich’s Phase-Shifting Music.” Perspectives of New Music 30/2: 146–77.

Clough, John. 1979. “Aspects of Diatonic Sets.” Journal of Music Theory 23: 45–61.

Cooke, Roger. 2005. The History of Mathematics: A Brief Course, 2nd ed. Hoboken, NJ: John Wiley & Sons.

Cope, David. 2001. Virtual Music: Computer Synthesis of Musical Style. Cambridge, MA: MIT Press.

Dummit, David S. and Richard M. Foote. 2004. Abstract Algebra, 3rd ed. Hoboken, NJ: John Wiley & Sons.

Forte, Allen. 1973. The Structure of Atonal Music. New Haven: Yale University Press.

Fripertinger, Harald. 1992, 1993. “Enumeration in Musical Theory.” Beiträge zur elektronischen Musik 1 (1992). Available online at http://www.uni-graz.at/~fripert/publications.html (1993 version of paper; accessed 2 October 2007).

__________. 1999. “Enumeration and Construction in Music Theory.” In Diderot Forum on Mathematics and Music: Computational and Mathematical Methods in Music, ed. H. G. Feichtinger and M. Dörfler (Vienna: Österreichische Computergesellschaft), 179–204. Available online at http://www.uni-graz.at/~fripert/publications.html (accessed 2 October 2007).

Haack, Joel K. 1991. “Clapping Music—A Combinatorial Problem.” College Mathematics Journal 22: 224–27.

Hardy, G. H. and E. M. Wright. 1979. An Introduction to the Theory of Numbers, 5th ed. Oxford: Oxford University Press.

Helm, E. Eugene. 1966. “Six Random Measures of C. P. E. Bach.” Journal of Music Theory 10: 139–51.

Hunter, David J. and Paul T. von Hippel. 2003. “How Rare is Symmetry in Musical 12-Tone Rows?” American Mathematical Monthly 110: 124–32.

Jedrzejewski, Franck. 2006. Mathematical Theory of Music. Paris: Editions Delatour France.

Knobloch, Eberhard. 2002. “The Sounding Algebra: Relations Between Combinatorics and Music from Mersenne to Euler.” In Mathematics and Music: A Diderot Mathematical Forum, ed. Gerard Assayag, Hans Georg Feichtinger, and José Francisco Rodrigues (Berlin: Springer), 27–48.

Kupper, Hubert. 1994–95. “Der allezeit fertige Polonaisen- und Menuettencomponist von Johann Philipp Kirnberger.” Available online at http://www.musikwissenschaft.uni-mainz.de/Musikinformatik/schriftenreihe/nr15/Kirnframe.html (accessed 2 October 2007).

Lester, Joel. 1992. Compositional Theory in the Eighteenth Century. Cambridge, MA: Harvard University Press.

Lewin, David. 1987. Generalized Musical Intervals and Transformations. New Haven: Yale University Press.

Mandelbaum, M. Joel. 1961. “Multiple Division of the Octave and the Tonal Resources of 19-Tone Temperament.” Ph.D. dissertation, Indiana University.

Morris, Robert D. 1987. Composition with Pitch-Classes: A Theory of Compositional Design. New Haven: Yale University Press.

__________. 1991. Class Notes for Atonal Music Theory. Lebanon, NH: Frog Peak Music.

__________. 2001. Class Notes for Advanced Atonal Music Theory. Lebanon, NH: Frog Peak Music.

Nolan, Catherine. 2003. “Combinatorial Space in Nineteenth- and Early Twentieth-Century Music Theory.” Music Theory Spectrum 25: 205–41.

Pólya, George. 1937. “Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen.” Acta Mathematica 68: 145–254.

__________. 2004 [1945]. How to Solve It: A New Aspect of Mathematical Method. Princeton, NJ: Princeton University Press.

Pólya, George, Robert E. Tarjan, and Donald R. Woods. 1983. Notes on Introductory Combinatorics. Boston: Birkhäuser.

Rahn, John. 1980. Basic Atonal Theory. New York: Longman.

Ratner, Leonard. 1970. “Ars combinatoria: Chance and Choice in Eighteenth-Century Music.” In Studies in Eighteenth-Century Music, ed. H. C. Robbins Landon and Roger E. Chapman (New York: Oxford University Press), 343–63.

__________. 1980. Classic Music: Expression, Form, and Style. New York: Macmillan.

Read, R. C. 1997. “Combinatorial Problems in the Theory of Music.” Discrete Mathematics 167–168: 543–51.

Reiner, David L. 1985. “Enumeration in Music Theory.” American Mathematical Monthly 92: 51–54.

Riordan, John. 1958. An Introduction to Combinatorial Analysis. New York: John Wiley & Sons.

Roeder, John. 2003. “Beat-Class Modulation in Steve Reich’s Music.” Music Theory Spectrum 25: 275–304.

Straus, Joseph N. 2005. Introduction to Post-Tonal Theory, 3rd ed. Upper Saddle River, NJ: Pearson Prentice Hall.

Struik, Dirk J. 1967. A Concise History of Mathematics, 3rd ed. New York: Dover.

Return to beginning of article

---

References

1. Some of the material in this article was presented at a Special Session on Mathematical Techniques in Musical Analysis at the Joint Mathematics Meetings in Phoenix in 2004.
Return to text

2. The fundamentals of combinatorics are summarized in many texts in “discrete mathematics” as well as more specialized texts in combinatorics. Cohen 1978 is both thorough and reader-friendly.
Return to text

3. There are numerous published histories of mathematics. Struik 1967 is compact and widely available; much of the information given here is from the more comprehensive Cooke 2005, especially pp. 210–19.
Return to text

4. A little reflection shows that 1 is the only mathematically reasonable way for 8⁰ (or n⁰) to be defined. Just as the “sum of zero terms” is 0 (the additive identity), the “product of zero factors” must be 1 (the multiplicative identity). This definition together with the definition n^–k = 1/n^k for negative exponents ensures that a sequence of numbers such as ... 8^–2 = 1/64, 8^–1 = 1/8, 8⁰ = 1, 8¹ = 8, 8² = 64, ... is a “geometric sequence” whose successive terms are always related by factors of 8. For similar reasons, 0! (0 factorial) is defined to be 1 also.
Return to text

5. For mathematical approaches to music in the eighteenth century as a reflection of the temper of their time, see Christensen 1993, 103–06. For more examples of specifically combinatorial approaches, see Ratner 1970; Ratner 1980, 98–102; Lester 1992, 226–29; and Knobloch 2002.
Return to text

6. Quoted in Lester 1992, 226.
Return to text

7. Quoted in Ratner 1970, 348. Galeazzi constructs lengthy melodies in several stages, first choosing a few notes literally at random and eventually superimposing other elements such as rhythm. He calculates the possibilities for melodies available by his method to be an immense number of 24 digits.
Return to text

8. The Musikalische Würfelspiel attributed to Mozart was published in 1793 and reprinted under his name by B. Schott, Mainz, in 1956. Dice games are discussed in more detail in Ratner 1970. Several online implementations of dice games are available. Particularly noteworthy is Kupper 1994–95, which includes facsimiles of Kirnberger’s complete pamphlet along with an extended discussion.
Return to text

9. Uniquely among the eighteenth-century dice games, C. P. E. Bach’s Einfall, einen doppelten Contrapunct in der Octave von sechs Takten zu machen, ohne die Regeln davon zu wissen of 1757 is based not upon a harmonic pattern but upon a two-voice contrapuntal model. Bach’s method, in which the two voices are generated independently, is described in detail in Helm 1966. Helm calculates that the game produces 9¹² = 282,429,536,481 possible compositions, but this calculation overlooks the fact that the nine versions of the lower voice in the last measure are identical; the correct total is 9¹¹ = 31,381,059,609.
Return to text

10. Transformation groups have enjoyed wide exposure in music theory through the work of David Lewin (1987) and his many followers. For basic group theory the reader may consult any abstract algebra text such as Dummit and Foote 2004.
Return to text

11. Burnside’s Lemma is named for William S. Burnside, who published it in 1897, but the result was known to earlier mathematicians, notably Augustin Cauchy as early as the 1840s.
Return to text

12. Hungarian-born mathematician George Pólya (1887–1985) made important contributions to many branches of mathematics. Renowned also as a teacher and writer, Pólya authored the widely-read and often-reprinted book of problem-solving strategies titled How to Solve It (2004 [1945]). Pólya published the enumeration theorem in 1937, motivated by a problem in chemistry: his goal was to enumerate chemical compounds subject to various constraints on molecular structure. Pólya’s own approach to teaching combinatorics is described in Pólya, Tarjan, and Woods 1983.
Return to text

13. These formulas appear in Reiner 1985, 52–53 and Fripertinger 1993, 4. Reiner’s formula for the cycle index of the dihedral group contains a misprint; the formula given here is correct.
Return to text

14. The function φ is well-known in number theory and has many interesting properties and applications; see Hardy and Wright 1979, 54ff. Calculation of φ is simplified by the following multiplicative property: if m and n are coprime, then φ(mn) = φ(m)φ(n). For example, 3 and 8 are coprime; φ(3) = 2 because the two integers 1 and 2 are both coprime to 3; φ(8) = 4 because the four integers 1, 3, 5, and 7 are each coprime to 8; and therefore φ(24) = φ(3 · 8) = φ(3) · φ(8) = 2 · 4 = 8. Indeed, the eight integers ≤ 24 that are coprime to 24 are 1, 5, 7, 11, 13, 17, 19, and 23.
Return to text

15. Mandelbaum (1961, 251) has proposed that “it is conceivable that there was a point around ... Zarlino’s time when music might have evolved as easily toward 19-tone temperament as toward 12-.” It is interesting to speculate about how much more difficult the classification of pc-sets would have been had such a scenario come to pass.
Return to text

16. The number of row classes can be calculated by elementary means in rather painstaking fashion. Whether a row class consists of 24 or 48 rows depends on the symmetry of the two hexachords. It is possible to determine, for each of the 50 hexachord classes, how many row classes of each cardinality arise. The much shorter calculation presented here, using Burnside’s Lemma, is based on Reiner 1985. A rather different algebraic proof appears in Hunter and von Hippel 2003, 129.
Return to text

17. Hunter and von Hippel 2003 offer statistical confirmation that twelve-tone composers choose symmetrical rows far more often than random selection would dictate.
Return to text

Return to beginning of article

---

Copyright Statement

Copyright � 2007 by the Society for Music Theory. All rights reserved.

[1] Copyrights for individual items published in Music Theory Online (MTO) are held by their authors. Items appearing in MTO may be saved and stored in electronic or paper form, and may be shared among individuals for purposes of scholarly research or discussion, but may not be republished in any form, electronic or print, without prior, written permission from the author(s), and advance notification of the editors of MTO.

[2] Any redistributed form of items published in MTO must include the following information in a form appropriate to the medium in which the items are to appear:

This item appeared in Music Theory Online in [VOLUME #, ISSUE #] on [DAY/MONTH/YEAR]. It was authored by [FULL NAME, EMAIL ADDRESS], with whose written permission it is reprinted here.

[3] Libraries may archive issues of MTO in electronic or paper form for public access so long as each issue is stored in its entirety, and no access fee is charged. Exceptions to these requirements must be approved in writing by the editors of MTO, who will act in accordance with the decisions of the Society for Music Theory.

This document and all portions thereof are protected by U.S. and international copyright laws. Material contained herein may be copied and/or distributed for research purposes only.

Return to beginning of article

Prepared by Brent Yorgason, Managing Editor
Updated 27 December 2007

Number of visits since December 2007: