FMM13

Friday Morning Math Problem

One-Handed Chords

The common 12-tone equal-tempered musical scale consists of a cyclically repeating sequence of 12 musical notes: C, Db, D, Eb, E, F, Gb, G, Ab, A, Bb, B. The 12 notes can be placed on a circle and labeled 0 to 11. A chord consists of a set of notes played simultaneously, and can consist of k notes, where k <= 12.

Today's math problem is related to counting the number of distinct chord types for a given tonic (first note) in a 12-note scale. This problem, in turn, is equivalent to counting the number of unique arrangements of a necklace of 2-color beads, with the necklace representing the chord, and the 2 bead colors (black/white) representing the note being selected (black) or not selected (white). (The number of distinct k-note chords Ch(n,k) is the number of n-bead necklaces with k black beads.)

Today's question: for a given tonic (first note), how many chords in the 12-tone scale can be played on a piano with one hand?

The equivalent necklace problem: how many 12-bead, 2-color necklaces have at most 5 black beads?

Solution

Special case of a configuration problem. In configuration problems, we specify conditions under which two configurations are considered distinct. We impose the restriction that two configurations are considered equivalent (isomorphic) if they are equal under any permutation from a set of permutations G. In the case of the chords/necklace problem, we restrict the permutations G considered isomorphic to cyclic permutations, defined as 1 2 3 ... n ... ... n 1 2 3 ... where the first row are the integers 1 to n in order and the second row is shifted cyclically by some number of places. In other words, two necklaces are considered the same if they are rotations of each other. Polya's Theorem solves the more general configuration-counting problem using any set of permutations G satisfying the restriction that G is a group. A set of permutations G is a group if two conditions are met: (1) set of permutations G is closed, meaning if any two permutations p and q from G are applied, the permutation that results is also in G; and (2) the inverse of every permutation in G is also in G, and applying a permutation followed by its inverse results in the identity permutation. The number of configurations (using n boxes and m different object types) with weight k1 w1 + k2 w2 + ... + km wm, where two configurations are considered equivalent under any permutation in a permutation group G, is equial to the coefficeint of w1^k1 w2^k2 ... wm^km in the polynomial 1/