Volume 13, Number 4, December 2007
Copyright © 2007 Society for Music Theory
Why Are There TwentyNine Tetrachords? A Tutorial on Combinatorics and Enumeration in Music Theory^{*}Julian HookKEYWORDS: combinatorics, enumeration, permutations, combinations, Pólya, pitchclass sets, set classes, twelvetone 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, pitchclass 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.

“Can you do addition?” the White Queen asked.
[1] Table 1 gives the number of pitchclass sets and the number of T_{n}/T_{n}I set classes of each cardinality from 0 through 12. The number of different pcsets of cardinality k, appearing in the central row of the table, may be calculated by a wellknown formula (to be reviewed below) for “the number of combinations of 12 things k at a time.” The setclass 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 1987and 1991, and Straus 2005, among various other texts. [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 fourelement subsets of a twelveelement 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 pitchclass 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 setclass 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_{n}I equivalence), and perhaps enumeration problems of entirely different sorts, involving twelvetone rows or rhythms, for example. Listing and counting all the mod12 set classes is feasible but already somewhat unwieldy, as the multipage 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 pitchclass sets) and historical notes (including a brief overview of the ars combinatoria that found its way into eighteenthcentury 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 setclass 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 musictheoretic 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 setclass enumeration problem and other musical situations may be found in Reiner 1985, 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 fiveperson 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.^{(1)} [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.^{(2)} [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 [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^{6} (8 to the 6th power) or 262,144—more than a quartermillion 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 allinclusive 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^{1} + 8^{2} + 8^{3} + 8^{4} + 8^{5} + 8^{6} = 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 onenote melody and a twonote melody and a
threenote 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^{1} · 8^{2} · 8^{3} · 8^{4} · 8^{5} · 8^{6}, is precisely 8^{21}, which is as we should
have suspected, since by making all the above choices in succession we would
effectively have composed a 21note melody.) Rather, the problem called for us
to choose a onenote melody or a twonote melody or a threenote melody
or [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 detailminded 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,^{(3)} so adding 8^{0} 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: twelvetone rows. How many possible twelvetone 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^{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^{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 twelvetone 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^{12}, which is almost 9 trillion. (As n increases, n! grows very rapidly—but not as rapidly as n^{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 twelvetone row have been selected, the twelfth is automatically determined—there are no more choices to make. In a twelvepc universe, the number of twelvetone rows is the same as the number of eleventone 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 wellknown 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 twelvetone 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 sixnote melody from our oneoctave 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 sixnote 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: pitchclass sets. How many pitchclass sets are there? It may not be immediately obvious that the multiplication principle applies to this question: pcsets are not permutations, and we do not ordinarily think of constructing a pcset 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 pcset may be uniquely specified by considering each of the twelve pitch classes in turn, and answering for each one a yesorno question. Is C in the set? Is Csharp in the set? Is D in the set? When all twelve questions have been answered, the set is determined. The number of pitchclass sets is the number of ways the questions can be answered, namely 2^{12} = 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 twelvetone 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^{n}. [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^{7} = 128. If sixteenthnote multiple durations are allowed, the number rises dramatically to 2^{15} = 32,768. [27] 1.8. Example: pitchclass sets of specified cardinality; combinations. How many fournote pitchclass sets are there? The figure 4,096 calculated in section 1.6 gives the total number of pcsets of all possible cardinalities in mod12 space, but we have not yet shown how to calculate the number of pcsets of any given size. There are P(12, 4) = 11,880 permutations of four pcs, but that is not the number of fournote pcsets: 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 pcsets 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 kelement subsets of a fixed nelement set. Clearly C(n, k) is a smaller number than P(n, k). How much smaller? In the case of fournote 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 kelement sets are in onetoone 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 n^{th} row and the k^{th} 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 n^{th} row is exactly 2^{n}. [31] The combination numbers appear also in the wellknown 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. [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)^{12} is (x + y)^{12} = C(12, 0)x^{12} + C(12, 1)x^{11}y + ^{. . .} + C(12, 11)xy^{11} + C(12, 12)y^{12}, which may be calculated as x^{12} + 12x^{11}y + 66x^{10}y^{2} + 220x^{9}y^{3} + 495x^{8}y^{4} + 792x^{7}y^{5} + 924x^{6}y^{6} 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 pcsets of each cardinality from 0 to 12. The binomial theorem therefore provides a method for calculating the pcset 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)^{12} is an enumeration function for the pcset 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 setclass 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 pitchclass sets. Consider for a moment the numbers
appearing in the k = 2 diagonal of Pascal’s triangle: 1, 3, 6, 10, 15, 21, 28, The number C(n, 2) has a natural musical interpretation as the number of 2note subsets—that is, intervals—within a pcset of cardinality n. This observation explains why the sum of the entries in the intervalclass vector of a pcset is always 3 for a trichord, 6 for a tetrachord, 10 for a pentachord, and so on. [35] 1.11. Ars combinatoria and eighteenthcentury 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 casebycase analysis more or less in the spirit of ars combinatoria.^{(4)} [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 fournote figure and exhibits all 4! = 24 possible permutations. Turning his attention to chord structure, he considers all possible three and fournote diatonic chords over a fixed bass note; this is a problem in combinations rather than permutations, and Riepel recognizes correctly that the possibilities for threenote chords number C(7, 2) = 21 and for fournote 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.”^{(5)} [37] Riepel was a practical musician, and as his disparaging reference to the pitchratio 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 fournote 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 teoricopratici 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:
[38] 1.12. Dice games. Among the bestknown examples of combinatorial activity in eighteenthcentury 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 (“EveryReady 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.^{(7)} [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 thirtytwo 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^{16}, a 17digit 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^{14}, 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 smalltown organist without ready access to large quantities of printed music (Lester 1992, 229; Ratner 1970, 357). [41] Eighteenthcentury dice games have been cited by David Cope as important precedents for his muchpublicized “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 quasicombinatorial 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 eightmeasure 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 fivepart 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.^{(8)} (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:
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^{(9)} 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 pcsets and set classes, the configurations are pcsets 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 subcounts 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 pitchclass operator such as T_{4}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:^{(10)}
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 setclass problem, it is instructive to consider two simpler situations of types commonly encountered in the study of combinatorics, which we shall call the birthdaycake 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: birthdaycake 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^{4} = 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_{4} of order 4. The elements of this group are analogous to transpositions in pitchclass space, so we may designate them by the labels T_{0}, T_{1}, T_{2}, and T_{3}. T_{0} is the identity transformation—the identity element of the group—and of course it fixes all 81 configurations, so ψ(T_{0}) = 81. T_{1} is a 90degree 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 singlecolor candle arrangements (all red candles, all blue, or all green), so ψ(T_{1}) = 3. Likewise T_{3}, the 90degree rotation in the opposite direction, fixes only these same three configurations, so ψ(T_{3}) = 3 also. For a configuration to be fixed by the 180degree rotation T_{2}, the candles opposite each other must be the same color, but the two pairs of opposite candles need not match; there are 3^{2} = 9 such configurations, so ψ(T_{3}) = 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 nottoodifficult 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 birthdaycake problem. The group is now the dihedral group D_{4}, which consists of eight transformations of the foursided figure. Four of these are the rotations T_{0}, T_{1}, T_{2}, T_{3} as before. The other four are reflections, which we may designate I (= T_{0}I), T_{1}I, T_{2}I, T_{3}I. The notation here pursues the analogy with familiar transformations of musical pitchclass space; I is understood to be a flip about the vertical axis in the diagram, and T_{j}I is the result of following the reflection I by the rotation T_{j}. Figure 4. The transformations in the dihedral group
D_{4} (click to enlarge) Table 2. Cycle structure of the permutations in the dihedral group
D_{4} (3color necklace problem) (click to enlarge) [48] To apply Burnside’s Lemma to the necklace problem, we must calculate the number of configurations fixed by each transformation in the group D_{4}. 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 T_{1} effects a 90degree 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 T_{1}I behaves somewhat differently, exchanging the numbers in two pairs (0→1→0, 2→3→2). [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_{1} 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 4cycle. The reflection I, in contrast, breaks down into two 1cycles and a 2cycle, (0)(1 3)(2), while T_{1}I breaks down into two 2cycles, (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_{1}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 fourbead 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 birthdaycake 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 birthdaycake 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^{1} in the case of T_{1} indicates a single
4cycle, while 1^{2}2^{1} in the case of I indicates two 1cycles and one 2cycle. The
cycle type is converted in a straightforward way to the cycle index, an
algebraic expression in which abstract variables t_{1}, t_{2}, t_{4} 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_{1}, t_{2}, where λ_{j}(g) is the number of jcycles 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. Table 3. Cycle structure of the permutations in the dihedral group D_{12} (setclass problem) (click to enlarge) [52] 2.6. Example: T_{n}/T_{n}I set classes. The setclass 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 pcset may be specified by coloring the pitch classes with two colors, called yes and no. That is, a pc either belongs to a given pcset or it does not; the 2^{12} colorings of the pitch classes uniquely determine each of the 2^{12} pcsets. The group of equivalences is the dihedral group D_{12} of order 24, consisting of twelve rotations (transpositions) and twelve reflections (inversions) of mod12 pitchclass 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: evennumbered inversions that fix two pitch classes, and oddnumbered 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 lowerright corner of Table 1. [53] 2.7. Weighted colors. The complete solution of the setclass 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 birthdaycake or necklace problem, for example, we could assign
the weights r, b, and g to the colors red, blue, and green. In the setclass
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_{1}, w_{2}, [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^{2}bg. In the setclass problem the weight of any tetrachord is x^{8}y^{4} (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 birthdaycake 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^{2}bg or any other such term is the number of distinct orbits of that weight. An enumeration function for the setclass 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^{8}y^{4} 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 orbitcounting formula we are now seeking—namely, the special case in which the group G consists of the identity permutation only, so that every pcset 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:^{(11)}
[57] The cycle index of the group G, it will be recalled, is a polynomial in N
variables, P_{G}(t_{1}, t_{2}, [58] 2.9. Example: birthdaycake problem, revisited. Let us consider in detail how Pólya’s theorem applies to the birthdaycake problem described previously, with N = 4 and k = 3. The group G is a cyclic group C_{4}, consisting only of the rotations T_{0}, T_{1}, T_{2}, T_{3}, whose cycle indices were presented in the top half of Table 2. These formulas involve the variables t_{1}, t_{2}, and t_{4} (t_{3} happens not to appear), for which we must now substitute α_{1}, α_{2}, and α_{4}, defined as α_{1} = r + b + g, α_{2} = r^{2} + b^{2} + g^{2}, and α_{4} = r^{4} + b^{4} + g^{4}. We consider each of the rotations T_{j} in turn. [59] The cycle index of T_{0}, as given in Table 2, is The contribution of T_{0} to the Pólya polynomial is therefore This expression appears rather unwieldy; there are, however, wellknown 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_{0} 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 birthdaycake problem, all of which, of course, are fixed by T_{0}. [60] The calculations involving T_{1} and T_{3} are much simpler. Both have cycle index t_{4}^{1}, so the Pólya polynomial has two terms of the form The only configurations fixed by T_{1} and T_{3} are the three singlecolor configurations, and the above expression is simply the sum of their weights. [61] Finally, T_{2} is a permutation of cycle index t_{2}^{2}, so it contributes the term This polynomial represents the sum of the weights of the nine configurations fixed by T_{2}. [62] The complete Pólya polynomial for the birthdaycake 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^{2}bg tells us that there are exactly three inequivalent configurations of weight r^{2}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 birthdaycake 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 birthdaycake problem, but requires additional terms for the transformations I, T_{1}I, T_{2}I, and T_{3}I in the dihedral group D_{4}. As Table 2 shows, two of these are permutations of cycle index t_{2}^{2}, so there are two more terms of the form α_{2}^{2}, identical to the term for T_{2} displayed above. The other two are of cycle index t_{1}^{2}t_{2}^{1}, 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 birthdaycake problem except that the terms involving r^{2}bg, rb^{2}g, and rbg^{2} 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_{n}I set classes, revisited. We are finally in a position to realize our original objective: that is, to verify the setclass counts from Table 1. Here N = 12 and k = 2. The Pólya polynomial for enumerating the set
classes involves the quantities α_{1} = x + y, α_{2} =
x^{2} + y^{2}, 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 setclass 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 birthdaycake problem. The group of equivalences in this situation is the cyclic group C_{12} rather than the dihedral group D_{12}; 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 pcsets 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_{n}I 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_{n}I 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_{n}I situation. [67] 2.13. Example: T_{n}/I/M set classes. If we create more ways for pcsets 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_{n}M and T_{n}MI in addition to the previous T_{n} and T_{n}I. The reader may verify that the transformation M is of cycle type 1^{4}2^{4} and therefore of cycle index t_{1}^{4}t_{2}^{4}; the various transformations T_{n}M and T_{n}MI are of several different types, including t_{2}^{6}, t_{4}^{3}, t_{6}^{2}, t_{1}^{4}t_{2}^{4}, t_{1}^{6}t_{2}^{3}, and t_{3}^{2}t_{6}^{1}. The Pólya polynomial reduces to which represents a considerable reduction in setclass 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 twoelement pcsets) 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_{n}I set classes in a 19note scale. Scales with 19 notes to the octave have received attention for their considerable acoustic and
structural similarities with the familiar twelvenote system (Mandelbaum 1961).
If N = 19 rather than 12, there are 38 pcset operations of the forms T_{n} and
T_{n}I. Although the transformation group is larger than in the twelvenote 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_{0}) is of cycle index t_{1}^{19}; the transpositions T_{1}, which, when expanded, becomes The numbers have increased greatly relative to the twelvenote situation. There are 120 tetrachords, almost 2500 ninenote 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 mod7 system, the identity (T_{0}) is of cycle index t_{1}^{7}; the transpositions
T_{1}, 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 knote set classes (either T_{n} classes or T_{n}/T_{n}I classes) in an Nnote scale system. In fact, there is such a formula, but it is not simple.^{(12)} 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).^{(13)} 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}^{–}^{k}y^{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}^{–}^{k}y^{k}—the number of T_{n} classes of knote sets in an Nnote 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_{n}I 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 12note system there are 43 T_{n} classes of tetrachords (ζ_{12}(4) = 43) and 29 T_{n}/T_{n}I classes of tetrachords (ξ_{12}(4) = 29), while in the 19note system the number of T_{n}/T_{n}I classes of tetrachords is 120 (ξ_{19}(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 19note cases. Table 4. Values of ζ_{N}(k), the number of T_{n} classes of
knote chords in an
Nnote scale (click to enlarge) Table 5. Values of ξ_{N}(k), the number of T_{n}/T_{n}I classes of
knote chords in an Nnote scale (click to enlarge) [74] The above formulas have been used to produce Tables 4 and 5, which enumerate the T_{n} and T_{n}/T_{n}I classes, respectively, of knote sets in an Nnote 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 knote set classes is the same as the number of (N – k)note set classes. (In a 19note scale, for instance, the number of 15note set classes does not appear in the table, but it is the same as the number of 4note set classes, which does appear.) The final column gives the total number of set classes of all cardinalities for each value of N. [75] These tables illustrate in dramatic fashion how set classes proliferate as N increases. In the quartertone system (N = 24), there are more than 350,000 T_{n}/T_{n}I 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_{n}I classes approaches 2, because symmetrical sets become statistically scarcer. Without venturing too far into the somewhat contentious question of the “privileged” nature of the mod12 system, we may at least note that the usual 224 T_{n}/T_{n}I 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.^{(14)} [76] 2.17. Example: beatclass sets. Similarities between pitch and rhythmic structures have been widely noted. For example, Cohn 1992 and Roeder 2003 employ beatclass sets, the rhythmic counterpart of pitchclass 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 knote subsets of an Nnote 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 twelvebeat 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 twelvebeat 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: twelvetone rows, revisited. In section 1.3 we observed that the total number of twelvetone 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.^{(15)}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_{0} (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_{0} 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_{1},
a_{2}, 0 + j = a_{11}, a_{1} + j =
a_{10}, all hold (mod 12). The first equation says that j = a_{11}; then the last equation implies that j = a_{11} = 6. (It cannot be 0, since 0 is the first note of the row and a_{11} is the last.) Retrograde symmetry, therefore, is possible only at the tritone transposition T_{6}. The second note a_{1} may be chosen freely from the remaining ten pcs (besides 0 and a_{11} = 6), but then a_{10} = a_{1} + 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_{1}, 0 + a_{11} = j, a_{1} + a_{10} = 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_{11} is determined; a_{1} can then be chosen from ten options, thereby determining a_{10}; 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 Rinvariant 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.^{(16)} [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 Nnote scale is [81] 2.19. Further examples and conclusions. Fripertinger (1993, 5) shows that if N
is even, the number of selfcomplementary N/2note set classes may be calculated
as P_{G}(0, 2, 0, 2, [82] and Read 1997 give many additional examples of advanced calculations. Among the phenomena for which Fripertinger devises methods of enumeration are knote row classes mod N (pages 11–12); allinterval rows (pages 13–17); “motifs” involving both pitch and rhythm (pages 18–20); and Hauer’s tropes (pages 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 musictheoretic 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 notsosimple 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 bruteforce listing is superseded by an elegant (if esoteric) enumeration procedure, or when early attempts at pcset 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 longstanding bond between music and mathematics.
Julian Hook Works CitedBenson, David J. 2007. Music: A Mathematical Offering. Cambridge, UK: Cambridge University Press. Benson, David J. 2007. Music: A Mathematical Offering. Cambridge, UK: Cambridge University Press. Bernard, Jonathan W. 1997. “Chord, Collection, and Set in TwentiethCentury 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. Bernard, Jonathan W. 1997. “Chord, Collection, and Set in TwentiethCentury 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. 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. Cohen, Daniel I. A. 1978. Basic Techniques of Combinatorial Theory. New York: John Wiley & Sons. Cohn, Richard. 1992. “Transpositional Combination of BeatClass Sets in Steve Reich’s PhaseShifting Music.” Perspectives of New Music 30/2: 146–77. Cohn, Richard. 1992. “Transpositional Combination of BeatClass Sets in Steve Reich’s PhaseShifting Music.” Perspectives of New Music 30/2: 146–77. Clough, John. 1979. “Aspects of Diatonic Sets.” Journal of Music Theory 23: 45–61. 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. 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. 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. 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. 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.unigraz.at/~fripert/publications.html (1993 version of paper; accessed 2 October 2007). Fripertinger, Harald. 1992, 1993. “Enumeration in Musical Theory.” Beiträge zur elektronischen Musik 1 (1992). Available online at http://www.unigraz.at/~fripert/publications.html (1993 version of paper; accessed 2 October 2007). Fripertinger, Harald. 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.unigraz.at/~fripert/publications.html (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.unigraz.at/~fripert/publications.html (accessed 2 October 2007). Haack, Joel K. 1991. “Clapping Music—A Combinatorial Problem.” College Mathematics Journal 22: 224–27. 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. 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. 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 12Tone Rows?” American Mathematical Monthly 110: 124–32. Hunter, David J. and Paul T. von Hippel. 2003. “How Rare is Symmetry in Musical 12Tone Rows?” American Mathematical Monthly 110: 124–32. Jedrzejewski, Franck. 2006. Mathematical Theory of Music. Paris: Editions Delatour France. 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. 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.unimainz.de/Musikinformatik/schriftenreihe/nr15/Kirnframe.html (accessed 2 October 2007). Kupper, Hubert. 1994–95. “Der allezeit fertige Polonaisen und Menuettencomponist von Johann Philipp Kirnberger.” Available online at http://www.musikwissenschaft.unimainz.de/Musikinformatik/schriftenreihe/nr15/Kirnframe.html (accessed 2 October 2007). Lester, Joel. 1992. Compositional Theory in the Eighteenth Century. Cambridge, MA: Harvard University Press. 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. 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 19Tone Temperament.” Ph.D. dissertation, Indiana University. Mandelbaum, M. Joel. 1961. “Multiple Division of the Octave and the Tonal Resources of 19Tone Temperament.” Ph.D. dissertation, Indiana University. Morris, Robert D. 1987. Composition with PitchClasses: A Theory of Compositional Design. New Haven: Yale University Press. Morris, Robert D. 1987. Composition with PitchClasses: A Theory of Compositional Design. New Haven: Yale University Press. Morris, Robert D. 1991. Class Notes for Atonal Music Theory. Lebanon, NH: Frog Peak Music. —————. 1991. Class Notes for Atonal Music Theory. Lebanon, NH: Frog Peak Music. Morris, Robert D. 2001. Class Notes for Advanced 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 TwentiethCentury Music Theory.” Music Theory Spectrum 25: 205–41. Nolan, Catherine. 2003. “Combinatorial Space in Nineteenth and Early TwentiethCentury 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. Pólya, George. 1937. “Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen.” Acta Mathematica 68: 145–254. Pólya, George. 2004 [1945]. How to Solve It: A New Aspect of Mathematical Method. Princeton, NJ: Princeton University Press. —————. 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. 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. Rahn, John. 1980. Basic Atonal Theory. New York: Longman. Ratner, Leonard. 1970. “Ars combinatoria: Chance and Choice in EighteenthCentury Music.” In Studies in EighteenthCentury Music, ed. H. C. Robbins Landon and Roger E. Chapman (New York: Oxford University Press), 343–63. Ratner, Leonard. 1970. “Ars combinatoria: Chance and Choice in EighteenthCentury Music.” In Studies in EighteenthCentury Music, ed. H. C. Robbins Landon and Roger E. Chapman (New York: Oxford University Press), 343–63. Ratner, Leonard. 1980. Classic Music: Expression, Form, and Style. New York: Macmillan. —————. 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. 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. 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. Riordan, John. 1958. An Introduction to Combinatorial Analysis. New York: John Wiley & Sons. Roeder, John. 2003. “BeatClass Modulation in Steve Reich’s Music.” Music Theory Spectrum 25: 275–304. Roeder, John. 2003. “BeatClass Modulation in Steve Reich’s Music.” Music Theory Spectrum 25: 275–304. Straus, Joseph N. 2005. Introduction to PostTonal Theory, 3rd ed. Upper Saddle River, NJ: Pearson Prentice Hall. Straus, Joseph N. 2005. Introduction to PostTonal Theory, 3rd ed. Upper Saddle River, NJ: Pearson Prentice Hall. Struik, Dirk J. 1967. A Concise History of Mathematics, 3rd ed. New York: Dover. Struik, Dirk J. 1967. A Concise History of Mathematics, 3rd ed. New York: Dover. Footnotes* 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. 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. 1. 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 readerfriendly. 2. 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 pages 210–19. 3. A little reflection shows that 1 is the only mathematically reasonable way for 8^{0} (or
n^{0}) 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 4. 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. 5. Quoted in Lester 1992, 226. 6. 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. 7. 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. 8. Uniquely among the eighteenthcentury 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 twovoice 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^{12} = 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^{11} = 31,381,059,609. 9. 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. 10. 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. 11. Hungarianborn 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 widelyread and oftenreprinted book of problemsolving strategies titled How to Solve It (2004). 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. 12. These formulas appear in Reiner 1985, 52–53 and Fripertinger 1992, 1993, 4. Reiner’s formula for the cycle index of the dihedral group contains a misprint; the formula given here is correct. 13. The function φ is wellknown 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. 14. Mandelbaum (1961, 251) has proposed that “it is conceivable that there was a point around 15. 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. 16. Hunter and von Hippel 2003 offer statistical confirmation that twelvetone composers choose symmetrical rows far more often than random selection would dictate. 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 readerfriendly. 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 pages 210–19. A little reflection shows that 1 is the only mathematically reasonable way for 8^{0} (or
n^{0}) 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 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. Quoted in Lester 1992, 226. 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. 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. Uniquely among the eighteenthcentury 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 twovoice 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^{12} = 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^{11} = 31,381,059,609. 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. 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. Hungarianborn 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 widelyread and oftenreprinted book of problemsolving strategies titled How to Solve It (2004). 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. These formulas appear in Reiner 1985, 52–53 and Fripertinger 1992, 1993, 4. Reiner’s formula for the cycle index of the dihedral group contains a misprint; the formula given here is correct. The function φ is wellknown 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. Mandelbaum (1961, 251) has proposed that “it is conceivable that there was a point around 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. Hunter and von Hippel 2003 offer statistical confirmation that twelvetone composers choose symmetrical rows far more often than random selection would dictate.
Copyright StatementCopyright © 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:
[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.
