\draw[blue, thick] (0,0) -- (2,2);
\draw[blue, thick] (0,0) -- (-2,2);
\draw[blue, thick] (1,1) -- (0,2);
\filldraw[black] (0,0) circle (5pt)  {};
\filldraw[black] (1,1) circle (5pt)  {};
\node at (0,0.7)[font=\fontsize{7pt}{0}]{$2$};
\node at (1,1.7)[font=\fontsize{7pt}{0}]{$3$};
\end{tikzpicture}
\Big)
\draw[blue, thick] (0,-1) -- (0,0);
\draw[blue, thick] (0,0) -- (2,2);
\draw[blue, thick] (0,0) -- (-3,3);
\draw[blue, thick] (-3,3) -- (-4,4);
\draw[blue, thick] (-3,3) -- (-2,4);
\draw[blue, thick] (2,2) -- (0,4);
\draw[blue, thick] (2,2) -- (3,3);
\draw[blue, thick] (3,3) -- (2,4);
\draw[blue, thick] (3,3) -- (4,4);
\filldraw[black] (0,0) circle (5pt)  {};
\filldraw[black] (-3,3) circle (5pt)  {};
\filldraw[black] (2,2) circle (5pt)  {};
\filldraw[black] (3,3) circle (5pt)  {};
\node at (0,0.7)[font=\fontsize{7pt}{0}]{$1$};
\node at (-3,3.7)[font=\fontsize{7pt}{0}]{$2$};
\node at (2,2.7)[font=\fontsize{7pt}{0}]{$3$};
\node at (3,3.7)[font=\fontsize{7pt}{0}]{$4$};
\end{tikzpicture}$. Compare with the same calculation using $\sigma_{2}/\sigma_{3}$: $\sigma_{2}/\sigma_{3} = \begin{tikzpicture}[scale=0.2,baseline=0pt]
\draw[blue, thick] (0,-1) -- (0,0);
\draw[blue, thick] (0,0) -- (3,3);
\draw[blue, thick] (0,0) -- (-3,3);
\draw[blue, thick] (-1,1) -- (1,3);
\draw[blue, thick] (0,2) -- (-1,3);
\filldraw[black] (0,0) circle (5pt)  {};
\filldraw[black] (-1,1) circle (5pt)  {};
\filldraw[black] (0,2) circle (5pt)  {};
\node at (0,0.7)[font=\fontsize{7pt}{0}]{$1$};
\node at (-1,1.7)[font=\fontsize{7pt}{0}]{$2$};
\node at (0,2.7)[font=\fontsize{7pt}{0}]{$3$};
\end{tikzpicture}
\mapsto \Big(
\begin{tikzpicture}[scale=0.2,baseline=0pt]
\draw[blue, thick] (0,-1) -- (0,0);
\draw[blue, thick] (0,0) -- (1,1);
\draw[blue, thick] (0,0) -- (-1,1);
\filldraw[black] (0,0) circle (5pt)  {};
\node at (0,0.7)[font=\fontsize{7pt}{0}]{$2$};
\end{tikzpicture},
\begin{tikzpicture}[scale=0.2,baseline=0pt]
\draw[blue, thick] (0,-1) -- (0,0);
\draw[blue, thick] (0,0) -- (2,2);
\draw[blue, thick] (0,0) -- (-2,2);
\draw[blue, thick] (-1,1) -- (0,2);
\filldraw[black] (0,0) circle (5pt)  {};
\filldraw[black] (-1,1) circle (5pt)  {};
\node at (0,0.7)[font=\fontsize{7pt}{0}]{$3$};
\node at (-1,1.7)[font=\fontsize{7pt}{0}]{$1$};
\end{tikzpicture}\Big) $ and 	$\begin{tikzpicture}[scale=0.2,baseline=0pt]
\draw[blue, thick] (0,-1) -- (0,0);
\draw[blue, thick] (0,0) -- (1,1);
\draw[blue, thick] (0,0) -- (-1,1);
\filldraw[black] (0,0) circle (5pt)  {};
\node at (0,0.7)[font=\fontsize{7pt}{0}]{$1$};
\end{tikzpicture}
\overleftarrow{\shuffle} \Big(
\begin{tikzpicture}[scale=0.2,baseline=0pt]
\draw[blue, thick] (0,-1) -- (0,0);
\draw[blue, thick] (0,0) -- (1,1);
\draw[blue, thick] (0,0) -- (-1,1);
\filldraw[black] (0,0) circle (5pt)  {};
\node at (0,0.7)[font=\fontsize{7pt}{0}]{$2$};
\end{tikzpicture},
\begin{tikzpicture}[scale=0.2,baseline=0pt]
\draw[blue, thick] (0,-1) -- (0,0);
\draw[blue, thick] (0,0) -- (2,2);
\draw[blue, thick] (0,0) -- (-2,2);
\draw[blue, thick] (-1,1) -- (0,2);
\filldraw[black] (0,0) circle (5pt)  {};
\filldraw[black] (-1,1) circle (5pt)  {};
\node at (0,0.7)[font=\fontsize{7pt}{0}]{$3$};
\node at (-1,1.7)[font=\fontsize{7pt}{0}]{$1$};
\end{tikzpicture}\Big)
\draw[blue, thick] (0,-1) -- (0,0);
\draw[blue, thick] (0,0) -- (4,4);
\draw[blue, thick] (0,0) -- (-4,4);
\draw[blue, thick] (-3,3) -- (-2,4);
\draw[blue, thick] (2,2) -- (0,4);
\draw[blue, thick] (1,3) -- (2,4);
\filldraw[black] (0,0) circle (5pt)  {};
\filldraw[black] (-3,3) circle (5pt)  {};
\filldraw[black] (2,2) circle (5pt)  {};
\filldraw[black] (1,3) circle (5pt)  {};
\node at (0,0.7)[font=\fontsize{7pt}{0}]{$1$};
\node at (-3,3.7)[font=\fontsize{7pt}{0}]{$3$};
\node at (2,2.7)[font=\fontsize{7pt}{0}]{$2$};
\node at (1,3.7)[font=\fontsize{7pt}{0}]{$4$};
\end{tikzpicture} \not \leq_{w}\tau$, so this lightening-split-choice satisfies (3).

Because a permutation is completely determined by its node labels,
without reference to the binary tree, the above calculation can be
entirely computed using the node labels only. (But the tree calculation
is necessary on similar algebras with unlabeled trees, or where the
node labels do not determine the tree.) Let $d_{i}=\deg\sigma_{1}+\cdots+\deg\sigma_{i}$,
i.e. $d_{i}$ is the $i$th element of $\GD(\sigma)$. If $\{d_{i-1}+1,d_{i-1}+2,\dots,d_{i}\}$
appear setwise to the left of $\{d_{i}+1,d_{i}+2,\dots,d_{i+1}\}$
(in the example, 2 and 3 are both to the left of 4), then “calculating
with $\sigma_{i}/\sigma_{i+1}$ instead of $\sigma_{i}\backslash\sigma_{i+1}$”
amounts to replacing $d_{i}+1,d_{i}+2,\dots,d_{i+1}$ with $d_{i-1}+1,d_{i-1}+2,\dots,d_{i-1}+(d_{i+1}-d_{i})$
(e.g. 4 with 2) and $d_{i-1}+1,d_{i-1}+2,\dots,d_{i}$ with $d_{i-1}+(d_{i+1}-d_{i})+1,\dots d_{i+1}$
(e.g. 2, 3 with 3, 4). We check condition (3) for the shuffle on the
right of (<ref>) using this expedited method. Here,
1 appears to the left of 2 and 3, and $3124\not\leq_{w}\tau$;
2 and 3 appear to the left of 4, and $1342\not\leq_{w}\tau$,
so this lightening-split-choice also satisfies (3).

Hence $\gamma_{\sigma}^{\tau}=2$.

§.§ The inheritance of the axioms through subalgebras and quotienting

This section contains two theorems for transferring  the above properties of monomial bases to subalgebras and quotient algebras.

In this section, we will
assume that  $\mathcal{H}$ is a connected
Hopf algebra satisfying conditions ($\Delta$1)-($\Delta$3), ($m$0)-($m$3) and ($\mathcal{S}$0)-($\mathcal{S}$3).

First, we consider subalgebras that are spanned by induced subposets:

Assume that $Q_{n}\subseteq P_{n}$ for each $n$, with the induced order, and
write $Q=\bigsqcup Q_{n}$.

* If for all $f,g\in Q$, we have ${}^{i}f,f^{i}\in Q$ for all
$i\in\allow(f)$ and $f/g\in Q$, then $\Span\{F_{f}:f\in Q\}$ is
a subcoalgebra of $\mathcal{H}$ satisfying ($\Delta$1)-($\Delta$3).

* If for all $f,g\in Q$,
we have $\zeta(f,g)\in Q$ for all $\zeta\in Sh(\cmpt(f),\cmpt(g))$
and, when defined,  $f\vee g\in Q$, then $\Span\{F_{f}:f\in Q\}$ is a subalgebra of
$\mathcal{H}$ satisfying ($m$0)-($m$3).

* If all above hypotheses on $Q$ hold,
and for all $f,g\in Q$, we have $f\backslash g\in Q$. Then $\Span\{F_{f}:f\in Q\}$
satisfies ($\mathcal{S}$0)-($\mathcal{S}$3).

The proof is trivial. Note that, because $Q$ is closed under “deconcatenation”
and “maximal concatenation” $/$, the meaning of $\GD$ is the
same in $Q$ as in $P$. However, unless $Q$ is obtained as a collection of upper order-ideals in $P$,
the monomial basis elements of $\Span\{F_{f}:f\in Q\}$ created using
$Q$ are not monomial basis elements of $\mathcal{H}$.

The next situation of inheritance of axioms is more technical but more interesting.
For example, it will be used to pass from labeled to unlabeled trees. For the rest
of this section, we will assume we have a second graded connected Hopf algebra $\bar{\mathcal{H}}$ defined  by a poset as follow.
Let $\bar{P}_{n}$ be posets for each integer  $n\geq0$.
Assume that $\bar{\mathcal{H}}$,  as  a graded vector
space, has a fundamental basis $\{F_{t}:t\in\bar{P}_{n}\}$. In both ${\mathcal{H}}$ and  $\bar{\mathcal{H}}$  we  define
a monomial basis $\{M_{f}:f\in P_{n}\}$ (resp. $\{M_{t}:t\in\bar{P}_{n}\}$), related by $F_{f}=\sum_{g\geq f}M_{g}$ (resp. $F_{t}=\sum_{s\geq t}M_{s}$).
Let $\pi_{n}:P_{n}\rightarrow\bar{P}_{n}$ be a sequence of surjective order-preserving
maps, and let $\Pi:\mathcal{H}\rightarrow\bar{\mathcal{H}}$ given
by $\Pi(F_{f})=F_{\pi_{\deg f}(f)}$ be the induced linear map. One
key axiom that  we need is the following:

($\pi$0).  For each $n$, there exists maps $\iota_{n}:\bar{P}_{n}\rightarrow P_{n}$
given by $\iota_{n}(t)=\max\{f\in P_{n}:\pi_{n}(f)=t\}$, and $\iota_{n}$
is order-preserving.

Axiom ($\pi$0) requires that, for each $t\in \bar{P}_{n}$, it is possible to compute $\max\{f\in P_{n}:\pi_{n}(f)=t\}$. In particular, $\{f\in P_{n}:\pi_{n}(f)=t\}$ must lie in the same connected component of $P_{n}$.
Axiom ($\pi$0) implies that $\pi_n$ and $\iota_n$ form a Galois connection, i.e. $\pi_n(f)\leq s$ if and only if $f\leq \iota_n(s)$. It follows that the connected components $C_{i}$ of $P_{n}$ are in bijection with the connected components $\bar{C}_{i}$ of $\bar{P}_{n}$. Since $\pi_n$ is part of a Galois connection it preserves least upper bounds, which we record as the following lemma.

If axiom ($\pi$0)
is satisfied, then $\pi_{n}(f\vee g)=\pi_{n}f\vee\pi_{n}g$ for all
$f,g\in C_{i}\subseteq P_{n}$.

An immediate consequence of this Lemma is that ($m$0) is satisfied for $\bar{P}_{n}$.
The other relevant axioms that we require from $\pi$ to be able to transfer axioms
($\Delta$1)-($\Delta$3), ($m$0)-($m$3), ($\mathcal{S}$0)-($\mathcal{S}$3) from $\mathcal{H}$ to  $\bar{\mathcal{H}}$ are:

($\pi\Delta$1).  for $t\in\bar{P}_{n}$, we have a map $\allow(t)\subseteq\{1,\ldots,n-1\}$ such that

$$\displaystyle\Delta_{+}(F_{t})=\sum_{i\in\allow(t)}F_{{}^{i}t}\otimes F_{t^{i}}$$

for some ${}^{i}t\in\bar{P}_{i}$, $t^{i}\in\bar{P}_{n-i}$; and for all $f\in P_{n}$, we have $\allow(f)=\allow(\pi_{n}f)$.

($\pi\Delta$2).  $\pi$ commutes with deconcatenation: ${}^{i}(\pi_{n}f)=\pi_{i}\left({}^{i}f\right)$,
$(\pi_{n}f)^{i}=\pi_{n-i}\left(f^{i}\right)$ for $f\in P_{n}$.

($\pi m$1).  For all connected components $\bar{C}_{i},\bar{C}_{j}$ of $\bar{P}_{n},\bar{P}_{m}$, we have a set $Sh(\bar{C}_{i},\bar{C}_{j})$ of shuffles such that,
for $s\in\bar{C}_{i}$ and $t\in\bar{C}_{j}$, we have $F_{s}F_{t}=\sum_{\bar{\zeta}\in Sh(\bar{C}_{i},\bar{C}_{j})}F_{\bar{\zeta}(s,t)}$.
Axiom ($\pi$0) gives us corresponding connected components ${C}_{i},{C}_{j}$ of ${P}_{n},{P}_{m}$ and we require a
bijection $Sh(C_{i},C_{j})\rightarrow Sh(\bar{C}_{i},\bar{C}_{j})$.

($\pi m$2).  For all $\zeta\in Sh(C_{i},C_{j})$, in bijection with $\bar{\zeta}\in Sh(\bar{C}_{i},\bar{C}_{j})$, and for all $f\in C_{i}$, $g\in C_{j}$,
we have $\pi_{n}(\zeta(f,g))=\bar{\zeta}(\pi_{n}(f),\pi_{m}(g))$.

($\pi\mathcal{S}$1).  $\GD(\iota_{n}(t))=\GD(t)$ for $t\in\bar{P}_{n}$.

($\pi\mathcal{S}$2).  $\pi_{n}(g/h)=\pi_{i}(g)/\pi_{n-i}(h)$ for all $g\in P_{i}$, $h\in P_{n-i}$.

For  $\mathcal{H},\bar{\mathcal{H}}$, if the maps $\pi_n\colon P_n\to\bar{P}_n$
satisfy ($\pi$0), then

\begin{equation}
\Pi(M_{f})=\begin{cases}
M_{t} & \text{if }f=\iota(t)\text{ for some }t;\\
0 & \text{otherwise}.
\end{cases}\label{eq:quotientmonomial}
\end{equation}

* If  ($\pi\Delta$1)-($\pi\Delta$2) are satisfied, then $\Pi$ is a coalgebra morphism,
and $\bar{\mathcal{H}}$ also satisfies axioms ($\Delta$1)-($\Delta$3), with
$s/t$ defined as $\pi_{n}(\iota_{i}(s)/\iota_{n-i}(t))$ for $s\in\bar{P}_{i}$
and $t\in\bar{P}_{n-i}$.

* If ($\pi m$1)-($\pi m$2) are satisfied, then $\Pi$ is an algebra morphism,
and $\bar{\mathcal{H}}$ also satisfies ($m$0)-($m$3).

* If  ($\pi\Delta$1)-($\pi\Delta$2),
($\pi m$1)-($\pi m$2) and ($\pi\mathcal{S}$1)-($\pi\mathcal{S}$2) are satisfied, then $\bar{\mathcal{H}}$ also
satisfies ($\mathcal{S}$0)-($\mathcal{S}$3).

See Section 7.4 for the proof.

Note that this theorem transfers the full axioms from $\mathcal{H}$ to $\bar{\mathcal{H}}$, in contrast to [2] where they only transfer the monomial basis formulas (for coproduct, product and antipode). The formula transfer uses only that $\pi_n$ and $\iota_n$ form a Galois connection, but transferring the axioms seems to require the stronger ($\pi$0) axiom.

§.§ Axioms on   and

Before using all the developed axiomatic machinery on new Hopf algebras we illustrate first how the axioms are satisfied by $\SSym$ and $\YSym$. We will use that the axioms are satisfied by these two Hopf algebras in our construction of a Hopf algebra on parking functions in Section <ref>.

$\SSym$ satisfies axioms
($\Delta$1)-($\Delta$3), ($m$0)-($m$3), ($\mathcal{S}$0)-($\mathcal{S}$3).

Axiom ($\Delta$1) is clear. ($\Delta$2) follows from <cit.>.
($\Delta$3) follows from <cit.>: the first case shows
that $/$ is order-preserving, and the third case gives the maximality.
That $/$ is a one-sided inverse to $\sigma\mapsto({}^{i}\sigma,\sigma^{i})$
is clear from the definitions.

Axiom ($m$0) is clear. Axiom ($m$1) is from the definition of the algebra (see Definition <ref>). Axioms ($m$2) and ($m$3) are <cit.>.

Axiom ($\mathcal{S}$0) follows from Remark <ref> and ($\mathcal{S}$1)
follows from <cit.>.

The intuition behind ($\mathcal{S}$2) is that all inversions of $\sigma'_{1}/\cdots/\sigma'_{k}$
are either “within” an $\sigma'_{i}$, in which case they are
in $\sigma'_{1}\backslash\cdots\backslash\sigma'_{k}$, or “between”
two $\sigma'_{i}$s, in which case they are in $\sigma_{1}/\cdots/\sigma_{k}$.
It may be rigorously deduced from <cit.> as
follows: define $\sigma'=\sigma'_{1}/\cdots/\sigma'_{k}$ and $\sigma=\sigma_{1}/\cdots/\sigma_{k}$
(here $\sigma_{i},\sigma_{i}'$ play the role of $f_{i},f'_{i}$).
By axiom $\Delta3$, $\sigma'\geq\sigma$, so $\sigma'\vee\sigma=\sigma'$.
Let $R=\emptyset$ and $S=\{\deg\sigma_{1}+\cdots+\deg\sigma_{i}:i\in\{1,\dots,k\}\}$;
note that $S\subseteq\GD(\sigma)$ and $\sigma|S=(\sigma_{1},\dots,\sigma_{k})$.
Then <cit.> says $\sigma'_{S}\vee\sigma_{R}=(\sigma\vee\sigma')_{R\cap S}$,
where their notation $\sigma_{S}$ denotes $\sigma_{1}\backslash\cdots\backslash\sigma_{k}$.
Thus $\sigma_{R}=\sigma=\sigma_{1}/\cdots/\sigma_{k}$, $\sigma'_{S}=\sigma'_{1}\backslash\cdots\backslash\sigma'_{k}$,
$(\sigma\vee\sigma')_{R\cap S}=\sigma\vee\sigma'=\sigma'=\sigma'_{1}/\cdots/\sigma'_{k}$.

Axiom ($\mathcal{S}$3) also follows from <cit.>,
by taking $\sigma=\sigma'=\sigma_{1}/\cdots/\sigma_{k}$, $R=\{d_{1},\dots,d_{i_{1}-1}\}\cup\{d_{j_{1}},\dots,d_{i_{2}-1}\}\cup\cdots\cup\{d_{j_{l-1}},\dots,d_{i_{l}-1}\}$,
where $d_{i}=\deg f_{1}+\cdots+\deg f_{i}$.

$\YSym$ satisfies axioms
($\Delta$1)-($\Delta$3), ($m$0)-($m$3), ($\mathcal{S}$0)-($\mathcal{S}$3).

Use Theorem <ref> to bootstrap from $\SSym$,
as Proposition <ref> provides the necessary
maps $\pi$ and $\iota$ satisfying ($\pi$0). It is clear that $\YSym$
satisfies axioms ($\pi\Delta$1) and ($\pi m$1). Axioms ($\pi\Delta$2),
($\pi m$2), ($\pi\mathcal{S}$1) and ($\pi\mathcal{S}$2) follow from Propositions
<ref> and <ref>.

§ HOPF ALGEBRA OF PLANAR TREES

§.§ Two isomorphic Hopf structures

In this section, we define two Hopf structures on the free vector space spanned by planar trees.

As a graded vector space, the Hopf algebra of planar trees, $\TSym$ is $\displaystyle\bigoplus_{n\geq 0}\Bbbk\PT_{n}$ where $\PT_{n}$ is the set of planar trees with $n+1$ leaves. By convention $\PT_{0}$ is the span of the empty tree. We denote two bases for $\TSym$ by $\{G_t:t\in\PT\}$ and $\{F_t:t\in\PT\}$.

Recall that a splitting $t\mapsto(t_1,t_2)$ is allowable if $\ideg(t)=\ideg(t_1)+\ideg(t_2)$. We can define two comultiplication structures on $\TSym$.

$$\Delta^A(\tilde{F}_t)=\sum_{t\mapsto(t_1,t_2)}\tilde{F}_{t_1}\otimes \tilde{F}_{t_2},$$

$$\Delta^B(F_t)=\sum_{\substack{\text{allowable} \\ t\mapsto(t_1,t_2)}}F_{t_1}\otimes F_{t_2}.$$

Then, we can define two multiplication structures on $\TSym$. Let $s,t\in \PT$,

$$m^A(\tilde{F}_s\otimes \tilde{F}_t)=\sum_{t\mapsto(t_1,\dots,t_{\deg(s)+1})}\tilde{F}_{s\shuffle (t_1,\dots,t_{\deg(s)+1})},$$

$$m^B(F_s\otimes F_t)=\sum_{\substack{\text{allowable}\\ t\mapsto(t_1,\dots,t_{\deg(s)+1})}}F_{s\shuffle (t_1,\dots,t_{\deg(s)+1})}.$$

It is not hard to see that both $(m^A,\Delta^A)$ and $(m^B,\Delta^B)$ preserve the degree, and $(m^B,\Delta^B)$ preserves the internal degree.

Let $t=\begin{tikzpicture}[scale=0.2,baseline=0pt]
\draw[blue, thick] (0,-1) -- (0,0);
\draw[blue, thick] (0,0) -- (4,4);
\draw[blue, thick] (0,0) -- (-4,4);
\draw[blue, thick] (0,0) -- (1,3);
\draw[blue, thick] (1,3) -- (2,4);
\draw[blue, thick] (1,3) -- (0,4);
\draw[blue, thick] (-3,3) -- (-2,4);
\filldraw[black] (0,0) circle (5pt)  {};
\filldraw[black] (1,3) circle (5pt)  {};
\filldraw[black] (-3,3) circle (5pt)  {};
\end{tikzpicture}$.

\tilde{F}_{\begin{tikzpicture}[scale=0.25,baseline=0pt]
\draw[blue, thick] (0,-1) -- (0,0);
\draw[blue, thick] (0,0) -- (1,1);
\draw[blue, thick] (0,0) -- (-1,1);
\filldraw[black] (0,0) circle (5pt)  {};
\end{tikzpicture}}\otimes
\tilde{F}_{\begin{tikzpicture}[scale=0.25,baseline=0pt]
\draw[blue, thick] (0,-1) -- (0,0);
\draw[blue, thick] (0,0) -- (-3,3);
\draw[blue, thick] (0,0) -- (3,3);
\draw[blue, thick] (0,0) -- (0,2);
\draw[blue, thick] (0,2) -- (1,3);
\draw[blue, thick] (0,2) -- (-1,3);
\filldraw[black] (0,0) circle (5pt)  {};
\filldraw[black] (0,2) circle (5pt)  {};
\end{tikzpicture}}+
\tilde{F}_{\begin{tikzpicture}[scale=0.25,baseline=0pt]
\draw[blue, thick] (0,-1) -- (0,0);
\draw[blue, thick] (0,0) -- (-2,2);
\draw[blue, thick] (0,0) -- (2,2);
\draw[blue, thick] (-1,1) -- (0,2);
\filldraw[black] (0,0) circle (5pt)  {};
\filldraw[black] (-1,1) circle (5pt)  {};
\end{tikzpicture}}\otimes
\tilde{F}_{\begin{tikzpicture}[scale=0.25,baseline=0pt]
\draw[blue, thick] (0,-1) -- (0,0);
\draw[blue, thick] (0,0) -- (-2,2);
\draw[blue, thick] (0,0) -- (2,2);
\draw[blue, thick] (-1,1) -- (0,2);
\filldraw[black] (0,0) circle (5pt)  {};
\filldraw[black] (-1,1) circle (5pt)  {};
\end{tikzpicture}}+
\tilde{F}_{\begin{tikzpicture}[scale=0.25,baseline=0pt]
\draw[blue, thick] (0,-1) -- (0,0);
\draw[blue, thick] (0,0) -- (-3,3);
\draw[blue, thick] (0,0) -- (3,3);
\draw[blue, thick] (2,2) -- (1,3);
\draw[blue, thick] (-2,2) -- (-1,3);
\filldraw[black] (0,0) circle (5pt)  {};
\filldraw[black] (2,2) circle (5pt)  {};
\filldraw[black] (-2,2) circle (5pt)  {};
\end{tikzpicture}}\otimes
\tilde{F}_{\begin{tikzpicture}[scale=0.25,baseline=0pt]
\draw[blue, thick] (0,-1) -- (0,0);
\draw[blue, thick] (0,0) -- (1,1);
\draw[blue, thick] (0,0) -- (-1,1);
\filldraw[black] (0,0) circle (5pt)  {};
\end{tikzpicture}}$,

\draw[blue, thick] (0,-1) -- (0,0);
\draw[blue, thick] (0,0) -- (1,1);
\draw[blue, thick] (0,0) -- (-1,1);
\filldraw[black] (0,0) circle (5pt)  {};
\end{tikzpicture}}\otimes
\draw[blue, thick] (0,-1) -- (0,0);
\draw[blue, thick] (0,0) -- (-3,3);
\draw[blue, thick] (0,0) -- (3,3);
\draw[blue, thick] (0,0) -- (0,2);
\draw[blue, thick] (0,2) -- (1,3);
\draw[blue, thick] (0,2) -- (-1,3);
\filldraw[black] (0,0) circle (5pt)  {};
\filldraw[black] (0,2) circle (5pt)  {};
\end{tikzpicture}}$.

