Return to Question

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.

Now it seems to me anecdotally that the number $M_n$ defined by $$M_n=\max_{K}{|A_K|}$$ is $o(n!)$. We have $$M_{10}\leq 0.35\cdot 10!$$ $$M_{11}\leq 0.32\cdot 11!$$ $$M_{12}\leq 0.27\cdot 12!$$ I'm looking for a good upper bound (not aymptotic) for $M_n$. This will be the amount of space required in my algorithm for computing the sequence http://oeis.org/A006245. 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.

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.

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.

Now it seems to me anecdotally that the number $M_n$ defined by $$M_n=\max_{K}{|A_K|}$$ is $o(n!)$. We have $$M_{10}\leq 0.35\cdot 10!$$ $$M_{11}\leq 0.32\cdot 11!$$ $$M_{12}\leq 0.27\cdot 12!$$ I'm looking for a good upper bound (not aymptotic) for $M_n$. This will be the amount of space required in my algorithm for computing the sequence http://oeis.org/A006245. 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.

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.

Now it seems to me anecdotally that the number $M_n$ defined by $$M_n=\max_{K}{|A_K|}$$ is $o(n!)$. We have $$M_{10}\leq 0.35\cdot 10!$$ $$M_{11}\leq 0.32\cdot 11!$$ $$M_{12}\leq 0.27\cdot 12!$$ I'm looking for a good upper bound (not aymptotic) for $M_n$. This will be the amount of space required in my algorithm for computing the sequence http://oeis.org/A006245. 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.

This is something that has come up in my research. 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]$. 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.

Now it seems to me anecdotally that the number $M_n$ defined by $$M_n=\max_{K}{|A_K|}$$ is $o(n!)$. We have $$M_{10}\leq 0.35\cdot 10!$$ $$M_{11}\leq 0.32\cdot 11!$$ $$M_{12}\leq 0.27\cdot 12!$$ I'm looking for a good upper bound (not aymptotic) for $M_n$. This will be the amount of space required in my algorithm for computing the sequence http://oeis.org/A006245. 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.

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.

Now it seems to me anecdotally that the number $M_n$ defined by $$M_n=\max_{K}{|A_K|}$$ is $o(n!)$. We have $$M_{10}\leq 0.35\cdot 10!$$ $$M_{11}\leq 0.32\cdot 11!$$ $$M_{12}\leq 0.27\cdot 12!$$ I'm looking for a good upper bound (not aymptotic) for $M_n$. This will be the amount of space required in my algorithm for computing the sequence http://oeis.org/A006245. 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.