Simple Permutations

One of the properties associated with my diurnal age today (28146) is that it's a member of OEIS A111111:

A111111: number of simple permutations of degree \(n\).

The initial members of this sequence beginning with \(n=1\) up to \(n=9\) are 1, 2, 0, 2, 6, 46, 338, 2926 and 28146.

I did not understand the explanation in the OEIS comments about what a simple permutation of degree \(n\) was so I turned to Gemini for help and its response forms the content of this blog post. I got NotebookLM to create a video overview of the post and then uploaded it to YouTube.

Understanding Simple Permutations

To understand OEIS A111111, it helps to think of the problem in terms of finding "hidden chunks" or "blocks" within a sequence of numbers.

The core rule is this: a permutation is simple if you cannot find any contiguous sub-sequence of length 2 or more (but less than the total length) that contains a continuous range of numbers, regardless of the order those numbers appear in.

Deconstructing the Example: 2647513

The comment in the sequence notes that the permutation 2647513 is not simple because of the interval of indices [2..5]. Let's map the positions (indices) to their actual values.

• Position 1: 2
• Position 2: 6
• Position 3: 4
• Position 4: 7
• Position 5: 5
• Position 6: 1
• Position 7: 3

If we look strictly at positions 2 through 5, the numbers present are 6, 4, 7, and 5. If we sort that subset of numbers, we get 4, 5, 6, 7. This forms a perfect, unbroken mathematical sequence (an interval). Because we found a contiguous block of positions that maps to a contiguous block of values, and this block is smaller than the entire sequence but larger than a single number, the permutation fails the test. It is not simple.

Why is n=3 exactly 0?

Looking at the sequence (1, 2, 0, 2, 6, 46...), the third term is 0. This means there are absolutely zero simple permutations of length 3. We can prove this by testing all six possible permutations of the numbers 1, 2, and 3:

• 123: Positions 1-2 contain {1, 2}. (Fails)
• 132: Positions 2-3 contain {3, 2}, which sorts to {2, 3}. (Fails)
• 213: Positions 1-2 contain {2, 1}, which sorts to {1, 2}. (Fails)
• 231: Positions 1-2 contain {2, 3}. (Fails)
• 312: Positions 2-3 contain {1, 2}. (Fails)
• 321: Positions 1-2 contain {3, 2}, which sorts to {2, 3}. (Fails)

Every single permutation of length 3 contains an embedded chunk of length 2 that forms a continuous range. Therefore, none of them are simple.

The n=4 Case: The Two Survivors

The sequence tells us there are exactly 2 simple permutations for n=4. Out of the 24 possible combinations, only two survive the test: 2413 and 3142.

Let's test 2413 to see why it passes:

Check all chunks of length 2:

• Positions 1-2: {2, 4} — Gap between 2 and 4.
• Positions 2-3: {4, 1} — Gap between 1 and 4.
• Positions 3-4: {1, 3} — Gap between 1 and 3.

Check all chunks of length 3:

• Positions 1-3: {2, 4, 1} — Sorts to {1, 2, 4}. Missing the 3.
• Positions 2-4: {4, 1, 3} — Sorts to {1, 3, 4}. Missing the 2.

Because no sub-sequence forms an unbroken chain of numbers, 2413 is a simple permutation. The same logic applies to 3142, making them the only two simple permutations of degree 4.

I then asked Gemini the following:

So in the case of n=9 we are looking at all permutations of the digits 123456789 and finding that there are 28146 simple permutations? Is that correct? Also, can you explain what is meant by a permutation of degree n. Is there a formula for calculating the number of simple permutations of degree n? 

The n=9 Case

For n=9, you are looking at all possible arrangements of the digits 1 through 9. There are 362880 total possible permutations for those nine digits (which is 9 factorial). If you were to test every single one of those 362880 arrangements for hidden consecutive blocks, you would find that exactly 28146 of them are simple permutations.

What is a "Permutation of Degree n"?

In combinatorial mathematics, the "degree" simply refers to the total number of elements in the set you are arranging.

• A permutation of degree 4 means you are finding the arrangements of a set containing exactly 4 distinct items (usually the integers 1, 2, 3, and 4).
• A permutation of degree n just means you are arranging the integers from 1 up to n.

It is just a formal way of stating the length of the string of numbers you are working with.

Is There a Formula?

There is no simple, single-line closed-form algebraic formula to instantly calculate the exact number of simple permutations for a specific degree. You cannot just plug n into a basic equation to get the answer.

Instead, mathematicians calculate exact values using generating functions and recurrence relations. The foundational logic is based on substitution decomposition: the idea that every standard permutation can be uniquely constructed by taking a simple permutation and "inflating" its individual points with other, smaller permutations. By knowing the total number of permutations (n!), mathematicians can work backward recursively to strip away the complex ones and isolate the count of simple ones.

However, there is a very elegant asymptotic formula for this sequence.