Let $s=$[scale=0.25,baseline=0pt]
[blue, thick] (0,-1) – (0,0);
[blue, thick] (0,0) – (-2,2);
[blue, thick] (0,0) – (2,2);
[blue, thick] (1,1) – (0,2);
[black] (0,0) circle (5pt)  ;
[black] (1,1) circle (5pt)  ;
, $t=$[scale=0.25,baseline=0pt]
[red, thick] (0,-1) – (0,0);
[red, thick] (0,0) – (-2,2);
[red, thick] (0,0) – (2,2);
[red, thick] (0,0) – (0,2);
[black] (0,0) circle (5pt)  ;

$m^A(\tilde{F}_s\otimes \tilde{F}_t)=
\tilde{F}_{\begin{tikzpicture}[scale=0.2,baseline=0pt]
\draw[blue, thick] (0,-1) -- (0,0);
\draw[blue, thick] (0,0) -- (-4,4);
\draw[blue, thick] (0,0) -- (2,2);
\draw[blue, thick] (1,1) -- (-2,4);
\draw[red, thick] (2,2) -- (0,4);
\draw[red, thick] (2,2) -- (2,4);
\draw[red, thick] (2,2) -- (4,4);
\filldraw[black] (0,0) circle (5pt)  {};
\filldraw[black] (1,1) circle (5pt)  {};
\filldraw[black] (2,2) circle (5pt)  {};
\end{tikzpicture}}+
\tilde{F}_{\begin{tikzpicture}[scale=0.2,baseline=0pt]
\draw[blue, thick] (0,-1) -- (0,0);
\draw[blue, thick] (0,0) -- (-4,4);
\draw[blue, thick] (0,0) -- (4,4);
\draw[blue, thick] (1,1) -- (0,2);
\draw[red, thick] (0,2) -- (-2,4);
\draw[red, thick] (0,2) -- (0,4);
\draw[red, thick] (0,2) -- (2,4);
\filldraw[black] (0,0) circle (5pt)  {};
\filldraw[black] (1,1) circle (5pt)  {};
\filldraw[black] (0,2) circle (5pt)  {};
\end{tikzpicture}}+
\tilde{F}_{\begin{tikzpicture}[scale=0.2,baseline=0pt]
\draw[blue, thick] (0,-1) -- (0,0);
\draw[blue, thick] (0,0) -- (-4,4);
\draw[blue, thick] (0,0) -- (4,4);
\draw[blue, thick] (3,3) -- (2,4);
\draw[red, thick] (-2,2) -- (0,4);
\draw[red, thick] (-2,2) -- (-2,4);
\draw[red, thick] (-2,2) -- (-4,4);
\filldraw[black] (0,0) circle (5pt)  {};
\filldraw[black] (-2,2) circle (5pt)  {};
\filldraw[black] (3,3) circle (5pt)  {};
\end{tikzpicture}}+
\tilde{F}_{\begin{tikzpicture}[scale=0.2,baseline=0pt]
\draw[blue, thick] (0,-1) -- (0,0);
\draw[blue, thick] (0,0) -- (-4,4);
\draw[blue, thick] (0,0) -- (3,3);
\draw[blue, thick] (1,1) -- (-1,3);
\draw[red, thick] (-1,3) -- (-2,4);
\draw[red, thick] (-1,3) -- (0,4);
\draw[red, thick] (3,3) -- (2,4);
\draw[red, thick] (3,3) -- (4,4);
\filldraw[black] (0,0) circle (5pt)  {};
\filldraw[black] (1,1) circle (5pt)  {};
\filldraw[black] (-1,3) circle (5pt)  {};
\filldraw[black] (3,3) circle (5pt)  {};
\end{tikzpicture}}+
\tilde{F}_{\begin{tikzpicture}[scale=0.2,baseline=0pt]
\draw[blue, thick] (0,-1) -- (0,0);
\draw[blue, thick] (0,0) -- (-3,3);
\draw[blue, thick] (0,0) -- (3,3);
\draw[blue, thick] (2,2) -- (0,4);
\draw[red, thick] (-3,3) -- (-4,4);
\draw[red, thick] (-3,3) -- (-2,4);
\draw[red, thick] (3,3) -- (2,4);
\draw[red, thick] (3,3) -- (4,4);
\filldraw[black] (0,0) circle (5pt)  {};
\filldraw[black] (2,2) circle (5pt)  {};
\filldraw[black] (3,3) circle (5pt)  {};
\filldraw[black] (-3,3) circle (5pt)  {};
\end{tikzpicture}}+
\tilde{F}_{\begin{tikzpicture}[scale=0.2,baseline=0pt]
\draw[blue, thick] (0,-1) -- (0,0);
\draw[blue, thick] (0,0) -- (-3,3);
\draw[blue, thick] (0,0) -- (4,4);
\draw[blue, thick] (2,2) -- (1,3);
\draw[red, thick] (-3,3) -- (-4,4);
\draw[red, thick] (-3,3) -- (-2,4);
\draw[red, thick] (1,3) -- (0,4);
\draw[red, thick] (1,3) -- (2,4);
\filldraw[black] (0,0) circle (5pt)  {};
\filldraw[black] (2,2) circle (5pt)  {};
\filldraw[black] (1,3) circle (5pt)  {};
\filldraw[black] (-3,3) circle (5pt)  {};
\end{tikzpicture}}$,

$m^B(F_s\otimes F_t)=
\draw[blue, thick] (0,-1) -- (0,0);
\draw[blue, thick] (0,0) -- (-4,4);
\draw[blue, thick] (0,0) -- (2,2);
\draw[blue, thick] (1,1) -- (-2,4);
\draw[red, thick] (2,2) -- (0,4);
\draw[red, thick] (2,2) -- (2,4);
\draw[red, thick] (2,2) -- (4,4);
\filldraw[black] (0,0) circle (5pt)  {};
\filldraw[black] (1,1) circle (5pt)  {};
\filldraw[black] (2,2) circle (5pt)  {};
\end{tikzpicture}}+
\draw[blue, thick] (0,-1) -- (0,0);
\draw[blue, thick] (0,0) -- (-4,4);
\draw[blue, thick] (0,0) -- (4,4);
\draw[blue, thick] (1,1) -- (0,2);
\draw[red, thick] (0,2) -- (-2,4);
\draw[red, thick] (0,2) -- (0,4);
\draw[red, thick] (0,2) -- (2,4);
\filldraw[black] (0,0) circle (5pt)  {};
\filldraw[black] (1,1) circle (5pt)  {};
\filldraw[black] (0,2) circle (5pt)  {};
\end{tikzpicture}}+
\draw[blue, thick] (0,-1) -- (0,0);
\draw[blue, thick] (0,0) -- (-4,4);
\draw[blue, thick] (0,0) -- (4,4);
\draw[blue, thick] (3,3) -- (2,4);
\draw[red, thick] (-2,2) -- (0,4);
\draw[red, thick] (-2,2) -- (-2,4);
\draw[red, thick] (-2,2) -- (-4,4);
\filldraw[black] (0,0) circle (5pt)  {};
\filldraw[black] (-2,2) circle (5pt)  {};
\filldraw[black] (3,3) circle (5pt)  {};
\end{tikzpicture}}$.

$(\TSym,m^A,\Delta^A)$ and $(\TSym,m^B,\Delta^B)$ are both graded Hopf algebras with respect to the degree. $(\TSym,m^B,\Delta^B)$ is a graded Hopf algebra with respect to the internal degree as well  (so it is bigraded).

It is clear that $\Delta^A$ and $\Delta^B$ are both coassociative. To see associativity, let $r,s,t$ be trees of degree $a-1,b-1,c-1$ respectively, then for $(\TSym,m^A,\Delta^A)$,

\begin{align*}
\tilde{F}_r\cdot (\tilde{F}_s\cdot \tilde{F}_t)&=\sum_{t\mapsto(t_1,\dots,t_b)}\sum_{\substack{u=s\shuffle(t_1,\dots,t_b) \\ u\mapsto(u_1,\dots,u_a)}}\tilde{F}_{r\shuffle(u_1,\dots,u_a)}\\
&=\sum_{\substack{s \mapsto (s_1,\dots,s_a) \\ t \mapsto(t_1,\dots,t_{a+b-1})}}\tilde{F}_{\left(r\shuffle(s_1,\dots,s_a)\right)\shuffle(t_1,\dots,t_{a+b-1})}\\
&=(\tilde{F}_r\cdot \tilde{F}_s)\cdot \tilde{F}_t.
\end{align*}

The second equality can be visualized using the following example.

Let $r=\begin{tikzpicture}[scale=0.25,baseline=0pt]
\draw[blue, thick] (0,-1) -- (0,0);
\draw[blue, thick] (0,0) -- (-2,2);
\draw[blue, thick] (0,0) -- (2,2);
\draw[blue, thick] (0,0) -- (0,2);
\filldraw[black] (0,0) circle (5pt)  {};
\end{tikzpicture}$, $s=\begin{tikzpicture}[scale=0.25,baseline=0pt]
\draw[red, thick] (0,-1) -- (0,0);
\draw[red, thick] (0,0) -- (-4,4);
\draw[red, thick] (0,0) -- (4,4);
\draw[red, thick] (-3,3) -- (-2,4);
\draw[red, thick] (2,2) -- (0,4);
\draw[red, thick] (1,3) -- (2,4);
\filldraw[black] (-3,3) circle (5pt)  {};
\filldraw[black] (1,3) circle (5pt)  {};
\filldraw[black] (2,2) circle (5pt)  {};
\end{tikzpicture}$ and $t=\begin{tikzpicture}[scale=0.25,baseline=0pt]
\draw[ForestGreen, thick] (0,-1) -- (0,0);
\draw[ForestGreen, thick] (0,0) -- (-3,3);
\draw[ForestGreen, thick] (0,0) -- (3,3);
\draw[ForestGreen, thick] (0,0) -- (-1,3);
\draw[ForestGreen, thick] (2,2) -- (1,3);
\filldraw[black] (0,0) circle (5pt)  {};
\filldraw[black] (2,2) circle (5pt)  {};
\end{tikzpicture}$.

The choice $t\mapsto\left(~
\begin{tikzpicture}[scale=0.25,baseline=0pt]
\draw[ForestGreen, thick] (0,-1) -- (0,1);
\end{tikzpicture}~,~
\begin{tikzpicture}[scale=0.25,baseline=0pt]
\draw[ForestGreen, thick] (0,-1) -- (0,0);
\draw[ForestGreen, thick] (0,0) -- (-2,2);
\draw[ForestGreen, thick] (0,0) -- (2,2);
\draw[ForestGreen, thick] (0,0) -- (0,2);
\filldraw[black] (0,0) circle (5pt)  {};
\end{tikzpicture}~,~
\begin{tikzpicture}[scale=0.25,baseline=0pt]
\draw[ForestGreen, thick] (0,-1) -- (0,1);
\end{tikzpicture}~,~
\begin{tikzpicture}[scale=0.25,baseline=0pt]
\draw[ForestGreen, thick] (0,-1) -- (0,0);
\draw[ForestGreen, thick] (0,0) -- (-1,1);
\draw[ForestGreen, thick] (0,0) -- (1,1);
\filldraw[black] (0,0) circle (5pt)  {};
\end{tikzpicture}~,~
\begin{tikzpicture}[scale=0.25,baseline=0pt]
\draw[ForestGreen, thick] (0,-1) -- (0,1);
\end{tikzpicture}~\right)$ makes $u=
\begin{tikzpicture}[scale=0.25,baseline=0pt]
\draw[red, thick] (0,-1) -- (0,0);
\draw[red, thick] (0,0) -- (-5,5);
\draw[red, thick] (0,0) -- (6,6);
\draw[red, thick] (-4,4) -- (-3,5);
\draw[ForestGreen, thick] (-5,5) -- (-7,7);
\draw[ForestGreen, thick] (-3,5) -- (-5,7);
\draw[ForestGreen, thick] (-3,5) -- (-3,7);
\draw[ForestGreen, thick] (-3,5) -- (-1,7);
\draw[ForestGreen, thick] (6,6) -- (7,7);
\draw[ForestGreen, thick] (2,6) -- (1,7);
\draw[red, thick] (4,4) -- (2,6);
\draw[red, thick] (3,5) -- (4,6);
\draw[ForestGreen, thick] (4,6) -- (3,7);
\draw[ForestGreen, thick] (4,6) -- (5,7);
\filldraw[black] (0,0) circle (5pt)  {};
\filldraw[black] (-4,4) circle (5pt)  {};
\filldraw[black] (-3,5) circle (5pt)  {};
\filldraw[black] (4,4) circle (5pt)  {};
\filldraw[black] (3,5) circle (5pt)  {};
\filldraw[black] (4,6) circle (5pt)  {};
\end{tikzpicture}$

and the choice $u\mapsto\left(~
\begin{tikzpicture}[scale=0.25,baseline=0pt]
\draw[red, thick] (0,-1) -- (0,0);
\draw[red, thick] (0,0) -- (-1,1);
\draw[red, thick] (0,0) -- (1,1);
\draw[ForestGreen, thick] (-1,1) -- (-2,2);
\draw[ForestGreen, thick] (1,1) -- (2,2);
\draw[ForestGreen, thick] (1,1) -- (0,2);
\filldraw[black] (0,0) circle (5pt)  {};
\filldraw[black] (1,1) circle (5pt)  {};
\end{tikzpicture}~,~
\begin{tikzpicture}[scale=0.25,baseline=0pt]
\draw[red, thick] (0,-1) -- (0,0);
\draw[red, thick] (0,0) -- (3,3);
\draw[red, thick] (2,2) -- (1,3);
\draw[red, thick] (0,0) -- (-3,3);
\draw[ForestGreen, thick] (-3,3) -- (-4,4);
\draw[ForestGreen, thick] (-3,3) -- (-2,4);
\draw[ForestGreen, thick] (1,3) -- (0,4);
\draw[ForestGreen, thick] (3,3) -- (4,4);
\filldraw[black] (0,0) circle (5pt)  {};
\filldraw[black] (2,2) circle (5pt)  {};
\filldraw[black] (-3,3) circle (5pt)  {};
\end{tikzpicture}~,~
\begin{tikzpicture}[scale=0.25,baseline=0pt]
\draw[red, thick] (0,-1) -- (0,0);
\draw[red, thick] (0,0) -- (1,1);
\draw[red, thick] (0,0) -- (-1,1);
\draw[ForestGreen, thick] (1,1) -- (2,2);
\draw[ForestGreen, thick] (-1,1) -- (-2,2);
\draw[ForestGreen, thick] (-1,1) -- (0,2);
\filldraw[black] (0,0) circle (5pt)  {};
\filldraw[black] (-1,1) circle (5pt)  {};
\end{tikzpicture}~\right)$ yields
\draw[blue, thick] (0,-1) -- (0,0);
\draw[blue, thick] (0,0) -- (-8,8);
\draw[red, thick] (-8,8) -- (-9,9);
\draw[red, thick] (-8,8) -- (-7,9);
\draw[ForestGreen, thick] (-7,9) -- (-8,10);
\draw[ForestGreen, thick] (-7,9) -- (-6,10);
\draw[ForestGreen, thick] (-9,9) -- (-10,10);
\draw[blue, thick] (0,0) -- (0,6);
\draw[red, thick] (0,6) -- (-3,9);
\draw[red, thick] (0,6) -- (3,9);
\draw[red, thick] (2,8) -- (1,9);
\draw[ForestGreen, thick] (-3,9) -- (-2,10);
\draw[ForestGreen, thick] (-3,9) -- (-4,10);
\draw[ForestGreen, thick] (1,9) -- (0,10);
\draw[ForestGreen, thick] (3,9) -- (4,10);
\draw[blue, thick] (0,0) -- (8,8);
\draw[red, thick] (8,8) -- (9,9);
\draw[red, thick] (8,8) -- (7,9);
\draw[ForestGreen, thick] (7,9) -- (8,10);
\draw[ForestGreen, thick] (7,9) -- (6,10);
\draw[ForestGreen, thick] (9,9) -- (10,10);
\filldraw[black] (0,0) circle (5pt)  {};
\filldraw[black] (-8,8) circle (5pt)  {};
\filldraw[black] (-7,9) circle (5pt)  {};
\filldraw[black] (0,6) circle (5pt)  {};
\filldraw[black] (-3,9) circle (5pt)  {};
\filldraw[black] (2,8) circle (5pt)  {};
\filldraw[black] (8,8) circle (5pt)  {};
\filldraw[black] (7,9) circle (5pt)  {};
\end{tikzpicture}$.

On the other hand, the choice $s\mapsto\left(~
\begin{tikzpicture}[scale=0.25,baseline=0pt]
\draw[red, thick] (0,-1) -- (0,0);
\draw[red, thick] (0,0) -- (-1,1);
\draw[red, thick] (0,0) -- (1,1);
\filldraw[black] (0,0) circle (5pt)  {};
\end{tikzpicture}~,~
\begin{tikzpicture}[scale=0.25,baseline=0pt]
\draw[red, thick] (0,-1) -- (0,0);
\draw[red, thick] (0,0) -- (-2,2);
\draw[red, thick] (0,0) -- (2,2);
\draw[red, thick] (1,1) -- (0,2);
\filldraw[black] (0,0) circle (5pt)  {};
\filldraw[black] (1,1) circle (5pt)  {};
\end{tikzpicture}~,~
\begin{tikzpicture}[scale=0.25,baseline=0pt]
\draw[red, thick] (0,-1) -- (0,0);
\draw[red, thick] (0,0) -- (-1,1);
\draw[red, thick] (0,0) -- (1,1);
\filldraw[black] (0,0) circle (5pt)  {};
\end{tikzpicture}~\right)$ makes $
\begin{tikzpicture}[scale=0.25,baseline=0pt]
\draw[blue, thick] (0,-1) -- (0,0);
\draw[blue, thick] (0,0) -- (-5,5);
\draw[blue, thick] (0,0) -- (5,5);
\draw[red, thick] (-5,5) -- (-6,6);
\draw[red, thick] (-5,5) -- (-4,6);
\draw[red, thick] (5,5) -- (4,6);
\draw[red, thick] (5,5) -- (6,6);
\draw[blue, thick] (0,0) -- (0,4);
\draw[red, thick] (0,4) -- (-2,6);
\draw[red, thick] (0,4) -- (2,6);
\draw[red, thick] (1,5) -- (0,6);
\filldraw[black] (0,0) circle (5pt)  {};
\filldraw[black] (-5,5) circle (5pt)  {};
\filldraw[black] (5,5) circle (5pt)  {};
\filldraw[black] (0,4) circle (5pt)  {};
\filldraw[black] (1,5) circle (5pt)  {};
\end{tikzpicture}$

and the choice $t\mapsto\left(~
\begin{tikzpicture}[scale=0.25,baseline=0pt]
\draw[ForestGreen, thick] (0,-1) -- (0,1);
\end{tikzpicture}~,~
\begin{tikzpicture}[scale=0.25,baseline=0pt]
\draw[ForestGreen, thick] (0,-1) -- (0,0);
\draw[ForestGreen, thick] (0,0) -- (-1,1);
\draw[ForestGreen, thick] (0,0) -- (1,1);
\filldraw[black] (0,0) circle (5pt)  {};
\end{tikzpicture}~,~
\begin{tikzpicture}[scale=0.25,baseline=0pt]
\draw[ForestGreen, thick] (0,-1) -- (0,0);
\draw[ForestGreen, thick] (0,0) -- (-1,1);
\draw[ForestGreen, thick] (0,0) -- (1,1);
\filldraw[black] (0,0) circle (5pt)  {};
\end{tikzpicture}~,~
\begin{tikzpicture}[scale=0.25,baseline=0pt]
\draw[ForestGreen, thick] (0,-1) -- (0,1);
\end{tikzpicture}~,~
\begin{tikzpicture}[scale=0.25,baseline=0pt]
\draw[ForestGreen, thick] (0,-1) -- (0,1);
\end{tikzpicture}~,~
\begin{tikzpicture}[scale=0.25,baseline=0pt]
\draw[ForestGreen, thick] (0,-1) -- (0,0);
\draw[ForestGreen, thick] (0,0) -- (-1,1);
\draw[ForestGreen, thick] (0,0) -- (1,1);
\filldraw[black] (0,0) circle (5pt)  {};
\end{tikzpicture}~,~
\begin{tikzpicture}[scale=0.25,baseline=0pt]
\draw[ForestGreen, thick] (0,-1) -- (0,1);
\end{tikzpicture}~\right)$ yields
\draw[blue, thick] (0,-1) -- (0,0);
\draw[blue, thick] (0,0) -- (-8,8);
\draw[red, thick] (-8,8) -- (-9,9);
\draw[red, thick] (-8,8) -- (-7,9);
\draw[ForestGreen, thick] (-7,9) -- (-8,10);
\draw[ForestGreen, thick] (-7,9) -- (-6,10);
\draw[ForestGreen, thick] (-9,9) -- (-10,10);
\draw[blue, thick] (0,0) -- (0,6);
\draw[red, thick] (0,6) -- (-3,9);
\draw[red, thick] (0,6) -- (3,9);
\draw[red, thick] (2,8) -- (1,9);
\draw[ForestGreen, thick] (-3,9) -- (-2,10);
\draw[ForestGreen, thick] (-3,9) -- (-4,10);
\draw[ForestGreen, thick] (1,9) -- (0,10);
\draw[ForestGreen, thick] (3,9) -- (4,10);
\draw[blue, thick] (0,0) -- (8,8);
\draw[red, thick] (8,8) -- (9,9);
\draw[red, thick] (8,8) -- (7,9);
\draw[ForestGreen, thick] (7,9) -- (8,10);
\draw[ForestGreen, thick] (7,9) -- (6,10);
\draw[ForestGreen, thick] (9,9) -- (10,10);
\filldraw[black] (0,0) circle (5pt)  {};
\filldraw[black] (-8,8) circle (5pt)  {};
\filldraw[black] (-7,9) circle (5pt)  {};
\filldraw[black] (0,6) circle (5pt)  {};
\filldraw[black] (-3,9) circle (5pt)  {};
\filldraw[black] (2,8) circle (5pt)  {};
\filldraw[black] (8,8) circle (5pt)  {};
\filldraw[black] (7,9) circle (5pt)  {};
\end{tikzpicture}$.

