**Question**

What are the various cyclic permutational suites containing a given permutation of distinct elements? This question has some importance in serial music where permutations can then be chosen according to their ability to lead to one another by means of their cyclic suites. I present a method below that could perhaps be refined for an automated algorithm. It’s however not straightforward enough to be expressed in code at this stage. Any suggestion will be most welcome in this perspective. Examples in this post are made with the help of scripts provided in the Code section of this blog.

**I. Definitions**

**D0 The B Set. **There are b figures available in base b, from which are made b! permutations of distinct elements (also called series), components of the B set.

Ex.:

$./permute 012

Computing permutations of 012 .. (Psiz=3)

012

021

102

120

201

210

6 permutations done in 0.00 s.

**D1 Cycle. **A cycle C is the cyclic suite stemming from a given permutation p of distinct elements.

Ex.:

$ ./gradual.pl 2130 1

2130 3102 0123

**D2 Power. **The power of any permutation is its position in a cycle.

Ex.:

$ ./compose.pl 2130 2130

3102

**D3 Root. **For each permutation in a cycle, the permutation of power 1 is called the root.

**D4 Natural Series. **The natural series S is the last permutation in each cycle. It is simply the ordered list of signs used by a permutation in the corresponding base b.

Ex.:

$ ./gradual.pl “2130” 1

2130 3102 0123

**D5 Degree. **The degree of a permutation p is the number of permutations contained in the cycle of which p is the root.

Ex.:

$ ./gradual.pl “2130”

3

**D6 Partition.** The partition (or elementary partition) P of a given permutation p is made of disjointed subsets of signs of S permuted in p and called “uplets”. The smallest of these subsets are singletons (designing occurences of non permuted signs). The order of elements of a partition is irrelevant. What qualifies a permutation p qualifies also most of the time the corresponding partition P, mutatis mutandis (for example, a partition will be said higher or lower in a suite according to the power of the corresponding permutation).

Ex.:

$ ./uplets.pl 2130

230 1

** D7 Uplet.** An uplet (n-uplet, n-tuple), is a subset in a partition (usually greater than a singleton). An uplet represents a specific chain of independent binary substitutions which is not alteredd by other permutations applied to S in order to end in a permutation p. An uplet U1 higher or lower than an uplet U2 is an uplet whose signs pertain to U2, element of a partition repectively higher or lower.

**D8 Pair.** A pair is an uplet of 2 signs.

**D9 Term.** The term is the last sign in an uplet.

**D10 Prime Cycle.** A prime cycle C is a cycle whose root partition is a single uplet showing the cardinality of a prime number; C contains each root of each of its member permutations and excludes other permutations.

Ex.:

$ ./gradual.pl 5264013 1

5264013 1630524 2345160 6401235 3052641 4516302 0123456

**D11 Miror.** The miror of a partition P in a cycle is a partition containing the same uplets as P, but in each one, the chain of signs preceding the term is reversed.

Ex.:

$ ./uplets.pl 4516302

4362150

$ ./uplets.pl 5264013

5126340

**D12 Type.** The type T of a partition P is a description of the content of P in size and quantity of its uplets. A type T1 is said higher than a type T2, as soon as appears in T1 starting from the right, a figure greater than its value in T2.

Ex.:

./type.pl 1645230

0210000

**II. Observed regularities (taken as postulates)**

**A0 Relation between partitions and the root.** There is a relation of transformation between the uplets of a root partition and the uplets of higher partitions in the cycle. Each uplet of the root can only be transformed in equal uplets of lower cardinality or remain the same. The uplet is divided by the greatest divisor common to its number of signs and the power of the partition.

Ex.:

**A1 Permanency of singletons.** Singletons of a root partition remain identical in all permutations of a cycle.

Ex.:

$ ./gradual.pl 3125064 1

3125064 5126340 6124503 4120635 0123456

$ ./uplets.pl 3125064

35640 1 2

$ ./uplets.pl 5126340

54360 1 2

$ ./uplets.pl 6124503

63450 1 2

$ ./uplets.pl 4120635

46530 1 2

$ ./uplets.pl 0123456

0 1 2 3 4 5 6

**A2 Transformation of pairs.** Pairs of a root partition are split in singletons in each partition of the cycle with an even power.

**A3 Complete Cycle.** The cycle of a permutation p whose root shows the same type as p, contains the total set of permutations involving p in their cycles. This is namely the case of prime cycles.

