I'm wondering if anybody has an easy way to compute the number of subintervals in weak order of $S_n$ (considered as a Coxeter group of type $A_{n-1}$) that are isomorphic to Boolean algebras. I know $[u,v]$ is such a subinterval if and only if $u\leq v$ and $vu^{-1}$ is a product of adjacent transpositions that pairwise commute with each other. Any insight is appreciated.
1 Answer
$\begingroup$
$\endgroup$
4
This is Exercise 3.185(h) in my book Enumerative Combinatorics, vol. 1, second ed. If $f(n,i)$ denotes the number of intervals in the weak order of $S_n$ that are isomorphic to boolean algebras of rank $i$, then $$ \sum_{n\geq 0}\sum_{i\geq 0}f(n,i)q^i\frac{x^n}{n!} = \frac{1}{1-x-\frac 12 qx^2}. $$ Putting $q=1$ shows that the total number $f(n)$ of boolean intervals satisfies $$ f(n+1)=(n+1)f(n)+{n+1\choose 2}f(n-1). $$ Unfortunately no solution is included.
-
$\begingroup$ Thanks. I've expressed the number of commutation classes of reduced words for the longest element as a determinant, and I think I could organize this into a bound with Hsdamard's inequality. I'm thinking the bound will probably be trivial, but we'll see. $\endgroup$ Nov 2, 2016 at 23:51
-
$\begingroup$ @MattSamuel: What is the determinant? This could be interesting for its own sake if it isn't too big or complicated. $\endgroup$ Nov 3, 2016 at 0:22
-
$\begingroup$ The element $C$ of the incidence algebra such that $C(u,v)$ is the number of commutation classes of $vu^{-1}$ is the inverse of a very simple element of the incidence algebra, namely $C^{-1}(u,v)=0$ unless $[u,v]$ is a Boolean algebra, in which case $C^{-1}(u,v)=(-1)^{\ell(u,v)}$. $\endgroup$ Nov 3, 2016 at 0:27
-
$\begingroup$ For further information about this problem, see arxiv.org/abs/2306.14734 $\endgroup$ Oct 18, 2023 at 17:16