It is left to see the compatibility. Let $s,t$ be two trees, $\deg(s)=k$. We use the notation $\Delta_i(s)=\Delta_{i,k-i}(s)={}^{(i)}s\otimes s^{(k-i)}$, then for $(\TSym,m^A,\Delta^A)$,

\begin{align*}
\Delta_i(\tilde{F}_s\cdot \tilde{F}_t)&=\sum_{t\mapsto(t_1,\dots,t_{k+1})}\Delta_i\tilde{F}_{s\shuffle (t_1,\dots,t_{k+1})}\\
&=\sum_{t\mapsto(t_1,\dots,t_{k+2})}\sum_{\deg(t_1)+\cdots+\deg(t_{n+1})=i-n}\tilde{F}_{^{(n)}s\shuffle (t_1,\dots,t_{n+1})}\otimes \tilde{F}_{s^{(k-n)}\shuffle(t_{n+2},\dots,t_{k+2})}\\
\end{align*}

The second equality can be visualized using the following example.

Let $s=\begin{tikzpicture}[scale=0.25,baseline=0pt]
\draw[red, thick] (0,-1) -- (0,0);
\draw[red, thick] (0,0) -- (-4,4);
\draw[red, thick] (0,0) -- (4,4);
\draw[red, thick] (-3,3) -- (-2,4);
\draw[red, thick] (2,2) -- (0,4);
\draw[red, thick] (1,3) -- (2,4);
\filldraw[black] (-3,3) circle (5pt)  {};
\filldraw[black] (1,3) circle (5pt)  {};
\filldraw[black] (2,2) circle (5pt)  {};
\end{tikzpicture}$, $t=\begin{tikzpicture}[scale=0.25,baseline=0pt]
\draw[ForestGreen, thick] (0,-1) -- (0,0);
\draw[ForestGreen, thick] (0,0) -- (-3,3);
\draw[ForestGreen, thick] (0,0) -- (3,3);
\draw[ForestGreen, thick] (0,0) -- (-1,3);
\draw[ForestGreen, thick] (2,2) -- (1,3);
\filldraw[black] (0,0) circle (5pt)  {};
\filldraw[black] (2,2) circle (5pt)  {};
\end{tikzpicture}$ and $i=2$.

The choice $t\mapsto\left(~
\begin{tikzpicture}[scale=0.25,baseline=0pt]
\draw[ForestGreen, thick] (0,-1) -- (0,1);
\end{tikzpicture}~,~
\begin{tikzpicture}[scale=0.25,baseline=0pt]
\draw[ForestGreen, thick] (0,-1) -- (0,0);
\draw[ForestGreen, thick] (0,0) -- (-2,2);
\draw[ForestGreen, thick] (0,0) -- (2,2);
\draw[ForestGreen, thick] (0,0) -- (0,2);
\filldraw[black] (0,0) circle (5pt)  {};
\end{tikzpicture}~,~
\begin{tikzpicture}[scale=0.25,baseline=0pt]
\draw[ForestGreen, thick] (0,-1) -- (0,1);
\end{tikzpicture}~,~
\begin{tikzpicture}[scale=0.25,baseline=0pt]
\draw[ForestGreen, thick] (0,-1) -- (0,0);
\draw[ForestGreen, thick] (0,0) -- (-1,1);
\draw[ForestGreen, thick] (0,0) -- (1,1);
\filldraw[black] (0,0) circle (5pt)  {};
\end{tikzpicture}~,~
\begin{tikzpicture}[scale=0.25,baseline=0pt]
\draw[ForestGreen, thick] (0,-1) -- (0,1);
\end{tikzpicture}~\right)$ gives $
\begin{tikzpicture}[scale=0.25,baseline=0pt]
\draw[red, thick] (0,-1) -- (0,0);
\draw[red, thick] (0,0) -- (-5,5);
\draw[red, thick] (0,0) -- (6,6);
\draw[red, thick] (-4,4) -- (-3,5);
\draw[ForestGreen, thick] (-5,5) -- (-7,7);
\draw[ForestGreen, thick] (-3,5) -- (-5,7);
\draw[ForestGreen, thick] (-3,5) -- (-3,7);
\draw[ForestGreen, thick] (-3,5) -- (-1,7);
\draw[ForestGreen, thick] (6,6) -- (7,7);
\draw[red, thick] (4,4) -- (2,6);
\draw[ForestGreen, thick] (2,6) -- (1,7);
\draw[red, thick] (3,5) -- (4,6);
\draw[ForestGreen, thick] (4,6) -- (3,7);
\draw[ForestGreen, thick] (4,6) -- (5,7);
\filldraw[black] (0,0) circle (5pt)  {};
\filldraw[black] (-4,4) circle (5pt)  {};
\filldraw[black] (-3,5) circle (5pt)  {};
\filldraw[black] (4,4) circle (5pt)  {};
\filldraw[black] (3,5) circle (5pt)  {};
\filldraw[black] (4,6) circle (5pt)  {};
\end{tikzpicture}\mapsto\left(~
\begin{tikzpicture}[scale=0.25,baseline=0pt]
\draw[red, thick] (0,-1) -- (0,0);
\draw[red, thick] (0,0) -- (-1,1);
\draw[red, thick] (0,0) -- (1,1);
\draw[ForestGreen, thick] (-1,1) -- (-2,2);
\draw[ForestGreen, thick] (1,1) -- (2,2);
\draw[ForestGreen, thick] (1,1) -- (0,2);
\filldraw[black] (0,0) circle (5pt)  {};
\filldraw[black] (1,1) circle (5pt)  {};
\end{tikzpicture}~,~
\begin{tikzpicture}[scale=0.25,baseline=0pt]
\draw[red, thick] (0,-1) -- (0,0);
\draw[red, thick] (0,0) -- (-4,4);
\draw[ForestGreen, thick] (-4,4) -- (-5,5);
\draw[ForestGreen, thick] (-4,4) -- (-3,5);
\draw[red, thick] (0,0) -- (4,4);
\draw[red, thick] (2,2) -- (0,4);
\draw[ForestGreen, thick] (0,4) -- (-1,5);
\draw[red, thick] (1,3) -- (2,4);
\draw[ForestGreen, thick] (4,4) -- (5,5);
\draw[ForestGreen, thick] (2,4) -- (1,5);
\draw[ForestGreen, thick] (2,4) -- (3,5);
\filldraw[black] (0,0) circle (5pt)  {};
\filldraw[black] (-4,4) circle (5pt)  {};
\filldraw[black] (2,2) circle (5pt)  {};
\filldraw[black] (1,3) circle (5pt)  {};
\filldraw[black] (2,4) circle (5pt)  {};
\end{tikzpicture}~\right)$. On the other hand, the choice $t\mapsto\left(~
\begin{tikzpicture}[scale=0.25,baseline=0pt]
\draw[ForestGreen, thick] (0,-1) -- (0,1);
\end{tikzpicture}~,~
\begin{tikzpicture}[scale=0.25,baseline=0pt]
\draw[ForestGreen, thick] (0,-1) -- (0,0);
\draw[ForestGreen, thick] (0,0) -- (-1,1);
\draw[ForestGreen, thick] (0,0) -- (1,1);
\filldraw[black] (0,0) circle (5pt)  {};
\end{tikzpicture}~,~
\begin{tikzpicture}[scale=0.25,baseline=0pt]
\draw[ForestGreen, thick] (0,-1) -- (0,0);
\draw[ForestGreen, thick] (0,0) -- (-1,1);
\draw[ForestGreen, thick] (0,0) -- (1,1);
\filldraw[black] (0,0) circle (5pt)  {};
\end{tikzpicture}~,~
\begin{tikzpicture}[scale=0.25,baseline=0pt]
\draw[ForestGreen, thick] (0,-1) -- (0,1);
\end{tikzpicture}~,~
\begin{tikzpicture}[scale=0.25,baseline=0pt]
\draw[ForestGreen, thick] (0,-1) -- (0,0);
\draw[ForestGreen, thick] (0,0) -- (-1,1);
\draw[ForestGreen, thick] (0,0) -- (1,1);
\filldraw[black] (0,0) circle (5pt)  {};
\end{tikzpicture}~,~
\begin{tikzpicture}[scale=0.25,baseline=0pt]
\draw[ForestGreen, thick] (0,-1) -- (0,1);
\end{tikzpicture}~\right)$ makes $n=1$ and hence $s\mapsto\left(~
\begin{tikzpicture}[scale=0.25,baseline=0pt]
\draw[red, thick] (0,-1) -- (0,0);
\draw[red, thick] (0,0) -- (1,1);
\draw[red, thick] (0,0) -- (-1,1);
\filldraw[black] (0,0) circle (5pt)  {};
\end{tikzpicture}~,~
\begin{tikzpicture}[scale=0.25,baseline=0pt]
\draw[red, thick] (0,-1) -- (0,0);
\draw[red, thick] (0,0) -- (-3,3);
\draw[red, thick] (1,1) -- (-1,3);
\draw[red, thick] (0,2) -- (1,3);
\draw[red, thick] (0,0) -- (3,3);
\filldraw[black] (0,0) circle (5pt)  {};
\filldraw[black] (1,1) circle (5pt)  {};
\filldraw[black] (0,2) circle (5pt)  {};
\end{tikzpicture}~\right)$.

The argument above works for $(\TSym,m^B,\Delta^B)$ as well, by taking the sum of all allowable splittings.

Alternatively, one may prove the associativity of the multiplication and the compatibility using operadic methods, such as <cit.>.

The two Hopf structures $(\TSym,m^A,\Delta^A)$ and $(\TSym,m^B,\Delta^B)$ are isomorphic.

We define a partial order $\leq$ on planar trees. The covering relation is as follows. Fix a tree $t$ and an internal node $x$ of degree at least 3. Fix a branch of $x$ in the middle, and move it along the left child of $x$ that creates a new internal node $y$. This process gives a new tree $s$ and we define the covering relation $t\lessdot s$.
See Figure <ref> to visualize the covering relation and an example of connected component of the partial order.

at (0,0)
at (0,0) $x$;
at (1.5,1.3) $B$;
at (-1.5,1.3) $A$;

[Mahogany,ultra thick] (0,0.3) – (0.5,1.2) – (1.2,1.2);
[ForestGreen,ultra thick] (0,0.3) – (-1.2,1.2) – (0.5,1.2);

at (0,2) $\uparrow$;

at (0,3) $x$;
at (-3,5.9) $A$;
at (1.5,4.5) $B$;
[black] (-1.5,4.5) circle (3pt)  ;

[ForestGreen,very thick] (-0.3,3.3) – (-1.2,4.2);
[Mahogany,very thick] (0.2,3.3) – (1.2,4.2) – (-0.8,4.2);
[ForestGreen,ultra thick] (-1.5,4.8) – (-2.7,5.7) – (-0.3,5.7);
at (8,0)
[Mahogany, ultra thick] (-2.2,2) – (-8.7,6);
[Mahogany, ultra thick] (-2.2,10) – (-8.7,14);
[Mahogany, ultra thick] (7.8,10) – (1.3,14);
[Mahogany, ultra thick] (7.8,18) – (1.3,22);

[ForestGreen, ultra thick] (2.2,2) – (8.7,6);
[ForestGreen, ultra thick] (2.2,10) – (4.475,11.4);
[ForestGreen, ultra thick] (5.45,12) – (8.7,14);
[ForestGreen, ultra thick] (-7.8,10) – (-5.525,11.4);
[ForestGreen, ultra thick] (-4.55,12) – (-1.3,14);
[ForestGreen, ultra thick] (-7.8,18) – (-1.3,22);

[YellowOrange, ultra thick] (0,2.3) – (0,5.7);
[YellowOrange, ultra thick] (-10,10.3) – (-10,13.7);
[YellowOrange, ultra thick] (10,10.3) – (10,13.7);
[YellowOrange, ultra thick] (0,18.3) – (0,21.7);

() at (0,0)[scale=0.1]
[blue, thick] (0,-1) – (0,0);
[blue, thick] (0,0) – (6,6);
[blue, thick] (0,0) – (-6,6);
[blue, thick] (0,0) – (-2,4);
[blue, thick] (-2,4) – (-4,6);
[blue, thick] (-2,4) – (-2,6);
[blue, thick] (-2,4) – (0,6);
[blue, thick] (0,0) – (2,6);
[blue, thick] (5,5) – (4,6);
[black] (0,0) circle (5pt)  ;
[black] (5,5) circle (5pt)  ;
[black] (-2,4) circle (5pt)  ;;
() at (-10,8)[scale=0.1]
[blue, thick] (0,-1) – (0,0);
[blue, thick] (0,0) – (6,6);
[blue, thick] (0,0) – (-6,6);
[blue, thick] (-2,4) – (-4,6);
[blue, thick] (-2,4) – (-2,6);
[blue, thick] (-3,3) – (0,6);
[blue, thick] (0,0) – (2,6);
[blue, thick] (5,5) – (4,6);
[black] (0,0) circle (5pt)  ;
[black] (5,5) circle (5pt)  ;
[black] (-3,3) circle (5pt)  ;
[black] (-2,4) circle (5pt)  ;;
() at (0,8)[scale=0.1]
[blue, thick] (0,-1) – (0,0);
[blue, thick] (0,0) – (6,6);
[blue, thick] (0,0) – (-6,6);
[blue, thick] (-2,2) – (-2,4);
[blue, thick] (-2,4) – (-4,6);
[blue, thick] (-2,4) – (-2,6);
[blue, thick] (-2,4) – (0,6);
[blue, thick] (-2,2) – (2,6);
[blue, thick] (5,5) – (4,6);
[black] (0,0) circle (5pt)  ;
[black] (-2,2) circle (5pt)  ;
[black] (5,5) circle (5pt)  ;
[black] (-2,4) circle (5pt)  ;;
() at (10,8)[scale=0.1]
[blue, thick] (0,-1) – (0,0);
[blue, thick] (0,0) – (6,6);
[blue, thick] (0,0) – (-6,6);
[blue, thick] (0,0) – (-2,4);
[blue, thick] (-2,4) – (-4,6);
[blue, thick] (-3,5) – (-2,6);
[blue, thick] (-2,4) – (0,6);
[blue, thick] (0,0) – (2,6);
[blue, thick] (5,5) – (4,6);
[black] (0,0) circle (5pt)  ;
[black] (5,5) circle (5pt)  ;
[black] (-3,5) circle (5pt)  ;
[black] (-2,4) circle (5pt)  ;;
() at (-10,16)[scale=0.1]
[blue, thick] (0,-1) – (0,0);
[blue, thick] (0,0) – (6,6);
[blue, thick] (0,0) – (-6,6);
[blue, thick] (-2,4) – (-4,6);
[blue, thick] (-2,4) – (-2,6);
[blue, thick] (-3,3) – (0,6);
[blue, thick] (-2,2) – (2,6);
[blue, thick] (5,5) – (4,6);
[black] (0,0) circle (5pt)  ;
[black] (-2,2) circle (5pt)  ;
[black] (5,5) circle (5pt)  ;
[black] (-3,3) circle (5pt)  ;
[black] (-2,4) circle (5pt)  ;;
() at (0,16)[scale=0.1]
[blue, thick] (0,-1) – (0,0);
[blue, thick] (0,0) – (6,6);
[blue, thick] (0,0) – (-6,6);
[blue, thick] (-2,4) – (-4,6);
[blue, thick] (-3,5) – (-2,6);
[blue, thick] (-3,3) – (0,6);
[blue, thick] (0,0) – (2,6);
[blue, thick] (5,5) – (4,6);
[black] (0,0) circle (5pt)  ;
[black] (-3,3) circle (5pt)  ;
[black] (5,5) circle (5pt)  ;
[black] (-3,5) circle (5pt)  ;
[black] (-2,4) circle (5pt)  ;;
() at (10,16)[scale=0.1]
[blue, thick] (0,-1) – (0,0);
[blue, thick] (0,0) – (6,6);
[blue, thick] (0,0) – (-6,6);
[blue, thick] (-2,2) – (-2,4);
[blue, thick] (-2,4) – (-4,6);
[blue, thick] (-3,5) – (-2,6);
[blue, thick] (-2,4) – (0,6);
[blue, thick] (-2,2) – (2,6);
[blue, thick] (5,5) – (4,6);
[black] (0,0) circle (5pt)  ;
[black] (-2,2) circle (5pt)  ;
[black] (5,5) circle (5pt)  ;
[black] (-3,5) circle (5pt)  ;
[black] (-2,4) circle (5pt)  ;;
() at (0,24)[scale=0.1]
[blue, thick] (0,-1) – (0,0);
[blue, thick] (0,0) – (6,6);
[blue, thick] (0,0) – (-6,6);
[blue, thick] (-2,4) – (-4,6);
[blue, thick] (-3,5) – (-2,6);
[blue, thick] (-3,3) – (0,6);
[blue, thick] (-2,2) – (2,6);
[blue, thick] (5,5) – (4,6);
[black] (0,0) circle (5pt)  ;
[black] (-3,3) circle (5pt)  ;
[black] (-2,2) circle (5pt)  ;
[black] (5,5) circle (5pt)  ;
[black] (-3,5) circle (5pt)  ;
[black] (-2,4) circle (5pt)  ;;

Covering relation and a connected component of the partial order on planar trees needed for Proposition <ref>

Applying the basic move at each internal node of a tree $t$ generates a boolean poset. Since the basic moves at two different internal nodes are independent of each other, we see that each connected component in this order is a boolean poset.

Fix a tree $t$, and an integer $i\in [1,\deg t-1]$. Construct the tree $t_{(i)}\geq t$ by applying the above cover relation to every node along the path from the $i+1$th leaf to the root, for the branch that is along this path. Then $t_{(i)}$ is a unique minimal tree  such that $t_{(i)}\geq t$ and the splitting at the $(i+1)$-th leaf of $t_{(i)}$ is allowable. Moreover, splitting $t_{(i)}$ and $t$ at the $(i+1)$-th leaf give the same result i.e. $({}^it,t^i)=({}^it_{(i)},t^i_{(i)})$. As an example, if we consider $t$ to be the bottom tree [scale=0.1]
[blue, thick] (0,-1) – (0,0);
[blue, thick] (0,0) – (6,6);
[blue, thick] (0,0) – (-6,6);
[blue, thick] (0,0) – (-2,4);
[blue, thick] (-2,4) – (-4,6);
[blue, thick] (-2,4) – (-2,6);
[blue, thick] (-2,4) – (0,6);
[blue, thick] (0,0) – (2,6);
[blue, thick] (5,5) – (4,6);
[black] (0,0) circle (5pt)  ;
[black] (5,5) circle (5pt)  ;
[black] (-2,4) circle (5pt)  ; in Figure <ref>, then [scale=0.1]
[blue, thick] (0,-1) – (0,0);
[blue, thick] (0,0) – (6,6);
[blue, thick] (0,0) – (-6,6);
[blue, thick] (-2,4) – (-4,6);
[blue, thick] (-3,5) – (-2,6);
[blue, thick] (-3,3) – (0,6);
[blue, thick] (0,0) – (2,6);
[blue, thick] (5,5) – (4,6);
[black] (0,0) circle (5pt)  ;
[black] (-3,3) circle (5pt)  ;
[black] (5,5) circle (5pt)  ;
[black] (-3,5) circle (5pt)  ;
[black] (-2,4) circle (5pt)  ; is the tree $t_{(2)}$.

We define a new basis $\{H_t\}$ such that $H_t=\displaystyle\sum_{s\geq t} F_s$. Then,

$$\Delta_i^B(H_t)=\sum_{s\geq t}\Delta_i^B(F_s)=\sum_{s\geq t_{(i)}}\Delta_i^B(F_s)=\sum_{s_1\geq {}^it,s_2\geq t^i}F_{s_1}\otimes F_{s_2}=H_{{}^it}\otimes H_{t^i}.$$

By construction, we know that $\Delta_i^A(\tilde{F}_t)=\tilde{F}_{{}^it}\otimes \tilde{F}_{t^i}$. And since the two multiplications $m^A$ and $m^B$ are based on the composed comultiplication $\Delta^A\circ\cdots\circ\Delta^A$ and $\Delta^B\circ\cdots\circ\Delta^B$, we have an isomorphism $(\TSym,m^B,\Delta^B)\to(\TSym,m^A,\Delta^A)$ such that $H_t\mapsto \tilde{F}_t$.

In the rest of this paper, we only consider the operations $m^B,\Delta^B$, which we will denote by $m,\Delta$.

The Hopf algebra $\YSym$ does not have a bidendriform bialgebra structure. Hence, we do not expect one for $\TSym$.

§.§ Planar Tamari order and monomial basis

A left rotation is the operation on planar trees described in Figure <ref>

at (0,0)
at (0,0) $x$;
[black] (1.5,1.5) circle (3pt)  ;
at (-0.5,1.5) $t_1~t_2\cdots\cdots$;
at (0,3) $t_a$;
at (2,3) $\cdots t_{a+b-1}~t_{a+b}$;

[ForestGreen,ultra thick] (0.3,0.3) – (1.2,1.2);
[ForestGreen,ultra thick] (-0.2,0.3) – (-1.2,1.2) – (0.8,1.2);
[Mahogany,ultra thick] (1.7,1.8) – (2.7,2.7) – (0.7,2.7);
[Mahogany,ultra thick] (1.2,1.8) – (0.3,2.7);
at (4,0) $\mapsto$;
at (8,0)
at (0,0) $x$;
[black] (-1.5,1.5) circle (3pt)  ;
at (-2,3) $t_1~t_2\cdots\cdots$;
at (0,3) $t_a$;
at (0.5,1.5) $\cdots t_{a+b-1}~t_{a+b}$;

[Mahogany,very thick] (0.2,0.3) – (1.2,1.2) – (-0.8,1.2);
[ForestGreen,very thick] (-0.3,0.3) – (-1.2,1.2);
[ForestGreen,very thick] (-1.7,1.8) – (-2.7,2.7) – (-0.7,2.7);
[Mahogany,very thick] (-1.2,1.8) – (-0.3,2.7);