Ex.: see Example 3 below.

**A4 Types and the root.** The type of a partition can only be equal or lower than the type of its root.

**A5 Criterion of the mirrors.** A partition endowed with an odd uplet or a single uplet is always accompanied by a mirror of itself within the same cycle.

**A6 Uplet Translation.** Each uplet is equivalent to one of its horizontal translations.

**A7 Term of an uplet.** There is always a higher uplet showing (possibly after translation) the same term as its lower uplet in the root.

**A8 Power Index.** When the term of a first uplet in a root is chosen as equivalent to the term of a first uplet in a higher partition (by A6 and D5), then the figure located at the index of the power of the higher permutation, in the root is the same as the first figure in the higher uplet.

**A9 Transitivity.** If a root P1 contains a partition P2 within its cycle then the root of P1 contains P2 within its own cycle too.

**A10 Reflexivity.** Each permutation is a root for itself.

**A11 Symetry.** A mirror is a root for its reflection.

**III. Application**

**Example 1**

**1.0 Statement**

We are searching the roots of permutation p = 43012 whose partition P = 420 31 and type T = 01100.

**1.1 Determine the type of roots**

Each uplet of a root can only be divided in equal parts in a higher partition, therefore, p having an odd base, a root of a single uplet can’t stand below P. (A0)

Neither can P be partition of power 2, because then:

- its root r should contain a 4-uplet and a singleton but this is impossible due to (A1)

- or r should contain a pair but this is impossible due to (A2)

Finally as the type of a root can only be greater or equal to the type of a higher partition, we find that P shares the type of its roots. (A4)

**1.2 Find the roots**

It suffices here to find the other member of the cycle of p, due to (A3). We could also proceed with the method shown in example 2 and that would illustrate A3.

**1.3 Verification**

./contents.pl "01234" "0" "43012" "gradual" Gradual suite of 23410 contains 43012 and its elementary partition is: 240 31 Gradual suite of 43012 contains 43012 and its elementary partition is: 420 31

**Example 2**

**2.0 Statement**

Find roots of permutation p = 104523 whose partition P = 10 42 53.

**2.1 Find the types of roots**

As each uplet of a root can be divided in equal parts in a higher partition, P being made of equal parts, there exist one or several roots of P differing from P. (A1)

An obvious root of P is made of a 6-tuple. But this root can’t precede immediately p because 3 is not a common divisor of 6 and 2. Therefore p’s power is a multiple of 3 and its root partition is made of a single uplet (or identical to itself). (A0,A2)

But p’s power can’t be greater than 3 because 4 and 5 are not multiples of 3 and 6 leads to the end of any cycle whose root is a single 6-tuple.

**2.2 Find the roots**

As on one hand there is always a lower uplet showing the same term as its root uplet and on the other hand a single uplet root is candidate to permutations that are not translations, one can infer that there are several 6-tuple roots for p. (A7,A6,A12)

As each root contains 0 and every root equals its horizontal translation, one can choose 0 as term for every 6-tuple root and 10 as first uplet of P. (A6,D5)

Then for each 6-tuple root, 0 is the last figure and 1 the third. (A7,A8)

**Method:**

We draw 6 empty boxes corresponding to the figures in our 6-tuple. We start by the the first known figure which is 1 and place the term of our 6-tuple. Then we jump to the third box to the right (3 being our root uplet divisor), starting again from left as needed, except if our last figure was the term of any uplet in P. In these last cases we don’t fill the third box but the next one:

**R2:
**

- ######
- ##1### (by A8) now from 1 we jump over the last 3 boxes,and take the next figure in P, i.e. 0, to fill the next box i.e. the last one:
- ##1##0 as 0 was chosen as term we knew that already…
- 4#1##0 as our last figure was a term we didn’t jump this time;
- 4#12#0 4 was not a term so we wrote 2 in the third box to the right of it;
- 4#1250 2 was a term so we didn’t jump and wrote 5 next to it;
- 431250 last jump and we’ve got a first root, let’s call it P2 (as P1 equals P by A10);

(Beware: this is not a permutation, but a partition, the corresponding permutation being 425130).

The other roots in this subset are easier to define since we know that they’re all made of 6-tuples. They will appear with the same method, varying the order of figures (horizontal translations) and uplets in P. We just keep one stable uplet in P, the first one, ensuring the horizontal coherence of the resulting partitions.

