Number of permutations in a set in an algorithm

Question

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$:

1. Let $A_0=\{e\}$, the set containing the identity.
2. 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}$$

Answer 1

The idea is here but not correctly expressed. I leave it until I can find a better way to present it.

This is much like the other problem, now restricted to permutations with at most two involution sizes. I will talk about the case where things are symmetric, where n(n-1)/4 is not an integer, and the number of permutations with one more involution is the same as the number of permutations with that number of involutions. I will leave the asymmetric case to you.

Since you are processing these (permutations with smaller involution size) in lexicographic order, all the ones beginning with 1 will be processed first. As a result, you can divide this part of the process into n pieces where the kth piece contains all permutations with first coordinates greater than k and second coordinate k or less (but restricted to the two involution sizes).

Actually that last sentence is incorrect. One moves from members with smaller involution count with first coordinate k or less to members with one more involution count, where either the first or the second coordinate is k or less. The following still has some meaning, but at present It is not so clear that one can get 1.25 from it.

Since the distribution of these permutations varies with the first coordinate and second coordinates, the situation is not quite as clean, but you should get that the maximal value occurs near when k is near floor(n/2). Again this involves about a fourth of the set, but you should take care for this part to show that the variation is not too severe.

The asymmetric case will be different but hopefully not much. Be sure to look at "entering" (adding to) the class that has the most members of that number of involution, as well as "leaving" (taking from) that class.

Gerhard "Some Things Withstand Time Tests" Paseman, 2018.01.01.