k$ or $i=k$ and $j$ and $<$ instead of $<$ and $\ge$. This yields \begin{equation} \G_\alpha \G_\beta = \G_\alpha \prec \G_\beta + \G_\alpha \succ \G_\beta\,, \end{equation} where \begin{equation}\label{eq:precG} \G_\alpha \prec \G_\beta = \sum_{\genfrac{}{}{0pt}{}{\gamma=uv \in \alpha*\beta} {|u|=|\alpha| ;\, \max(v)<\max(u)}} \G_\gamma\,, \end{equation} \begin{equation} \G_\alpha \succ \G_\beta = \sum_{\genfrac{}{}{0pt}{}{\gamma=u v\in \alpha*\beta} {|u|=|\alpha| ;\, \max(v)\geq\max(u)}} \G_\gamma\,. \end{equation} Then $x=\G_1$ generates a free dendriform algebra in $\FQSym$, isomorphic to $\PBT$, the Loday--Ronco algebra of planar binary trees~\cite[Prop.~3.7]{LR1} and~\cite[Prop.~5.3]{LR2}. The notations used here are those of~\cite{HNT}, where more details can be found. Recall that the shuffle product $\shuffle$ is recursively defined by \begin{equation}\label{eq:shuffle} ua\shuffle vb = (ua\shuffle v)b+(u\shuffle vb)a, \end{equation} where $a,b$ are letters and $u,v$ words. The scalar 1 (representing the empty word) is the neutral element. The shuffle can be split into two half-products $\prec$ and $\succ$ defined by \begin{equation} ua \prec vb = (u\shuffle vb)a, \ ua\succ vb = (ua\shuffle v)b, \end{equation} We shall not need dendriform products involving $1$ and thus leave these undefined. In terms of the dual basis $\F_\sigma:=\G_{\sigma^{-1}}$, \begin{align} \F_\alpha\F_\beta &= \sum_{\gamma\in \alpha\shuffle \beta[k]}\F_\gamma,\\ \F_\alpha\prec \F_\beta &= \sum_{\gamma\in \alpha\prec \beta[k]}\F_\gamma,\\ \F_\alpha\succ \F_\beta &= \sum_{\gamma\in \alpha\succ \beta[k]}\F_\gamma, \end{align} where $\alpha\in\SG_k$, $\beta[k]$ denotes $\beta$ with its entries shifted by $k$. There is an inclusion of Hopf algebras $\Sym\hookrightarrow \PBT$ of noncommutative symmetric functions into $\PBT$~\cite{LR1,LR2}, which is given by \begin{equation} S_n= (\dots((x\succ x)\succ x)\dots)\succ x\quad\text{($n$ times).} \end{equation} Indeed, the r.h.s is the sum of nondecreasing words, i.e., $\G_{1\ldots n}=S_n$. \subsection{A dendriform lift of the Bell recurrence} We shall define the free Bell polynomials as elements of $\K\ \otimes\FQSym$ by \begin{equation}\label{eq:recBB} \B_0=1,\quad \B_{n+1} = \sum_{k=0}^n Y_{k+1} S_{k+1} \prec \B_{n-k}, \end{equation} the $\otimes$ sign being omitted for notational convenience, and $\prec$ is actually $\cdot\,\otimes\prec$. Recall also that $S_{k+1}=\G_{1\ldots k+1}$. The first $\B_n$ are \begin{equation} \begin{split} \B_0 & = 1 \\ \B_1 & = Y^1\G_1 \\ \B_2 & = Y^2\G_{12} + Y^{11}\G_{21} \\ \B_3 & = Y^3\G_{123} + Y^{21}(\G_{132}+\G_{231}) + Y^{12}\G_{312} + Y^{111}\G_{321} \\ \B_4 & = Y^4\G_{1234} + Y^{31}(\G_{1243}+\G_{1342}+\G_{2341}) \\ &\,\quad+ Y^{22}(\G_{1423}+\G_{2413}+\G_{3412}) + Y^{211}(\G_{1432}+\G_{2431}+\G_{3421}) \\ &\,\quad+ Y^{13}\G_{4123} + Y^{121}(\G_{4132}+\G_{4231}) + Y^{112}\G_{4312} + Y^{1111}\G_{4321}. \\ \end{split} \end{equation} Clearly, for each $n\ge 0$, $\B_n$ is a (left) $\FQSym$-linear combination of the $Y^I$ for various compositions $I$ of $n$. The coefficient $C_I(A)$ of $Y^I$ in $\B_n$ is by definition in $\FQSym$ but is in fact in $\PBT$: \begin{lemm}\label{lem:CI} Let $I=(i_1,\dots,i_r)$ be a composition. Then $C_I(A)$ is equal to $\P_T$ where $T$ is the right-comb tree whose left branches have sizes from top to bottom equal to $i_1$, $i_2,\ldots,i_r$. \end{lemm} \begin{proof} The coefficient $C_I(A)$ is by definition equal to \begin{equation}\label{eq:lprod} S_{i_1}\prec (S_{i_2}\prec(\cdots (S_{i_{r-1}}\prec S_{i_r})\cdots). \end{equation} Let $n$ be $i_1+\dots+i_r$ and expand that product in $\FQSym$ on the $\G$ basis. Consider any permutation $\tau$ such that $\G_\tau$ occurs in the expansion. By definition of $\prec$, the first $i_1$ letters of $\tau$ are increasing and the $i_1$-th letter is $n$, then followed by a word whose standardization $\sigma$ belongs to $S_{i_2}\prec(\cdots (S_{i_{r-1}}\prec S_{i_r}))\cdots)$. Hence, by induction on $r$, the decreasing tree (see~\cite{LR1,HNT}) of all these elements is obtained by grafting the shape of the decreasing tree of $\sigma$ to the right of the root of a left branch of size $i_1$. Conversely, since any permutation of decreasing tree $T$ belongs to the left product~\eqref{eq:lprod}, this product is equal to $\P_T$. \end{proof} \begin{exem}\label{ex:Y221} The coefficient of $Y^{221}$ in $\B_5$ is \begin{align*} \G_{12}\prec (\G_{132}+\G_{231})&= \G_{15243}+\G_{25143}+\G_{35142}+\G_{45132}\\ &\quad\,+\G_{15342}+\G_{25341}+\G_{35241}+\G_{45231}\\ &=\P_{\includegraphics[scale=1]{fig2.pdf}} \end{align*} \end{exem} For a set partition $\pi$ of $[n]$, let $\pi^\flat$ be the set composition obtained by ordering the blocks w.r.t. their maximal values in decreasing order, and let $K(\pi)$ be the composition recording the lengths of these blocks. Let also $\hat\pi^\flat$ be the permutation obtained by reading the blocks in this order, where each block is read from the smallest to the largest element. \begin{exem} If $\pi = 347|28|1|56$, we have $\pi^\flat= 28|347|56|1$, so that $\hat\pi^\flat=28347561$, and $K(\pi)=(2,3,2,1)$. \end{exem} \begin{prop}\label{pr:CI} The coefficient of $Y^I$ in $\B_n$ is the sum of all $\G_{\hat\pi^\flat}$ where $\pi$ ranges over set partitions such that $K(\pi)=I$: \begin{equation} \B_n = \sum_{\pi\vdash [n]}Y^{K(\pi)} \G_{\hat\pi^\flat}. \end{equation} \end{prop} \begin{proof} This follows from the product rule~\eqref{eq:precG}. Indeed, as we have already seen, this coefficient is $S_{i_1}\prec (S_{i_2}\prec(\cdots (S_{i_{r-1}}\prec S_{i_r}))\cdots)$, which is the sum of $\G_\sigma$ over all permutations of the form $\sigma=u_1u_2\cdots u_r$, where each $u_j$ is an increasing word of length $i_j$ whose last letter is greater than all letters to its right. But these permutations are precisely the $\hat\pi^\flat$ for the set partitions $\pi$ such that $K(\pi)=I$. \end{proof} These permutations $\hat\pi^\flat$ are not those avoiding the pattern $1-32$ as above, but those avoiding the pattern $21-3$. As observed in~\cite[Prop.~1]{Cla}, there is a statistic-preserving bijection between both classes (in this case, the Sch\"utzenberger involution, which preserves the inversion number). Since the inverse major index and the inversion number are equidistributed on the set of permutations having a decreasing tree of a given shape~\cite[Thm.~2.7]{HNT2}, the generating polynomial of $\inv$ on $1-32$ or of $\imaj$ on $21-3$-avoiding permutations with descent composition $I$ is \begin{equation} c_I(q)=C_I\left(\frac1{1-q}\right) \end{equation} where the alphabet $\frac1{1-q}$ (the principal specialization of $\FQSym$) is defined by \begin{equation} A\mapsto \{q^n|n\ge 0\} \ \text{ordered by $q^i j$}. \end{equation} Indeed, \begin{equation} C_I\left(\frac1{1-q}\right) =\sum_{K(\pi)=I} \G_{\hat\pi^\flat}\left(\frac1{1-q}\right), \end{equation} and \begin{equation} \G_\sigma\left(\frac1{1-q}\right)=F_I\left(\frac1{1-q}\right) \end{equation} where $I$ is the descent composition of $\sigma^{-1}$. It is well-known (see~\cite[Lem.~5.2]{GeR} or~\cite[Prop.~5.10]{NCSF1}) the specializations of the fundamental quasi-symmetric functions are \begin{equation} F_I\left(\frac1{1-q}\right) =\frac{q^{\maj(I)}}{(q)_n}. \end{equation} where $\maj(I)=\maj(\tau)$ for any permutation $\tau$ of shape $I$. Thus, specializing the $\FQSym$ coefficients in $\B_n$, we obtain \begin{equation} (q)_n\B_n\left(\frac1{1-q}\right) = B''_n(q), \end{equation} since by definition, the recurrence~\eqref{eq:recBB} is a lift of~\eqref{eq:recBb}. Now that we understand that $c_I(q)$ is the principal specialization of a quasi-symmetric function, we can replace it by the commutative image $C_I(X)$ of $C_I(A)$ in $\QSym$. Recall that if the letters $a_i$ of our underlying alphabet $A$ are replaced by commuting variables $x_i$, then $\F_\sigma$ becomes the fundamental quasi-symmetric function $F_I(X)$ where $I$ is the descent composition of $\sigma$. \begin{exem} Recording the recoil compositions of the permutations occuring in $C_{221}$, we find \begin{equation} C_{221}(X)= F_{1121} + F_{1211} + F_{122} + F_{131} + F_{212} + 2F_{221} + F_{311}. \end{equation} This may be compared with the dual immaculate basis of~\cite{BBSSZ}: \begin{equation} \SG_{221}^*= F_{1121} + F_{113} + F_{1211} + 2F_{122} + F_{131} + F_{212} + F_{221}. \end{equation} \end{exem} \begin{theo}\label{th:dualimm} Define the bar involution on $QSym$ by $\overline{F_I} = F_{\bar I}$, where for $I=(i_1,\ldots,i_r)$, $\bar I =(i_r,\ldots,i_1)$ denotes the mirror composition. Then, the dual immaculate basis is given by \begin{equation} \SG_I^* = \overline{C_I(X)}. \end{equation} \end{theo} \begin{proof} According to~\cite[Prop.~3.37]{BBSSZ}, \begin{equation} \SG_I^* = \sum_T F_{D(T)} \end{equation} where the sum runs over all standard immaculate tableaux of shape $I$, and $D(T)$ denotes the descent composition of $T$ as defined in~\cite{BBSSZ}. This should not be confused with the usual descent composition of a permutation $\sigma$, which will be denoted by $C(\sigma)$. A standard immaculate tableau $T$ of shape $I$ is a planar representation of a set partition $\pi=(\pi_1,\ldots,\pi_r)$, whose blocks have been ordered in such a way that $\min(\pi_1)<\min(\pi_2)<\dots<\min(\pi_r)$, and such that $|\pi_j|=i_j$. For example, the standard immaculate tableaux of shape $I=(2,2,1)$ are \begin{equation} \young{1 & 5\\ 2& 4\\ 3\\}\ \ \ \young{1 & 5\\ 2&3 \\4 \\}\ \ \ \young{1 &4 \\ 2&5 \\ 3\\}\ \ \ \young{1 & 4\\ 2& 3\\ 5\\}\ \ \ \young{1 &3 \\2 &5 \\ 4 \\}\ \ \ \young{1 & 3\\ 2& 4\\ 5\\}\ \ \ \young{1&2\\3&5\\ 4\\}\ \ \ \young{1 & 2\\ 3& 4\\ 5\\} \end{equation} The descent composition $D(T)$ encodes the set $\{i|i+1\ \text{is in a lower row}\}$, which is therefore the recoil set of the permutation $\hat T$ obtained by reading the rows of $T$ from bottom to top and from left to right. The descent compostions $D(T)$ of the above tableaux are \begin{equation} 113,\ 122,\ 1121,\ 131,\ 122,\ 1211,\ 212,\ 221. \end{equation} These are the recoil compositions of the permutations $\hat T$ \begin{equation} 32415,\ 42315,\ 32514,\ 52314,\ 42513,\ 52413,\ 43512,\ 53412, \end{equation} whose descent compositions are obviously always $\bar I=(1,2,2)$. The Sch\"utzenberger involution $\nu$ sends a permutation $\sigma\in\SG_n$ to the permutation $\sigma'=\nu(\sigma)$ obtained by replacing each entry $i$ of $\sigma$ by $n+1-i$ and then reading the resulting word from right to left. In other words, $\sigma'= \omega\sigma\omega$, where $\omega=n\,n-1\cdots 21$. The effect of $\nu$ on descent compositions is the mirror image $C(\sigma')=\overline{C(\sigma)}$. Thus, for any standard immmaculate tableau $T$ of shape $I$ and descent composition $J$, applying $\nu$ to the permutation $\sigma=\nu(\hat T)$ yields \begin{equation} C(\sigma) = C(\nu(\hat T)) =\overline{C(\hat T)} = \overline{\bar I} = I \end{equation} while \begin{equation} C(\sigma^{-1})=\overline{D(\hat T)} = \bar J. \end{equation} Moreover, $\nu$ exchanges the maxima and the minima, so that the rows of the ribbon diagram of $\sigma$ form the blocks of a set partition $\pi=(\pi_1,\ldots,\pi_r)$ ordered in such a way that $\max(\pi_1)>\max(\pi_2)>\dots>\max(\pi_r)$, and $|\pi_j|=i_j$. That is, $\sigma=\hat\pi^\flat$ for a set partition such that $K(\pi)=I$. Therefore, \begin{equation} \SG_I^* = \sum_{K(\pi)=I}\overline{F_{K(\hat\pi^\flat)}}= \overline{C_I(X)}. \end{equation} On our running example, the permutations $\nu(\hat T)$ are \begin{equation} 15243,\ 15342,\ 25143,\ 25341,\ 35142,\ 35241,\ 45132,\ 45231. \end{equation} Their recoil compositions are, in order \begin{equation} 311,\ 221,\ 1211,\ 131,\ 221,\ 1121,\ 212,\ 122.\qedhere \end{equation} \end{proof} \begin{enonce}[remark]{Note} Theorem~\ref{th:dualimm} provides an expression of the dual immaculate basis very similar to the one obtained by Grinberg~\cite{Gri}. However, our dendriform operations are different. The relations between both constructions will be clarified in the forthcoming section. \end{enonce} \begin{coro} The $C_I(X)$ form a basis of $QSym$, so that the $\P_T$ indexed by right combs form a section of the projection $\PBT\rightarrow QSym$. \end{coro} \begin{coro} $c_I(q)$ is given by the Bj\"orner--Wachs $q$-hook-length formula~\cite{BW}: the inversion polynomial of the set of permutations having a decreasing tree of shape $T$ is given by the same hook length formula as for the inverse major index, which is \begin{equation} \sum_{{\mathcal T}(\sigma)=T}q^{l(\sigma)} = [n]_q! \prod_{v\in T}\frac{q^{\delta_v}}{[h_v]_q}\,, \end{equation} where $v$ runs over the vertices of $T$, $h_v$ is the number of vertices of the subtree with root $v$, and $\delta_v$ is the number of vertices in the right subtree of $v$. \end{coro} See~\cite{HNT2} for a short proof of the version used here. \begin{exem} For $I=221$, the hook-lengths $h_v$ of the right comb are $5,3,1,1,1$, and the cardinalities of the right subtrees are $3,1$. Hence, \begin{equation} c_{221}(q) = [5]_q!\frac{q^{3+1}}{[5]_q[3]_q[1]_q^3} ={q}^{4}+2\,{q}^{5}+2\,{q}^{6}+2\,{q}^{7}+{q}^{8}. \end{equation} \end{exem} Applying the Sch\"utzenberger involution $\nu$ to $C_I$ amounts to sending $\G_\sigma$ to $\check\G_\sigma= \G_{\omega\sigma\omega}$, so that we can also reformulate Theorem~\ref{th:dualimm} as \begin{equation} \check C_I(X)=\SG_I^*. \end{equation} \begin{coro}[\cite{BBSSZ2}] $\overline{\SG_I^*}$ is the characteristic of an indecomposable $0$-Hecke algebra module. \end{coro} \begin{proof} The inverses of the permutations occuring in $C_I(A)$ are the linear extensions of a poset (a binary tree in this case), hence form the basis of a $0$-Hecke module, see Section~3.9 of~\cite{NCSF6}. Thus, the commutative image $C_I(X)=\overline{\SG_I^*}$ of $C_I(A)$ in $QSym$ is the characteristic of this module. The same is true of their images by the Sch\"utzenberger involution, the poset being now a binary tree turned upside-down. Moreover, these modules are indecomposable, since they are of the form $\mathbf{N}_\sigma$ described in~\cite[Def.~4.3]{NCSF6}. Indeed, the right-comb tree associated with a composition $I$ is the shape of the decreasing tree of the maximal permutation $\omega(I)$ of the descent class $I$. This permutation (which is sent to $\omega(\bar I)$ by the Sch\"utzenberger involution) spans the (one-dimensional) socle of the module, which must be contained in any submodule, so that no submodule can be a direct summand. \end{proof} See~\cite{NCSF4} or~\cite{Thib} for an introduction to the representation theory of the 0-Hecke algebra. \section{The dual immaculate basis} \subsection{Half-shuffles and \texorpdfstring{$\FQSym$}{FQSym}} The shuffle product on $\K\$ can be recursively defined by~\eqref{eq:shuffle}: \begin{equation} ua \shuffle vb = (ua\shuffle v)b + (u\shuffle vb)a \end{equation} or symmetrically by \begin{equation}\label{eq:halfsh2} au \shuffle bv = a(u\shuffle bv) + b(au\shuffle v), \end{equation} where $a,b\in A$ and $u,v\in A^*$. The half-shuffles are also known as chronological products. Both ways of splitting the shuffle can be used to define a dendriform structure on $\FQSym$. In this section, we shall use the second possibility~\eqref{eq:halfsh2} and set \begin{equation} au\prec' bv = a(u\shuffle bv),\ \ \text{and}\ \ au\succ' bv = b(au\shuffle v). \end{equation} If $\gamma$ is a linear combination of some permutations $\rho$, we write for short $\F_\gamma$ for the same linear combination of the $\F_\rho$. On $\FQSym$, we set, for $\sigma\in\SG_k$ and $\tau\in\SG_l$ \begin{equation} \F_\sigma\prec' \F_\tau = \F_{\sigma\prec' \tau[k]},\ \text{and}\ \F_\sigma\succ' \F_\tau = \F_{\sigma\succ' \tau[k]}. \end{equation} Here, $\succ'$ coincides with Grinberg's $\succ$, which we will denote by $\succ_G$ to avoid confusions. \begin{lemm} For any two words $u$ and $v$, \begin{equation}\label{eq:halfsh} u\prec' v = \sum_{v_1v_2=v} (-1)^{|v_1|} (\overline{v_1}u) \shuffle v_2, \end{equation} where $\bar w$ denotes the mirror image of a word $w$. \end{lemm} \begin{proof} By definition \begin{equation} au\prec' bv = au\shuffle bv - au\succ' bv, \end{equation} and since \begin{equation} au\succ' bv = bau\prec' v, \end{equation} the result follows by induction. \end{proof} For example, \begin{equation} 1234\prec' 567 = 1(234 \shuffle 567) = 1234 \shuffle 567 - 51234 \shuffle 67 + 651234 \shuffle 7 - 7651234. \end{equation} In $\FQSym$, this implies \begin{equation}\label{eq:hsfqs} \F_\sigma\prec' \F_\tau = \sum_{uv = \tau[k]}(-1)^{|u|}\F_{(\bar u \cdot\sigma)\shuffle v}. \end{equation} For example, \begin{equation}\label{eq:exdend} \F_{2143}\prec'\F_{312} = \F_{2143\shuffle 756}-\F_{72143\shuffle 56}+\F_{572143\shuffle 6}-\F_{6572143}. \end{equation} \subsection{Descents in half-shuffles} For $w\in A^*$, let $\alph(w)\subseteq A$ be the set of letters occuring in $w$. The following property appears as Lemma~4.1 in~\cite{NTsuper}: \begin{lemm}\label{desshuf} If $\alph(u)\cap\alph(v)=\emptyset$, then \begin{equation} \=\\\,, \end{equation} where the linear map $\< \,\>$ is defined by $\ :=F_{C(u)}$, where $C(u)$ denotes the descent composition of the word $u$. In particular, the descents of the elements of a shuffle on disjoint alphabets depend only on the descents of the initial elements. \end{lemm} There is a refined statement for the dendriform half-products~\cite[Thm.~4.2]{NTsuper} that we adapt to our half-products: \begin{theo}\label{deshalf} Let $u=u_1\cdots u_k$ and $v=v_1\cdots v_\ell$ be two nonempty words of respective lengths $k$ and $\ell$. If $\alph(u)\cap\alph(v)=\emptyset$, then \begin{equation} \=\<\sigma\prec' \tau\> \end{equation} where $\sigma=\std(u)$ and $\tau=\std(v)[k]$ if $u_1v_1$. \end{theo} For example, we have \begin{equation} \begin{split} \<14\prec' 23\> &= \<1423+1243+1234\> = F_{22} + F_{31} + F_4 \\ \<12\prec' 34\> &= \<1234+1324+1342\> = F_4 + F_{22} + F_{31}, \end{split} \end{equation} whereas \begin{equation} \begin{split} \<24\prec' 13\> &= \<2413+2143+2134\> = F_{22} + F_{121} + F_{13} \\ \<34\prec' 12\> &= \<3412+3142+3124\> = F_{22} + F_{121} + F_{13}. \end{split} \end{equation} \subsection{Projection onto \texorpdfstring{$QSym$}{QSym}} Let $\pi:\ \FQSym\rightarrow QSym$ be the canonical projection sending $\F_\sigma$ to $F_{C(\sigma)}$. Then $\pi$ is compatible with the products of both structures, and we can define half-products $\prec'$ and $\succ'$ on $QSym$ in such a way that $\pi$ will be compatible with the half-products as well. This follows from an even more general trivial property. Let us consider $\sigma$ and $\sigma'$ having the same descents and $\tau$ and $\tau'$ also. Any word $w$ in the shifted shuffle $\sigma\ssh\tau=\sigma\shuffle \tau[k]$ ($\sigma\in\SG_k$) is characterized by the sequence of positions of the letters of $\sigma$. Then the word $w'$ in $\sigma'\ssh\tau'$ with the same sequence of positions of the letters of $\sigma'$ has obviously the same descents as $w$. Since it is true for all elements, it is in particular true when one sums over subsets of the shuffle, e.g., $\prec'$ and $\succ'$. Thus, if $C(\sigma)=I$ and $C(\tau)=J$, we can define in $QSym$ \begin{equation}\label{eq:QSdend} F_I\prec' F_J :=\pi(\F_\sigma\prec' \F_\tau). \end{equation} For example, \begin{equation} \F_{21}\prec' \F_{132} = \F_{21354}+\F_{23154}+\F_{23514}+\F_{23541}, \end{equation} so that \begin{equation}\label{eq:exgauF} F_{11}\prec' F_{21} = F_{131}+ F_{221}+ F_{32}+ F_{311}, \end{equation} which could have been computed as well from \begin{equation} \F_{21}\prec' \F_{231} = \F_{21453}+\F_{25153}+\F_{24513}+\F_{24531}. \end{equation} Applying Lemma~\ref{desshuf}, we can project~\eqref{eq:hsfqs} to $QSym$. If the descent composition of $u$ is $H$ and that of $\sigma$ is $I$, the descent composition of $\bar u$ is the conjugate composition $H^\sim$, and if $u_1>\sigma_1$, the descent composition of $\bar u \cdot \sigma$ is $H^\sim\cdot I$. We have therefore \begin{equation} F_I\prec' F_J = \sum_{J\in\{HK,H\triangleright K\}}(-1)^{|H|}F_{ H^{\sim}\cdot I}F_K, \end{equation} where for two compositions $H=(h_1,\ldots,h_r)$ and $K=(k_1,\ldots,k_s)$ \begin{equation} HK = (h_1,\ldots,h_r,k_1,\ldots,k_s)\ \text{and}\ H\triangleright K=(h_1,\ldots,h_r+k_1,\ldots,k_s). \end{equation} For example, \begin{equation} \F_{21}\prec' \F_{132} = \F_{21\shuffle 354} - \F_{321\shuffle 54} + \F_{5321\shuffle 4} - \F_{45321}, \end{equation} so that \begin{equation} \pi(\F_{21}\prec' \F_{132}) = F_{11} F_{21} - F_{111} F_{11} + F_{1111} F_{1} - F_{2111}, \end{equation} corresponding to the decompositions $J=\emptyset\cdot 21$, $1\triangleright 11$, $2\cdot 1$, and $21 \cdot\emptyset$. Since the antipode $S$ of $QSym$ is given by \begin{equation} S(F_H)=(-1)^{|H|}F_{ H^{\sim}}, \end{equation} and the coproduct by \begin{equation} \Delta(F_J)=\sum_{J\in\{HK,H\triangleright K\}}F_H\otimes F_K \end{equation} we obtain in this way~\cite[Detailed version (ancillary file), Thm.~3.15]{Gri}: \begin{theo}\label{th:precs} Let the $\prec'$ product on $QSym$ be defined by~\eqref{eq:QSdend}. Then, for $f,g\in QSym$, \begin{equation}\label{eq:fprecg} f\prec' g = \sum_{(g)}\left(S(g_{(1)})\bullet f\right)g_{(2)} \end{equation} where $F_I\bullet F_J := F_{I\cdot J}$ and $\Delta g = \sum_{(g)} g_{(1)}\otimes g_{(2)}$. \end{theo} For example, applying $\pi$ to~\eqref{eq:exdend}, we obtain \begin{equation}\label{eq:exFF} F_{121}\prec' F_{12} = F_{121}F_{12}-F_{1121}F_{2}+F_{2121}F_1-F_{12121.} \end{equation} \subsection{Quasi-differential operators} Theorem~\ref{th:precs} can be reformulated in terms of quasi-differential operators, as in~\cite{Gri}. According to~\cite[Def.~4.5]{NCSF2}, for $f\in QSym$, \begin{equation} f(X-Y) = \sum_I S(F_I)(Y)\cdot R_I^\perp(f)(X), \end{equation} where the quasi-differential operator $R_I^\perp$ is defined as in~\cite{Gri}, i.e., as the adjoint of the linear map $f\mapsto R_I f$. Indeed, recall that $f(X-Y)$ is defined as $f((-Y)\hat+ X)$, where $\hat+$ is the ordinal sum of alphabets, $f(-Y)=S(f)(Y)$. Now, \begin{align} f(X\hat+ Y) &= \sum_{J,K}\<\Delta f, R_J\otimes R_K\>F_J(X)F_K(Y)\\ &= \sum_{J,K}\ F_J(X)F_K(Y)\\ &= \sum_{J,K}\ F_J(X)F_K(Y)\\ &= \sum_J F_J(X)\sum_K\ )F_K(Y)\\ &= \sum_J F_J(X)(R_J^\perp f)(Y). \end{align} Replacing $X,Y$ by $-Y,X$, this becomes \begin{equation} f(-Y\hat+ X)= \sum_J F_J(-Y)(R_J^\perp f)(X)= \sum_J S(F_J)(Y)\cdot R_J^\perp(f)(X), \end{equation} We can therefore rewrite~\eqref{eq:fprecg} as \begin{equation} f\prec' g (X) = [g(X-Y)\bullet_Y f(Y)]_{Y=X}. \end{equation} For example \begin{align} F_{12}(X-Y) &=F_{12}((-Y)\hat+ X) \\ &=F_{12}(-Y)+F_{11}(-Y)F_1(X)+F_1(-Y)F_2(X)+F_{12}(X)\nonumber\\ &=-F_{12}(Y)+F_2(Y)F_1(X)-F_1(Y)F_{2}(X)+F_{12}(X). \end{align} Taking the $\bullet$ product with $F_{121}(Y)$, we obtain \begin{multline} F_{12}(X-Y)\bullet F_{121}(Y) \\ = -F_{12121}(Y)+F_{2121}(Y)F_1(X)-F_{1121}(Y)F_{2}(X)+F_{121}(Y)F_{12}(X), \end{multline} and setting $Y=X$, we recover~\eqref{eq:exFF}. Similarly, we have for the right product \begin{equation} u\succ' v = \sum_{u_1u_2=u}(-1)^{|u_1|}u_2\shuffle \overline{u_1}v. \end{equation} Thus, on $QSym$, if one defines $\btr$ by $F_I\btr F_J=F_{I \triangleright J}$, then \begin{equation} f\succ'g = \sum_{(f)}\left(S(f_{(1)})\btr g\right) f_{(2)}. \end{equation} This is precisely~\cite[Thm.~3.7]{Gri}. For example, \begin{equation} \F_{132}\succ' \F_{21} = \F_{132\shuffle 54 - 32\shuffle 154 + 2\shuffle 3154 - 23154}, \end{equation} which projects onto \begin{equation} F_{21}\succ' F_{11} = F_{21}F_{11} - F_{11}F_{21} + F_{1}F_{121} - F_{221} = F_{131} + F_{1121} + F_{122} + F_{1211}. \end{equation} \subsection{Standard dendriform structures} With the usual definitions \begin{equation} ua\prec vb = (u\shuffle vb)a,\quad ua\succ vb = (ua\shuffle v)b, \end{equation} the half-shuffle identity becomes \begin{equation} u\prec v = \sum_{v_1v_2=v}(-1)^{|v_2|}u\overline{v_2}\shuffle v_1 \end{equation} which induces an operation on $QSym$ defined by \begin{equation} F_I\prec F_J = \sum_{J\in\{HK,H\triangleright K\}} (-1)^{|K|}F_{I\triangleright K^\sim}F_H, \end{equation} or equivalently, \begin{equation} f\prec g = \sum_{(g)}g_{(1)}\left(f\btr S(g_{(2)})\right). \end{equation} For example, \begin{equation} \F_{21}\prec \F_{132}=\F_{35421}+\F_{35241}+ \F_{32541}+\F_{23541} \end{equation} and \begin{equation} F_{11}\prec F_{21}=F_{2111}+F_{221}+F_{1211}+F_{311}. \end{equation} Then, \begin{equation} F_I\prec F_J = F_I(Y)\btr_Y F_J(X-Y)|_{Y=X}. \end{equation} For example, \begin{equation} F_{21}(X-Y) = F_{21}(X) - F_{1}(Y)F_{2}(X) + F_{2}(Y)F_{1}(X) - F_{21}(Y) \end{equation} and \begin{multline} F_{11}(Y)\btr_Y F_{21}(X-Y)\\ = F_{11}(Y)F_{21}(X) - F_{12}(Y)F_{2}(X) + F_{13}(Y)F_{1}(X) - F_{131}(Y) \end{multline} so that \begin{equation} F_{11}\prec F_{21}= F_{11}F_{21} - F_{12}F_{2}+ F_{13}F_{1} - F_{131}. \end{equation} For the right product, we have \begin{equation} u\succ v = \sum_{u_1u_2=u}(-1)^{|u_2|}u_1\shuffle v\overline{u_2}, \end{equation} and on $QSym$, \begin{equation} f\succ g = \sum_{(f)}f_{(1)}\left(g\bullet S(f_{(2)})\right). \end{equation} For example, \begin{equation} \F_{21}\succ \F_{231} = \F_{21\shuffle 453 - 2\shuffle 4531 + 45312} \end{equation} which yields on $QSym$ \begin{equation} F_{11}\succ F_{21}=F_{11}F_{21}- F_{1} F_{211}+ F_{212} = F_{131}+F_{122}+ F_{221}+ F_{32}+ F_{1121}+ F_{212}. \end{equation} \subsection{Grinberg's operations} In~\cite{Gri}, a left product $\prec_G$ on $QSym$ is induced from an operation on monomials. This operation is the commutative image of the left tridendriform product on words defined in~\cite{NTpark} (with the use of $\min$ instead of $\max$, so that we shall consistently denote it by $\prec'$), and amounts to taking the canonical projection $\pi: \WQSym\rightarrow QSym$ of the tridendriform product of $\WQSym$: \begin{equation} M_I\prec_G M_J := \pi(\M_u\prec' \M_v) \end{equation} where $u,v$ are any packed words of evaluation $I,J$. For example, to evaluate $F_{11}\prec_G F_{21}$, we compute $M_{11}\prec_G (M_{21}+M_{111})$, hence $\M_{21}\prec'(\M_{132}+\M_{121})$: \begin{gather*} \M_{21}\prec'\M_{132} = \M_{21243}+ \M_{21354}+ \M_{31243}+ \M_{41243}+ \M_{51243}+ \M_{41253}+ \M_{31254}, \\ \M_{21}\prec' \M_{121}= \M_{21232}+ \M_{31212}+ \M_{21343}+ \M_{31242}+ \M_{41232} \end{gather*} so that \begin{equation} \begin{split} F_{11}\prec_G F_{21} &= 3M_{1211}+2M_{1121}+M_{1112}+M_{122}+M_{131}+4M_{1111}\\ &= F_{131}+F_{122}+F_{1121}+F_{1211}, \end{split} \end{equation} which is different from all previous examples such as~\eqref{eq:exgauF}. This operation can then be lifted to $\FQSym$ as \begin{equation} \F_\sigma \prec_G \F_\tau := \F_{\sigma[l]\prec'\tau}, \end{equation} where $l=|\tau|$, and $au\prec' bv$ is defined as $a(u\shuffle bv)$. Then Equation~\eqref{eq:halfsh} yields~\cite[Thm.~3.7]{Gri} \begin{equation} F_I\prec_G F_J = \sum_{J\in\{HK,H\triangleright K\}}(-1)^{|H|}F_{ H^{\sim}\triangleright I}F_K. \end{equation} For example, \begin{equation} \F_{21}\prec_G \F_{132} = \F_{54132}+ \F_{51432}+ \F_{51342}+ \F_{51234}, \end{equation} and one can check that \begin{equation} 54\prec' 132 = 54\shuffle 132-154\shuffle 32+3154\shuffle 2 -23154, \end{equation} so that \begin{equation} F_{11}\prec_G F_{21} = F_{11}F_{21}-F_{21}F_{11}+F_{121}F_1-F_{221}. \end{equation} Alternatively, we can describe $\prec_G$ as \begin{equation} \F_\sigma\prec_G \F_\tau = \F_\tau\succ' \F_\sigma. \end{equation} On $QSym$, this translates as \begin{equation} f\prec_G g = \sum_{(g)} g_{(2)}\left(S(g_{(1)})\btr f\right) \end{equation} which is now~\cite[Thm.~3.7]{Gri} in its original form. Grinberg's expression of the dual immaculate basis can now be restated as \begin{equation} \SG_I^* = (\cdots (F_{i_r}\succ' F_{i_{r-1}})\succ'\cdots)\succ' F_{i_1}. \end{equation} For example, \begin{equation} \SG_{221}^*=(F_1\succ' F_2)\succ' F_2= (F_{12}+F_{21})\succ' F_2. \end{equation} \begin{enonce}[remark]{Note} On $\FQSym$, the operation $\prec_G$ is not a left dendriform product in the usual sense, as it is in fact a flipped right product. The $\prec'$ operation on $\WQSym$ which induces it does not preserve the standard $\FQSym$ subalgebra of $\WQSym$. \end{enonce} Finally, it is also possible to deduce Theorem~\ref{th:dualimm} from Grinberg's results. The following argument has been suggested by an anonymous referee. Let $f\mapsto \bar f$ be the anti-involution of $\FQSym$ defined by $\overline{\F_\sigma}=\F_{\omega\sigma\omega}$, and denote by $\pi:\ \FQSym\rightarrow QSym$ the canonical projection $\pi(\F_\sigma)=F_{C(\sigma)}$. As already observed, $\pi(\bar f)=\overline{\pi(f)}$. It is easy to see that \begin{equation}\label{eq:abba1} \overline{a\prec b}=\bar b\succ_G\bar a\quad\text{for all $a,b\in\FQSym$}. \end{equation} Moreover, in~\cite[\S 6]{Gri}, it is said that \begin{equation}\label{eq:abba2} \pi(a)\prec_G \pi(b) = \pi(a\succ b) \quad\text{for all $a,b\in\FQSym$}. \end{equation} Now, let $I=(i_1,i_2,\ldots,i_r)$ be a composition. Then, \cite[Cor.~4.7]{Gri} shows that \begin{align*} \SG_I^* &= h_{i_1}\prec_G (h_{i_2}\prec_G(\cdots (h_{i_r}\prec_G 1)\cdots))\\ &= h_{i_1}\prec_G (h_{i_2}\prec_G(\cdots (h_{i_{r-1}}\prec_G h_{i_r})\cdots))\\ &= \pi(S_{i_1}) \prec_G(\pi(S_{i_2}) \prec_G(\cdots\prec_G \pi(S_{i_{r-1}}) \prec_G \pi(S_{i_r}))\cdots))\\ & \mkern -18mu\text{(since $h_k=\pi(S_k)$ for all $k$)}\\ &=\pi(((\cdots (S_{i_r} \succ_G S_{i_{r-1}}) \succ_G\cdots) \succ_G S_{i_2}) \succ_G S_{i_1})\\ & \mkern -18mu\text{(by applying~\eqref{eq:abba2} many times)}\\ &=\pi(((\cdots (\overline{S_{i_r}} \succ_G \overline{S_{i_{r-1}}}) \succ_G\cdots) \succ_G \overline{S_{i_2}}) \succ_G \overline{S_{i_1}})\\ &\mkern -18mu \text{(since $\overline{S_k}=S_k$)}\\ &=\pi\left(\overline{S_{i_1}\prec(S_{i_2}\prec(\cdots\prec(S_{i_{r-1}}\prec S_{i_r})\cdots))}\right)\\ &\mkern -18mu \text{(by applying~\eqref{eq:abba1} many times)}\\ &=\pi\left(\overline{C_I(A)}\right) \quad\text{as seen in the proof of Lemma~\ref{lem:CI}}\\ &=\overline{\pi(C_I(A))}\\ &= \overline{C_I(X)}. \end{align*} Hence, Theorem~\ref{th:dualimm} follows from~\cite[Cor.~4.7]{Gri}. \section{Hopf algebras of set partitions} We have seen that the Bell polynomial $\B_n$ can be identified with the formal sum of permutations avoiding $21-3$ (up to the $Y^I$ which can be reconstructed from the descent sets). This raises the question of the existence of a Hopf subalgebra or quotient of $\FQSym$ whose bases are naturally labeled by these permutations. The most obvious Hopf algebra of set partitions is $\WSym$, or symmetric functions in noncommuting variables (not to be confused with noncommutative symmetric functions $\NCSF$). In~\cite{HNT1}, a quotient of $\WSym$ isomorphic to $\NCSF$ and a $QSym$ subalgebra of its dual are related to Bell polynomials. In~\cite{BCLM}, analogues of the Bell polynomials in various other Hopf algebras are considered. \subsection{The Bell Hopf algebra} The Hopf algebra $\WSym$ is cocommutative. Quite often, combinatorial objects also admit a self-dual Hopf algebra structure. Such an algebra has been constructed by Rey~\cite{rey2,rey} for set partitions from the Burstein--Lankham correspondence, a combinatorial construction derived from the patience sorting algorithm. More precisely, the Bell classes of Rey are indexed by permutations avoiding $23-1$, and these are their minimal elements (for the weak order). We can modify the construction so as to have classes whose maximal elements avoid $21-3$ as follows. Let $A$ be a totally ordered alphabet. The (modified) Bell congruence on $A^*$ is generated by the relations\footnote{As observed by Grinberg (private communication), an alternative description is $bcu\equiv buc$ for $b _P$ is generated by the following requirements: order $S$ as above, and, for any element $x$ of a block $s$ of $S$, write $x>_Px'$ where $x'$ is the greatest element smaller than $x$ in $s$ and write $x>_Px''$ where $x''$ is the smallest element greater than $x$ in the block immediately to the left of $s$ in $S$ (if such a block and such an element exist). The transitive closure of $>_P$ defines a poset which will be denoted by $P(S)$ or by $P(w)$ if $S$ is the result of the (modified) patience sorting algorithm applied to $w$. Note that by removing the edges of the Hasse diagram of $P(S)$ where the element above is greater than the element below, one recovers $S$ itself. Hence it makes sense to refer to the columns of $S$ as the corresponding columns of the poset $P(S)$. For $w$ in $P$, we shall write $C(w)$ for its column. As usual with posets, we shall only represent the covering relations. For example, starting with the set $S$ computed before, we get (orienting the Hasse diagrams upside-down, with minimal elements at the top): \begin{equation} \begin{aligned} \xymatrix@C=2mm@R=2mm{ *{} & *{} & {3}\ar@{-}[dr]\ar@{-}[dl] \\ *{} & {6}\ar@{-}[dd]\ar@{-}[dl] & *{} & {1}\ar@{-}[dl] \\ {7} & *{} & {2}\ar@{-}[dl] \\ *{} & {4}\ar@{-}[dl] \\ {5} \\ } \end{aligned} \end{equation} Indeed, the first column of $S$ is $(3,6,7)$ and $6>3$ and $7>6$. Now, on the second column we have $5>4>2>1$ and the relations between these elements and the first column are: $1>_P3$, $2>_P3$, $4>_P6$, and $5>_P6$, whence the Hasse diagram above. %\medskip Starting with $S=(6,10,11|2,4,8,9|3,7|5|1)$, one gets \[ S = \young{6&2&3&5&1\\ 10&4&7&\none&\none \\ 11&8&\none&\none&\none \cr \none & 9} \] and \begin{equation} P(S)=\begin{aligned} \xymatrix@C=2mm@R=2mm{ *{} & *{} & {6}\ar@{-}[dr]\ar@{-}[dl] \\ *{} & {10}\ar@{-}[dd]\ar@{-}[dl] & *{} & {2}\ar@{-}[dl] \\ {11} & *{} & {4}\ar@{-}[dl]\ar@{-}[dr] \\ *{} & {8}\ar@{-}[dl]\ar@{-}[dr] & *{} & {3}\ar@{-}[dl] \\ {9} & *{} & 7\ar@{-}[dr] \\ *{} & *{} & *{} & 5\ar@{-}[dr] \\ *{} & *{} & *{} & *{} & 1\\ } \end{aligned} \end{equation} Note that in this representation, the columns of $P(S)$ are the straight lines going from south-west to north-east. \subsection{Proofs} We shall now prove Theorem~\ref{th:posets}: all elements in a given Bell class have the same poset $P(w)=P(\PSA(w))$, and the linear extensions (taken from top to bottom in our representation) of such a poset give elements of the same Bell class. Hence being in the same Bell class is equivalent to having the same poset. %\medskip \subsubsection{All elements in a given Bell class have the same poset} First, let us prove that all elements in a given Bell class have the same poset, or, equivalently, the same result by the PSA algorithm. We only need to prove this for two elements $w$ and $w'$ obtained from one another by a single rewriting rule. So, let us consider $w=vbuac$ and $w'=vbuca$ where all letters of $u$ are smaller than $b$. When $b$ is inserted, it is the bottommost element of its column, and it remains so during the insertion of all $u$, since all the letters of $u$ are smaller than $b$. Now, a letter $c>b$ is necessarily inserted into a column to the left of $C(b)$ or into it, independently of the insertion of $a$. Meanwhile, a letter $a$ smaller than $b$ is necessarily inserted into a column strictly to the right of $C(b)$ (whether or not $c$ has already been inserted). Thus, the insertions of $c$ and $a$ do not interfere with each other. So $w$ and $w'$ satisfy $\PSA(w)=\PSA(w')$. Note that the condition that all letters of $u$ are smaller than $b$ is necessary to ensure that $c$ and $a$ cannot both be inserted in the same column, which would prevent $w$ and $w'$ from yielding the same result by the modified patience sorting algorithm. %\medskip \subsubsection{All linear extensions of a poset are Bell congruent} Let us now prove that all linear extensions of a poset $P(\sigma)$ are Bell congruent to $\sigma$.\footnote{Grinberg (private communication) has proposed another proof, an induction of the length of~$\sigma$.} First note that the poset obtained from a permutation $\sigma$ has a unique minimal element $m$ at its top: indeed, it is easy to see that whenever $p _P$ to the smallest element of the $p$th column. Now, $\sigma$ is a linear extension of it, since when we insert a new letter $r$, we do not get a new covering relation of the form $s>_Pr$. One can thus rebuild the corresponding set partition $\PSA(\sigma)$ since each column of $P(\sigma)$ is a saturated chain of the poset $P(\sigma)$, and conversely, if we remove all edges of the form $u>_P v$ satisfying $u_P$ the smallest value $v'$ greater than itself in $C'$, hence below all values smaller than itself. Now the same property holds for $v'>v$ on the next column to its left and so on. Let us now consider two elements $x$ and $z$ such that $x<_P z$, so that $C(x)$ is equal to, or to the left of $C(z)$, which we shall write as $C(x)\preceq C(z)$. Two cases may appear: $x z$. Let us consider the first case and let $y$ be another element of $P$ such that $x _Py$ or $y<_Pz$. Let us now consider the second case where $x>z$ and let $y$ be another element of $P$ such that $x>y>z$. If $C(y)\preceq C(z)$ or $C(y)\succeq C(x)$, the same argument as before applies. Otherwise, it means that $C(x)\preceq C(y)\preceq C(z)$. But in that case, since there is a saturated chain from $x$ down to $z$, all elements in between are either comparable to $x$ (if they are below the path) or to $z$ (if they are above the path). So in all cases, we proved that $y$ satisfies either $x<_P y$ or $y<_Pz$, hence proving that our posets are regular. %\medskip \subsubsection{The maximal elements of the Bell classes avoid \texorpdfstring{$21-3$}{21-3}} Let us finally prove that the maximal elements of the Bell classes avoid the pattern $21-3$. There are several ways to prove this. One could say for example that the Bell classes are in bijection with set partitions, hence splitting the permutations of size $n$ into as many classes as the number of permutations avoiding $21-3$. Now, if a permutation $\sigma$ does not avoid $21-3$, let us consider such a pattern with letters $ba\dots c$ in $\sigma$ where the distance between $a$ and $c$ is minimal. Then the letter immediately to the left of $c$ (if it exists: the other case is easy) has to be smaller than $b$, hence denoted naturally by $a'$. All letters $x$ between $b$ and $a'$ are necessarily smaller than $b$, otherwise $ba\cdots x\cdots a'c$ would have $ba\cdot x$ as a shorter pattern $21-3$, which would contradict the minimality of the initial one. So we are in the conditions of the Bell congruence, and $\sigma$ is not a maximal element of its class. So all maximal elements necessarily avoid the pattern $21-3$. Since both sets, the maximal elements of Bell classes and the permutations avoiding $21-3$ have same cardinality, they must be equal. Another proof consists in applying the greedy algorithm that takes a Bell poset as entry and takes the linear extension where at each step one chooses the maximal available value. It is easy to see that these elements necessarily avoid the pattern $21-3$ and conclude in the same way as before. Note that the minimal elements are not characterized by pattern avoidance. %\medskip \subsubsection{Proof of Theorem~\ref{th:rey}} As for Theorem~\ref{th:rey}, it follows from a well-known result about algebras defined by congruences, see e.g., Theorem~2.1 of~\cite{NT16} or Chapter~2.1 of~\cite{JNZ}. \longthanks{This research has been partially supported by the ANR program CARMA. Thanks also to Darij Grinberg for his useful comments on the first version of this text.} \bibliographystyle{amsplain-ac} \bibliography{ALCO_Thibon_87} \end{document}