# FMM13

### From charlesreid1

# 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 equal to the coefficeint of w1^k1 w2^k2 ... wm^km in the polynomial
That is, replace each zr in the cycle-index polynomial with sum w_i^r and then divide by , where denotes number of elements in G. To apply Polya's theorem, we need to determine the permutation group G associated with an n-bead necklace, then determine the cycle-index polynomial of G. The group G is all cyclic permutations of n objects. There are n such permutations. This group is called the cyclic group of order n, Cn. This is a group. The cycle-index polynomial of Cn depends on k and n as follows: possible cycles in elements of Cn are all divisors d of n. For a given d, there are phi(d) such elements (where phi(d) is number of integers < d and relatively prime to d). each of those elements has n/d cycles. Applying Polya's theorem:
Values of this function are also symmetrical: Why? Because the size of the set of necklaces with n black beads is the same as the size of the set with n white beads and n-k black beads. |

## Flags

Friday Morning Math ProblemsSpider Socks and Shoes FMM1 Sums of Powers of 2 FMM2 Fifty Coins FMM3 The Zeta Monogram FMM4 The Cthulhus Monogram FMM4B Multiplication Logic FMM5 The Termite and the Cube FMM6 Sharing Dump Trucks FMM7 The Flippant Juror FMM8 Bus Routes FMM9 A Robust Bus System FMM9B Square-Free Sequence FMM10 Inferring Rule from Sequence FMM11 Checkerboard Color Schemes FMM12 One-Handed Chords FMM13 First Ace FMM14 Which Color Cab FMM15 Petersburg Paradox Revisited FMM16 A Binomial Challenge FMM17 A Radical Sum FMM18 Memorable Phone Numbers FMM19 Arrange in Order FMM20 A Pair of Dice Games: FMM21
Category:Puzzles · Template:FMMFlag · e |