“adm-n2” — 2018/7/24 — 18:29 — page 165 — #3
Algebra and Discrete Mathematics RESEARCH ARTICLE
Volume 25 (2018). Number 2, pp. 165–176
c© Journal “Algebra and Discrete Mathematics”
Enumeration of strong dichotomy patterns
Octavio A. Agustín-Aquino
Communicated by I. V. Protasov
Abstract. We apply the version of Pólya-Redfield theory
obtained by White to count patterns with a given automorphism
group to the enumeration of strong dichotomy patterns, that is, we
count bicolor patterns of Z2k with respect to the action of Aff(Z2k)
and with trivial isotropy group. As a byproduct, a conjectural
instance of phenomenon similar to cyclic sieving for special cases of
these combinatorial objects is proposed.
1. Introduction
In a short and beautiful paper [10], White proved an analogue of
Cauchy-Frobenius-Burnside lemma tailored for the purpose of counting
patterns with a fixed group of automorphisms. Before stating it, we warn
the reader that we will use the Iverson bracket1 as defined by Graham,
Knuth and Patashnik [4, p. 24]: if P is a property, then
[P ] =
{
1, P is true,
0, otherwise.
Theorem 1 (D. E. White, 1975). Let S be a finite set, G a finite group
acting on S and ∆ a system of orbit representatives for G acting on S.
2010 MSC: 00A65, 05E18.
Key words and phrases: strong dichotomy pattern, Pólya-Redfield theory, cyclic
sieving.
1White uses the similar notation χ(P ) in his articles, which was introduced first by
Adriano Garsia in a paper from 1979 according to Knuth [6], although White’s paper
predates it by four years.
“adm-n2” — 2018/7/24 — 18:29 — page 166 — #4
166 Enumeration of strong dichotomy patterns
Suppose {G1, . . . , GN} is a traversal of the orbits of the subgroups of G
under the conjugation action, such that
|G1| > · · · > |GN |.
Given a weight function w : S → T such that w(σs) = w(s) for all
σ ∈ G and all s ∈ S, we have
∑
s∈∆
w(s)[Gs ∼ Gi] =
N
∑
j=1
bi,j
∑
s∈S
w(s)[Gjs = s],
where B = (bi,j) is the inverse of the table of marks matrix
Mi,j =
1
|Gj |
∑
σ∈G
[σGiσ−1 ⊆ Gj ].
Note that the table of marks matrix is invertible because it is triangular
and no element of the diagonal is 0.
Let S = RD, where both R and D are finite sets. If G acts on R
(the set of colors), it is well known that the action can be extended to
S defining σ · f = f ◦ σ−1, where σ is reinterpreted as a member of the
permutation group of D. We know that the action of Gi on D defines a
set of disjoint orbits
OGi:D := {Gix1, . . . , Gixℓ}
which is a partition of D, so we can define
qGi(d) =
ℓ
∑
i=1
[|Gxi| = d].
This allows us to define the orbit index monomial as
Pi(z1, z2, . . . , z|D|) :=
∏
d∈D
zqGi (d)d ,
which can be used in a straightforward manner to obtain a pattern inven-
tory polynomial.
Theorem 2 (D. E. White, 1975). The pattern inventory polynomial for
patterns fixed by the subgroup Gi is
Qi =
N
∑
j=1
bi,jPj(z1, z2, . . . , z|D|),
where the substitution yi =
∑
r∈R xir is made.
“adm-n2” — 2018/7/24 — 18:29 — page 167 — #5
O. A. Agustín-Aquino 167
We will use White’s results (and one further generalization obtained
by him that we will discuss later) to count bicolor patterns under a group
G which are of particular interest for mathematical musicology. The usual
choices forG are cyclic, dihedral and general affine groups, since they model
common musically meaningful transformations, such as transpositions,
inversions, retrogradations and others related to twelve-tone techniques,
to name a few (see [7, Chapter 8] for more examples).
One reason to study this kind of combinatorial objects is that they
represent rhythmic patterns if they are interpreted as onsets in a mea-
sure (see [2] and [5] and the references therein for more information).
Another reason is that they can be seen as abstractions of the concepts
of consonance and dissonance in Renaissance counterpoint. In particular,
self-complementary (that is, those whose complement belongs to its orbit)
and rigid (which means that they are invariant only under the identity)
patterns, hereafter called strong, are known to be used in both Western
and Eastern music [7, Part VII], and that their combinatorial structure
lead to significant musicological results [7, Chapter 31]. Note in passing
that self-complementarity forces the patterns to be subsets of cardinality
k of sets of even cardinality 2k. In general, dichotomy patterns are those
of cardinality k within a set of cardinality 2k.
In the following section we provide simple examples of White’s theory
in action to explain the algorithms we use in the main computations. The
results of these calculations appear in Section 3, and in the final section
we provide some further comments regarding them.
2. Two easy examples
Suppose we color black or white the vertices of a rectangle that is not
a square. The group of symmetries acting on the colorings of the vertices
is the Klein four-group
V = 〈a, b|a2 = b2 = (ab)2 = e〉.
We will find the patterns that are invariant under G1 = V , G2 = 〈a〉,
G3 = 〈b〉, G4 = 〈ab〉 and G5 = 〈e〉 using White’s formulas. Since all the
proper subgroups of V are normal, we easily calculate the table of marks
matrix
MV =






1 0 0 0 0
1 2 0 0 0
1 0 2 0 0
1 0 0 2 0
1 2 2 2 4






,
“adm-n2” — 2018/7/24 — 18:29 — page 168 — #6
168 Enumeration of strong dichotomy patterns
whose inverse is
B =






1 0 0 0 0
−12 12 0 0 0
−12 0 12 0 0
−12 0 0 12 01
2 −14 −14 −14 14






.
It is illustrative to make explicit the formula of Theorem 1 for this
simple example. Let us code the colorings of the vertices with the strings
u1u2u3u4 over the alphabet {n, b}, using the clockwise order and beginning
from the upper left corner. Then
∆ = {nnnn, nnnb, nnbb, nbbn, nbnb, nbbb, nnnn}.
For G1 the formula trivially asserts that the only patterns invariant
under the full group are the monochromatic ones. For G2 we have
− 12(w(nnnn) + w(bbbb))
+ 12(w(nnnn) + w(nnbb) + w(bbnn) + w(bbbb))
= 12(w(bbnn) + w(nnbb)) = w(nnbb)
because w(bbnn) = w(nnbb), by hypothesis. The colorings bbnn and nnbb
are precisely those who represent the only pattern which is invariant under
the reflection with vertical axis. The cases of G3 and G4 are analogous.
Finally, the case of the trivial subgroup is more interesting:
1
2(w(nnnn) + w(bbbb))
− 14(w(nnnn) + w(nnbb) + w(bbnn) + w(bbbb))
− 14(w(nnnn) + w(nbbn) + w(bnnb) + w(bbbb))
− 14(w(nnnn) + w(nbnb) + w(bnbn) + w(bbbb))
+ 14
∑
all strings
w(s)
= 14(w(nnnb) + w(nnbn) + w(nbnn) + w(nbbb)
+ w(bnnn) + w(bnbb) + w(bbnb) + w(bbbn))
= w(nnnb) + w(nbbb),
and it informs us of the two patterns that are invariant under the action
of the trivial subgroup only; they are precisely those with only one black
or only one white vertex.
“adm-n2” — 2018/7/24 — 18:29 — page 169 — #7
O. A. Agustín-Aquino 169
Let us confirm the former using the orbit index polynomials for each
subgroup. For G1, we have only one orbit of four elements, thus
P1 = z4.
The orbits defined by G2, G3 and G4 are all of cardinality two, thus
P2 = P3 = P4 = z22 .
Finally, there are four orbits of cardinality one for the trivial subgroup,
hence
P5 = z41 .
Using these polynomials, we can calculate all the pattern inventories
at once:






Q1
Q2
Q3
Q4
Q5






=






1 0 0 0 0
−12 12 0 0 0
−12 0 12 0 0
−12 0 0 12 01
2 −14 −14 −14 14












z4
z22
z22
z22
z41






=






z4
1
2z22 − 12z41
2z22 − 12z41
2z22 − 12z41
2z4 − 34z22 + 14z41






.
Upon the substitution zi = 1+ xi, that allows us to count the number
of bicolor patterns according to the number of black elements (say), we
find






Q1
Q2
Q3
Q4
Q5






=






1 + x4
x2
x2
x2
x + x3






.
We proceed now with a more complicated example that introduces
the group we will use in our main computation. Define
Aff(Z2k) = Z/2kZ ⋉ Z/2kZ×.
Denote an element (u, v) ∈ Aff(Z2k) by eu.v. The action of Aff(Z2k)
on Z/2kZ is given by
eu.v(x) = vx + u.
“adm-n2” — 2018/7/24 — 18:29 — page 170 — #8
170 Enumeration of strong dichotomy patterns
Let us compute the number of patterns of the action of Aff(Z6). We
have the following sequence of normal subgroups,
G1 = 〈e1.1, e0.5〉, G2 = 〈e4.1, e5.5〉, G3 = 〈e1.1, e0.5〉, G4 = 〈e1.1〉,
G5 = 〈e3.1, e0.5〉, G6 = 〈e2.1〉, G7 = 〈e5.5〉, G8 = 〈e0.5〉,
G9 = 〈e3.1〉, G10 = {e0.1},
The computation of the table of marks matrix is not as direct as before,
in part because the subgroups G5, G7 and G9 are not normal. But using
GAP [3] we readily find
M =
















1 0 0 0 0 0 0 0 0 0
1 2 0 0 0 0 0 0 0 0
1 0 2 0 0 0 0 0 0 0
1 0 0 2 0 0 0 0 0 0
1 0 0 0 1 0 0 0 0 0
1 2 2 2 0 4 0 0 0 0
1 2 0 0 1 0 2 0 0 0
1 0 2 0 1 0 0 2 0 0
1 0 0 2 3 0 0 0 6 0
1 2 2 2 3 4 6 6 6 12
















whose inverse is
B =
















1
12 0 0 0 0 0 0 0 0 0
− 112 16 0 0 0 0 0 0 0 0
−14 0 12 0 0 0 0 0 0 0
−14 0 0 12 0 0 0 0 0 0
− 112 0 0 0 14 0 0 0 0 01
2 −12 −12 −12 0 1 0 0 0 01
12 −16 0 0 −14 0 12 0 0 01
4 0 −12 0 −14 0 0 12 0 01
4 0 0 −12 −14 0 0 0 12 0
−12 12 12 12 12 −1 −12 −12 −12 1
















The orbit index polynomials are
P1 = z6, P2 = z6, P3 = z23 , P4 = z6, P5 = z2z4, P6 = z23 ,
P7 = z32 , P8 = z21z22 , P9 = z32 , P10 = z61
“adm-n2” — 2018/7/24 — 18:29 — page 171 — #9
O. A. Agustín-Aquino 171
whence
Q(z1, . . . , z6) = BP =
















z6
0
1
2z23 − 12z6
0
z2z4 − z6
0
−12z32 − 12z2z41
2z6 − 12z2z4 − 12z23 + 12z21z221
3z6 − 12z2z4 + 16z32
−16z6 + 12z2z4 + 16z23 − 13z32 − 14z21z22 + 112z61
















thus
Q(1 + x, . . . , 1 + x6) =
















x6 + 1
0
x3
0
x4 + x2
0
x4 + x2
x5 + x4 + x3 + x2 + x
0
x3
















.
It is interesting to learn that there are no patterns that are exclusively
invariant under the subgroups generated, respectively, by the translations
e1.1, e2.1, e3.1. In other words: arithmetic progressions with common dif-
ference 1, 2 and 3 are invariant under symmetries that are not translations.
3. Main calculations
Denoting by D the set of dichotomies, and by S and R the subsets of
the self-complementary and rigid dichotomies (respectively), we know by
the principle of inclusion and exclusion (PIE) that
|D| > |S ∪ R| = |S|+ |R| − |S ∩ R|
where |S ∩ R| is precisely the number of strong dichotomies. Hence
|S ∩ R| > |S|+ |R| − |D|.
“adm-n2” — 2018/7/24 — 18:29 — page 172 — #10
172 Enumeration of strong dichotomy patterns
We can calculate |D| and |S| with the classical Pólya-Redfield theory,
and |R| with White’s formulas, so we may expect this inequality to
provide reasonably good bounds on the number of strong dichotomies.
But, unfortunately, in general it does not, as we can readily see in Table
1, since many of them are negative.
However, not everything is lost. After examining the cases when the PIE
yields a nontrivial bound, we discover that this happens when k is a power
of a prime and, more importantly, the value of |Q1(−1)| coincides with the
number of strong dichotomy patterns calculated by direct construction
for these cases (see [1]). On the other hand, it is known that the classical
pattern inventory polynomials of the Pólya-Redfield theory exhibit a form
of the cyclic sieving phenomenon [8, Corollary 6.2], which means that
if p(x) is the generating function of the number of patterns according
to its number of black elements, then p(−1) yields the number of self-
complementary patterns.
Since the polynomials for White’s formulas do not count cycles but
orbits, in general they fail to cyclically sieve patterns, but we may expect
it to work when Z×2k is cyclic. Indeed, if the group of units is generated
by a single element, it is plausible to think that all the orbits are cycles
of e1.1 and a generator of Z×2k. Furthermore, it is a well-known fact that
the group of units of Zn is cyclic precisely when n = 1, 2, pk, where p
is a prime number. This discussion, however, is not a full proof, so we
formalize it as a conjecture. Hopefully, it will be proved soon.
Conjecture 1. Let GN = Aff(Z2k) and {Gi} be a set of representatives
of the orbits of the conjugation action such that |GN | > · · · > |G1| and
let B = (bi,j) be the inverse of its table of marks. If k is equal to 1, 2 or a
power of an odd prime number, then the pattern inventory polynomial
for bicolor patterns fixed by the subgroup Gi
Qi =
N
∑
j=1
bi,jPj(1 + x, 1 + x2, . . . , 1 + x|D|),
is such that |Qi(−1)| counts the number of self-complementary dichoto-
mies with automorphism group Gi. In particular, |Q1(−1)| counts the
number of strong dichotomies.
For the general case, we can use another formula of White [9]. Now
we need to consider the swapping action on the colors of the patterns
simultaneously with that of the affine group, so we see G = Aff(Z2k)×Z2
“adm-n2” — 2018/7/24 — 18:29 — page 173 — #11
O. A. Agustín-Aquino 173
2k |D| |S| |R| PIE bound |Q1(−1)|
2 1 1 1 1 1
4 2 2 0 0 0
6 3 3 0 0 1
8 6 4 1 −1 1
10 9 7 5 3 3
12 34 18 10 −6 4
14 47 15 37 5 9
16 129 21 83 −25 1
18 471 55 436 20 40
20 1280 134 1052 −94 66
22 3235 115 3181 61 105
24 15008 440 13331 −1237 33
26 33429 385 33253 209 355
28 121466 1194 117422 −2850 886
30 648819 3365 643901 −1153 3007
32 1182781 2189 1165498 −15094 1432
34 4290533 4375 4288913 2755 4305
36 21082620 18404 20933318 −130898 15518
38 51677171 15347 51671611 9787 15267
40 215804540 49684 214972319 −782537 25659
42 1068159497 133285 1067785287 −240925 130839
44 2392981542 171662 2389064994 −3744886 155346
46 8135833183 198943 8135769049 134809 198753
48 42007923187 786707 41970277573 −36858907 643019
50 126410742103 872893 126410471144 601934 871992
Table 1. Summary of the information that can be obtained via the classical
Pólya-Redfield theory and White’s extension, for 1 6 k 6 25.
as acting both in R and D, according to
(σ, τ) · r = τ · r and (σ, τ) · d = σ · d;
hence G acts doubly on RD in the following manner
g · f = g ◦ f ◦ g−1.
We provide a quick sketch of White’s reasoning to obtain the count-
ing formula, in part because our problem’s conditions lead to a simpler
statement and in part because his original paper has some minor (but
misleading) typographical errors.
“adm-n2” — 2018/7/24 — 18:29 — page 174 — #12
174 Enumeration of strong dichotomy patterns
In order to apply Theorem 1, we must characterize first the patterns f
such that H ′ ⊆ Gf . If a g ∈ H ′ leaves a pattern invariant, it means that
it sends an element of OH′:D to an element of OH′:R.
Thus, let B ∈ OH′:D and f(B) = C ∈ OH′:R. Taking arbitrary ele-
ments b ∈ B and c ∈ C, we deduce that f must be defined by f(γ1b) = γ1c.
This relation, however, might not be functional, for it may happen that
f(γ1b) 6= f(γ2b) when γ1b = γ2b, unless γ1c = γ2c, or γ−11 γ2 ∈ Hc. In
other words, if the function is well defined then
γ−11 γ2 ∈ Hb implies that γ−11 γ2 ∈ Hc (1)
or, equivalently,
Hb ⊆ Hc
(note that these isotropy groups are relative to H). To check that (1) is
also sufficient is direct, like the fact that the election of b is irrelevant.
We have
∑
f∈S
w(s)[Gjf = f ] =
∑
fˆ∈OOH:DH:R
∏
B∈OH:D
|fˆ(B)|−1
∑
j=0
[Hb ⊆ Hτjc]w(f)
and, reorganizing the terms (in what White calls sum-product interchange),
we get
∑
f∈S
w(f)[Gjf = f ] =
∏
B∈OH:D
∑
C∈OH:R
|C|−1
∑
j=0
[Hb ⊆ Hτjc]w(f) (2)
where
w(f) =
|B|−1
∏
i=0
xτjc. (3)
For bicolor patterns we have C = {0, 1}, therefore the invariance under
the action of the whole group reduces the weights w(f) to the following
choices:
w(f) =
{
x|B|/20 x
|B|/2
1 , H swaps colors,
x|B|0 = x
|B|
1 , otherwise.
Thus we can reuse the previous algorithm that involves the inverse of
the table of marks matrix, but with the larger group Aff(Z2k)× Z2 and
calculating the corresponding vector of polynomials with (2) and (3). The
only remaining detail is that no longer we may read the total number
“adm-n2” — 2018/7/24 — 18:29 — page 175 — #13
O. A. Agustín-Aquino 175
2k |S ∩ R|
6 1
8 1
12 2 + 4 = 6
16 1 + 14 = 15
20 3 + 6 + 54 + 27 = 90
24 14 + 54 + 63 + 228 = 359
28 38 + 76 + 326 + 652 = 1092
32 120 + 2032 = 2152
36 560 + 1120 + 5382 + 10764 = 17826
40 1572 + 6357 + 8100 + 32520 = 48549
42 3936 + 12135 + 28320 + 86448 = 130839
44 4662 + 9324 + 52278 + 104556 = 170820
48 21435 + 65040 + 172410 + 521760 = 780645
Table 2. Summary of the information that can be obtained via White’s
extension of Pólya-Redfield theory for strong dichotomy patterns and selected
values of k. The totals of strong dichotomies are displayed as sums, where each
summand represents the number of patterns with a specific polarity. Thus, the
number of summands on each row is the number of polarities.
of strong dichotomy patterns in a single entry of the output vector, for
such patterns have automorphism groups of cardinality two; namely, the
identity (e0.1, 0) and the color swap (e0.1, 1) composed with a unique
symmetry of Aff(Z2k), which is called the polarity of the pattern. Hence,
we gain a feature and not an inconvenience, for now we can know the
number of strong dichotomy patterns for each polarity.
The first case that is not covered by Conjecture 1 is n = 8, but the
table of marks matrix is of size 148× 148, so we will not display it here.
Let us simply state that there is only one strong dichotomy, whose polarity
is e5.− 1. In Table 2 we summarize the information that can be calculated
with this algorithm up to 2k = 48.
4. Concluding remarks
The enumerations of strong dichotomies done here coincide with the
explicit ones performed in [1] and subsequent verifications done by the
author, with a variation of the original algorithm presented in [1]. It
is interesting to note that Conjecture 1 is of practical interest, since it
significantly simplifies the computation of the table of marks: we should
consider that the volume of calculations is exacerbated when we have to
“adm-n2” — 2018/7/24 — 18:29 — page 176 — #14
176 Enumeration of strong dichotomy patterns
calculate with the product Aff(Z2k)× Z2; its table of marks can be much
bigger that the one of its largest factor.
Harald Fripertinger noted in a personal communication with the author
that the number of self-complementary patterns |S| seems to approach
asymptotically to the number of the strong ones (or, equivalently, that
the vast majority of dichotomies is rigid). In particular, |S| provides a
direct and fast way (it does not require to compute the table of marks) to
determine a very good upper bound for the number of strong patterns, a
useful fact in order to partially validate the exact (but lengthy) calculations.
References
[1] Octavio A. Agustín-Aquino, Extensiones microtonales de contrapunto, Ph.D. thesis,
Universidad Nacional Autónoma de México, 2011.
[2] Harald Fripertinger, Enumeration of mosaics, Discrete Mathematics 199 (1999),
no. 1-3, 49–60.
[3] The GAP Group, GAP – Groups, Algorithms, and Programming, Version 4.7.4,
2014.
[4] Ronald L. Graham, Donald E. Knuth, and Oren Patashnik, Concrete mathematics:
a foundation for computer science, 2 ed., Addison Wesley, Reading, Massachusetts,
1994.
[5] Rachel W. Hall and Paul Klingsberg, Asymmetric rhythms and tiling canons,
American Mathematical Monthly 113 (2006), no. 10, 887–896.
[6] Donald E. Knuth, Two notes on notation, The American Mathematical Monthly
99 (1992), no. 5, 403–422.
[7] Guerino Mazzola, The topos of music: Geometric logic of concepts, theory, and
performance, Birkhäuser Verlag, Basel, 2002.
[8] Victor Reiner, Dennis Stanton, and Dennis E. White, The cyclic sieving phe-
nomenon, Journal of Combinatorial Theory, Series A 108 (2004), no. 1, 17–50.
[9] Dennis E. White,Classifying patterns by automorphism group: an operator theoretic
approach, Discrete Mathematics 13 (1975), no. 3, 277–295.
[10] Dennis E. White, Counting patterns with a given automorphism group, Proceedings
of the American Mathematical Society 47 (1975), no. 1, 41–44.
Contact information
Octavio A.
Agustín-Aquino
Universidad Tecnológica de la Mixteca,
Instituto de Física y Matemáticas, Carretera a
Acatlima Km. 2.5, Huajuapan de León, Oaxaca,
México, C.P. 69000
E-Mail(s): octavioalberto@mixteco.utm.mx
Received by the editors: 03.02.2016
and in final form 01.02.2018.