Ponder This

June 2009

<<May June July>>

2+mod(N_i,2) is 2 for i in an even length cycle and 3 for i in an odd length cycle. Since 14 is even, there are an even number of elements in odd cycles and an even number of elements in even length cycles. So the product is:

1. a multiple of 36 for permutations with mixed odd and even cycles;
2. 2¹⁴ for permutations with even-only cycles; and
3. 3¹⁴ for odd-only cycles.

Since 1299 divides 4³⁶-1, the remainder modulo 1299 of 4^x depends only on x modulo 36. So

1. permutations with mixed odd-even cycles contribute 1;
2. permutations with even-only cycles contribute 4**2¹⁴ = 4**{mod (2¹⁴,36)} (mod 1299) = 4⁴ (mod 1299) = 256; and
3. permutations with odd-only cycles contribute 4**3¹⁴ = 4**{mod (3¹⁴,36)} (mod 1299) = 4⁹ (mod 1299) = 1045.

Since the number of permutations with only odd cycles is the same as the number of permutations with only even cycles (Thanks to Vladeta Jovovic for suggesting this equality and to Eytan Sayag for the elegant proof) we have 256+1045 = 2 (mod 1299) from each pair so all together we get the sum of 14! (mod 1299) = 648.

Proving the equivalence between permutation of odd-only cycles and even-only cycles can be shown by writing the first in canonical form (sorting each cycle to start with the biggest element and sorting the cycles by their first element in descending order); then pairing them (if n is even, the number of odd-cycles should be even) and moving the last value from the second cycle of each pair after the last value of the first cycle in the pair. It is easy to show that this transformation is one-to-one from permutation with odd-only cycles to permutation with even-only cycles.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com