**R3:** As R2 but translating the 2nd pair: (A6)

##1##0 > 2#1##0 –> 2#14#0 > 2#1450 –> 231450 = R3

**R4:** As R2 translating the 3d pair: (A6)

##1##0 > 4#1##0 –> 4#12#0 > 4#1230 –> 451230 = R4

**R5:** As R2 but translating the 2nd and 3d pairs: (A6)

##1##0 > 2#1##0 –> 2#14#0 > 2#1430 –> 251430 = R5

**R6:** As R2 but changing the order of pairs: (D5)

##1##0 > 5#1##0 –> 5#13#0 > 5#1340 –> 521340 = R6

**R7:** As R2 but changing the order of pairs: (D5)

##1##0 > 3#1##0 –> 3#15#0 > 3#1540 –> 321540 = R7

**R8:** As R3 but changing the order of pairs: (D5)

##1##0 > 5#1##0 –> 5#13#0 > 5#1320 –> 541320 = R8

**R9:** As R3 but changing the order of pairs: (D5)

##1##0 > 3#1##0 –> 3#15#0 > 3#1520 –> 341520 = R9

To these 8 root partitions can we add partition P as R1 because any permutation is its own root. This makes a set of 8 roots for p. (A10)

**2.3 Verification**

$ ./contents.pl "012345" "0" "104523" "gradual" Gradual suite of 104523 contains 104523 and its elementary partition is: 10 42 53 Gradual suite of 243150 contains 104523 and its elementary partition is: 231450 Gradual suite of 245031 contains 104523 and its elementary partition is: 251430 Gradual suite of 350412 contains 104523 and its elementary partition is: 341520 Gradual suite of 351204 contains 104523 and its elementary partition is: 321540 Gradual suite of 423051 contains 104523 and its elementary partition is: 451230 Gradual suite of 425130 contains 104523 and its elementary partition is: 431250 Gradual suite of 530214 contains 104523 and its elementary partition is: 541320 Gradual suite of 531402 contains 104523 and its elementary partition is: 521340

**Example 3**

**3.0 Statement**

Find roots of permutation p = 5264013 whose partition is P = 5126340.

**3.1 Find the types of roots**

Here we have a single uplet in a prime base, thus it’s a prime suite with 6 roots. (D10,A3)

**3.2 Find the roots**

We can simply trust A3 or rebuild the various roots with the same method as above:

As P has power 2, 5 will be put in second place, i.e. at index 1, and 0 will be the term of the uplet:

*(5126340) -> R2 skipping 1:*

#5##### -> #5#1### -> #5#1#2# -> 65#1#2# -> 6531#2#-> 653142#-> 6531420 = R2

As there is no further uplet to treat we can’t find new roots varying the order or horizontally translating the uplets. However as the root of a root of p contains p too, we can try to find the other roots recursively this way:

*(6531420) -> R3 skipping 1:*

#6##### -> #6#5### -> #6#5#3# -> 16#5#3# -> 1645#3#-> 164523#-> 1645230 = R3

(1645230) .. etc.

The simplest way with a prime root remains to extract the contents of its gradual suite directly:

$ ./gradual.pl ” 5264013″

5264013, 1630524, 2345160, 6401235, 3052641, 4516302, 0123456

**3.3 Verification**

./contents.pl "0123456" "0" "5264013" "gradual" Gradual suite of 1630524 contains 5264013 and its elementary partition is: 1645230 Gradual suite of 2345160 contains 5264013 and its elementary partition is: 2413560 Gradual suite of 3052641 contains 5264013 and its elementary partition is: 3254610 Gradual suite of 4516302 contains 5264013 and its elementary partition is: 4362150 Gradual suite of 5264013 contains 5264013 and its elementary partition is: 5126340 Gradual suite of 6401235 contains 5264013 and its elementary partition is: 6531420

**Example 4**

**4.0 Statement**

Find the roots of p = 0125346 whose elementary partition P = 0 1 2 543 6

**4.1 Determine the types of roots**

*Step 1:*

If P is a partition of power 2:

The root can’t contain two 3-tuples as one 3-tuple power 2 cannot become singletons this way. (A0)

The root can’t contain a 6-tuple either. (A0)

The root can only have groups of pairs and one 3-tuple. (A0)

Possible groups of pairs: (01,26) ou (12,06) ou (16,20) (A6)

*Step 2:*

At second stage the roots found this way will be shown to contain p in their gradual suites too. (A9)

