FMM13 - Revision history

Admin at 22:46, 16 November 2019

2019-11-16T22:46:49Z

← Older revision		Revision as of 22:46, 16 November 2019
Line 45:		Line 45:

	<math>		<math>
	N(n,k) = \frac{1}{n} \sum_{d \vert n,k} \phi(d) \binom{\frac{n}{d}, \frac{k}{d}}		N(n,k) = \frac{1}{n} \sum_{d \vert n,k} \phi(d) \binom{\frac{n}{d}}{\frac{k}{d}}
	</math>		</math>

Admin at 22:45, 16 November 2019

2019-11-16T22:45:10Z

← Older revision		Revision as of 22:45, 16 November 2019
Line 45:		Line 45:

	<math>		<math>
	N(n,k) = 1/n \sum_{d \| n,k} \phi(d) \binom{n/d, k/d}		N(n,k) = \frac{1}{n} \sum_{d \vert n,k} \phi(d) \binom{\frac{n}{d}, \frac{k}{d}}
	</math>		</math>

Admin at 22:44, 16 November 2019

2019-11-16T22:44:18Z

← Older revision		Revision as of 22:44, 16 November 2019
Line 45:		Line 45:

	<math>		<math>
	N(n,k) = 1/n sum_{d \| n,k} \phi(d) \binom{n/d, k/d}		N(n,k) = 1/n \sum_{d \| n,k} \phi(d) \binom{n/d, k/d}
	</math>		</math>

Admin at 22:42, 16 November 2019

2019-11-16T22:42:34Z

← Older revision		Revision as of 22:42, 16 November 2019
Line 30:		Line 30:
	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		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

	<~~pre~~>		<math>
	1/\|G\| P(G; \sum w_i, \sum w_i^2, ...)		\frac{1}{\|G\|} P(G; \sum w_i, \sum w_i^2, ...)
	</~~pre~~>		</math>

	That is, replace each zr in the cycle-index polynomial with sum w_i^r and then divide by \|G\|, where \|G\| denotes number of elements in G.		That is, replace each zr in the cycle-index polynomial with sum w_i^r and then divide by <math>\|G\|</math>, where <math>\|G\|</math> 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.		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.
Line 44:		Line 44:
	Applying Polya's theorem:		Applying Polya's theorem:

	N(n,k) = 1/n sum_{d \| n,k} phi(d) binom{n/d, k/d}		<math>
			N(n,k) = 1/n sum_{d \| n,k} \phi(d) \binom{n/d, k/d}
			</math>

	Values of this function are also symmetrical:		Values of this function are also symmetrical:

			<math>
	N(n, n-k) = N(n, k)		N(n, n-k) = N(n, k)
			</math>

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

	}}		}}

Admin at 22:41, 16 November 2019

2019-11-16T22:41:22Z

← Older revision		Revision as of 22:41, 16 November 2019
Line 28:		Line 28:
	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.		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		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

			<pre>
	1/\|G\| P(G; \sum w_i, \sum w_i^2, ...)		1/\|G\| P(G; \sum w_i, \sum w_i^2, ...)
			</pre>
	That is, replace each zr in the cycle-index polynomial with sum w_i^r and then divide by \|G\|, where \|G\| denotes number of elements in G.
			That is, replace each zr in the cycle-index polynomial with sum w_i^r and then divide by \|G\|, where \|G\| 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.		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 ~~gorup~~ 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 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.		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.

Admin: Created page with "{{FMM |title=One-Handed Chords |problem= The common 12-tone equal-tempered musical scale consists of a cyclically repeating sequence of 12 musical notes: C, Db, D, Eb, E, F,..."

2019-11-16T22:40:39Z

Created page with "{{FMM |title=One-Handed Chords |problem= The common 12-tone equal-tempered musical scale consists of a cyclically repeating sequence of 12 musical notes: C, Db, D, Eb, E, F,..."

New page

{{FMM
|title=One-Handed Chords
|problem=

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

<pre>
1 2 3 ... n ...
... n 1 2 3 ...
</pre>

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/|G| P(G; \sum w_i, \sum w_i^2, ...)

That is, replace each zr in the cycle-index polynomial with sum w_i^r and then divide by |G|, where |G| 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 gorup 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:

N(n,k) = 1/n sum_{d | n,k} phi(d) binom{n/d, k/d}

Values of this function are also symmetrical:

N(n, n-k) = N(n, k)

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.

}}