A left rotation: the cover relation of planar Tamari order

We define the planar Tamari order on planar trees as follow. A cover relation $s\lessdot_{PT}t$ is defined if $t$ is obtained from $s$ by doing a left rotation at a node $x$, where $y$ is the right most child of $x$, and $B$ is the left most branch of $y$ as depicted Figure <ref>. The planar left Tamari of size $n$ is the transitive closure of this relation. For example see Figure <ref> and  <ref>.

at (0,0) [scale=0.4]
() at (0,0)[scale=0.2,baseline=0pt]
[blue, thick] (0,-1) – (0,0);
[blue, thick] (0,0) – (3,3);
[blue, thick] (0,0) – (1,3);
[blue, thick] (0,0) – (-1,3);
[blue, thick] (0,0) – (-3,3);
[black] (0,0) circle (5pt)  ;;
() at (0,5)[scale=0.25,baseline=0pt]
[blue, thick] (0,-1) – (0,0);
[blue, thick] (0,0) – (3,3);
[blue, thick] (0,2) – (1,3);
[blue, thick] (0,2) – (-1,3);
[blue, thick] (0,0) – (-3,3);
[blue, thick] (0,0) – (0,2);
[black] (0,0) circle (5pt)  ;
[black] (0,2) circle (5pt)  ;;
at (3,0) [scale=0.4]
[ForestGreen, ultra thick] (0,1.5) – (0,3.5);
() at (0,0)[scale=0.2,baseline=0pt]
[blue, thick] (0,-1) – (0,0);
[blue, thick] (0,0) – (3,3);
[blue, thick] (1,1) – (1,3);
[blue, thick] (1,1) – (-1,3);
[blue, thick] (0,0) – (-3,3);
[black] (0,0) circle (5pt)  ;
[black] (1,1) circle (5pt)  ;;
() at (0,5)[scale=0.25,baseline=0pt]
[blue, thick] (0,-1) – (0,0);
[blue, thick] (0,0) – (3,3);
[blue, thick] (0,0) – (1,3);
[blue, thick] (-2,2) – (-1,3);
[blue, thick] (0,0) – (-3,3);
[black] (0,0) circle (5pt)  ;
[black] (-2,2) circle (5pt)  ;;
at (6,0) [scale=0.4]
[ForestGreen, ultra thick] (0,1.5) – (0,3.5);
() at (0,0)[scale=0.2,baseline=0pt]
[blue, thick] (0,-1) – (0,0);
[blue, thick] (0,0) – (3,3);
[blue, thick] (2,2) – (1,3);
[blue, thick] (0,0) – (-1,3);
[blue, thick] (0,0) – (-3,3);
[black] (0,0) circle (5pt)  ;
[black] (2,2) circle (5pt)  ;;
() at (0,5)[scale=0.25,baseline=0pt]
[blue, thick] (0,-1) – (0,0);
[blue, thick] (0,0) – (3,3);
[blue, thick] (-1,1) – (1,3);
[blue, thick] (-1,1) – (-1,3);
[blue, thick] (0,0) – (-3,3);
[black] (0,0) circle (5pt)  ;
[black] (-1,1) circle (5pt)  ;;
at (10.5,0) [scale=0.4]
[ForestGreen, ultra thick] (-3,6.5) – (-3,8.5);
[ForestGreen, ultra thick] (1,1.5) – (2.7,6);
[ForestGreen, ultra thick] (1,14) – (2.7,9.5);
[ForestGreen, ultra thick] (-1,14) – (-2.7,12);
[ForestGreen, ultra thick] (-1,1.5) – (-2.7,3.5);
() at (0,0)[scale=0.2,baseline=0pt]
[blue, thick] (0,-1) – (0,0);
[blue, thick] (0,0) – (3,3);
[blue, thick] (2,2) – (1,3);
[blue, thick] (1,1) – (-1,3);
[blue, thick] (0,0) – (-3,3);
[black] (0,0) circle (5pt)  ;
[black] (1,1) circle (5pt)  ;
[black] (2,2) circle (5pt)  ;;
() at (-3,5)[scale=0.25,baseline=0pt]
[blue, thick] (0,-1) – (0,0);
[blue, thick] (0,0) – (3,3);
[blue, thick] (0,2) – (1,3);
[blue, thick] (1,1) – (-1,3);
[blue, thick] (0,0) – (-3,3);
[black] (0,0) circle (5pt)  ;
[black] (1,1) circle (5pt)  ;
[black] (0,2) circle (5pt)  ;;
() at (-3,10)[scale=0.25,baseline=0pt]
[blue, thick] (0,-1) – (0,0);
[blue, thick] (0,0) – (3,3);
[blue, thick] (-1,1) – (1,3);
[blue, thick] (0,2) – (-1,3);
[blue, thick] (0,0) – (-3,3);
[black] (0,0) circle (5pt)  ;
[black] (-1,1) circle (5pt)  ;
[black] (0,2) circle (5pt)  ;;
() at (3,7.5)[scale=0.25,baseline=0pt]
[blue, thick] (0,-1) – (0,0);
[blue, thick] (0,0) – (3,3);
[blue, thick] (2,2) – (1,3);
[blue, thick] (-2,2) – (-1,3);
[blue, thick] (0,0) – (-3,3);
[black] (0,0) circle (5pt)  ;
[black] (2,2) circle (5pt)  ;
[black] (-2,2) circle (5pt)  ;;
() at (0,15)[scale=0.25,baseline=0pt]
[blue, thick] (0,-1) – (0,0);
[blue, thick] (0,0) – (3,3);
[blue, thick] (-1,1) – (1,3);
[blue, thick] (-2,2) – (-1,3);
[blue, thick] (0,0) – (-3,3);
[black] (0,0) circle (5pt)  ;
[black] (-1,1) circle (5pt)  ;
[black] (-2,2) circle (5pt)  ;;

Planar Tamari order on trees with $4$ leaves.

at (0,0)
() at (0,0)[scale=0.2,baseline=0pt]
[blue, thick] (0,-1) – (0,0);
[blue, thick] (0,0) – (5,5);
[blue, thick] (4,4) – (3,5);
[blue, thick] (-1,3) – (1,5);
[blue, thick] (0,4) – (-1,5);
[blue, thick] (-1,3) – (-3,5);
[blue, thick] (0,0) – (-5,5);
[blue, thick] (0,0) – (-1,3);
[black] (0,0) circle (5pt)  ;
[black] (4,4) circle (5pt)  ;
[black] (-1,3) circle (5pt)  ;
[black] (0,4) circle (5pt)  ;;
() at (-3,3)[scale=0.2,baseline=0pt]
[blue, thick] (0,-1) – (0,0);
[blue, thick] (0,0) – (5,5);
[blue, thick] (-1,1) – (3,5);
[blue, thick] (-1,3) – (1,5);
[blue, thick] (0,4) – (-1,5);
[blue, thick] (-1,3) – (-3,5);
[blue, thick] (0,0) – (-5,5);
[blue, thick] (-1,1) – (-1,3);
[black] (0,0) circle (5pt)  ;
[black] (-1,1) circle (5pt)  ;
[black] (-1,3) circle (5pt)  ;
[black] (0,4) circle (5pt)  ;;
() at (3,3)[scale=0.2,baseline=0pt]
[blue, thick] (0,-1) – (0,0);
[blue, thick] (0,0) – (5,5);
[blue, thick] (4,4) – (3,5);
[blue, thick] (-1,3) – (1,5);
[blue, thick] (-2,4) – (-1,5);
[blue, thick] (-1,3) – (-3,5);
[blue, thick] (0,0) – (-5,5);
[blue, thick] (0,0) – (-1,3);
[black] (0,0) circle (5pt)  ;
[black] (4,4) circle (5pt)  ;
[black] (-1,3) circle (5pt)  ;
[black] (-2,4) circle (5pt)  ;;
() at (0,6)[scale=0.2,baseline=0pt]
[blue, thick] (0,-1) – (0,0);
[blue, thick] (0,0) – (5,5);
[blue, thick] (-1,1) – (3,5);
[blue, thick] (-1,3) – (1,5);
[blue, thick] (-2,4) – (-1,5);
[blue, thick] (-1,3) – (-3,5);
[blue, thick] (0,0) – (-5,5);
[blue, thick] (-1,1) – (-1,3);
[black] (0,0) circle (5pt)  ;
[black] (-1,1) circle (5pt)  ;
[black] (-1,3) circle (5pt)  ;
[black] (-2,4) circle (5pt)  ;;

[ForestGreen,ultra thick] (0.8,0.8) – (2.4,2.4);
[ForestGreen,ultra thick] (-0.8,0.8) – (-2.4,2.4);
[ForestGreen,ultra thick] (-2.2,3.8) – (-0.6,5.4);
[ForestGreen,ultra thick] (2.2,3.8) – (0.6,5.4);

Another connected component of planar Tamari order.

Let $F_s$ and $F_t$ be two basis elements in $\TSym$, and let $F_s^*$, $F_t^*$ be their dual basis elements in the graded dual $\TSym^*$. Then,

$$m(F_s^*\otimes F_t^*)=\sum_{s\backslash t\leq_{PT} r\leq_{PT} s/t}F_r^*.$$

The proof will be given as Corollary <ref>, after introducing a partial order on generalized Stirling permutations.

The monomial basis of $\TSym$ are defined as the elements satisfying $\displaystyle F_s=\sum_{t\geq_{PT} s}M_t$. The monomial basis is unique by triangularity and it forms a basis via Möbius inversion.

Let $t$ be a planar tree of degree $n$. Its global descent set is $\GD(t)=\{i\in[n-1]:t=s/r\text{ for some }s,r\text{ and }\deg(s)=i\}$.

The coproduct of
monomial basis elements of $\TSym$ is given by

\[
\Delta_{+}(M_{t})=\sum_{i\in\GD(f)}M_{{}^{i}t}\otimes M_{t^{i}}.
\]

The product
of monomial basis elements of $\TSym$ is given by $M_{s}\cdot M_{t}=\sum_{r}\alpha_{s,t}^{r}M_{r}$,
where $\alpha_{s,t}^{r}=|A_{s,t}^{r}|$ is defined as in (<ref>).

antipode of monomial basis elements in $\TSym$ is given by $\mathcal{S}(M_{t})=(-1)^{\GD(t)+1}\sum_{s}\beta_{t}^{s}M_{s}$
where $\beta_{t}^{s}$ is defined as in (<ref>).

We check the axioms of Theorem <ref>, for the
case $\bar{\mathcal{H}}=\TSym$ and $\mathcal{H}=\STSym$, the algebra
of generalized Stirling permutations of the next section. This would
provide the axioms for Theorems <ref>, <ref>
and <ref>, which give respectively the results above.

The proofs of Propositions <ref>, <ref>
and <ref> below show that $\STSym$
satisfies all necessary axioms for Theorem <ref>.
Proposition <ref> checks the conditions on $\pi$ and $\iota$,
and axiom ($\pi$0). It is clear that $\TSym$ satisfies axioms ($\pi\Delta$1)
and ($\pi m$1), and axioms ($\pi\Delta$2), ($\pi m$2), ($\pi\mathcal{S}$1)
and ($\pi\mathcal{S}$2) follow from Propositions <ref>,
and Lemma <ref>.

When all internal nodes of a tree $t$ have $m+1$ children, we obtain $(m+1)$-ary trees. Restricting our planar Tamari order to $(m+1)$-ary trees gives a partial order that coarsens the $m$-Tamari order defined in [3], and the associated Hopf subalgebra of $\TSym$ is isomorphic to the one defined in [21]. Moreover, for every given subset of positive integers $A \subseteq \mathbb{P}$ we obtain a Hopf subalgebra of $\TSym$ restricting to trees whose internal nodes are all in $A$. This is  related to a partition, studied by Ceballos and González D'León in [5], of the set of planar trees  in terms of compositions, which they call signatures. An open question is to find further Hopf constructions that are compatible with the notion of signature.

§ HOPF ALGEBRA OF GENERALIZED STIRLING PERMUTATIONS

§.§ Generalized Stirling permutations and packed words

In this section, we extend $\TSym$ to the context of generalized Stirling permutations, and we study their connections with packed words and ordered set compositions.

A generalized Stirling permutation $u$ of degree $n$ is a labeled tree with $n+1$ leaves and $\kappa_u$ is a bijection from the set of internal nodes to $\{1,2,\dots,\ideg(u)\}$ such that the label of each internal node is less than the labels of its children. The set of generalized Stirling permutations is denoted by $\GSP$. See for example Figure <ref>.

[blue, thick] (0,-1) – (0,0);
[blue, thick] (0,0) – (3,3);
[blue, thick] (0,0) – (-3,3);
[blue, thick] (0,0) – (-1,3);
[blue, thick] (0,0) – (1,3);
[black] (0,0) circle (5pt)  ;
at (-1,1.5)[font=7pt0]$1$;
at (0,1.5)[font=7pt0]$1$;
at (1,1.5)[font=7pt0]$1$;

[blue, thick] (0,-1) – (0,0);
[blue, thick] (0,0) – (3,3);
[blue, thick] (0,0) – (-3,3);
[blue, thick] (0,0) – (-1,3);
[blue, thick] (2,2) – (1,3);
[black] (0,0) circle (5pt)  ;
[black] (2,2) circle (5pt)  ;
at (-1,1.5)[font=7pt0]$1$;
at (0.5,1.5)[font=7pt0]$1$;
at (2,2.7)[font=7pt0]$2$;

[blue, thick] (10,-1) – (10,0);
[blue, thick] (10,0) – (13,3);
[blue, thick] (10,0) – (7,3);
[blue, thick] (10,0) – (10,2);
[blue, thick] (10,2) – (9,3);
[blue, thick] (10,2) – (11,3);
[black] (10,0) circle (5pt)  ;
[black] (10,2) circle (5pt)  ;
at (9.5,1)[font=7pt0]$1$;
at (10.5,1)[font=7pt0]$1$;
at (10,2.7)[font=7pt0]$2$;

[blue, thick] (20,-1) – (20,0);
[blue, thick] (20,0) – (23,3);
[blue, thick] (20,0) – (17,3);
[blue, thick] (20,0) – (21,3);
[blue, thick] (18,2) – (19,3);
[black] (20,0) circle (5pt)  ;
[black] (18,2) circle (5pt)  ;
at (21,1.5)[font=7pt0]$1$;
at (19.5,1.5)[font=7pt0]$1$;
at (18,2.7)[font=7pt0]$2$;

[blue, thick] (30,-1) – (30,0);
[blue, thick] (30,0) – (33,3);
[blue, thick] (30,0) – (27,3);
[blue, thick] (29,1) – (31,3);
[blue, thick] (29,1) – (29,3);
[black] (30,0) circle (5pt)  ;
[black] (29,1) circle (5pt)  ;
at (30,0.7)[font=7pt0]$1$;
at (28.5,2)[font=7pt0]$2$;
at (29.5,2)[font=7pt0]$2$;

[blue, thick] (40,-1) – (40,0);
[blue, thick] (40,0) – (37,3);
[blue, thick] (40,0) – (43,3);
[blue, thick] (41,1) – (41,3);
[blue, thick] (41,1) – (39,3);
[black] (40,0) circle (5pt)  ;
[black] (41,1) circle (5pt)  ;
at (40,0.7)[font=7pt0]$1$;
at (40.5,2)[font=7pt0]$2$;
at (41.5,2)[font=7pt0]$2$;

[blue, thick] (0,-1) – (0,0);
[blue, thick] (0,0) – (3,3);
[blue, thick] (0,0) – (-3,3);
[blue, thick] (1,1) – (-1,3);
[blue, thick] (2,2) – (1,3);
[black] (0,0) circle (5pt)  ;
[black] (1,1) circle (5pt)  ;
[black] (2,2) circle (5pt)  ;
at (0,0.7)[font=7pt0]$1$;
at (1,1.7)[font=7pt0]$2$;
at (2,2.7)[font=7pt0]$3$;

[blue, thick] (10,-1) – (10,0);
[blue, thick] (10,0) – (13,3);
[blue, thick] (10,0) – (7,3);
[blue, thick] (11,1) – (9,3);
[blue, thick] (10,2) – (11,3);
[black] (10,0) circle (5pt)  ;
[black] (11,1) circle (5pt)  ;
[black] (10,2) circle (5pt)  ;
at (10,0.7)[font=7pt0]$1$;
at (11,1.7)[font=7pt0]$2$;
at (10,2.7)[font=7pt0]$3$;

[blue, thick] (20,-1) – (20,0);
[blue, thick] (20,0) – (23,3);
[blue, thick] (20,0) – (17,3);
[blue, thick] (22,2) – (21,3);
[blue, thick] (18,2) – (19,3);
[black] (20,0) circle (5pt)  ;
[black] (22,2) circle (5pt)  ;
[black] (18,2) circle (5pt)  ;
at (20,0.7)[font=7pt0]$1$;
at (18,2.7)[font=7pt0]$2$;
at (22,2.7)[font=7pt0]$3$;

[blue, thick] (30,-1) – (30,0);
[blue, thick] (30,0) – (33,3);
[blue, thick] (30,0) – (27,3);
[blue, thick] (32,2) – (31,3);
[blue, thick] (28,2) – (29,3);
[black] (30,0) circle (5pt)  ;
[black] (32,2) circle (5pt)  ;
[black] (28,2) circle (5pt)  ;
at (30,0.7)[font=7pt0]$1$;
at (32,2.7)[font=7pt0]$2$;
at (28,2.7)[font=7pt0]$3$;

[blue, thick] (40,-1) – (40,0);
[blue, thick] (40,0) – (43,3);
[blue, thick] (40,0) – (37,3);
[blue, thick] (39,1) – (41,3);
[blue, thick] (40,2) – (39,3);
[black] (40,0) circle (5pt)  ;
[black] (39,1) circle (5pt)  ;
[black] (40,2) circle (5pt)  ;
at (40,0.7)[font=7pt0]$1$;
at (39,1.7)[font=7pt0]$2$;
at (40,2.7)[font=7pt0]$3$;

[blue, thick] (50,-1) – (50,0);
[blue, thick] (50,0) – (47,3);
[blue, thick] (50,0) – (53,3);
[blue, thick] (49,1) – (51,3);
[blue, thick] (48,2) – (49,3);
[black] (50,0) circle (5pt)  ;
[black] (49,1) circle (5pt)  ;
[black] (48,2) circle (5pt)  ;
at (50,0.7)[font=7pt0]$1$;
at (49,1.7)[font=7pt0]$2$;
at (48,2.7)[font=7pt0]$3$;

Generalized Stirling permutations of degree 3.

For each internal node $x$, we give the label $\kappa(x)$ to all regions between its children. Let $u$ be a generalized Stirling permutation of degree $n$, by reading the labels of the regions from left to right, we get a word $\mathbf{w}(u)=\mathbf{w}(u)_1\cdots \mathbf{w}(u)_n$. For example, let $u=$[scale=0.2,baseline=0pt]
[blue, thick] (0,-1) – (0,0);
[blue, thick] (0,0) – (7,7);
[blue, thick] (0,0) – (-7,7);
[blue, thick] (-5,5) – (-3,7);
[blue, thick] (-4,6) – (-5,7);
[blue, thick] (0,0) – (1,5);
[blue, thick] (1,5) – (-1,7);
[blue, thick] (1,5) – (1,7);
[blue, thick] (1,5) – (3,7);
[blue, thick] (6,6) – (5,7);
[black] (0,0) circle (5pt)  ;
[black] (1,5) circle (5pt)  ;
[black] (6,6) circle (5pt)  ;
[black] (-5,5) circle (5pt)  ;
[black] (-4,6) circle (5pt)  ;
at (-0.35,1.2)[font=7pt0]$1$;
at (0.55,1.2)[font=7pt0]$1$;
at (0.55,6.2)[font=7pt0]$3$;
at (1.45,6.2)[font=7pt0]$3$;
at (6,6.8)[font=7pt0]$2$;
at (-4,6.8)[font=7pt0]$5$;
at (-5,5.8)[font=7pt0]$4$;
. Then $\mathbf{w}(u)=4513312$. By abuse of notation, we use $u_i$ to mean $\mathbf{w}(u)_i$ for generalized Stirling permutation $u$.

Via $\mathbf{w}$, the set of generalized Stirling permutations in which all internal nodes have $3$ children is in bijection with the set of Stirling permutations defined in [11].

A word $w=w_1w_2\cdots w_n$ is a packed word if $w_i$ is a positive integer for $i=1,\dots, n$ and for each $1\leq a<w_i$, there exists a $j$ such that $w_j=a$. The set of packed words is denoted by $\PW$.

A packed word $w$ can be seen as a surjection $f_w\colon [n]\to[k]$  where $f_w(i)=w_i$ for some $k$. The sequence  $w^{-1}=(f_w^{-1}(1),f_w^{-1}(2), \ldots,f^{-1}(k))$ gives us an ordered set partition of $[n]$ with non-empty parts. We call such ordered set partition a set composition. We thus have a bijection $w\leftrightarrow w^{-1}$  between pack words with maximal entry $k$ and set compositions with $k$ parts. See for example Figure <ref>. This bijection extend the notion of $w^{-1}$ for permutations.

&&&&&&w\leftrightarrow w^{-1}&&&&&&\\
111&&&&&&&&&&&& 123\\ \\
112 &121 &  211 &  221 &  122 &  212   & & 12|3 &  13|2 &  23|1 &  3|12  & 1|23 &  2|13\\ \\
123&  132&  213&  312&  231&  321& & 1|2|3& 1|3|2&  2|1|3&  2|3|1&  3|1|2&  3|2|1\\
\end{array}$$

Packed words of length $3$ and their corresponding set compositions on the right. We use the shorthand notation $13|2$ instead of $(\{1,3\},\{2\})$

A word $w$ is said to be $212$-avoiding if whenever $w_i=w_k$ and $i<j<k$, we must have $w_j\ge w_i$. A word $w$ is said to be $213$-avoiding if whenever $i<j<k$, we must not have $w_k>w_i>w_j$.

A packed word $w$ is $212$-avoiding if and only if there is a generalized Stirling permutation $u$ such that $w=\mathbf{w}(u)$.

Clearly, for any generalized Stirling permutation $u$, $\mathbf{w}(u)$ must be $212$-avoiding. Conversely, if a packed word $w$ is $212$-avoiding, we can write $w$ as $W_11W_21\cdots 1W_k$ where $W_i$ are subwords of $w$ that does not contain $1$. Since $W_i$ are $212$-avoiding, by induction on length of the packed words, we have corresponding generalized Stirling permutation $\mathbf{t}(W_i)$ (with labels shifted up). Then $w$ corresponds to the generalized Stirling permutation [scale=0.2,baseline=0pt]
[blue, thick] (0,-1) – (0,0);
[blue, thick] (0,0) – (5,5);
[blue, thick] (0,0) – (-1,5);
[blue, thick] (0,0) – (0.7,2);
[blue, thick] (0,0) – (-5,5);
[black] (0,0) circle (5pt)  ;
at (-0.7,1.3)[font=7pt0]$1$;
at (-5,5.7)[font=7pt0]$\mathbf{t}(W_1)$;
at (5,5.7)[font=7pt0]$\mathbf{t}(W_k)$;
at (-1,5.7)[font=7pt0]$\mathbf{t}(W_2)$;
at (1,2.7)[font=7pt0]$\cdots$;

From the characterization in Lemma <ref> we deduce, by removing the largest entry in a generalized Stirling permutation, that the numbers $a_n$ of generalized Stirling permutation with degree $n$ satisfy the recurrence given by $a_0=1$ and