As the degree n becomes very large, the number of simple permutations, denoted as \( S_n\), can be approximated by:$$ S_n \approx \frac{n!}{e^2}$$Here, e is Euler's number. Because e² is approximately 7.389056, this formula reveals a fascinating property of permutations: as the length of the number string approaches infinity, the probability that a randomly generated permutation will be simple approaches 1 / e², or roughly 13.53%.

So, while calculating the exact integer for a specific degree requires heavy recursive computation, calculating the approximate scale of simple permutations for massive degrees is surprisingly straightforward.

I asked Gemini to give an example for the case of \(n=9\):

An Example for \(n=9\)

Here is one of the 28146 simple permutations of the digits 1 through 9:

4 1 7 3 9 6 2 8 5

To verify that this permutation is simple, we can apply the same logic used previously. We must ensure that no subset of contiguous positions (from length 2 up to length 8) contains a continuous range of values.

Why This Example Works

The easiest way to prove it is simple is to test the difference between the highest and lowest values within various blocks. If the difference between the maximum and minimum values in a block equals the length of the block minus 1, it forms a continuous interval.

• Testing Length 2 Blocks: Let's look at the adjacent pairs: {4, 1}, {1, 7}, {7, 3}, {3, 9}, {9, 6}, {6, 2}, {2, 8}, and {8, 5}. None of these pairs are consecutive numbers. The smallest gap is 3 (between 1 and 4, 6 and 9, 5 and 8). Because no pair has a difference of exactly 1, there are no length 2 intervals.
• Testing Length 4 Blocks: If we take the first four positions (4, 1, 7, 3), the highest value is 7 and the lowest is 1. The span is 6, which is much larger than the block length of 4. If we take the last four positions (6, 2, 8, 5), the highest is 8 and the lowest is 2. The span is 6. Because the numbers are scattered, they do not pack tightly enough to form an interval.
• Testing Length 8 Blocks: If we take the first eight numbers (4, 1, 7, 3, 9, 6, 2, 8), the values range from 1 to 9. The only missing number is 5. Because 5 is missing from the middle of the set, the remaining numbers cannot form an unbroken sequence. The same applies to the last eight numbers (1, 7, 3, 9, 6, 2, 8, 5), which are missing the 4.

Because this "scattering" holds true for every possible block size between 2 and 8, the permutation strictly avoids all intervals and perfectly satisfies the definition of a simple permutation.

I asked Gemini the following: 

Of what use are simple permutations? Are there any practical applications or is the concept purely theoretical.

While simple permutations originated as a purely theoretical concept in combinatorial mathematics, they have proven to be surprisingly useful in several practical, real-world applications. Because mathematics is the language of structure, these "irreducible" sequences provide the foundational logic for any field that needs to analyze, dismantle, or scramble data.

Here is a breakdown of how simple permutations bridge the gap between pure theory and practical application.

The "Prime Numbers" of Permutations (Theoretical Foundation)

Before looking at applied fields, it is helpful to understand their role in pure mathematics. Just as every integer can be factored into a unique set of prime numbers, every single permutation can be uniquely broken down into a "tree" of simple permutations through a process called substitution decomposition. In this sense, simple permutations are the fundamental, indivisible building blocks of all mathematical sequences.

Bioinformatics and Evolutionary Genomics

One of the most robust practical applications of this concept is in computational biology, specifically regarding genome rearrangement.

When scientists compare the DNA sequences of different species, they look at how chunks of genes have moved around over millions of years of evolution. A sequence of genes in a fruit fly might be a permuted version of the same genes in a mosquito. If a block of genes moves together as a single, unbroken unit during evolution, it forms an "interval" (meaning the permutation of that genome is not simple).

Simple permutations represent the extreme cases of genetic mutation: complete and total structural rearrangement where no contiguous blocks of genes have been preserved intact. By programming algorithms to search for and isolate these simple permutation structures, geneticists can map exactly where and how evolutionary divergence occurred.

Computer Science and Algorithm Optimization

In computational analysis, particularly when writing custom data analysis scripts in Python or SageMath, efficiency is critical. Because every complex sequence can be mathematically decomposed into a structural tree of simple permutations, computer scientists use these trees to drastically speed up sorting and search algorithms.

Problems involving "permutation pattern matching" that would normally take an impossible amount of exponential computing time can often be reduced to manageable polynomial time. The algorithm simply breaks the massive dataset down into its simple permutation components first, and then solves the problem on those smaller, irreducible blocks.

Cryptography and Data Diffusion

A secure cryptographic cipher relies on two primary principles: confusion and diffusion. Diffusion requires that a small, localized change in the input data is spread completely across the entire output data.

Because the strict definition of a simple permutation means it perfectly avoids forming neat, predictable blocks of adjacent numbers, it represents a state of maximum "scattering." This mathematical framework helps cryptographers design the substitution-permutation networks (the architecture behind modern encryption standards like AES) that resist pattern analysis and keep digital communications secure.

While you may never see a simple permutation explicitly named in a piece of commercial software, the mathematical rules governing them are silently working behind the scenes to optimize data, track genetic history, and secure information.