Previously I asked a question about the space usage in an algorithm of mine: Upper bound on the number of permutations in a set during an algorithm. This question does not depend on the previous one, so no need to follow the link to proceed.

If the input to the algorithm is $n$, it computes the number of commutation classes of reduced words of the longest element of $S_n$.

In terms of speed the algorithm has been greatly improved, and the space usage has gotten a bit worse. The number of units of space seems to have gotten better, but this is cancelled out by the fact that the unit is inflated by a factor of $n-1$.

In any case, I estimate that the number of units of space it uses (which corresponds to a set of permutations) is about 1.25 times the number of permutations with $\lfloor \frac{n(n-1)}4\rfloor$ inversions. I'm wondering if someone can verify that for me.

We have a total ordering $<$ on $S_n$ such that $u<v$ if $u$ has fewer inversions than $v$ or if $u$ and $v$ have the same number of inversions and $u$ comes before $v$ in lexicographical order. The relevant part of the algorithm for my question is as follows, which constructs sets $A_N\subset S_n$:

- Let $A_0=\{e\}$, the set containing the identity.
- Construct $A_N$ as follows. Let $u$ be the minimal element in $A_{N-1}$ (so it has the fewest inversions, and among those it comes first in lexicographical order). Add all elements of $A_{N-1}$ to $A_N$ except for $u$. For each $i$ with $u(i)<u(i+1)$, add $u\cdot (i,i+1)$ (that is, add all permutations gotten from $u$ by flipping one ascent).

Can anyone verify that $$M_n=\max_N |A_N|$$ is roughly $1.25I_n$, where $I_n$ is the number of permutations with half as many inversions as the longest element?

It's easy to see that $$I_n\leq M_n<2I_n$$ The lower bound is because when we remove the last element with a given number of inversions, what's left is exactly the set of elements with one more inversion. The upper bound is because we are storing at most two levels at a time, and the largest level has size $I_n$.

To clarify at bit more what I'm saying, I've observed that $$M_n\approx 1.25I_n$$ For $n=12,13$. I'm trying to figure out if this trend continues.

By the way, $I_n$ is the largest Mahonian number for $S_n$, equal to the coefficient of $q^{\lfloor n(n-1)/4\rfloor}$ in $$\prod_{i=1}^n \frac{1-q^i}{1-q}$$