$$ a_n = \sum_{k=1}^n (n-k+1) a_{n-k}.$$

From this we conclude that  $a_n = (n+1)a_{n-1}$ for $n\ge 1$ and hence $a_n=\frac{(n+1)!}{2}$.

Let $u$ be a $212$-avoiding packed word, we denote by $\mathbf{t}(u)$ the unique generalized Stirling permutation such that $\mathbf{w}(\mathbf{t}(u))=u$.

By forgetting the labels, we have a forgetful map $\pi_\ptree:\GSP\to\PT$ (this map agrees with $\pi$ of Proposition <ref>). In the other direction, the map $\iota_\gsp:\PT\to\GSP$ sends a tree $t$ to the unique $213$-avoiding generalized Stirling permutation $\iota_\gsp(t)$ such that $\pi_\ptree\circ\iota_\gsp(t)=t$. Indeed, the generalized Stirling permutation $\iota_\gsp(t)$ can be constructed by induction on the number of internal nodes as follows. The root of $t$ has label $1$. Suppose the root of $t$ has $k$ children, $x_1,\dots,x_k$. Let $s_i$ be the subtree of $t$ rooted at $x_i$. Then, we label $s_k$ by $\{2,\dots,\ideg(s_k)+1\}$ such that $s_k$ is $213$-avoiding. Such labeling exists by induction hypothesis. Similarly, we label $s_{k-1}$ by $\{\ideg(s_k)+2,\dots,\ideg(s_{k-1})+\ideg(s_{k})+1\}$ such that $s_{k-1}$ is $213$-avoiding. We keep doing this process to all $s_i$, and we obtain $\iota_\gsp(t)$.
If $t$ is a binary tree, then the $213$-avoiding permutation $\iota_\gsp(t)$ was denoted $\iota(t)$ in Section <ref>.

Using a similar construction, there is a unique 312-avoiding generalized Stirling permutation $u$ such that $\pi_\ptree(u)=t$.

§.§ Hopf algebra structure

We define a Hopf structure on generalized Stirling permutations, and recall the Hopf structure on packed words [19] dual to the Hopf algebra on set composition [4]. We then analyse their connections.

As a graded vector space, the Hopf algebra of generalized Stirling permutations, $\STSym$ is  $\displaystyle\bigoplus_{n\geq 0}\Bbbk\GSP_n$ where $\GSP_n$ is the set of generalized Stirling permutations of degree $n$. By convention $\GSP_0$ is the span of the empty generalized Stirling permutation. The fundamental basis of $\STSym$ is $\{F_u:u\in\GSP\}$.

The multiplication is given by shifted shuffle i.e. if $u$ and $v$ are generalized Stirling permutations and $u$ has $k$ leaves, then

$$\displaystyle m(F_u\otimes F_v)=\sum_{\substack{\text{allowable} \\ v\mapsto\left(v_1,\dots,v_k\right)}}F_{u\overleftarrow{\shuffle} \left(v_1,\dots,v_k\right)}.$$

The comultiplication is given by deconcatenation followed by standardization i.e.

$$\Delta(F_u)=\sum_{\substack{\text{allowable} \\ u\mapsto(u_1,u_2)}}F_{\std(u_1)}\otimes F_{\std(u_2)}.$$

Let $u=$[scale=0.25,baseline=0pt]
[blue, thick] (0,-1) – (0,0);
[blue, thick] (0,0) – (-2,2);
[blue, thick] (0,0) – (2,2);
[blue, thick] (1,1) – (0,2);
[black] (0,0) circle (5pt)  ;
[black] (1,1) circle (5pt)  ;
at (0,0.7)[font=7pt0]$1$;
at (1,1.7)[font=7pt0]$2$;
, $v=$[scale=0.25,baseline=0pt]
[red, thick] (0,-1) – (0,0);
[red, thick] (0,0) – (-2,2);
[red, thick] (0,0) – (2,2);
[red, thick] (0,0) – (0,2);
[black] (0,0) circle (5pt)  ;
at (-0.4,1)[font=7pt0]$1$;
at (0.4,1)[font=7pt0]$1$;

$m(F_u\otimes F_v)=
\draw[blue, thick] (0,-1) -- (0,0);
\draw[blue, thick] (0,0) -- (-4,4);
\draw[blue, thick] (0,0) -- (2,2);
\draw[blue, thick] (1,1) -- (-2,4);
\draw[red, thick] (2,2) -- (0,4);
\draw[red, thick] (2,2) -- (2,4);
\draw[red, thick] (2,2) -- (4,4);
\filldraw[black] (0,0) circle (5pt)  {};
\filldraw[black] (1,1) circle (5pt)  {};
\filldraw[black] (2,2) circle (5pt)  {};
\node at (0,0.7)[font=\fontsize{7pt}{0}]{$1$};
\node at (1,1.7)[font=\fontsize{7pt}{0}]{$2$};
\node at (1.6,3)[font=\fontsize{7pt}{0}]{$3$};
\node at (2.4,3)[font=\fontsize{7pt}{0}]{$3$};
\end{tikzpicture}}+
\draw[blue, thick] (0,-1) -- (0,0);
\draw[blue, thick] (0,0) -- (-4,4);
\draw[blue, thick] (0,0) -- (4,4);
\draw[blue, thick] (1,1) -- (0,2);
\draw[red, thick] (0,2) -- (-2,4);
\draw[red, thick] (0,2) -- (0,4);
\draw[red, thick] (0,2) -- (2,4);
\filldraw[black] (0,0) circle (5pt)  {};
\filldraw[black] (1,1) circle (5pt)  {};
\filldraw[black] (0,2) circle (5pt)  {};
\node at (0,0.7)[font=\fontsize{7pt}{0}]{$1$};
\node at (1,1.7)[font=\fontsize{7pt}{0}]{$2$};
\node at (-0.4,3)[font=\fontsize{7pt}{0}]{$3$};
\node at (0.4,3)[font=\fontsize{7pt}{0}]{$3$};
\end{tikzpicture}}+
\draw[blue, thick] (0,-1) -- (0,0);
\draw[blue, thick] (0,0) -- (-4,4);
\draw[blue, thick] (0,0) -- (4,4);
\draw[blue, thick] (3,3) -- (2,4);
\draw[red, thick] (-2,2) -- (0,4);
\draw[red, thick] (-2,2) -- (-2,4);
\draw[red, thick] (-2,2) -- (-4,4);
\filldraw[black] (0,0) circle (5pt)  {};
\filldraw[black] (-2,2) circle (5pt)  {};
\filldraw[black] (3,3) circle (5pt)  {};
\node at (0,0.7)[font=\fontsize{7pt}{0}]{$1$};
\node at (3,3.7)[font=\fontsize{7pt}{0}]{$2$};
\node at (-1.6,3)[font=\fontsize{7pt}{0}]{$3$};
\node at (-2.4,3)[font=\fontsize{7pt}{0}]{$3$};
\end{tikzpicture}}$.

Let $u=$[scale=0.25,baseline=0pt]
[blue, thick] (0,-1) – (0,0);
[blue, thick] (0,0) – (7,7);
[blue, thick] (0,0) – (-7,7);
[blue, thick] (-5,5) – (-3,7);
[blue, thick] (-4,6) – (-5,7);
[blue, thick] (0,0) – (1,5);
[blue, thick] (1,5) – (-1,7);
[blue, thick] (1,5) – (1,7);
[blue, thick] (1,5) – (3,7);
[blue, thick] (6,6) – (5,7);
[black] (0,0) circle (5pt)  ;
[black] (1,5) circle (5pt)  ;
[black] (6,6) circle (5pt)  ;
[black] (-5,5) circle (5pt)  ;
[black] (-4,6) circle (5pt)  ;
at (-0.4,1)[font=7pt0]$1$;
at (0.5,1)[font=7pt0]$1$;
at (0.6,6)[font=7pt0]$3$;
at (1.4,6)[font=7pt0]$3$;
at (6,6.7)[font=7pt0]$2$;
at (-4,6.7)[font=7pt0]$5$;
at (-5,5.7)[font=7pt0]$4$;

\draw[blue, thick] (0,-1) -- (0,0);
\draw[blue, thick] (0,0) -- (1,1);
\draw[blue, thick] (0,0) -- (-1,1);
\filldraw[black] (0,0) circle (5pt)  {};
\node at (0,0.7)[font=\fontsize{7pt}{0}]{$1$};
\end{tikzpicture}}\otimes
\draw[blue, thick] (0,-1) -- (0,0);
\draw[blue, thick] (0,0) -- (6,6);
\draw[blue, thick] (0,0) -- (-6,6);
\draw[blue, thick] (-5,5) -- (-4,6);
\draw[blue, thick] (0,0) -- (0,4);
\draw[blue, thick] (0,4) -- (0,6);
\draw[blue, thick] (0,4) -- (-2,6);
\draw[blue, thick] (0,4) -- (2,6);
\draw[blue, thick] (5,5) -- (4,6);
\filldraw[black] (0,0) circle (5pt)  {};
\filldraw[black] (0,4) circle (5pt)  {};
\filldraw[black] (5,5) circle (5pt)  {};
\filldraw[black] (-5,5) circle (5pt)  {};
\node at (-0.4,1)[font=\fontsize{7pt}{0}]{$1$};
\node at (0.4,1)[font=\fontsize{7pt}{0}]{$1$};
\node at (-0.4,5)[font=\fontsize{7pt}{0}]{$3$};
\node at (0.4,5)[font=\fontsize{7pt}{0}]{$3$};
\node at (5,5.7)[font=\fontsize{7pt}{0}]{$2$};
\node at (-5,5.7)[font=\fontsize{7pt}{0}]{$4$};
\end{tikzpicture}}+
\draw[blue, thick] (0,-1) -- (0,0);
\draw[blue, thick] (0,0) -- (-2,2);
\draw[blue, thick] (0,0) -- (2,2);
\draw[blue, thick] (1,1) -- (0,2);
\filldraw[black] (0,0) circle (5pt)  {};
\filldraw[black] (1,1) circle (5pt)  {};
\node at (0,0.7)[font=\fontsize{7pt}{0}]{$1$};
\node at (1,1.7)[font=\fontsize{7pt}{0}]{$2$};
\end{tikzpicture}}\otimes
\draw[blue, thick] (0,-1) -- (0,0);
\draw[blue, thick] (0,0) -- (5,5);
\draw[blue, thick] (0,0) -- (-5,5);
\draw[blue, thick] (0,0) -- (-1,3);
\draw[blue, thick] (-1,3) -- (-3,5);
\draw[blue, thick] (-1,3) -- (-1,5);
\draw[blue, thick] (-1,3) -- (1,5);
\draw[blue, thick] (4,4) -- (3,5);
\filldraw[black] (0,0) circle (5pt)  {};
\filldraw[black] (-1,3) circle (5pt)  {};
\filldraw[black] (4,4) circle (5pt)  {};
\node at (-0.6,1)[font=\fontsize{7pt}{0}]{$1$};
\node at (0.4,1)[font=\fontsize{7pt}{0}]{$1$};
\node at (-1.4,4)[font=\fontsize{7pt}{0}]{$3$};
\node at (-0.6,4)[font=\fontsize{7pt}{0}]{$3$};
\node at (4,4.7)[font=\fontsize{7pt}{0}]{$2$};
\end{tikzpicture}}+
\draw[blue, thick] (0,-1) -- (0,0);
\draw[blue, thick] (0,0) -- (6,6);
\draw[blue, thick] (0,0) -- (-6,6);
\draw[blue, thick] (-4,4) -- (-2,6);
\draw[blue, thick] (-3,5) -- (-4,6);
\draw[blue, thick] (0,0) -- (2,4);
\draw[blue, thick] (2,4) -- (0,6);
\draw[blue, thick] (2,4) -- (2,6);
\draw[blue, thick] (2,4) -- (4,6);
\filldraw[black] (0,0) circle (5pt)  {};
\filldraw[black] (2,4) circle (5pt)  {};
\filldraw[black] (-4,4) circle (5pt)  {};
\filldraw[black] (-3,5) circle (5pt)  {};
\node at (-0.2,1)[font=\fontsize{7pt}{0}]{$1$};
\node at (1.5,2)[font=\fontsize{7pt}{0}]{$1$};
\node at (1.6,5)[font=\fontsize{7pt}{0}]{$2$};
\node at (2.4,5)[font=\fontsize{7pt}{0}]{$2$};
\node at (-3,5.7)[font=\fontsize{7pt}{0}]{$4$};
\node at (-4,4.7)[font=\fontsize{7pt}{0}]{$3$};
\end{tikzpicture}}\otimes
\draw[blue, thick] (0,-1) -- (0,0);
\draw[blue, thick] (0,0) -- (1,1);
\draw[blue, thick] (0,0) -- (-1,1);
\filldraw[black] (0,0) circle (5pt)  {};
\node at (0,0.7)[font=\fontsize{7pt}{0}]{$1$};
\end{tikzpicture}}$.

Under these operations, $\STSym$ forms a Hopf algebra. By forgetting the labels, we have a Hopf projection $\Pi_\ptree:\STSym\to\TSym$, $F_u\mapsto F_{\pi_\ptree(u)}$.

$\STSym$ is a Hopf algebra.

The associativity, coassociativity and compatibility follow from the ones for $\TSym$. One only need to check that the labels are shifted and standardized correctly. The arguments in the proof of Proposition <ref> can be transferred almost identically, by using allowable splitting, shifted shuffle and standardization in proper places.

We then have the following commutative square of Hopf algebras.

at (0,0) $\YSym$;
at (3,0) $\TSym$;
at (3,2) $\STSym$;
at (0,2) $\SSym$;
[black,thick, right hook->] (0.8,0) – (2.2,0);
[black,thick, right hook->] (0.8,2) – (2.2,2);
[black,thick, ->>] (0,1.5) – (0,0.5);
[black,thick, ->>] (3,1.5) – (3,0.5);

§.§ Connections to packed words

We first recall that the dual Hopf algebra of packed words is $\NCQSym=\displaystyle\WQSym^*=\bigoplus_{n\geq 0}\Bbbk\PW_n^{-1}$ where $\PW_n$ is the set of packed words of length $n$. We use the $Q$ basis $\{Q_{u^{-1}}:u\in\PW\}$ as introduced in [4].

For a word $w_1 \cdots w_n$, let $\pack(w_1 \cdots w_n)$ be the unique packed word $u_1\cdots u_n$ such that $u_i< u_j$ if and only if $w_i< w_j$. The product and coproduct formula for the $Q$ basis are as follows.

$$Q_{u^{-1}}\cdot Q_{v^{-1}}=\sum_{\substack{
w=w_1\cdots w_{n+m},\\
\pack(w_1\cdots w_n)=u,\\
\pack(w_{n+1}\cdots w_{n+m})=v,\\
\{w_1,\dots,w_n\}\cap\{w_{n+1},\dots,w_{n+m}\}=\emptyset}}Q_{w^{-1}},$$

where $n=\deg(u)$ and $m=\deg(v)$, and

$$\Delta(Q_{w^{-1}})=\sum_{i=0}^{n+m}\sum_{\substack{u_1<\cdots<u_n\\ v_1<\cdots<v_m\\ w_{u_j}\leq i,w_{v_j}>i}}Q_{\pack(w_{u_1}\cdots w_{u_n})^{-1}}\otimes Q_{\pack(w_{v_1}\cdots w_{v_m})^{-1}},$$

where $\deg(w)=n+m$.

The linear map $\STSym^*\to\NCQSym$ defined by $F_u^*\mapsto Q_{u^{-1}}$ is a Hopf embedding.

In terms of packed words, the product and coproduct of the $F$ basis are given by

$$F_u\cdot F_v=\sum_{w\in (u\overline{\shuffle} v)\cap \GSP}F_w,$$

where $u\overline{\shuffle} v$ denotes the shifted shuffle i.e. the set of shuffles of the two words $u_1\cdots u_{\deg(u)}$ and $(v_1+\deg(u))\cdots(v_{\deg(v)}+\deg(u))$.

$$\Delta(F_w)=\sum_{\substack{0\leq i\leq n \\ \{w_1,\dots,w_i\}\cap\{w_{i+1},\dots,w_n\}=\emptyset}} F_{\pack(w_1\cdots w_i)}\otimes F_{\pack(w_{i+1}\cdots w_n)},$$

where $n=\deg(w)$.

The proof is completed by rewriting the formula above in the dual basis, and comparing to the formula of $Q$ basis.

For a generalized Stirling permutation $u$, the underlying set partition of $u^{-1}$ is a noncrossing partition i.e. whenever $a<b<c<d$ and $a,c\in B_i$ for some $i$, we must not have $b,d\in B_j$ for some $j$.
Hence the embedding  $\STSym^*\hookrightarrow \NCQSym $ can be further refined with the Hopf subalgebra of non-crossing set compositions inside the Hopf algebra of set compositions.
Using the basis $Q$ of [4] we have that the subspace $\NCQSym^{nc}$ spanned by $Q_B$ where the parts of $B$ are non-crossing is a Hopf subalgebra. Hence

$$\STSym^*\hookrightarrow \NCQSym^{nc}\hookrightarrow \NCQSym .$$

Taking the dual in the embedding of Proposition <ref> gives us a projection $\WQSym\to\STSym$, given by

\[Q_{u^{-1}}^* \mapsto
\begin{cases}F_u & \text{if } u \in \GSP,\\
0 & \text{otherwise}.
\end{cases}\]

In light of Corollary <ref>, it is reasonable to ask for finding an explicit Hopf embedding $\STSym\to\WQSym$.

§.§ Bidendriform structure

In this section we show that $\STSym$ is free, cofree and self-dual. We achieve these by giving $\STSym$ a bidendriform structure.

A Hopf algebra $(\cH,\cdot,\Delta)$ has a bidendriform structure if it has the operations $\ll, \gg,\Delta_\ll,\Delta_\gg$ such that

* $a\cdot b=a\ll b+a\gg b$

* $(a\ll b)\ll c = a\ll(b\cdot c)$

* $a\gg (b\gg c)=(a\cdot b)\gg c$

* $a\gg(b\ll c) = (a\gg b)\ll c$

* $\Delta_+=\Delta_\ll+\Delta_\gg$

* $(\Delta_\ll \otimes id)\circ\Delta_\ll=(id\otimes\Delta_+)\circ\Delta_\ll$

* $(id \otimes \Delta_\gg)\circ\Delta_\gg=(\Delta_+\otimes id)\circ\Delta_\gg$

* $(\Delta_\gg \otimes id)\circ\Delta_\ll=(id\otimes\Delta_\ll)\circ\Delta_\gg$

* $\Delta_\gg(a\gg b)=a'b_\gg'\otimes a''\gg b_\gg''+a'\otimes a''\gg b+b_\gg'\otimes a\gg b_\gg''+ab_\gg'\otimes b_\gg''+a\otimes b$

* $\Delta_\gg(a\ll b)=a'b_\gg'\otimes a''\ll b_\gg''+a'\otimes a''\ll b+b_\gg'\otimes a\ll b_\gg''$

* $\Delta_\ll(a\gg b)=a'b_\ll'\otimes a''\gg b_\ll''+b_\ll'\otimes a\gg b_\ll''+ab_\ll'\otimes b_\ll''$

* $\Delta_\ll(a\ll b)=a'b_\ll'\otimes a''\ll b_\ll''+b_\ll'\otimes a\ll b_\ll''+a'b\otimes a''+b\otimes a$

