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.



Upper bound on the number of permutations in a set during an algorithm
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.


