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.
![Inflation Definition](https://tanyakhovanova.com/BlogStuff/Combinatorics/InflationDefinition.png)
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.
Share:![Share on Facebook Facebook](https://blog.tanyakhovanova.com/wp-content/plugins/social-media-feather/synved-social/image/social/regular/48x48/facebook.png)
![Share on Twitter twitter](https://blog.tanyakhovanova.com/wp-content/plugins/social-media-feather/synved-social/image/social/regular/48x48/twitter.png)
![Share on Reddit reddit](https://blog.tanyakhovanova.com/wp-content/plugins/social-media-feather/synved-social/image/social/regular/48x48/reddit.png)
![Pin it with Pinterest pinterest](https://blog.tanyakhovanova.com/wp-content/plugins/social-media-feather/synved-social/image/social/regular/48x48/pinterest.png)
![Share on Linkedin linkedin](https://blog.tanyakhovanova.com/wp-content/plugins/social-media-feather/synved-social/image/social/regular/48x48/linkedin.png)
![Share by email mail](https://blog.tanyakhovanova.com/wp-content/plugins/social-media-feather/synved-social/image/social/regular/48x48/mail.png)
Angelo Scordo:
I can confirm your example of 3-inflatable permutations of size 17: E534BGA9HC2D1687F and B3CE1H76F5A49D2G8.
9 January 2019, 8:00 am