where the pairs $(x',x''),(x_\ll',x_\ll''),(x_\gg',x_\gg '')$ are all possible elements in $\Delta(x),\Delta_\ll(x),\Delta_\gg(x)$, as in Sweedler's notation.

We now present a bidendriform structure on $\STSym$, but leave the details for the interested reader.

* $\displaystyle F_u\ll F_v:=\sum_{w\in u\shuffle v,w_n\leq |u|}F_w$

* $\displaystyle F_u\gg F_v:=\sum_{w\in u\shuffle v,w_n> |u|}F_w$

* $\displaystyle\Delta_\ll(F_w):=\sum_{w\mapsto(u,v),\max(w)\in v}F_u\otimes F_v$

* $\displaystyle\Delta_\gg(F_w):=\sum_{w\mapsto(u,v),\max(w)\in u}F_u\otimes F_v.$

The operations $\ll, \gg,\Delta_\ll,\Delta_\gg$ defined above puts a bidendriform structure on $\STSym$.

The proof of this Proposition is technical and lengthy, yet straightforward.  It would take too much space to include here and we prefer to leave it for the interested reader.  The following corollary follows from the results of Foissy in [8, 9].

The Hopf algebra $\STSym$ is free, cofree and self-dual.

Find an explicit Hopf isomorphism $\STSym\to\STSym^*$.

§.§ Weak order on packed words

Our partial order on generalized Stirling permutations follows from the (left) weak order of packed words, as defined in [25].

For a packed word $w$ we denote by $w^{-1}(i)$ the $i$th component of $w^{-1}$. For example, if $w=1322122$, then $w^{-1}=15|3467|2$ and $w^{-1}(2)=\{3,4,6,7\}$.
We define the inversed-inversion set of a packed word $w$ to be

$$\iInv(w)=\{(a,b):a<b\text{ and }\min w^{-1}(a) > \max w^{-1}(b)\}. $$

In the example above $\iInv(1322122)=\{(2,3)\}$.

For a packed word $w$ define $T_a(w)$ as the  packed word obtained from $w$ by interchanging all $a$'s and $a+1$'s, i.e. if $u=T_a(w)$  then

a & \text{if }w_i=a+1,\\
a+1 & \text{if }w_i=a,\\
w_i & \text{otherwise.}
\end{cases}$$

The planar weak order $\leq_{Pw}$ on packed words is as follows: $u$ is covered by $w$ if and only if there exists $a$ such that $|\iInv(w)| = |\iInv(u)|+1$ and  $u=T_a(w)$.

By abuse of notations, we also use $\leq_{Pw}$ as the partial order on generalized Stirling permutations i.e. $u\leq_{Pw} v$ if and only if $\mathbf{w}(u)\leq_{Pw}\mathbf{w}(v)$.

The following proposition shows that, if $T_a(w)$ covers $w$, then all occurrences of $a$ in $w$ are to the left of all occurences of $a+1$.

For a packed word $w$, $T_a(w)$ covers $w$ if and only if $\max w^{-1}(a)<\min w^{-1}(a+1)$.
In particular, if there exists $i<j<k$ with $w_i=w_k=a$, $w_j=a+1$, then $w$ and $T_a(w)$ are not comparable.

For any $b$ and $c$ satisfying $b<a$ and $a+1<c$  we have that,

* $(b,a)\in\iInv(w)$ if and only if $(b,a+1)\in\iInv(T_a(w))$,

* $(b,a+1)\in\iInv(w)$ if and only if $(b,a)\in\iInv(T_a(w))$,

* $(a,c)\in\iInv(w)$ if and only if $(a+1,c)\in\iInv(T_a(w))$,

* $(a+1,c)\in\iInv(w)$ if and only if $(a,c)\in\iInv(T_a(w))$,

* $(b,c)\in\iInv(w)$ if and only if $(b,c)\in\iInv(T_a(w))$.

Hence, $|\iInv(T_a(w))|=|\iInv(w)|+1$ if and only if $(a,a+1)\notin\iInv(w)$ and $(a,a+1)\in\iInv (T_a(w))$. By definition of $\iInv$, the second condition is equivalent to $\min  T_a(w)^{-1}(a)>\max T_a(w)^{-1}(a+1)$, i.e. $\min w^{-1}(a+1)>\max w^{-1}(a)$, which also ensures $(a,a+1)\notin\iInv(w)$.

If there exists $i<j<k$ with $w_i=w_k=a$, $w_j=a+1$, then $(a,a+1)\notin\iInv(w)$ and $(a,a+1)\not\in\iInv T_a(w)$, hence $|\iInv(T_a(w))|=|\iInv(w)|$ so that $T_a(w)$ and $w$ are incomparable.

The goal of the remainder of this section is Theorem <ref>, describing the connected components under the weak order and  relating this order on packed words to the weak order of permutations.

For each packed word $w$, let $w^{-1} = (B_1,B_2,\ldots,B_k)$ with $B_i=w^{-1}(i)$. We define $\setpar(w)=\{B_1,B_2,\dots,B_k\}$ to be the underlying set partition of $w^{-1}$, and
$\delrpt(w)=\sigma$ to be the initial permutation, obtained by taking only the first appearance of each letter in $w$. In other words, $\delrpt(w)=\sigma$ is the unique permutation $\sigma\colon[k]\to[k]$ such that $\min B_{\sigma(1)}<\min B_{\sigma(2)}<\cdots<\min B_{\sigma(k)}$. (Our notation follows [12], note that [26] calls this the left-standardization.)
Given a set composition $B=(B_1,\dots,B_k)$ we denote by $w=B^{-1}$ the packed word such that $B=w^{-1}$.

Given a set partition  ${\mathcal B}=\{B_1,B_2,\dots,B_k\}$ such that $\min B_1<\cdots<\min B_k$ and a permutation $\sigma\colon[k]\to[k]$,
we define $\pw({\mathcal B},\sigma) = (B_{\sigma^{-1}(1)},B_{\sigma^{-1}(2)},\dots,B_{\sigma^{-1}(k)})^{-1}$. For $w=\pw({\mathcal B},\sigma)$ we
have $\setpar(w)={\mathcal B}$ and $\delrpt(w)=\sigma$.

at (0,0) [scale=0.48]
[ForestGreen, ultra thick] (0,1.5) – (0,3.5);
[ForestGreen, ultra thick] (0,6.5) – (0,8.5);

() at (0,0) $1213$;
() at (0,5) $1312$;
() at (0,10) $2321$;
at (5,0) [scale=0.4]
[ForestGreen, ultra thick] (5,1.7) – (5,3);
[ForestGreen, ultra thick] (5,6.7) – (5,8);

() at (5,0) [scale=0.2,baseline=0pt]
[blue, thick] (0,-1) – (0,0);
[blue, thick] (0,0) – (4,4);
[blue, thick] (3,3) – (2,4);
[blue, thick] (0,0) – (-1,3);
[blue, thick] (-1,3) – (0,4);
[blue, thick] (-1,3) – (-2,4);
[blue, thick] (0,0) – (-4,4);
[black] (0,0) circle (5pt)  ;
[black] (-1,3) circle (5pt)  ;
[black] (3,3) circle (5pt)  ;
at (-0.6,1)[font=7pt0]$1$;
at (0.4,1)[font=7pt0]$1$;
at (3,3.7)[font=7pt0]$3$;
at (-1,3.7)[font=7pt0]$2$;
() at (5,5) [scale=0.2,baseline=0pt]
[blue, thick] (0,-1) – (0,0);
[blue, thick] (0,0) – (4,4);
[blue, thick] (3,3) – (2,4);
[blue, thick] (0,0) – (-1,3);
[blue, thick] (-1,3) – (0,4);
[blue, thick] (-1,3) – (-2,4);
[blue, thick] (0,0) – (-4,4);
[black] (0,0) circle (5pt)  ;
[black] (-1,3) circle (5pt)  ;
[black] (3,3) circle (5pt)  ;
at (-0.6,1)[font=7pt0]$1$;
at (0.4,1)[font=7pt0]$1$;
at (3,3.7)[font=7pt0]$2$;
at (-1,3.7)[font=7pt0]$3$;
() at (5,10) [scale=0.2,baseline=0pt]
[blue, thick] (0,-1) – (0,0);
[blue, thick] (0,0) – (4,4);
[blue, thick] (-1,1) – (2,4);
[blue, thick] (-1,1) – (-1,3);
[blue, thick] (-1,3) – (0,4);
[blue, thick] (-1,3) – (-2,4);
[blue, thick] (0,0) – (-4,4);
[black] (0,0) circle (5pt)  ;
[black] (-1,3) circle (5pt)  ;
[black] (-1,1) circle (5pt)  ;
at (-1.5,2)[font=7pt0]$2$;
at (-0.5,2)[font=7pt0]$2$;
at (0,0.7)[font=7pt0]$1$;
at (-1,3.7)[font=7pt0]$3$;
at (10,0) [scale=0.48]
[ForestGreen, ultra thick] (0,1.5) – (0,3.5);
[ForestGreen, ultra thick] (0,6.5) – (0,8.5);

() at (0,0) $123$;
() at (0,5) $132$;
() at (0,10) $231$;

Connected components of packed words and generalized Stirling permutations with underlying set partition $\{\{1,3\},\{2\},\{4\}\}$, and their image under $\delrpt$.

Since $\setpar(T_a(w))=\setpar(w)$, we have that $u$ and $w$ are incomparable if $\setpar(u)\neq\setpar(w)$. Hence, in each connected component, all elements have the same underlying set partition. But the converse is not true e.g. 121 and $212$ are not comparable, by Proposition <ref>. The correct statement as it will be seen in Theorem <ref> is: two packed words are in the same connected component if and only if they have the same underlying set partition and the same nested inversions.

Let $w$ be a packed word, $\delrpt(w)=\sigma$ and $\setpar(w)=\{B_1,\dots,B_k\}$ such that $\min B_1<\cdots<\min B_k$. Let $b_i=\min B_i$ for each $i$. We define the inversion set of $w$ to be $\Inv(w)=\Inv(\sigma)=\{(i,j):i<j\text{ and }w_{b_i}>w_{b_j}\}$. In particular, when $w$ is a permutation, its inversion set is consistent with the inversion set as a permutation.

For $\setpar(w)=\{B_1,\dots,B_k\}$, two blocks $B_i,B_j$ are nested if $\min B_i<\min B_j<\max B_i$.

If $u$ and $w$ are packed words, then $u\leq_{Pw}w$ implies $\Inv(u)\subseteq\Inv(w)$.

Let $\setpar(u)=\{B_1,\dots,B_k\}$ such that $\min B_1<\cdots<\min B_k$. If $u<_{Pw} T_a(u)$ for some $a$, then $a\in B_i$, $a+1\in B_j$ for some $i<j$ and $\max B_i<\min B_j$. Then, $\Inv(T_a(u))=\Inv(u)\cup\{(i,j)\}$.
The transitive closure of the relation implies the statement.

If $u$ and $w$ are packed words such that

* $\setpar(u)=\setpar(w)=\{B_1,\dots,B_k\}$,

* If $B_i,B_j$ are nested, then either $(i,j)\in\Inv(u)\cap\Inv(w)$ or $(i,j)\notin\Inv(u)\cup\Inv(w)$.

Then, $\Inv(u)\subseteq\Inv(w)$ implies $u\leq_{Pw}w$.

Assume $\min B_1 <\cdots< \min B_k$.

Let $\tau=\delrpt(w)$. If we have $\Inv(\sigma)=\Inv(u)\subseteq \Inv(w)=\Inv(\tau)$, then $\sigma$ is less than $\tau$ in the weak order. We proceed by induction on $m=\ell(\tau)-\ell(\sigma)$. If $m=0$ the result is obvious.
If $m>0$, then we can find $a$ such that $\sigma \lessdot (a,a+1)\sigma\leq \tau$ in the weak order and hence
$$\Inv(\sigma)\subset  \Inv((a,a+1)\sigma)=\Inv(\sigma)\cup\{(\sigma^{-1}(a),\sigma^{-1}(a+1))\}\subseteq \tau.$$

Let $(i,j)=(\sigma^{-1}(a),\sigma^{-1}(a+1))$. The blocks $B_i$ and $B_j$ are not nested according to the assumption (2).
Since $i<j$, we have $\min B_i <\min B_j$, and we must have $\min B_i \leq \max B_i <\min B_j$, otherewise they would be nested.
Hence, using Proposition <ref>, we have that $u\lessdot_{Pw} T_a(u)$, and we can conlude from the induction hypothesis.

If $u$ and $w$ are packed words such that condition (2) in Lemma <ref> does not hold, then $u$ and $w$ are incomparable.

By assumption, there is some $B_i,B_j$ nested, such that $(i,j)\in\Inv(u)$ and $(i,j)\notin\Inv(w)$ (by exchanging the roles of $u$ and $w$ if necessary). By Lemma <ref>, $u \not \leq _{Pw} w$ because $\Inv(u)\nsubseteq\Inv(w)$. Since $B_i,B_j$ are nested, we can find $p<q<r$ such that $p,r\in B_i$ and $q\in B_j$. Then we have that $u_p=u_r>u_q$ and $w_p=w_r<w_q$. We claim that for all $w\leq_{Pw}v$, we must have $v_p=v_r<v_q$. It suffices to check for $v=T_a(w)$.

Suppose not, i.e. $v_p=v_r>v_q$. Since $v=T_a(w)$, the only possibility is that $w_p=w_r=v_q=a$ and $w_q=v_p=v_r=a+1$. But then by Proposition <ref>, $v$ and $w$ are incomparable. Therefore, $w$ is not less than $u$ either.

Fix a set partition $\{B_1,\dots,B_k\}$ with $\min B_1<\cdots<\min B_k$. Let $X=\{(i,j):i<j,B_i,B_j\text{ are nested}\}$. Then each $A\subseteq X$ induces a connected component (possibly empty) of the planar weak order consisting of packed words $w$ such that $A\subseteq\Inv(w)$, $(X\setminus A)\cap\Inv(w)=\emptyset$ and $\setpar(w)=\{B_1,\dots,B_k\}$.

Hence each connected component in the planar weak order is a bounded lattice, and is isomorphic to an interval of the weak order. In particular,

* $u\vee w=\pw(\setpar(u),\delrpt(u)\vee\delrpt(w))$,

* $u\land w=\pw(\setpar(u),\delrpt(u)\land\delrpt(w))$.

We only need to check that $u\vee w$ and $u\land w$ are in the connected component of $u$ and $w$. The rest follows from Propositions <ref> and <ref> and the observation that $\Inv(\delrpt(w))=\Inv(w)$. A connected component $W$ in the planar weak order corrsponds to the interval $\{\delrpt(w):w\in W\}$ in the weak order.

We show the case of $u\vee w$, and omit the case of $u\land w$. Suppose not, that means we can find $B_i,B_j\in\setpar(u)=\{B_1,\dots,B_k\}$ nested such that

* $(i,j)\in \Inv(u)\cap\Inv(w)$ but $(i,j)\notin\Inv(u\vee w)$, or

* $(i,j)\notin \Inv(u)\cup\Inv(w)$ but $(i,j)\in\Inv(u\vee w)$.

Case (1) cannot be true because $\Inv(u) = \Inv(\delrpt u) \subseteq \Inv( (\delrpt u) \vee (\delrpt w) )=\Inv(u\vee w)$. In case (2), recall the well-known fact that $\Inv(u\vee w)$ equals the transitive closure of $\Inv(u)\cup\Inv(w)$. Hence, we can find $i<h<j$ such that $(i,h)$ and $(h,j)$ are each in either $\Inv(u)$ or $\Inv(w)$ (or both). Without loss of generality, we can assume $(i,h)\in\Inv(u)$. If $(h,j)\in \Inv(u)$ also, then by transitivity $(i,j)\in \Inv(u)$, contradicting (2). So we must have $(h,j)\in \Inv(w)$, and by the same transitivity argument we must have $(i,h)\notin\Inv(w)$. Now since $B_i,B_j$ are nested, $\min B_i<\min B_{h}<\min B_j<\max B_i$. That means $B_i$ and $B_{h}$ are also nested. But then by Proposition <ref>, $u$ and $w$ are not comparable, which is a contradiction.

§.§ Planar weak order on generalized Stirling permutations

Recall from the end of Section <ref> the maps $\pi_\ptree:\GSP\to\PT$ that forgets the labels, and $\iota_\gsp:\PT\to\GSP$ sending a planar tree $t$ to the unique $213$-avoiding generalized Stirling permutation with underlying planar tree $t$.

The generalized Stirling permutation $\iota_\gsp(t)$ is the maximal preimage of $t$ under $\pi_\ptree$.

If $\pi_\ptree(u)=t$ and $u$ is not $213$-avoiding, we claim that we can find $a$ and $i<m<j$ such that $u_i=a$, $u_j=a+1$ and $u_m<a$. We can find $i<m<j$ such that $u_j>u_i>u_m$. We search iteratively on $u_j-u_i$. If $u_j-u_i>1$, then we can find $u_n=u_i+1$ for some $n$. If $n>m$, then the triple $(i,m,n)$ is what we want. If $n<m$, then the triple $(n,m,j)$ satisfies $u_j>u_n>u_m$ and $u_j-u_n<u_j-u_i$. The claim will be fulfilled by keep doing this process.

In this case, the node with label $a+1$ is not on top of the node with label $a$ i.e. $\pi_\ptree(T_a(u))=t$. Since $T_a(u)\geq_{Pw} u$, the statement follows.

Let $u,v$ be generalized Stirling permutations and $s,t$ be trees. Then

* if $u\leq_{Pw}v$, then $\pi_\ptree(u)\leq_{PT}\pi_\ptree(v)$;

* if $s\leq_{PT}t$, then $\iota_\gsp(s)\leq_{Pw}\iota_\gsp(t)$.

We begin with (1). Let $w$ be a $212$-avoiding packed word, and $u$ covered by $w$ in the planar weak order. It suffices to show that $\pi_\ptree(\mathbf{t}(u))\leq_{PT}\pi_\ptree(\mathbf{t}(w))$. Let $u=T_a(w)$, $x=\min\{i:w_i=a\}$, $y=\max\{i:w_i=a+1\}$. We must have $y<x$ because otherwise, $w$ and $u$ are not comparable by Proposition <ref>. Then we have two cases.

Case 1. There exists $y<m<x$ such that $w_m<a$. In this case, the node with label $a+1$ is not on top of the node with label $a$. Then $u$ and $w$ have the same underlying tree.

Case 2. For any $y<m<x$, $w_m>a+1$. In this case, the node with label $a+1$ is on the left most leaf of the node with label $a$. Then, $\pi_\ptree(u)$ is covered by $\pi_\ptree(w)$ in the planar Tamari order, as shown in Definition <ref>.

To prove (2), let $s,t$ be trees and $s$ covered by $t$ in the planar Tamari order. Suppose $t$ is obtained from $s$ by a left rotation at node $x$, and let $y$ be the right most child of $x$ in $s$ i.e. $y$ is the left most child of $x$ in $t$. Let $\kappa_{\iota_{\gsp}(s)}(x)=a$, by construction, we must have $\kappa_{\iota_{\gsp}(s)}(y)=a+1$ because $\iota_{\gsp}(s)$ is $213$-avoiding. Let $u$ be the labeled tree such that $\pi_\ptree(u)=t$ and $\kappa_u(x)=a$, $\kappa_u(y)=a+1$ and $\kappa_u(i)=\kappa_{\iota_{\gsp}(s)}(i)$ for all internal nodes $i$. Then, $u$ is well defined and $u=T_a(\iota_{\gsp}(s))$.

By Lemma <ref>, we know that $\iota_{\gsp}(t)$ is maximal. Therefore, $\iota_{\gsp}(s)\leq_{Pw}u\leq_{Pw}\iota_{\gsp}(t)$.

From Lemma <ref> and Proposition <ref> we obtain the following corollary.

The maps $\pi_{ptree}$ and $\iota_{gsp}$ form a   Galois connection between the weak order on Stirling permutations and the Tamari order on planar trees.

Assume $w \leq_{Pw} \iota_{gsp}(t)$. Then $\pi_{ptree}(w)\leq_{PT} \pi_{ptree}(\iota_{gsp} t)= t$, because $\pi_{ptree}$ is order-preserving.

Conversely, assume $\pi_{ptree}(w) \leq_{PT} t$. Then $w\leq_{Pw} \iota_{gsp}(\pi_{ptree} w)\leq_{Pw} \iota_{gsp}(t)$ - the first inequality is by Lemma <ref>, and the second because $\iota_{gsp}$ is order-preserving.

Let $F_u$ and $F_v$ be two basis elements in $\STSym$, and let $F_u^*$, $F_v^*$ be their dual basis elements in the graded dual $\STSym^*$. Then,

$$m(F_u^*\otimes F_v^*)=\sum_{u\backslash v\leq_{Pw} w\leq_{Pw} u/v}F_w^*.$$

Recall from Proposition <ref> that

$$F_u^*\cdot F_v^*=\sum_{\substack{
w=w_1\cdots w_{n+m},\\
\pack(w_1\cdots w_n)=u,\\
\pack(w_{n+1}\cdots w_{n+m})=v,\\
\{w_1,\dots,w_n\}\cap\{w_{n+1},\dots,w_{n+m}\}=\emptyset}}F_w^*,$$

where $n=\deg(u)$ and $m=\deg(v)$.

For each $w$ in the summand above, clearly $\setpar(w)=\setpar(u\backslash v)=\setpar(u/v)$. Hence $w$, $u\backslash v$ and $u/v$ must be in the same connected component by Theorem <ref>.

Moreover, since $\pack(w_1\cdots w_n)=u$, for $i<j\leq n$, $(i,j)\in\Inv(w)$ if and only if $(i,j)\in\Inv(u)\cap\Inv(u\backslash v)\cap\Inv(u/v)$. Similarly, for $n<i<j$, $(i,j)\in\Inv(w)$ if and only if $(i-n,j-n)\in\Inv(v)$ if and only if $(i,j)\in\Inv(u\backslash v)\cap\Inv(u/v)$.

For $i\leq n<j$, $(i,j)\notin\Inv(u\backslash v)$ and $(i,j)\in\Inv(u/v)$ whenever $i=\min B_a$, $j=\min B_b$ for some $B_a, B_b\in\setpar(w)$. Therefore, $\Inv(u\backslash v)\subseteq\Inv(w)\subseteq\Inv(u/v)$. By Lemma <ref>, we must have $u\backslash v\leq_{Pw} w\leq_{Pw} u/v$.

Let $F_s$ and $F_t$ be two basis elements in $\TSym$, and let $F_s^*$, $F_t^*$ be their dual basis elements in the graded dual $\TSym^*$. Then,

$$m(F_s^*\otimes F_t^*)=\sum_{s\backslash t\leq_{PT} r\leq_{PT} s/t}F_r^*.$$

Fix a tree $r$ and let $w=\iota_\gsp(r)$. Since $\Pi_\ptree:\STSym\to\TSym$ is a Hopf morphism, by Proposition <ref>, we have

$$\Delta(F_r)=(\Pi_\ptree\otimes\Pi_\ptree)\circ\Delta(F_w)=\sum_{u\backslash v\leq_{Pw} w\leq_{Pw} u/v}F_{\pi_\ptree(u)}\otimes F_{\pi_\ptree(v)}.$$

Fix a pair $u,v$ such that $u\backslash v\leq_{Pw} w\leq_{Pw} u/v$, let $\pi_\ptree(u)=s$ and $\pi_{\ptree}(v)=t$. By Propositions <ref> and <ref>, we have $s\backslash t\leq_{PT} r\leq_{PT}s/t$.

Conversely, fix a pair $s,t$ such that $s\backslash t\leq_{PT} r\leq_{Pw}s/t$, let $\iota_\gsp(s)=u$ and $\iota_{\gsp}(t)=v$. By Propositions <ref> and <ref>, we have $u\backslash v\leq_{Pw} w\leq_{Pw}u/v$.

Finally, from the definition of comultiplication, we have $\langle F_u^*\otimes F_v^*,\Delta(F_w)\rangle=0$ or $1$ and $\langle F_s^*\otimes F_t^*,\Delta(F_r)\rangle=0$ or $1$. Therefore,

$$\Delta(F_r)=\sum_{u\backslash v\leq_{Pw} w\leq_{Pw} u/v}F_{\pi_\ptree(u)}\otimes F_{\pi_\ptree(v)}=\sum_{s\backslash t\leq_{PT} r\leq_{PT} s/t}F_s\otimes F_t.$$

§.§ Monomial basis

The planar weak order allows the definition of a monomial basis for $\STSym$, exactly analogous to our previous algebras.

The monomial basis of $\STSym$ are defined as the elements satisfying $\displaystyle F_u=\sum_{v\geq_{Pw} u}M_v$. The monomial basis is unique by triangularity and it forms a basis via Möbius inversion.

Note that, because of Theorem <ref>, the image
of monomial basis elements under the Hopf projection $\Pi_{\ptree}$
are either monomials or zero:

\[
\Pi(M_{u})=\begin{cases}
M_{\pi_{\ptree}(u)} & \text{if }u\text{ is $213$-avoiding};\\
0 & \text{otherwise}.
\end{cases}
\]

The rest of this section gives the usual formulas for the coproduct, product and antipode of the monomial basis.

Let $u$ be a generalized Stirling permutation of degree $n$. Its global descent set is $\GD(u)=\{i\in[n-1]:u=v/w \text{ for some }v, w\text{ and }\deg(v)=i\}$. Equivalently, $\GD(u)=\{i\in[n-1]:u_a>u_b\text{ for all }a\leq i< b\}$.

The following two lemmas are useful for checking the axioms of Section <ref>:

The map $\iota_\gsp$ preserves global descents i.e. $\GD(t)=\GD(\iota_\gsp(t))$ for a tree $t$.

Let $u=\iota_\gsp(t)$. $\GD(\iota_\gsp(t))\subseteq\GD(t)$ follows directly from the definitions of global descents. If $i\in\GD(t)$, since labels in generalized Stirling permutations are increasing along branches, for any $a\leq i$, we have $u_a>u_{i+1}$. Then, $213$-avoiding property implies that for any $a\leq i<b$, we must have $u_a>u_b$ i.e. $i\in\GD(u)$.

Given generalized Stirling permutations $u,v$ and a
fixed allowable splitting $v\mapsto(v_{1},\dots,v_{k})$, then $\delrpt(u\overleftarrow{\shuffle}(v_{1},\dots,v_{k}))=\delrpt(u)\overleftarrow{\shuffle}(\sigma_{1},\dots,\sigma_{l})$
where $\sigma=\delrpt(v)$ and $\sigma\mapsto(\sigma_{1},\dots,\sigma_{l})$
is some splitting where $\deg\sigma_{1},\dots,\deg\sigma_{l}$ depend
only on $\deg v_{1},\dots,\deg v_{k}$ and on $\setpar(u)$, $\setpar(v)$.

If $u=u_{1}\cdots u_{k-1}$, then, as words, $u\overleftarrow{\shuffle}(v_{1},\dots,v_{k})$
is $v_{1}^{\uparrow}u_{1}v_{2}^{\uparrow}u_{2}\cdots v_{k-1}^{\uparrow}u_{k-1}v_{k}^{\uparrow}$,
where $v_{i}^{\uparrow}$ denotes that each number in $v_{i}$ is
shifted up by $\max u$. (Note that $u_{i}$ is a letter but $v_{i}$
is a word.) Since $v\mapsto(v_{1},\dots,v_{k})$ is allowable, the
letters $v_{i}$ and $v_j$ are distinct when $i\ne j$. Moreover, because of the shifting,
the letters in $v_{1}^{\uparrow},\dots,v_{k}^{\uparrow}$ are also
different from $u_{1},\dots,u_{k-1}$. Let $\setpar(u)=\{B_1,\ldots,B_\ell\}$ and let
$i_j=\min B_j$ assuming that $1=i_1<i_2<\cdots<i_\ell$.
In particular $\delrpt(u)=u_1u_{i_{2}}\cdots u_{i_{\ell}}$ for some $\ell\le k-1$.
We proceed in the same way with $v=v_1v_2\cdots v_k$ to get $\delrpt(v)=\sigma=\tau_1\cdots\tau_k$ where $\tau_j$ (a word, possibly empty)
is the first occurrence of the distinct letters of $v$ that happen in the word $v_j$. We then have

\begin{align*}
\delrpt(u\overleftarrow{\shuffle}(v_{1},\dots,v_{k})) & =( \tau_{1}^{\uparrow})u_{1}(\tau_{2}^{\uparrow}\cdots \tau_{i_{2}}^{\uparrow})u_{i_{2}}(\tau_{i_{2}+1}^{\uparrow}\cdots \tau_{i_{3}}^{\uparrow})u_{i_{3}}\cdots
u_{i_{\ell}}(\tau_{i_{\ell}+1}^{\uparrow}\cdots \tau_{k}^{\uparrow})\\
& =\delrpt(u)\overleftarrow{\shuffle}(\tau_{1},\,\tau_{2}\cdots \tau_{i_{2}},\ \ldots\ ,\ \tau_{i_{\ell}+1}\cdots \tau_{k})
\end{align*}

If we let $\sigma_{1}= \tau_{1}$ and $\sigma_{j}=\tau_{i_{j-1}+1}\cdots \tau_{i_{j}}$, then
$\sigma\mapsto(\sigma_{1},\dots,\sigma_{l})$ is a valid splitting and
$\delrpt(u\overleftarrow{\shuffle}(v_{1},\dots,v_{k}))=\delrpt(u)\overleftarrow{\shuffle}(\sigma_{1},\dots,\sigma_{l})$ as desired.
The $\deg \sigma_j$ is the number of letters in $\tau_{i_{j-1}+1}\cdots \tau_{i_{j}}$. This depends on the $i_j$'s (built from $\setpar(u)$),
the corresponding indexes in $v$ (built from $\setpar(v)$) and where they fall in the decomposition $v=v_1v_2\cdots v_k$
(which depend on on the size of $v_i$, namely $\deg(v_i)$).

The coproduct
in the monomial basis of $\STSym$ is:

\[
\Delta_{+}(M_{u})=\sum_{i\in\GD(u)}M_{{}^{i}u}\otimes M_{u^{i}}.
\]

We check the axioms in Theorem <ref>. To see
($\Delta$1), note that $i\not\in\allow(u)$ if and only there is
$j,k$ with $j\leq i<k$ and $u_{j}=u_{k}$. Then, in $u'=T_{a}(u)$
covering $u$, we have $u'_{j}=u'_{k}$, so $i\not\in\allow(u')$

To check ($\Delta$2): consider $u'=T_{a}(u)$ covering $u$, and $i\in\allow(u)$,
so either $\max u^{-1}(a) \le i$ or $\min u^{-1}(a) >i$,
and similarly for $a+1$. Thus there are four scenarios:

* $\max u^{-1}(a)\le i$ and $\max u^{-1}(a+1)\leq i$: then
${}^{i}(T_{a}u)=T_{b}({}^{i}u)$ for some $b$ (being the image of
$a$ under $\std({}^{i}u)$) and $(T_{a}u)^{i}=u^{i}$;

* $\max u^{-1}(a)>i$ and $\max u^{-1}(a+1)>i$: then ${}^{i}(T_{a}u)={}^{i}u$
and $(T_{a}u)^{i}=T_{b}(u^{i})$ for some $b$ (being the image of
$a$ under $\std(u^{i})$) ;

* $\max u^{-1}(a)\leq i$ and $\max u^{-1}(a+1)>i$: then ${}^{i}(T_{a}u)={}^{i}u$
and $(T_{a}u)^{i}=u^{i}$;

* $\max u^{-1}(a)>i$ and $\max u^{-1}(a+1)\leq i$:
this case is not possible by Proposition <ref>.

So, in all cases, ${}^{i}(T_{a}u)\geq_{Pw}{}^{i}u$ and $(T_{a}u)^{i}\geq_{Pw}u^{i}$.

To check ($\Delta$3): $u/v=\max\{w|{}^{i}w=u,w^{i}=v\}$
follows from Proposition <ref>.
And $/$ is order-preserving
because $(T_{a}u)/v=T_{a}(u/v)$, and $u/(T_{a}v)=T_{a+\max u}(u/v)$.

The product
of monomial basis elements in $\STSym$ is given by $M_{u}\cdot M_{v}=\sum_{w}\alpha_{u,v}^{w} M_{w}$,
where $\alpha_{u,v}^{w} =|A_{u,v}^{w}|$ is defined as in (<ref>).

We check the axioms in Theorem <ref>. Axiom ($m$0)
is true because of Theorem <ref>. To see ($m$1): the set $Sh(\setpar(u),\setpar(v))$ correspond to the set
of sequences $0\le i_1\le i_2\le\cdots\le i_ {\deg u-1}\le \deg v$ of allowable split positions of
$v$. These allowable split positions depend only on $\setpar(v)=\{B_1,\ldots,B_k\}$,
as $i_j$ is not allowed if and only if $\min B_p < i_j < \max B_p$ for some $p$.

To see ($m$2): suppose $\deg u=k-1$ and $v\mapsto(v_{1},\dots,v_{k})$
is an allowable splitting. If $T_{a}(u)$ covers $u$, then $(T_{a}u)\overleftarrow{\shuffle}(v_{1},\dots,v_{k})=T_{a}(u\overleftarrow{\shuffle}(v_{1},\dots,v_{k}))$.
If $T_{a}(v)$ covers $v$, then $T_{a}(v)\mapsto(T_{a}(v_{1}),\dots,T_{a}(v_{k}))$
and $u\overleftarrow{\shuffle}(T_{a}(v_{1}),\dots,T_{a}(v_{k}))=T_{a+\max u}(u\overleftarrow{\shuffle}(v_{1},\dots,v_{k}))$.

To check ($m$3): consider comparable $u,u'$ with $k$ leaves, and
comparable $v,v'$. Fix $\zeta\in Sh(\setpar(u),\setpar(v))$, i.e.
fix $k-1$ allowable splitting positions (possibly repeated) in $v$,
and compute $v\mapsto(v_{1},\dots,v_{k})$, $v'\mapsto(v'_{1},\dots,v'_{k})$
and $v\vee v'\mapsto((v\vee v')_{1},\dots,(v\vee v')_{k})$ all at
this same multiset of lightening positions. Then $\zeta(u,v)=u\overleftarrow{\shuffle}(v_{1},\dots,v_{k})$,
and similarly for $u',v'$ and for $u\vee u',v\vee v'$. Because $\setpar(u)=\setpar(u')$
and $\setpar(v)=\setpar(v')$, and because the split positions are
fixed, so $\setpar(u\overleftarrow{\shuffle}(v_{1},\dots,v_{k}))=\setpar(u'\overleftarrow{\shuffle}(v'_{1},\dots,v'_{k}))=\setpar((u\vee u')\overleftarrow{\shuffle}((v\vee v')_{1},\dots,(v\vee v')_{k}))$.
So, by Theorem <ref>, it suffices to show

$$\delrpt((u\vee u')\overleftarrow{\shuffle}((v\vee v')_{1},\dots,(v\vee v')_{k}))\leq\delrpt(u\overleftarrow{\shuffle}(v_{1},\dots,v_{k}))\vee\delrpt(u'\overleftarrow{\shuffle}(v'_{1},\dots,v'_{k})).$$

This follows from axiom ($m$3) in $\SSym$ and Lemma <ref>.

antipode of monomial basis elements in $\STSym$ is given by $\mathcal{S}(M_{u})=(-1)^{\GD(u)+1}\sum_{v}\beta_{u}^{v}M_{v}$
where $\beta_{f}^{g}$ is defined as in (<ref>).

We check the axioms in Theorem <ref>. Axioms ($\Delta$1)-($\Delta$3)
and ($m$0)-($m$3) were already checked in the previous two proofs.

Axiom ($\mathcal{S}$0) follows from Remark <ref>. To see
($\mathcal{S}$1): suppose $T_{a}(u)\geq_{Pw}u$ and $i\in\GD(u)$.
So $j\leq i<k\implies u_{j}>u_{k}$ . By Proposition <ref>,
$T_{a}(u)\geq_{Pw}u$ means that we cannot have $u_{j}=a+1$ and $u_{k}=a$.
Thus, $\{u_{j},u_{k}\}\neq\{a,a+1\}$ and so $T_{a}(u_{j})>T_{a}(u_{k})$.

To see ($\mathcal{S}$2): given $u'_{i}\geq_{Pw}u_{i}$ for each $i$,
first note that $\setpar(u'_{i})=\setpar(u_{i})$, so

\begin{equation}
\setpar(u'_{1}/\cdots/u'_{k})=\setpar(u_{1}/\cdots/u_{k})=\setpar(u'_{1}\backslash\cdots\backslash u'_{k}).\label{eq:setparS3}
\end{equation}

Also, $\delrpt(u'_{i})\geq\delrpt(u_{i})$, so by axiom ($\mathcal{S}$2)
in $\SSym$,

\[
(\delrpt u'_{1})/\cdots/(\delrpt u'_{k})\leq_{w}[(\delrpt u_{1})/\cdots/(\delrpt u_{k})]\vee[(\delrpt u'_{1})\backslash\cdots\backslash(\delrpt u'_{k})].
\]

Clearly $\delrpt(v/w)=\delrpt(v)/\delrpt(w)$ and $\delrpt(v\backslash w)=\delrpt(v)\backslash\delrpt(w)$,

\begin{align*}
\delrpt(u'_{1}/\cdots/u'_{k}) & \leq_{w}\delrpt(u_{1}/\cdots/u_{k})\vee\delrpt(u'_{1}\backslash\cdots\backslash u'_{k})\\
& \leq_{w}\delrpt((u_{1}/\cdots/u_{k})\vee(u'_{1}\backslash\cdots\backslash u'_{k}))
\end{align*}

using Theorem <ref> and (<ref>). Combining with
$\setpar(u'_{1}/\cdots/u'_{k})=\setpar((u_{1}/\cdots/u_{k})\vee(u'_{1}\backslash\cdots\backslash u'_{k}))$
gives the result.

Axiom ($\mathcal{S}$3) is proved similarly.

§ HOPF ALGEBRA OF PARKING FUNCTIONS

§.§ Parking functions

Recall that a parking function of degree $n$ is an integer sequence $(p_1,\dots,p_n)$ where $p_{j_i}\le i$ for all $i$, whenever $p_{j_1}\le p_{j_2}\le \cdots \le p_{j_n}$ is its nonincreasing rearrangement. An equivalent definition of a parking function is that of a Dyck path of length $2n$ with a bijection between north steps and $[n]$ such that the labels of consecutive $N$ steps are increasing from bottom to top.

In this section, we have an alternative view of parking functions as labeled binary trees satisfying certain conditions.

A parking function of degree $n$ is a pair $(\sigma,t)\in\Perm_n\times\PBT_n$ such that $\Des(t)\subseteq\Des(\sigma)$. We write a parking function $f=(\sigma,t)$ as a binary tree $t$ with labels on the internal nodes such that the $i$-th internal node in-order traversal is labeled $\sigma(i)$. Recall that in-order traversal of a binary tree is the one where recursively we visit first the left subtree in-order then the root and then the right subtree in-order. The set of parking functions is denoted by $\PF$.

at (0,5) $123$;
at (10,5) $132$;
at (20,5) $213$;
at (30,5) $312$;
at (40,5) $231$;
at (50,5) $321$;

[blue, thick] (0,-1) – (0,0);
[blue, thick] (0,0) – (3,3);
[blue, thick] (0,0) – (-3,3);
[blue, thick] (1,1) – (-1,3);
[blue, thick] (2,2) – (1,3);
[black] (0,0) circle (5pt)  ;
[black] (1,1) circle (5pt)  ;
[black] (2,2) circle (5pt)  ;
at (0,0.7)[font=7pt0]$1$;
at (1,1.7)[font=7pt0]$2$;
at (2,2.7)[font=7pt0]$3$;

[blue, thick] (10,-1) – (10,0);
[blue, thick] (10,0) – (13,3);
[blue, thick] (10,0) – (7,3);
[blue, thick] (11,1) – (9,3);
[blue, thick] (12,2) – (11,3);
[black] (10,0) circle (5pt)  ;
[black] (11,1) circle (5pt)  ;
[black] (12,2) circle (5pt)  ;
at (10,0.7)[font=7pt0]$1$;
at (11,1.7)[font=7pt0]$3$;
at (12,2.7)[font=7pt0]$2$;

[blue, thick] (20,-1) – (20,0);
[blue, thick] (20,0) – (23,3);
[blue, thick] (20,0) – (17,3);
[blue, thick] (21,1) – (19,3);
[blue, thick] (22,2) – (21,3);
[black] (20,0) circle (5pt)  ;
[black] (21,1) circle (5pt)  ;
[black] (22,2) circle (5pt)  ;
at (20,0.7)[font=7pt0]$2$;
at (21,1.7)[font=7pt0]$1$;
at (22,2.7)[font=7pt0]$3$;

[blue, thick] (30,-1) – (30,0);
[blue, thick] (30,0) – (33,3);
[blue, thick] (30,0) – (27,3);
[blue, thick] (31,1) – (29,3);
[blue, thick] (32,2) – (31,3);
[black] (30,0) circle (5pt)  ;
[black] (31,1) circle (5pt)  ;
[black] (32,2) circle (5pt)  ;
at (30,0.7)[font=7pt0]$3$;
at (31,1.7)[font=7pt0]$1$;
at (32,2.7)[font=7pt0]$2$;

[blue, thick] (40,-1) – (40,0);
[blue, thick] (40,0) – (43,3);
[blue, thick] (40,0) – (37,3);
[blue, thick] (41,1) – (39,3);
[blue, thick] (42,2) – (41,3);
[black] (40,0) circle (5pt)  ;
[black] (41,1) circle (5pt)  ;
[black] (42,2) circle (5pt)  ;
at (40,0.7)[font=7pt0]$2$;
at (41,1.7)[font=7pt0]$3$;
at (42,2.7)[font=7pt0]$1$;

[blue, thick] (50,-1) – (50,0);
[blue, thick] (50,0) – (53,3);
[blue, thick] (50,0) – (47,3);
[blue, thick] (51,1) – (49,3);
[blue, thick] (52,2) – (51,3);
[black] (50,0) circle (5pt)  ;
[black] (51,1) circle (5pt)  ;
[black] (52,2) circle (5pt)  ;
at (50,0.7)[font=7pt0]$3$;
at (51,1.7)[font=7pt0]$2$;
at (52,2.7)[font=7pt0]$1$;

[blue, thick] (10,-6) – (10,-5);
[blue, thick] (10,-5) – (13,-2);
[blue, thick] (10,-5) – (7,-2);
[blue, thick] (11,-4) – (9,-2);
[blue, thick] (10,-3) – (11,-2);
[black] (10,-5) circle (5pt)  ;
[black] (11,-4) circle (5pt)  ;
[black] (10,-3) circle (5pt)  ;
at (10,-4.3)[font=7pt0]$1$;
at (11,-3.3)[font=7pt0]$2$;
at (10,-2.3)[font=7pt0]$3$;

[blue, thick] (40,-6) – (40,-5);
[blue, thick] (40,-5) – (43,-2);
[blue, thick] (40,-5) – (37,-2);
[blue, thick] (41,-4) – (39,-2);
[blue, thick] (40,-3) – (41,-2);
[black] (40,-5) circle (5pt)  ;
[black] (41,-4) circle (5pt)  ;
[black] (40,-3) circle (5pt)  ;
at (40,-4.3)[font=7pt0]$2$;
at (41,-3.3)[font=7pt0]$1$;
at (40,-2.3)[font=7pt0]$3$;

[blue, thick] (50,-6) – (50,-5);
[blue, thick] (50,-5) – (53,-2);
[blue, thick] (50,-5) – (47,-2);
[blue, thick] (51,-4) – (49,-2);
[blue, thick] (50,-3) – (51,-2);
[black] (50,-5) circle (5pt)  ;
[black] (51,-4) circle (5pt)  ;
[black] (50,-3) circle (5pt)  ;
at (50,-4.3)[font=7pt0]$3$;
at (51,-3.3)[font=7pt0]$1$;
at (50,-2.3)[font=7pt0]$2$;

[blue, thick] (20,-11) – (20,-10);
[blue, thick] (20,-10) – (23,-7);
[blue, thick] (20,-10) – (17,-7);
[blue, thick] (22,-8) – (21,-7);
[blue, thick] (18,-8) – (19,-7);
[black] (20,-10) circle (5pt)  ;
[black] (22,-8) circle (5pt)  ;
[black] (18,-8) circle (5pt)  ;
at (20,-9.3)[font=7pt0]$1$;
at (22,-7.3)[font=7pt0]$3$;
at (18,-7.3)[font=7pt0]$2$;

[blue, thick] (30,-11) – (30,-10);
[blue, thick] (30,-10) – (33,-7);
[blue, thick] (30,-10) – (27,-7);
[blue, thick] (32,-8) – (31,-7);
[blue, thick] (28,-8) – (29,-7);
[black] (30,-10) circle (5pt)  ;
[black] (32,-8) circle (5pt)  ;
[black] (28,-8) circle (5pt)  ;
at (30,-9.3)[font=7pt0]$1$;
at (32,-7.3)[font=7pt0]$2$;
at (28,-7.3)[font=7pt0]$3$;

[blue, thick] (50,-11) – (50,-10);
[blue, thick] (50,-10) – (53,-7);
[blue, thick] (50,-10) – (47,-7);
[blue, thick] (52,-8) – (51,-7);
[blue, thick] (48,-8) – (49,-7);
[black] (50,-10) circle (5pt)  ;
[black] (52,-8) circle (5pt)  ;
[black] (48,-8) circle (5pt)  ;
at (50,-9.3)[font=7pt0]$2$;
at (52,-7.3)[font=7pt0]$1$;
at (48,-7.3)[font=7pt0]$3$;

[blue, thick] (10,-16) – (10,-15);
[blue, thick] (10,-15) – (13,-12);
[blue, thick] (10,-15) – (7,-12);
[blue, thick] (9,-14) – (11,-12);
[blue, thick] (10,-13) – (9,-12);
[black] (10,-15) circle (5pt)  ;
[black] (9,-14) circle (5pt)  ;
[black] (10,-13) circle (5pt)  ;
at (10,-14.3)[font=7pt0]$2$;
at (9,-13.3)[font=7pt0]$1$;
at (10,-12.3)[font=7pt0]$3$;

[blue, thick] (40,-16) – (40,-15);
[blue, thick] (40,-15) – (43,-12);
[blue, thick] (40,-15) – (37,-12);
[blue, thick] (39,-14) – (41,-12);
[blue, thick] (40,-13) – (39,-12);
[black] (40,-15) circle (5pt)  ;
[black] (39,-14) circle (5pt)  ;
[black] (40,-13) circle (5pt)  ;
at (40,-14.3)[font=7pt0]$1$;
at (39,-13.3)[font=7pt0]$2$;
at (40,-12.3)[font=7pt0]$3$;

[blue, thick] (50,-16) – (50,-15);
[blue, thick] (50,-15) – (53,-12);
[blue, thick] (50,-15) – (47,-12);
[blue, thick] (49,-14) – (51,-12);
[blue, thick] (50,-13) – (49,-12);
[black] (50,-15) circle (5pt)  ;
[black] (49,-14) circle (5pt)  ;
[black] (50,-13) circle (5pt)  ;
at (50,-14.3)[font=7pt0]$1$;
at (49,-13.3)[font=7pt0]$3$;
at (50,-12.3)[font=7pt0]$2$;

[blue, thick] (50,-21) – (50,-20);
[blue, thick] (50,-20) – (47,-17);
[blue, thick] (50,-20) – (53,-17);
[blue, thick] (49,-19) – (51,-17);
[blue, thick] (48,-18) – (49,-17);
[black] (50,-20) circle (5pt)  ;
[black] (49,-19) circle (5pt)  ;
[black] (48,-18) circle (5pt)  ;
at (50,-19.3)[font=7pt0]$1$;
at (49,-18.3)[font=7pt0]$2$;
at (48,-17.3)[font=7pt0]$3$;

Parking functions of degree $3$. Elements from the same column have the same underlying permutation.

We present a bijection from our definition of parking functions to the classical one.

Given a parking function $(\sigma,t)$ of degree $n$, the Dyck path is constructed from $t$ as follows. We order the $2n+1$ nodes (including internal nodes and leaves) of $t$ in preorder, that is, we visit first the root, then the left subtree in preorder and then the right subtree in preorder.
Let $x_1x_2\cdots x_{2n}$ be the nodes of $t$ ignoring the right most leaf. From the order of the nodes, we construct Dyck path from $(n,n)$, the $n$ internal nodes correspond to west steps and the first $n$ leaves correspond to south steps. Then, we label of the $i$-th $N$ step, reading from top to bottom, by $\sigma(i)$.

[gray, thin] (0,0) – (0,3);
[gray, thin] (1,0) – (1,3);
[gray, thin] (2,0) – (2,3);
[gray, thin] (3,0) – (3,3);
[gray, thin] (0,0) – (3,0);
[gray, thin] (0,1) – (3,1);
[gray, thin] (0,2) – (3,2);
[gray, thin] (0,3) – (3,3);
[red, ultra thick] (0,0) – (0,1);
[red, ultra thick] (0,1) – (1,1);
[red, ultra thick] (1,1) – (1,2);
[red, ultra thick] (1,2) – (2,2);
[red, ultra thick] (2,2) – (2,3);
[red, ultra thick] (2,3) – (3,3);
at (0.5,0.4)[font=7pt0]$3$;
at (1.5,1.4)[font=7pt0]$2$;
at (2.5,2.4)[font=7pt0]$1$;

[gray, thin] (10,0) – (10,3);
[gray, thin] (11,0) – (11,3);
[gray, thin] (12,0) – (12,3);
[gray, thin] (13,0) – (13,3);
[gray, thin] (10,0) – (13,0);
[gray, thin] (10,1) – (13,1);
[gray, thin] (10,2) – (13,2);
[gray, thin] (10,3) – (13,3);
[red, ultra thick] (10,0) – (10,1);
[red, ultra thick] (10,1) – (11,1);
[red, ultra thick] (11,1) – (11,2);
[red, ultra thick] (11,2) – (12,2);
[red, ultra thick] (12,2) – (12,3);
[red, ultra thick] (12,3) – (13,3);
at (10.5,0.4)[font=7pt0]$2$;
at (11.5,1.4)[font=7pt0]$3$;
at (12.5,2.4)[font=7pt0]$1$;

[gray, thin] (20,0) – (20,3);
[gray, thin] (21,0) – (21,3);
[gray, thin] (22,0) – (22,3);
[gray, thin] (23,0) – (23,3);
[gray, thin] (20,0) – (23,0);
[gray, thin] (20,1) – (23,1);
[gray, thin] (20,2) – (23,2);
[gray, thin] (20,3) – (23,3);
[red, ultra thick] (20,0) – (20,1);
[red, ultra thick] (20,1) – (21,1);
[red, ultra thick] (21,1) – (21,2);
[red, ultra thick] (21,2) – (22,2);
[red, ultra thick] (22,2) – (22,3);
[red, ultra thick] (22,3) – (23,3);
at (20.5,0.4)[font=7pt0]$3$;
at (21.5,1.4)[font=7pt0]$1$;
at (22.5,2.4)[font=7pt0]$2$;

[gray, thin] (30,0) – (30,3);
[gray, thin] (31,0) – (31,3);
[gray, thin] (32,0) – (32,3);
[gray, thin] (33,0) – (33,3);
[gray, thin] (30,0) – (33,0);
[gray, thin] (30,1) – (33,1);
[gray, thin] (30,2) – (33,2);
[gray, thin] (30,3) – (33,3);
[red, ultra thick] (30,0) – (30,1);
[red, ultra thick] (30,1) – (31,1);
[red, ultra thick] (31,1) – (31,2);
[red, ultra thick] (31,2) – (32,2);
[red, ultra thick] (32,2) – (32,3);
[red, ultra thick] (32,3) – (33,3);
at (30.5,0.4)[font=7pt0]$2$;
at (31.5,1.4)[font=7pt0]$1$;
at (32.5,2.4)[font=7pt0]$3$;

[gray, thin] (40,0) – (40,3);
[gray, thin] (41,0) – (41,3);
[gray, thin] (42,0) – (42,3);
[gray, thin] (43,0) – (43,3);
[gray, thin] (40,0) – (43,0);
[gray, thin] (40,1) – (43,1);
[gray, thin] (40,2) – (43,2);
[gray, thin] (40,3) – (43,3);
[red, ultra thick] (40,0) – (40,1);
[red, ultra thick] (40,1) – (41,1);
[red, ultra thick] (41,1) – (41,2);
[red, ultra thick] (41,2) – (42,2);
[red, ultra thick] (42,2) – (42,3);
[red, ultra thick] (42,3) – (43,3);
at (40.5,0.4)[font=7pt0]$1$;
at (41.5,1.4)[font=7pt0]$3$;
at (42.5,2.4)[font=7pt0]$2$;

[gray, thin] (50,0) – (50,3);
[gray, thin] (51,0) – (51,3);
[gray, thin] (52,0) – (52,3);
[gray, thin] (53,0) – (53,3);
[gray, thin] (50,0) – (53,0);
[gray, thin] (50,1) – (53,1);
[gray, thin] (50,2) – (53,2);
[gray, thin] (50,3) – (53,3);
[red, ultra thick] (50,0) – (50,1);
[red, ultra thick] (50,1) – (51,1);
[red, ultra thick] (51,1) – (51,2);
[red, ultra thick] (51,2) – (52,2);
[red, ultra thick] (52,2) – (52,3);
[red, ultra thick] (52,3) – (53,3);
at (50.5,0.4)[font=7pt0]$1$;
at (51.5,1.4)[font=7pt0]$2$;
at (52.5,2.4)[font=7pt0]$3$;

[gray, thin] (10,-5) – (10,-2);
[gray, thin] (11,-5) – (11,-2);
[gray, thin] (12,-5) – (12,-2);
[gray, thin] (13,-5) – (13,-2);
[gray, thin] (10,-5) – (13,-5);
[gray, thin] (10,-4) – (13,-4);
[gray, thin] (10,-3) – (13,-3);
[gray, thin] (10,-2) – (13,-2);
[red, ultra thick] (10,-5) – (10,-3);
[red, ultra thick] (10,-3) – (12,-3);
[red, ultra thick] (12,-3) – (12,-2);
[red, ultra thick] (12,-2) – (13,-2);
at (10.5,-4.6)[font=7pt0]$2$;
at (10.5,-3.6)[font=7pt0]$3$;
at (12.5,-2.6)[font=7pt0]$1$;

[gray, thin] (40,-5) – (40,-2);
[gray, thin] (41,-5) – (41,-2);
[gray, thin] (42,-5) – (42,-2);
[gray, thin] (43,-5) – (43,-2);
[gray, thin] (40,-5) – (43,-5);
[gray, thin] (40,-4) – (43,-4);
[gray, thin] (40,-3) – (43,-3);
[gray, thin] (40,-2) – (43,-2);
[red, ultra thick] (40,-5) – (40,-3);
[red, ultra thick] (40,-3) – (42,-3);
[red, ultra thick] (42,-3) – (42,-2);
[red, ultra thick] (42,-2) – (43,-2);
at (40.5,-4.6)[font=7pt0]$1$;
at (40.5,-3.6)[font=7pt0]$3$;
at (42.5,-2.6)[font=7pt0]$2$;

[gray, thin] (50,-5) – (50,-2);
[gray, thin] (51,-5) – (51,-2);
[gray, thin] (52,-5) – (52,-2);
[gray, thin] (53,-5) – (53,-2);
[gray, thin] (50,-5) – (53,-5);
[gray, thin] (50,-4) – (53,-4);
[gray, thin] (50,-3) – (53,-3);
[gray, thin] (50,-2) – (53,-2);
[red, ultra thick] (50,-5) – (50,-3);
[red, ultra thick] (50,-3) – (52,-3);
[red, ultra thick] (52,-3) – (52,-2);
[red, ultra thick] (52,-2) – (53,-2);
at (50.5,-4.6)[font=7pt0]$1$;
at (50.5,-3.6)[font=7pt0]$2$;
at (52.5,-2.6)[font=7pt0]$3$;

[gray, thin] (20,-10) – (20,-7);
[gray, thin] (21,-10) – (21,-7);
[gray, thin] (22,-10) – (22,-7);
[gray, thin] (23,-10) – (23,-7);
[gray, thin] (20,-10) – (23,-10);
[gray, thin] (20,-9) – (23,-9);
[gray, thin] (20,-8) – (23,-8);
[gray, thin] (20,-7) – (23,-7);
[red, ultra thick] (20,-10) – (20,-9);
[red, ultra thick] (20,-9) – (21,-9);
[red, ultra thick] (21,-9) – (21,-7);
[red, ultra thick] (21,-7) – (23,-7);
at (20.5,-9.6)[font=7pt0]$3$;
at (21.5,-8.6)[font=7pt0]$1$;
at (21.5,-7.6)[font=7pt0]$2$;

[gray, thin] (30,-10) – (30,-7);
[gray, thin] (31,-10) – (31,-7);
[gray, thin] (32,-10) – (32,-7);
[gray, thin] (33,-10) – (33,-7);
[gray, thin] (30,-10) – (33,-10);
[gray, thin] (30,-9) – (33,-9);
[gray, thin] (30,-8) – (33,-8);
[gray, thin] (30,-7) – (33,-7);
[red, ultra thick] (30,-10) – (30,-9);
[red, ultra thick] (30,-9) – (31,-9);
[red, ultra thick] (31,-9) – (31,-7);
[red, ultra thick] (31,-7) – (33,-7);
at (30.5,-9.6)[font=7pt0]$2$;
at (31.5,-8.6)[font=7pt0]$1$;
at (31.5,-7.6)[font=7pt0]$3$;

[gray, thin] (50,-10) – (50,-7);
[gray, thin] (51,-10) – (51,-7);
[gray, thin] (52,-10) – (52,-7);
[gray, thin] (53,-10) – (53,-7);
[gray, thin] (50,-10) – (53,-10);
[gray, thin] (50,-9) – (53,-9);
[gray, thin] (50,-8) – (53,-8);
[gray, thin] (50,-7) – (53,-7);
[red, ultra thick] (50,-10) – (50,-9);
[red, ultra thick] (50,-9) – (51,-9);
[red, ultra thick] (51,-9) – (51,-7);
[red, ultra thick] (51,-7) – (53,-7);
at (50.5,-9.6)[font=7pt0]$1$;
at (51.5,-8.6)[font=7pt0]$2$;
at (51.5,-7.6)[font=7pt0]$3$;

[gray, thin] (10,-15) – (10,-12);
[gray, thin] (11,-15) – (11,-12);
[gray, thin] (12,-15) – (12,-12);
[gray, thin] (13,-15) – (13,-12);
[gray, thin] (10,-15) – (13,-15);
[gray, thin] (10,-14) – (13,-14);
[gray, thin] (10,-13) – (13,-13);
[gray, thin] (10,-12) – (13,-12);
[red, ultra thick] (10,-15) – (10,-13);
[red, ultra thick] (10,-13) – (11,-13);
[red, ultra thick] (11,-13) – (11,-12);
[red, ultra thick] (11,-12) – (13,-12);
at (10.5,-14.6)[font=7pt0]$2$;
at (10.5,-13.6)[font=7pt0]$3$;
at (11.5,-12.6)[font=7pt0]$1$;

[gray, thin] (40,-15) – (40,-12);
[gray, thin] (41,-15) – (41,-12);
[gray, thin] (42,-15) – (42,-12);
[gray, thin] (43,-15) – (43,-12);
[gray, thin] (40,-15) – (43,-15);
[gray, thin] (40,-14) – (43,-14);
[gray, thin] (40,-13) – (43,-13);
[gray, thin] (40,-12) – (43,-12);
[red, ultra thick] (40,-15) – (40,-13);
[red, ultra thick] (40,-13) – (41,-13);
[red, ultra thick] (41,-13) – (41,-12);
[red, ultra thick] (41,-12) – (43,-12);
at (40.5,-14.6)[font=7pt0]$1$;
at (40.5,-13.6)[font=7pt0]$3$;
at (41.5,-12.6)[font=7pt0]$2$;

[gray, thin] (50,-15) – (50,-12);
[gray, thin] (51,-15) – (51,-12);
[gray, thin] (52,-15) – (52,-12);
[gray, thin] (53,-15) – (53,-12);
[gray, thin] (50,-15) – (53,-15);
[gray, thin] (50,-14) – (53,-14);
[gray, thin] (50,-13) – (53,-13);
[gray, thin] (50,-12) – (53,-12);
[red, ultra thick] (50,-15) – (50,-13);
[red, ultra thick] (50,-13) – (51,-13);
[red, ultra thick] (51,-13) – (51,-12);
[red, ultra thick] (51,-12) – (53,-12);
at (50.5,-14.6)[font=7pt0]$1$;
at (50.5,-13.6)[font=7pt0]$2$;
at (51.5,-12.6)[font=7pt0]$3$;

[gray, thin] (50,-20) – (50,-17);
[gray, thin] (51,-20) – (51,-17);
[gray, thin] (52,-20) – (52,-17);
[gray, thin] (53,-20) – (53,-17);
[gray, thin] (50,-20) – (53,-20);
[gray, thin] (50,-19) – (53,-19);
[gray, thin] (50,-18) – (53,-18);
[gray, thin] (50,-17) – (53,-17);
[red, ultra thick] (50,-20) – (50,-17);
[red, ultra thick] (50,-17) – (53,-17);
at (50.5,-19.6)[font=7pt0]$1$;
at (50.5,-18.6)[font=7pt0]$2$;
at (50.5,-17.6)[font=7pt0]$3$;

Labeled Dyck paths of degree $3$, the positions are in correspondence with the positions of parking functions in Figure <ref>.

§.§ Hopf algebra of parking functions

We define a Hopf structure on parking functions.

As a graded vector space, the Hopf algebra of parking functions, $\PSym$ is  $\displaystyle\bigoplus_{n\geq 0}\Bbbk\PF_n$ where $\PF_n$ is the set of parking functions of degree $n$. By convention $\PF_0$ is the span of the empty parking function. The fundamental basis of $\PSym$ is defined as $\{F_f:f\in\PF\}$.

For $f\in \PF_n$ we let $\allow(f)=\{1,2,\ldots,n-1\}$. In particular,
the comultiplication and multiplication rules for $\PSym$ are

$$\Delta(F_f)=\sum_{i=0}^{\deg(f)}F_{^if}\otimes F_{f^i}=\sum_{f\mapsto(f_1,f_2)}F_{\std(f_1)}\otimes F_{\std(f_2)},$$

$$F_f\cdot F_g=\sum_{g\mapsto(g_1,\dots,g_{\deg(f)+1})}F_{f\overleftarrow{\shuffle}(g_1,\dots,g_{\deg(f)+1})}.$$

Let $f=\begin{tikzpicture}[scale=0.2,baseline=0pt]
\draw[blue, thick] (0,-1) -- (0,0);
\draw[blue, thick] (0,0) -- (2,2);
\draw[blue, thick] (0,0) -- (-2,2);
\draw[blue, thick] (-1,1) -- (0,2);
\filldraw[black] (0,0) circle (5pt)  {};
\filldraw[black] (-1,1) circle (5pt)  {};
\node at (-1,1.7)[font=\fontsize{7pt}{0}]{$2$};
\node at (0,0.7)[font=\fontsize{7pt}{0}]{$1$};
\end{tikzpicture}$ and $g=\begin{tikzpicture}[scale=0.2,baseline=0pt]
\draw[red, thick] (0,-1) -- (0,0);
\draw[red, thick] (0,0) -- (2,2);
\draw[red, thick] (0,0) -- (-2,2);
\draw[red, thick] (1,1) -- (0,2);
\filldraw[black] (0,0) circle (5pt)  {};
\filldraw[black] (1,1) circle (5pt)  {};
\node at (0,0.7)[font=\fontsize{7pt}{0}]{$1$};
\node at (1,1.7)[font=\fontsize{7pt}{0}]{$2$};
\end{tikzpicture}$. Then

$$F_f\cdot F_g=
\draw[blue, thick] (0,-1) -- (0,0);
\draw[blue, thick] (0,0) -- (2,2);
\draw[blue, thick] (0,0) -- (-4,4);
\draw[red, thick] (2,2) -- (0,4);
\draw[red, thick] (2,2) -- (4,4);
\draw[red, thick] (3,3) -- (2,4);
\draw[blue, thick] (-3,3) -- (-2,4);
\filldraw[black] (0,0) circle (5pt)  {};
\filldraw[black] (2,2) circle (5pt)  {};
\filldraw[black] (3,3) circle (5pt)  {};
\filldraw[black] (-3,3) circle (5pt)  {};
\node at (-3,3.7)[font=\fontsize{7pt}{0}]{$2$};
\node at (0,0.7)[font=\fontsize{7pt}{0}]{$1$};
\node at (2,2.7)[font=\fontsize{7pt}{0}]{$3$};
\node at (3,3.7)[font=\fontsize{7pt}{0}]{$4$};
\end{tikzpicture}}+
\draw[blue, thick] (0,-1) -- (0,0);
\draw[blue, thick] (0,0) -- (4,4);
\draw[blue, thick] (0,0) -- (-4,4);
\draw[blue, thick] (-1,1) -- (0,2);
\draw[red, thick] (0,2) -- (-2,4);
\draw[red, thick] (0,2) -- (2,4);
\draw[red, thick] (1,3) -- (0,4);
\filldraw[black] (0,0) circle (5pt)  {};
\filldraw[black] (-1,1) circle (5pt)  {};
\filldraw[black] (0,2) circle (5pt)  {};
\filldraw[black] (1,3) circle (5pt)  {};
\node at (-1,1.7)[font=\fontsize{7pt}{0}]{$2$};
\node at (0,0.7)[font=\fontsize{7pt}{0}]{$1$};
\node at (0,2.7)[font=\fontsize{7pt}{0}]{$3$};
\node at (1,3.7)[font=\fontsize{7pt}{0}]{$4$};
\end{tikzpicture}}+
\draw[blue, thick] (0,-1) -- (0,0);
\draw[blue, thick] (0,0) -- (4,4);
\draw[blue, thick] (0,0) -- (-2,2);
\draw[blue, thick] (-1,1) -- (2,4);
\draw[red, thick] (-2,2) -- (0,4);
\draw[red, thick] (-2,2) -- (-4,4);
\draw[red, thick] (-1,3) -- (-2,4);
\filldraw[black] (0,0) circle (5pt)  {};
\filldraw[black] (-1,1) circle (5pt)  {};
\filldraw[black] (-2,2) circle (5pt)  {};
\filldraw[black] (-1,3) circle (5pt)  {};
\node at (-2,2.7)[font=\fontsize{7pt}{0}]{$3$};
\node at (-1,3.7)[font=\fontsize{7pt}{0}]{$4$};
\node at (-1,1.7)[font=\fontsize{7pt}{0}]{$2$};
\node at (0,0.7)[font=\fontsize{7pt}{0}]{$1$};
\end{tikzpicture}}+
\draw[blue, thick] (0,-1) -- (0,0);
\draw[blue, thick] (0,0) -- (3,3);
\draw[blue, thick] (0,0) -- (-4,4);
\draw[red, thick] (3,3) -- (2,4);
\draw[red, thick] (3,3) -- (4,4);
\draw[blue, thick] (-2,2) -- (-1,3);
\draw[red, thick] (-1,3) -- (-2,4);
\draw[red, thick] (-1,3) -- (0,4);
\filldraw[black] (0,0) circle (5pt)  {};
\filldraw[black] (3,3) circle (5pt)  {};
\filldraw[black] (-2,2) circle (5pt)  {};
\filldraw[black] (-1,3) circle (5pt)  {};
\node at (-2,2.7)[font=\fontsize{7pt}{0}]{$2$};
\node at (-1,3.7)[font=\fontsize{7pt}{0}]{$3$};
\node at (0,0.7)[font=\fontsize{7pt}{0}]{$1$};
\node at (3,3.7)[font=\fontsize{7pt}{0}]{$4$};
\end{tikzpicture}}+
\draw[blue, thick] (0,-1) -- (0,0);
\draw[blue, thick] (0,0) -- (3,3);
\draw[blue, thick] (0,0) -- (-3,3);
\draw[red, thick] (3,3) -- (2,4);
\draw[red, thick] (3,3) -- (4,4);
\draw[blue, thick] (-2,2) -- (0,4);
\draw[red, thick] (-3,3) -- (-2,4);
\draw[red, thick] (-3,3) -- (-4,4);
\filldraw[black] (0,0) circle (5pt)  {};
\filldraw[black] (3,3) circle (5pt)  {};
\filldraw[black] (-2,2) circle (5pt)  {};
\filldraw[black] (-3,3) circle (5pt)  {};
\node at (-3,3.7)[font=\fontsize{7pt}{0}]{$3$};
\node at (-2,2.7)[font=\fontsize{7pt}{0}]{$2$};
\node at (0,0.7)[font=\fontsize{7pt}{0}]{$1$};
\node at (3,3.7)[font=\fontsize{7pt}{0}]{$4$};
\end{tikzpicture}}+
\draw[blue, thick] (0,-1) -- (0,0);
\draw[blue, thick] (0,0) -- (4,4);
\draw[blue, thick] (0,0) -- (-3,3);
\draw[blue, thick] (-1,1) -- (1,3);
\draw[red, thick] (-3,3) -- (-2,4);
\draw[red, thick] (-3,3) -- (-4,4);
\draw[red, thick] (1,3) -- (0,4);
\draw[red, thick] (1,3) -- (2,4);
\filldraw[black] (0,0) circle (5pt)  {};
\filldraw[black] (-1,1) circle (5pt)  {};
\filldraw[black] (-3,3) circle (5pt)  {};
\filldraw[black] (1,3) circle (5pt)  {};
\node at (-3,3.7)[font=\fontsize{7pt}{0}]{$3$};
\node at (-1,1.7)[font=\fontsize{7pt}{0}]{$2$};
\node at (1,3.7)[font=\fontsize{7pt}{0}]{$4$};
\node at (0,0.7)[font=\fontsize{7pt}{0}]{$1$};
\end{tikzpicture}}$$

