# Why Are There Twenty-Nine Tetrachords? A Tutorial on Combinatorics and Enumeration in Music Theory
^{*}

## Julian Hook

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*

Copyright © 2007 Society for Music Theory

“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 *T _{n}*/

*T*set classes of each cardinality from 0 through 12. The number of different pc-sets of cardinality

_{n}I*, 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 1987and 1991, and Straus 2005, among various other texts.*

*k*[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*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.

_{n}I[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, 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.^{(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 *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^{6} (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^{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 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^{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 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* *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,^{(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: 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^{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 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

*.) This is a very large number—almost half a billion—but it is nevertheless far smaller than 12*

*n*^{12}, which is almost 9 trillion. (As

*increases,*

*n**! grows very rapidly—but not as rapidly as*

*n**.)*

*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 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

*!. Occasionally it is useful to form a permutation of some*

*n**subset*of the available objects rather than of all of them; that is, there are

*objects from which to choose, but we are to construct an ordered arrangement of only*

*n**k*of them, for some

*k*<

*. Such arrangements are referred to as “permutations of*

*n**objects*

*n**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^{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 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^{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 sixteenth-note multiple durations are
allowed, the number rises dramatically to 2^{15} = 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 *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 well-known *binomial theorem*. If the
algebraic expression * x* +

*(a*

*y**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} + 12*x*^{11}*y* + 66*x*^{10}*y*^{2} + 220*x*^{9}*y*^{3} + 495*x*^{8}*y*^{4} + 792*x*^{7}*y*^{5} + 924*x*^{6}*y*^{6}

+ 792*x*^{5}*y*^{7} + 495*x*^{4}*y*^{8} + 220*x*^{3}*y*^{9} + 66*x*^{2}*y*^{10} + 12*xy*^{11} +
*y*^{12}.

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*)^{12} 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, *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*.^{(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 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.”^{(5)}

[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.

^{(6)}

[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.^{(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 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^{16}, 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^{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
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.^{(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:

Ars combinatoriais 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*^{(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 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*_{4}*I* may be regarded as a permutation of the twelve pitch classes, either
as a mapping

0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | A | B |

↓ | ↓ | ↓ | ↓ | ↓ | ↓ | ↓ | ↓ | ↓ | ↓ | ↓ | ↓ |

4 | 3 | 2 | 1 | 0 | B | A | 9 | 8 | 7 | 6 | 5 |

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*. Of course,

_{N}*G*need not include every permutation in

*S*. 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.

_{N}[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)}

If a group

Gacts on a setZof configurations, the number of orbits iswhere |

G| denotes the order (cardinality) of the groupG; the sum is taken over all permutationsgin the groupG; andψ(g) denotes the number of configurations fixed by the permutationg(that is, the number of configurationszinZsuch thatg(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^{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 pitch-class 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 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*_{1}) = 3. Likewise *T*_{3}, the 90-degree rotation in the opposite direction, fixes
only these same three configurations, so *ψ*(*T*_{3}) = 3 also. For a configuration to
be fixed by the 180-degree 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 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*_{4}, which consists of *eight* transformations of the four-sided
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 pitch-class
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} (3-color 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 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 *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 *4-cycle*. The reflection *I*, in contrast, breaks down into two 1-cycles and a
2-cycle, (0)(1 3)(2), while *T*_{1}*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*_{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 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^{1} in the case of *T*_{1} indicates a single
4-cycle, while 1^{2}2^{1} 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*_{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},

*t*, namely

_{N}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.

**Table 3**. Cycle structure of the permutations in the dihedral group *D*_{12} (set-class problem)

(click to enlarge)

[52] *2.6. Example*: *T _{n}*/

*T*

_{n}I*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 2

^{12}colorings of the pitch classes uniquely determine each of the 2

^{12}pc-sets. The group of equivalences is the dihedral group

*D*

_{12}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.

[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*_{1}, *w*_{2}, *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*^{2}*bg*. In the set-class 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 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*^{2}*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*^{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
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*:^{(11)}

Suppose a transformation group

Gacts on configurations ofNobjects colored withkcolors. Let the weights assigned to the colors bew_{1},w_{2},. . . ,w, and define_{k}Let

Pbe the cycle index of the group_{G}G. Then the sum of the weights of all the orbits, counting each orbit once, isP(_{G}α_{1},α_{2},. . . ,α_{N}).

[57] The cycle index of the group *G*, it will be recalled, is a polynomial in *N*
variables, *P _{G}*(

*t*

_{1},

*t*

_{2},

*t*), calculated by averaging together the cycle indices of the various permutations in the group. Pólya’s theorem instructs us to substitute

_{N}*α*

_{1},

*α*

_{2},

*α*

_{N}for the variables

*t*

_{1},

*t*

_{2},

*t*in this expression. Because

_{N}*α*

_{1},

*α*

_{2},

*α*

_{N }are defined as sums of powers of the weights

*w*

_{1},

*w*

_{2},

*w*, the resulting expression

_{k}*P*(

_{G}*α*

_{1},

*α*

_{2},

*α*

_{N}) is ultimately a polynomial in

*w*

_{1},

*w*

_{2},

*w*; it is known as the

_{k}*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*_{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, 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*_{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
birthday-cake 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 single-color
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 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 3*r*^{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 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*_{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 birthday-cake 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 set-class 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},

*α*

_{12}=

*x*

^{12}+

*y*

^{12}. There are 24 terms to be added, corresponding to the cycle structures of the transformations

*T*and

_{n}*T*, 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

_{n}Iwhich 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*

_{12}rather than the dihedral group

*D*

_{12}; we need only consider the terms associated with the transpositions

*T*(the top half of Table 3) in the above calculation. The resulting Pólya polynomial is

_{n}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*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

_{n}I*T*/

_{n}*T*variety splits into two set classes of the

_{n}I*T*variety. There are now 43 tetrachords rather than 29, because 14 asymmetrical tetrachord types have split. The total number of

_{n}*T*set classes of all cardinalities, obtained by summing all the coefficients, is 352, compared with 224 in the

_{n}*T*/

_{n}*T*situation.

_{n}I[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*

_{n}*M*and

*T*in addition to the previous

_{n}MI*T*and

_{n}*T*. The reader may verify that the transformation

_{n}I*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*are of several different types, including

_{n}MI*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 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_{n}I 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*and

_{n}*T*. 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 (

_{n}I*T*

_{0}) is of cycle index

*t*

_{1}

^{19}; the transpositions

*T*

_{1},

*T*

_{18}are all of type

*t*

_{19}

^{1}(each permuting the nineteen pcs in one large cycle); and the inversions

*I*,

*T*

_{1}

*I*,

*T*

_{18}

*I*are all of type

*t*

_{1}

^{1}

*t*

_{2}

^{9}(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*_{0}) is of cycle index *t*_{1}^{7}; the transpositions
*T*_{1}, *T*_{6} are all of type *t*_{7}^{1}; and the inversions *I*, *T*_{1}*I*, *T*_{6}*I* are all of type
*t*_{1}^{1}*t*_{2}^{3}. 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*classes) in an

_{n}I*N*-note 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*or the dihedral group

_{N}*D*, as appropriate. Such formulas can be found in the combinatorial literature (e.g., Riordan 1958, 149–50) and will be given here without proof.

_{N}[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}*

^{–}

*when*

^{k}y^{k}*α*

_{j}=

*x*+

^{j}*y*

*is substituted for*

^{j}*t*in each of these equations, as Pólya’s theorem specifies. In the cyclic case, the coefficient of

_{j}*x*

^{N}^{–}

*—the number of*

^{k}y^{k}*T*classes of

_{n}*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*classes—is

_{n}IAgain, 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 (

*ζ*

_{12}(4) = 43) and 29

*T*/

_{n}*T*classes of tetrachords (

_{n}I*ξ*

_{12}(4) = 29), while in the 19-note system the number of

*T*/

_{n}*T*classes of tetrachords is 120 (

_{n}I*ξ*

_{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 19-note cases.

**Table 4**. Values of *ζ _{N}*(

*k*), the number of

*T*classes of

_{n}*k*-note chords in an

*N*-note scale

(click to enlarge)

**Table 5**. Values of *ξ*_{N}(*k*), the number of *T _{n}*/

*T*classes of

_{n}I*k*-note chords in an

*N*-note 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*classes, respectively, of

_{n}I*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*.

[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*classes and almost 700,000

_{n}I*T*classes. The latter number is almost twice the former; indeed, as

_{n}*N*increases, the ratio of

*T*classes to

_{n}*T*/

_{n}*T*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

_{n}I*T*/

_{n}*T*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.

_{n}I^{(14)}

[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.^{(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*classes of rows acted upon by a group of order 4 consisting of

_{n}*T*

_{0}(the identity),

*I*,

*R*, and

*RI*(=

*IR*). Each

*T*class consists of exactly twelve rows, and may be represented by a single row that starts with 0. The number of orbits of the

_{n}*T*classes in this simplified setting is the same as the number of orbits of rows in the original situation.

_{n}[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*classes, and

_{n}*I*fixes none (an inverted form of a row can never be a transposition of the original row). For a

*T*class represented by a row (0,

_{n}*a*

_{1},

*a*

_{2},

*a*

_{11}) to be fixed by

*R*, the retrograde (

*a*

_{11},

*a*

_{10},

*a*

_{1}, 0) must be some transposition

*T*of the row. That is, for some

_{j}*j*, the twelve equations

0 + *j* = *a*_{11}, *a*_{1} + *j* =
*a*_{10}, *a*_{11} + *j* = 0

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*classes, but the rows of Berg’s

_{n}*Lyric Suite*and Webern’s Symphony, Op. 21 are of this type.

[79] Finally, if a *T _{n}* class represented by (0,

*a*

_{1},

*a*

_{11}) is fixed by

*RI*, the equations become

0 + *a*_{11} = *j*, *a*_{1} + *a*_{10} = *j*, *a*_{5} + *a*_{6} = *j*

for some *j*. Even values of *j* are impossible: indeed, if *j* = 2*i*, 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

*R*-invariant classes but still rare among all

*T*classes; the rows of Webern’s String Quartet, Op. 28, Cantata, Op. 29, and Variations, Op. 30 are all of this type.

_{n}^{(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 *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,

*t*in the cycle index of the group of equivalences (which as usual may be either

_{j}*C*or

_{N}*D*). One can use this formula together with the cycle index formulas given previously to verify that for

_{N}*N*= 12 the number of self-complementary hexachords is 8 if the group of equivalences is

*C*(that is, eight

_{N}*T*types of hexachords are related to their complements by some

_{n}*T*), or 20 if the group is

_{n}*D*(twenty

_{N}*T*/

_{n}*T*types of hexachords are related to their complements by some

_{n}I*T*and/or

_{n}*T*).

_{n}I[82] 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* (pages 11–12); all-interval 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 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.

Julian Hook

Jacobs School of Music

Indiana University

Bloomington, IN 47405

juhook@indiana.edu

### Works Cited

*Music: A Mathematical Offering*. Cambridge, UK: Cambridge University Press.

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

*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 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.

*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.

*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.

*Perspectives of New Music*30/2: 146–77.

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

*Journal of Music Theory*23: 45–61.

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

*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.

*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.

*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.

*The Structure of Atonal Music*. New Haven: Yale University Press.

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

*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).

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).

*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).

—————. 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).

*College Mathematics Journal*22: 224–27.

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

*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.

*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.

*American Mathematical Monthly*110: 124–32.

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

*Mathematical Theory of Music*. Paris: Editions Delatour France.

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

*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.

*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).

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).

*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.

*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 19-Tone Temperament.” Ph.D. dissertation, Indiana University.

*Composition with Pitch-Classes: A Theory of Compositional Design*. New Haven: Yale University Press.

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

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

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

*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.

*Music Theory Spectrum*25: 205–41.

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

*Acta Mathematica*68: 145–254.

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

*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.

*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.

*Basic Atonal Theory*. New York: Longman.

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

*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.

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.

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

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

*Discrete Mathematics*167–168: 543–51.

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

*American Mathematical Monthly*92: 51–54.

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

*An Introduction to Combinatorial Analysis*. New York: John Wiley & Sons.

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

*Music Theory Spectrum*25: 275–304.

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

*Introduction to Post-Tonal Theory*, 3rd ed. Upper Saddle River, NJ: Pearson Prentice Hall.

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

*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.

Return to text

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 reader-friendly.

Return to text

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.

Return to text

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*for negative exponents ensures that a sequence of numbers such as

^{k}^{–2}= 1/64, 8

^{–1}= 1/8, 8

^{0}= 1, 8

^{1}= 8, 8

^{2}= 64,

Return to text

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.

Return to text

5. Quoted in Lester 1992, 226.

Return to text

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.

Return to text

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.

Return to text

8. 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^{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.

Return to text

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.

Return to text

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.

Return to text

11. 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). 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

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.

Return to text

13. 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

14. Mandelbaum (1961, 251) has proposed that “it is conceivable that there was a point around

Return to text

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.

Return to text

16. 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

^{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

*= 1/*

*n*^{–k}*n*for negative exponents ensures that a sequence of numbers such as

^{k}^{–2}= 1/64, 8

^{–1}= 1/8, 8

^{0}= 1, 8

^{1}= 8, 8

^{2}= 64,

*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.

*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

^{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.

*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.

*φ*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.

### 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 Onlinein [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.

Prepared by Brent Yorgason, Managing Editor and Stefanie Acevedo, Editorial Assistant