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.



Number of Boolean algebra subintervals in weak order of $S_n$
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.