Let $f=$
[blue, thick] (0,-1) – (0,0);
[blue, thick] (0,0) – (5,5);
[blue, thick] (0,0) – (-5,5);
[blue, thick] (2,2) – (-1,5);
[blue, thick] (1,3) – (3,5);
[blue, thick] (2,4) – (1,5);
[blue, thick] (-4,4) – (-3,5);
[black] (0,0) circle (5pt)  ;
[black] (2,2) circle (5pt)  ;
[black] (1,3) circle (5pt)  ;
[black] (2,4) circle (5pt)  ;
[black] (-4,4) circle (5pt)  ;
at (-4,4.7)[font=7pt0]$4$;
at (0,0.7)[font=7pt0]$2$;
at (1,3.7)[font=7pt0]$3$;
at (2,4.7)[font=7pt0]$5$;
at (2,2.7)[font=7pt0]$1$;
. Then

\draw[blue, thick] (0,-1) -- (0,0);
\draw[blue, thick] (0,0) -- (1,1);
\draw[blue, thick] (0,0) -- (-1,1);
\filldraw[black] (0,0) circle (5pt)  {};
\node at (0,0.7)[font=\fontsize{7pt}{0}]{$1$};
\end{tikzpicture}}\otimes
\draw[blue, thick] (0,-1) -- (0,0);
\draw[blue, thick] (0,0) -- (4,4);
\draw[blue, thick] (0,0) -- (-4,4);
\draw[blue, thick] (1,1) -- (-2,4);
\draw[blue, thick] (0,2) -- (2,4);
\draw[blue, thick] (1,3) -- (0,4);
\filldraw[black] (0,0) circle (5pt)  {};
\filldraw[black] (1,1) circle (5pt)  {};
\filldraw[black] (0,2) circle (5pt)  {};
\filldraw[black] (1,3) circle (5pt)  {};
\node at (0,0.7)[font=\fontsize{7pt}{0}]{$2$};
\node at (0,2.7)[font=\fontsize{7pt}{0}]{$3$};
\node at (1,3.7)[font=\fontsize{7pt}{0}]{$4$};
\node at (1,1.7)[font=\fontsize{7pt}{0}]{$1$};
\end{tikzpicture}}+
\draw[blue, thick] (0,-1) -- (0,0);
\draw[blue, thick] (0,0) -- (2,2);
\draw[blue, thick] (0,0) -- (-2,2);
\draw[blue, thick] (-1,1) -- (0,2);
\filldraw[black] (0,0) circle (5pt)  {};
\filldraw[black] (-1,1) circle (5pt)  {};
\node at (-1,1.7)[font=\fontsize{7pt}{0}]{$2$};
\node at (0,0.7)[font=\fontsize{7pt}{0}]{$1$};
\end{tikzpicture}}\otimes
\draw[blue, thick] (0,-1) -- (0,0);
\draw[blue, thick] (0,0) -- (3,3);
\draw[blue, thick] (0,0) -- (-3,3);
\draw[blue, thick] (-1,1) -- (1,3);
\draw[blue, thick] (0,2) -- (-1,3);
\filldraw[black] (0,0) circle (5pt)  {};
\filldraw[black] (-1,1) circle (5pt)  {};
\filldraw[black] (0,2) circle (5pt)  {};
\node at (0,0.7)[font=\fontsize{7pt}{0}]{$1$};
\node at (-1,1.7)[font=\fontsize{7pt}{0}]{$2$};
\node at (0,2.7)[font=\fontsize{7pt}{0}]{$3$};
\end{tikzpicture}}+
\draw[blue, thick] (0,-1) -- (0,0);
\draw[blue, thick] (0,0) -- (3,3);
\draw[blue, thick] (0,0) -- (-3,3);
\draw[blue, thick] (2,2) -- (1,3);
\draw[blue, thick] (-2,2) -- (-1,3);
\filldraw[black] (0,0) circle (5pt)  {};
\filldraw[black] (2,2) circle (5pt)  {};
\filldraw[black] (-2,2) circle (5pt)  {};
\node at (-2,2.7)[font=\fontsize{7pt}{0}]{$3$};
\node at (0,0.7)[font=\fontsize{7pt}{0}]{$1$};
\node at (2,2.7)[font=\fontsize{7pt}{0}]{$2$};
\end{tikzpicture}}\otimes
\draw[blue, thick] (0,-1) -- (0,0);
\draw[blue, thick] (0,0) -- (2,2);