2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ As before, let m=(n-1)! Do you know what I_m is? I suspect I_m=M_m, and that for many easily comparable indices the sizes of I and M agree. It may be that the maximum over all indices of the sizes of I and M differ, but remember that what I gave is a lower bound. If that lower bound still holds for I, then it tightens the relationship between I and M. Gerhard "Start Off With A Bijection" 2018.01.01. $\endgroup$ Jan 1, 2018 at 19:02
  • $\begingroup$ @Gerhard $I_n$ is the coefficient of $q^{n(n-1)/4}$ in $\frac{\prod_{i=1}^{n}{(1-q^i)}}{(1-q)^n}$. $\endgroup$ Jan 1, 2018 at 19:08

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ I think I see what's going on, at least partially. It's not so simple. When we remove all the permutations that start with 1, we add those all back with one more inversion to the next level, plus we also add 21, 31, ..., etc. Depending on $n$, this could make it immediately significantly larger, and it's easy to write a formula for how much. Relative sizes are a bit harder to estimate. $\endgroup$ Jan 2, 2018 at 17:25
  • $\begingroup$ Using your idea I wrote a program that computes $M_n$ pretty quickly and the constant actually seems to be more like 1.28-1.3, and it happens after it processes permutations that start with $n/2$. $\endgroup$ Jan 2, 2018 at 21:03
  • $\begingroup$ That sounds like the makings of a good answer to me. I suggest posting a summary with some numerics, especially on how the permutations are distributed in bins by number of involutions and first coordinate. Gerhard "Maybe Richard Stanley Will Respond" Paseman, 2018.01.02 $\endgroup$ Jan 2, 2018 at 21:24
  • $\begingroup$ If only I had that kind of time. Maybe this weekend. I didn't become an academic and I got a job that requires me to work 12 hour days (part of that time is spent traveling to work, but basically I start working at 5:30 AM and stop at 5:30 PM or later). $\endgroup$ Jan 3, 2018 at 2:04
  • $\begingroup$ For n=300 the constant is 1.255. So it gets smaller, but not monotonically. $\endgroup$ Jan 3, 2018 at 23:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.