Upper bound on the number of permutations in a set during an algorithm

Question

Fix $n\geq 2$ and let $S_n$ be the symmetric group on $n$ letters with identity $e$. We consider elements of $S_n$ to be bijections $[n]\to [n]$ as well as sequences (one line notation). For $1\leq i<n$, let $s_i$ be the transposition exchanging $i$ and $i+1$. Consider the following algorithm that successively constructs subsets $A_N\subseteq S_n$.

1. Let $A_0=\{e\}$.
2. At step $K$, remove the least element from $A_K$ in lexicographical order, say $f\in A_K$, and for each subset $B\subseteq [n-1]$ such that if $B=\{b_1,\ldots,b_m\}$, then $|b_i-b_j|\geq 2$ for all $i\neq j$ and $f(b_i)<f(b_{i}+1)$ for all $i$, add the permutation $fs_{b_1}s_{b_2}\cdots s_{b_m}$ to $A_K$. (In weak order, this will add all maximal elements of Boolean algebra intervals with minimal element $f$). After this one removal and all such additions we obtain the set $A_{K+1}$.

Step 2 is repeated until the ultimate set is empty. The penultimate set will contain only the longest element, the reversal permutation.

I'm interested in estimating the number $M_n$ defined by $$M_n=\max_{K}{|A_K|}$$ We have $$M_5\leq 0.32\cdot 5!$$ $$M_6\leq 0.3125\cdot 6!$$ $$M_7\leq 0.294\cdot 7!$$ $$M_8\leq 0.292\cdot 8!$$ $$M_9\leq 0.282\cdot 9!$$ $$M_{10}\leq 0.2811\cdot 10!$$ $$M_{11}\leq 0.2753\cdot 11!$$ $$M_{12}\leq 0.2749\cdot 12!$$ This will be the amount of space required in my algorithm for computing the sequence http://oeis.org/A006245. To me it seems $M_n$ is just as hard to compute as this sequence, which is why I'm looking for an estimate. I'm mostly interested in $n=16$, since this is the first unknown value. If $M_{16}$ is around $0.27\cdot 16!$, then it's not feasible at the moment to do the computation, whereas if it's $0.2\cdot 16!$ it might be.

Answer 1

I have bad news. The (constant for large n for your) upper bound will never drop below 1/4. Thus my prediction in a comment above will hold.

A key observation is that every permutation sits in one of the A_k, and so you will run through this n factorial times. One way to see this is that by induction every permutation of the smaller elements is generated, and then take up to n-1 steps to move the largest element in position. If I had known this yesterday, I could have answered sooner.

With this observation, we can see a key property. Setting m =(n-1)!, we process all the permutations beginning with 1 so that A_m has exactly those permutations with second element 1. One can then conclude the nature of A_jm: It is all permutations with first element larger than j and second element j or less. This gives a lower bound on the constant of (n-j)*j/(n(n-1)), which is bounded from below by 1/4 when j is floor(n/2).

You can extend this to analyze A_(jm +r) where r is a multiple of a smaller factorial. For a Starbucks card I might extend the analysis for you, especially if the sequence is algebraically related to M_n. For programming purposes, the idea that the upper bound is not far from 1/4 (maybe 1/4 times (1 + 1/(n-2)?) should suffice for your planning.

Gerhard "Proofreads For Starbucks Cards Too" Paseman, 2017.12.01.