3-Symmetric Permutations

I want to study patterns inside permutations. Consider a permutation of size 4: 1432. Today I am excited by ordered subset of size 3 inside this permutation. For example, I can drop the last number and look at 143. The ordering in 143 is the same as in 132, or, as a mathematician would say, 143 is order-isomorphic to 132. In my example of 1432, I have four subsets depending on which number I remove: 432 is order-isomorphic to 321, while 132, 142 and 143 are all order-isomorphic to 132.

The density of a pattern 123 in the permutation 1432 is the ratio of subsets of size 3 that are order-isomorphic to 123 to all subsets of size 3. As I already calculated, the density of 123 in 1432 is zero, while the density of 321 is 1/4, and the density of 132 is 3/4.

A permutation is called 3-symmetric if the densities of all patterns of size 3 (123, 132, 213, 231, 312, 321) are the same. The reason I love this notion, is that 3-symmetric permutations are similar to random permutations with respect to patterns of size 3.

My example permutation, 1432, is not 3-symmetric. Thinking about it, no permutation of size 4 can be 3-symmetric. The number of subsets of size 3 is four, which is not divisible by 6.

I wanted to find 3-symmetric permutations. So the size n of the permutation needs to be such that n choose 3 is divisible by 6. The numbers with this property are easy to find. The sequence starts as 1, 2, 9, 10, 18, 20, 28, 29, 36, 37, 38, 45, 46. The sequence is periodic with period 36.

Any permutation of sizes 1 or 2 is 3-symmetric as all densities are zero. Duh!

The next interesting size is 9. My student, Eric Zhang, wrote a program and found that there are two 3-symmetric permutations of size 9: 349852167 and 761258943. These numbers are so cool!. First, they are reverses of each other. This is not very surprising: if a permutations is 3-symmetric, then its reverse must also be 3-symmetric. There is another property: the permutations are rotational symmetries of each other. That is, the sum of two digits in the same place is 10. You can see that rotating a 3-symmetric permutation produces a 3-symmetric permutation.

I decided to write a program to find 3-symmetric permutations of the next size: 10. There is none. I do not trust my programming skills completely, so adjusted my program to size 9 and got the same result as Eric. I trust Eric’s programming skills, so I am pretty sure that there are no 3-symmetric permutations of size 10. Maybe there are some 3-symmetric permutations in size 18.

Let’s find 2-symmetric permutations. These are permutations with the same number of ascends and descends inversions and non-inversions. For n to be the size of such permutation n choose 2 needs to be divisible by 2. That means n has to have remainder 0 or 1 modulo 4. The first nontrivial case is n = 4. There are six 2-symmetric permutations: 1432, 2341, 2413, 3142, 3214, 4123. We can also group them into reversible pairs: 1432 and 2341, 2413 and 3142, 3214 and 4123. If we look at rotational symmetry we get different pairs: 1432 and 4123, 2341 and 3214, 2413 and 3142.

You can try to find non-trivial 4-symmetric permutations. Good luck! The smallest nontrivial size is 33. Finding 5-symmetric permutations is way easier: the smallest nontrivial size is 28. The sequence of nontrivial sizes as a function of n is: 1, 4, 9, 33, 28, 165, 54, 1029, 40832, 31752, 28680, 2588680, 2162700, and so on. My computer crashed while calculating it.

Share:Facebooktwittergoogle_plusredditpinterestlinkedinmail

6 Comments

  1. Leo Broukhis:

    s/no any/none/

  2. Drake Thomas:

    The number of 2-balanced permutations of 4, 5, 8, 9 are 6, 22, 3836, 29228 respectively. The ones for 5 are 14532, 15342, 15423, 23541, 24351, 24513, 25143, 25314, 31542, 32451, 32514, 34152, 34215, 35124, 41352, 41523, 42153, 42315, 43125, 51243, 51324, 52134.

    I would expect these numbers to be a result of some simple computation, but they’re weird: 3836 has a factor of 137. Not sure what’s going on here, and it suggests a basic combinatorial argument probably won’t cut it (I was thinking something about viewing the permutation as a chosen breakpoint in a circular rearrangement of 1,…,n, since from that perspective everything is nice with respect to 2-balancing or its analogue, but this doesn’t seem to lead anywhere nice).

    There’s also something going on with the allowable cycle decompositions in these things ((a,b,c) means cycles of lengths a, b, c with multiplicity):
    * 4 only has (4) and (1,1,2)
    * 5 has (1,4) (2,3) (1,1,1,2)
    * 8 has (1,1,1,1,2,2) (1,1,1,5) (1,1,2,4) (1,1,3,3) (1,2,2,3) (2,2,2,2) (1,7) (2,6) (3,5) (4,4)
    I haven’t thought about this to tell whether the ones that don’t occur are trivially rules out by some simple consideration.

    Curiously enough, this sequence (both with added zeros and without) isn’t in the OEIS, nor is your list of nontrivial sizes; I would have expected something this simple to show up at least in the case of 2.

    I can also confirm your results for 3-balanced permutations of sizes 9 and 10.

  3. tanyakh:

    Drake,

    The sequence of the number of 2-balanced permutations is submitted, but is not approved yet. I was planning to submit more sequences on the subject.

  4. tanyakh:

    Thank you Leo,

    I fixed the typo.

  5. Drake Thomas:

    Some other notes:

    The reason that the number of permutations of 5 is not a multiple of 4 is because the pair 25314 41352 is closed under reversal AND element-wise inversion, so it only generates 2 permutations from the seed instead of 4. (This happens for 9 too, but the number of such pairs is 150, an even number.)

    Iterating through all permutations for large values is computationally intractable, so I checked some things probabilistically: none of 54,000,000 random permutations of 18 elements were 3-balanced, though with only one nontrivial datapoint it’s hard to tell what our expected density should be – there could easily be millions and I wouldn’t expect to have encountered any.

    At least one 2-balanced permutation exists for every multiple of 4: if n=4k, we take (1,2,…k,4k-k+1,4k-k+2,…,4k,4k-k,4k-k-1,….k+2,k+1). I’m less sure about things which are 1 mod 4; the similar pattern I tried breaks down in the 20s.

    The 3-balanced patterns for 9 have this nice structure if you plot them; you’ve got this symmetric structure about 5, with alternatingly increasing and decreasing runs of equal length. Sadly, this fails to be 3-balanced for 29, the next 3-valid number congruent to 1 mod 4.

  6. Tanya Khovanova's Math Blog » Blog Archive » 3-Symmetric Graphs:

    […] « 3-Symmetric Permutations […]

Leave a comment