These roots can afford a further 4-tuple plus a 3-tuple but the base does not permit lower rooting.

Finally we can postulate that a partition containing an odd uplet entails always a mirror partition in the gradual suite and this makes a new root because a mirror is always a root for its reflection. This adds one root to the set. (A5,A11)

**4.2 Find the roots**

*Step 1:*

3-tuples + pairs:

We can choose to place the 3-tuple in head of P and keep the term as 3:

**R2**: #5# > 45# > 453 …

let’s choose 2 pairs: 01 and 26:

453 01 26 = R2 et so with the 2 other groups of pairs: 453 12 06 = R3 et 453 16 20 = R4.

*Step 2:*

Each root in step 1 can be the power 2 in a suite whose root is made of a 4-tuple and a 3- tuple. (A0,A12)

Suppressing unuseful translations there remains the following possible 4-tuples:

0126, 0162, 1026, 1062, 1206, 1260, 2106, 2160, 1620, 1602, 6120,6102, in other words each group of pairs generates n/2*(n/2)! valid uplets, here 12. . (A0,A12)

*Step 3:*

One can now rely on partitions. Their suites will contain the wanted permutation:

For each 4-tuple we’ll get two partitions corresponding to the mirrors of 543, and this makes 24 different roots to which we can add the 3 groups of pair, multiplied by their own mirrors = 6 additional roots, plus p and its mirror = 32 roots.

**4.3 Verification **

./contents.pl "0123456" "0" "0125346" "gradual" Gradual suite of 0124536 contains 0125346 and its elementary partition is: 0 1 2 453 6 Gradual suite of 0125346 contains 0125346 and its elementary partition is: 0 1 2 543 6 Gradual suite of 0164532 contains 0125346 and its elementary partition is: 0 1 62 453 Gradual suite of 0165342 contains 0125346 and its elementary partition is: 0 1 62 543 Gradual suite of 0214536 contains 0125346 and its elementary partition is: 0 21 453 6 Gradual suite of 0215346 contains 0125346 and its elementary partition is: 0 21 543 6 Gradual suite of 0624531 contains 0125346 and its elementary partition is: 0 61 2 453 Gradual suite of 0625341 contains 0125346 and its elementary partition is: 0 61 2 543 Gradual suite of 1024536 contains 0125346 and its elementary partition is: 10 2 453 6 Gradual suite of 1025346 contains 0125346 and its elementary partition is: 10 2 543 6 Gradual suite of 1064532 contains 0125346 and its elementary partition is: 10 62 453 Gradual suite of 1065342 contains 0125346 and its elementary partition is: 10 62 543 Gradual suite of 1264530 contains 0125346 and its elementary partition is: 1260 453 Gradual suite of 1265340 contains 0125346 and its elementary partition is: 1260 543 Gradual suite of 1604532 contains 0125346 and its elementary partition is: 1620 453 Gradual suite of 1605342 contains 0125346 and its elementary partition is: 1620 543 Gradual suite of 2064531 contains 0125346 and its elementary partition is: 2610 453 Gradual suite of 2065341 contains 0125346 and its elementary partition is: 2610 543 Gradual suite of 2104536 contains 0125346 and its elementary partition is: 20 1 453 6 Gradual suite of 2105346 contains 0125346 and its elementary partition is: 20 1 543 6 Gradual suite of 2604531 contains 0125346 and its elementary partition is: 20 61 453 Gradual suite of 2605341 contains 0125346 and its elementary partition is: 20 61 543 Gradual suite of 2614530 contains 0125346 and its elementary partition is: 2160 453 Gradual suite of 2615340 contains 0125346 and its elementary partition is: 2160 543 Gradual suite of 6014532 contains 0125346 and its elementary partition is: 6210 453 Gradual suite of 6015342 contains 0125346 and its elementary partition is: 6210 543 Gradual suite of 6124530 contains 0125346 and its elementary partition is: 60 1 2 453 Gradual suite of 6125340 contains 0125346 and its elementary partition is: 60 1 2 543 Gradual suite of 6204531 contains 0125346 and its elementary partition is: 6120 453 Gradual suite of 6205341 contains 0125346 and its elementary partition is: 6120 543 Gradual suite of 6214530 contains 0125346 and its elementary partition is: 60 21 453 Gradual suite of 6215340 contains 0125346 and its elementary partition is: 60 21 543 32/5040.