Permutations

# Permutation Zendo

Permutation Zendo refers to a Zendo game where the koans consist of digits from 1 (or 0) to some number, with each digit appearing exactly once in the koan. For example, if the digits are 1 to 8, then 32817564 is a valid koan, but neither 43825 (not all digits used) nor 2371118564 (repeated digits) nor 1234567890 (extra digits) are allowed.

It is now customary to include the cycle notation when submitting koans. Permutations can be thought of as a function (so the example 32817564 from earlier is a function that sends 1 to 3, 2 to 2, 3 to 8, and so on). This allows analysis of how the inputs are moved around when the function is applied repeatedly. For example, with 32817564, the input 1 is sent to 3, 3 is sent to 8, 8 to 4, and 4 to 1. These four numbers form a cycle. There is another cycle in that function, of length 3 (5 => 7 => 6 => 5), and 2 maps to itself, which is sometimes called a cycle of length 1, but is sometimes ignored. This information can be written compactly as (1384)(576). An equivalent notation is (8413)(765), because the initial number in each cycle is irrelevant, but they are usually written with the smallest digit first.

## Properties of Koans

Permutations have a number of properties, many of which are easier to determine from the cycle notation. For example, the order of a permutation is the minimum number of iterations required before ALL inputs are moved back to their original positions. For example, the order of the permutation 3124 is 3, because 4 always stays put, and the remaining numbers are part of a 3-cycle, so cycling it 3 times will move every number back where it started.

Wait, what?! OK: for 3124, 1 goes to 3, 2 goes to 1, 3 goes to 2, and 4 goes to 4:

1. Applying the function once sends 1 to 3. Applying it a second time moves 1 to 2 (because it went to 3, and the second time it went to wherever 3 would normally go). Applying it a third time moves 1 to 1.
2. 2 is sent to 1, then 3, then 2.
3. 3 is sent to 2, then 1, then 3.
4. 4 is always sent to 4.

Therefore, the order of 3124 is 3. In fact, the order of any cycle is simply the length of the cycle. For a permutation composed of several cycles, like (1384)(576), the order would be the least common multiple of 4 and 3, i.e. 12. (After 4 and 8 times, the 4-cycle resets but the 3-cycle has not. Similarly, after 3, 6, or 9 iterations, 567 are in place but 1348 are moved. Only after 12 do all eight digits return to their homes.)

Similarly, the order of a digit in the permutation is the length of the cycle it is part of.

## Permutation Cycle Generator

Type your permutation into the first box (example: 32817564). In the second box, enter the base permutation, usually 12345678 or similar. (However, if playing a 10-digit permutation game, make sure you check with the master whether the base is 1234567890 or 0123456789, as this can make a difference.)