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

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.

• I think the quickest answer will be to compute M13 through M15 first. I do not understand the description well enough to estimate it for you. (Sizes for small n, say n =6, as well as Ak for small k might help. Even knowing if Ak sizes is a unimodular sequence and for which k there is a peak might help.). I encourage you to post an answer with more detail, so that people can refer to the detail separately. Gerhard "Even Though Not An Answer" Paseman, 2017.11.30. – Gerhard Paseman Nov 30 '17 at 18:20
• In which of 4 possible directions does your lexicographical order go? (from the beginning or from the end, increasing or decreasing?) – fedja Nov 30 '17 at 18:55
• @fedja From the beginning, increasing. Literally alphabetical order. – Matt Samuel Nov 30 '17 at 19:02
• So $15423< 31452$, right? (just to make sure that we have no misunderstanding here) – fedja Nov 30 '17 at 19:05
• Might be worth looking at EC2: 4TB instances are available now (x1e.32xlarge) with 16TB in the pipeline. Of course you have to get your wallet out .. – J.J. Green Dec 1 '17 at 21:00

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.

• Thanks. I'm actually trying to compute $M_{13}$ because I realized there's a way to do it using far less memory. – Matt Samuel Dec 1 '17 at 20:05
• You're welcome. I recommend trying n=7 and n=8 and checking my characterization of A_jm. If I have it right, you can probably use it to speed up your computation of M16 as well. Gerhard "Don't Call It A Monster" Paseman, 2017.12.01. – Gerhard Paseman Dec 1 '17 at 20:21
• @MattSamuel Interesting. If we have such a clear idea of what $A_K$ are at least sometimes, why should we keep all their elements in the memory in the literal sense? If not a secret, how does your algorithm use them? – fedja Dec 2 '17 at 0:05
• @fedja It's not a secret. It's actually the iterative version of the Maple code on the sequence web page (which is recursive). You take the value at the node you remove and add it to the values at the nodes you add, with a sign of $(-1)^{|B|}$. The value at the identity is $1$ in the first step. The result is the final value at the longest element. – Matt Samuel Dec 2 '17 at 1:27
• Of course, I should add that for n=16, the constant is above 0.266666 (4/15), so it looks like you need to rearrange memory usage, perhaps writing to disk. Gerhard "Good Luck With Massive Computation" Paseman, 2017.12.06. – Gerhard Paseman Dec 6 '17 at 15:55