## 3-Inflatable Permutations

We can inflate one permutation with another permutation. Let me define the inflation by examples and pictures. Suppose we have a permutation 132 which we want to inflate using permutation 21. The result is the permutation 216543 that can be divided into three blocks 21|65|43. The blocks are ordered as the first permutation 132, and within each block the order is according to the second permutation. This operation is often called a tensor product of two permutations. The operation is non-commutative: the inflation of 21 with 132 is 465132.

As one might guess this post is related to *k*-symmetric permutations, that is, permutations that contain all possible patterns of size *k* with the same frequency. As I mentioned in my recent post 3-Symmetric Permutations, the smallest non-trivial examples of 3-symmetric permutations are 349852167 and 761258943 in size 9.

A permutation is called *k*-inflatable if its inflation with *k*-symmetric permutation is *k*-symmetric. One of my PRIMES projects was about 3-inflatable permutations. The result of this project is the paper On 3-Inflatable Permutations written with Eric Zhang and posted at the arxiv.

The smallest non-trivial examples of 3-inflatable permutations are in size 17: E534BGA9HC2D1687F and B3CE1H76F5A49D2G8, where capital letters denote numbers greater than nine. Another cool property discovered in the paper is that the tensor product of two *k*-inflatable permutations is *k*-inflatable.

## Angelo Scordo:

I can confirm your example of 3-inflatable permutations of size 17: E534BGA9HC2D1687F and B3CE1H76F5A49D2G8.

9 January 2019, 8:00 am