%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[finalversion]{FPSAC2020}
\articlenumber{6}
\addbibresource{fpsac.bib}

%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}
\crefname{theorem}{Theorem}{Theorems}
\crefname{conjecture}{Conjecture}{Conjectures}


\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{example}[theorem]{Example}
\crefname{example}{Example}{Examples}


\usepackage{shuffle, xstring, xparse}
\usepackage{paralist}
\usepackage{xargs}
\usepackage{ulem}\normalem
\usepackage{wrapfig}
\usepackage{stmaryrd}
\usepackage{picins/picins}
\usepackage{tikz}\usetikzlibrary{trees, snakes, shapes, arrows, matrix, calc, graphs}
\tikzset{blueNode/.style={blue, edge from parent/.style={blue, draw}}}
\tikzset{redNode/.style={red, edge from parent/.style={red, draw}}}
\graphicspath{{figures/}}

%%%%% AUTHOR'S COMMANDS %%%%%

% special letters
\newcommand{\R}{\mathbb{R}} % reals
\newcommand{\N}{\mathbb{N}} % naturals
\newcommand{\Z}{\mathbb{Z}} % integers
\newcommand{\C}{\mathbb{C}} % complex
\newcommand{\K}{\mathbb{K}} % field
\newcommand{\fS}{\mathfrak{S}} % symmetric group

% math commands
\newcommand{\set}[2]{\left\{ #1 \;\middle|\; #2 \right\}} % set notation
\newcommand{\bigset}[2]{\big\{ #1 \;|\; #2 \big\}} % big set notation
\newcommand{\biggset}[2]{\bigg\{ #1 \;\bigg|\; #2 \bigg\}} % bigg set notation
\newcommand{\ssm}{\smallsetminus} % small set minus
\newcommand{\dotprod}[2]{\langle \, #1 \; | \; #2 \, \rangle} % dot product
\newcommand{\symdif}{\,\triangle\,} % symmetric difference
\newcommand{\one}{{1\!\!1}} % the all one vector
\newcommand{\eqdef}{\mbox{\,\raisebox{0.2ex}{\scriptsize\ensuremath{\mathrm:}}\ensuremath{=}\,}} % :=
\newcommand{\defeq}{\mbox{~\ensuremath{=}\raisebox{0.2ex}{\scriptsize\ensuremath{\mathrm:}} }} % =:

% others
\newcommand{\ie}{\textit{i.e.}~} % id est
\newcommand{\eg}{\textit{e.g.}~} % exempli gratia
\newcommand{\Eg}{\textit{E.g.}~} % Exempli gratia
\newcommand{\aka}{\textit{a.k.a.}~} % also known as
\newcommand{\viceversa}{\textit{vice versa}} % exempli gratia
\definecolor{PineGreen}{RGB}{2,120,120} % pinegreen color
\newcommand{\red}{\color{red}} % red command
\newcommand{\blue}{\color{blue}} % blue command
\newcommand{\green}{\color{green}} % green command
\newcommand{\defn}[1]{\emph{#1}} % emphasis of a definition
\newcommand{\shiftedShuffle}{\,\underline{\shuffle}\,} % shifted shuffle
\newcommand{\parabf}[1]{\noindent\textbf{#1}.} % paragraph bf

% Operads
\newcommandx{\Operad}[1][1=O]{\mathcal{#1}} % operad
\newcommand{\Operations}{\mathfrak{B}} % all operations
\newcommandx{\operation}[1][1=b]{\mathfrak{#1}} % operation
\newcommandx{\tree}[1][1=t]{\mathfrak{#1}} % tree
\newcommand{\Free}[1][\Operations]{\mathbf{Free}(#1)} % free operad
\newcommand{\Syntax}[1][\Operations]{\mathbf{Trees}(#1)} % syntax tree
\newcommandx{\syntaxTree}[1][1=t]{\mathfrak{#1}} % syntax tree
\newcommand{\Relations}{\mathfrak{R}} % all relations
\newcommand{\algebra}{\mathsf{Alg}} % algebra
\newcommand{\Hilbert}{\mathcal{H}} % Hilbert series
\newcommand{\koszul}{{\smash{\boldsymbol{!}}}}
\newcommand{\compoR}[2]{
	\begin{tikzpicture}[baseline=-.5cm, inner sep=2pt, level 1/.style={sibling distance = .6cm, level distance = .5cm}, level 2/.style={sibling distance = .6cm, level distance = .4cm}]
		\node [rectangle, draw] {$\op{#1}$}
			child {node {}}
			child {node [rectangle, draw] {$\op{#2}$}
				child {node {}}
				child {node {}}
			}
		;
	\end{tikzpicture}
} % right composition
\newcommand{\compoL}[2]{
	\begin{tikzpicture}[baseline=-.5cm, inner sep=2pt, level 1/.style={sibling distance = .6cm, level distance = .5cm}, level 2/.style={sibling distance = .6cm, level distance = .4cm}]
		\node [rectangle, draw] {$\op{#2}$}
			child {node [rectangle, draw] {$\op{#1}$}
				child {node {}}
				child {node {}}
			}
			child {node {}}
		;
	\end{tikzpicture}
} % left composition

% signaletic operads
\newcommand{\Dend}{\mathsf{Dend}} % dendriform operad
\newcommand{\Dias}{\mathsf{Diass}} % diassociative operad
\newcommand{\Quad}{\mathsf{Quad}} % quad operad
\newcommand{\Twist}{\mathsf{Twist}} % twist operad
%\newcommand{\parallel}{{||}} % parallel
\newcommand{\series}{{\ddagger}} % series
\newcommandx{\signaletic}[1][1=k]{\smash{\mathsf{Sig}_{#1}}} % signaletic operad
\newcommandx{\signaleticParallel}[1][1=k]{\smash{\mathsf{Sig}^\parallel_{#1}}} % parallel signaletic operad
\newcommandx{\signaleticSeries}[1][1=k]{\smash{\mathsf{Sig}^\series_{#1}}} % series signaletic operad
\newcommandx{\citelangis}[1][1=k]{\smash{\mathsf{Cit}_{#1}}} % citelangis operad
\newcommandx{\citelangisParallel}[1][1=k]{\smash{\mathsf{Cit}^\parallel_{#1}}} % parallel citelangis operad
\newcommandx{\citelangisSeries}[1][1=k]{\smash{\mathsf{Cit}^\series_{#1}}} % series citelangis operad
\newcommand{\op}[1]{
	\foreach \letters in {#1} {
		\StrLeft{\letters}{1}[\firstletter]
		\StrRight{\letters}{1}[\lastletter]
		\IfEqCase{\lastletter}{%
			{a}{\red}%
			{b}{\blue}%
			{c}{\green}%
			{f}{\bf}%
		}%
		\hspace{-.1mm}
		\IfEqCase{\firstletter}{%
			{l}{\prec}%
			{m}{\prec\hspace*{-.27cm}\succ}%
			{r}{\succ}%
			{o}{\odot}%
		
		
		
			{*}{\color{gray}\prec}%
			{n}{\color{white}\prec}%
		} \hspace{-.1mm}
	}
}
\newcommand{\destVect}[2]{\llparenthesis\, #1\, \rrparenthesis_{#2}} % destination vector
\newcommand{\ind}[1]{\mathsf{#1}} % indices
\newcommand{\EulPol}[1]{\mathrm{Eul}_{#1}} % Euler polynomial
\newcommand{\EulNum}[2]{\genfrac{\langle}{\rangle}{0pt}{}{#1}{#2}} % Euler number
\newcommand{\FQSym}{\mathsf{FQSym}} % Free quasi-symmetric functions
\DeclareMathOperator{\des}{des} % descents
\newcommand{\EvalPermSeries}{\smash{\mathrm{Perm}^\series}} % evaluation of a syntax tree in messy series citelangis algebra
\newcommand{\EvalPosetSeries}{\smash{\mathrm{Pos}^\series}} % evaluation of a syntax tree in messy series citelangis algebra
\DeclareMathOperator{\LexMin}{LexMin} % lexicographic minimal
\DeclareMathOperator{\Root}{Root} % root
\DeclareMathOperator{\LinExt}{LinExt} % linear extensions

%%%%% END AUTHOR'S COMMANDS %%%%%

%% define your title in the usual way
\title{Signaletic operads}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{
	\stepcounter{footnote}
	\stepcounter{footnote}
	Florent Hivert\thanks{\href{mailto:florent.hivert@lri.fr}{florent.hivert@lri.fr}. Supp. by ANR CARMA~12\,BS01\,0017.}\addressmark{1}
	\and
	Vincent Pilaud\thanks{\href{mailto:vincent.pilaud@lix.polytechnique.fr}{vincent.pilaud@lix.polytechnique.fr}. Supp. by ANR SC3A~15\,CE40\,0004\,01 and CAPPS~17\,CE40\,0018.}\addressmark{2}
}

%% then use \addressmark to match authors to institutions here
\address{
	\addressmark{1} LRI, Universit\'e Paris-Sud, Orsay, France \\
	\addressmark{2} CNRS \& LIX, \'Ecole Polytechnique, Palaiseau, France
}

%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
%\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{
We define signaletic operads that extend the dendriform and diassociative operads by abstracting shuffle product decompositions according to the provenance of the first $k$ letters.
We realize these operads combinatorially in terms of multipermutations and multiposets avoiding certain patterns.
}

%% put your French abstract here, or comment this out if you don't have one
%\resumetitle{R\'esum\'e}
\resume{
Nous d\'efinissons les op\'erades signaletiques qui g\'en\'eralisent les op\'erades dendriforme et diassociative par abstraction de d\'ecompositions du produit de m\'elange selon la provenance des $k$ premi\`eres lettres. Nous r\'ealisons ces op\'erades combinatoirement en termes de multipermutations et multiposets \'evitant certains motifs. }

%% put your keywords here, or comment this out if you don't have them yet
\keywords{Shuffle product splitting, operads, Koszul duality, dendriform algebras}

%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations, ie. [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want

%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\begin{document}

\maketitle
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above

\section{Introduction}
\label{sec:intro}

%
\parabf{Shuffle splitting}
%
In his study of Leibniz algebras (\aka non-commutative Lie algebras), \mbox{J.-L.~Loday} introduced dendriform algebras~\cite{Loday-dialgebras}.
They formalize the splitting of the shuffle product~$\shuffle$ into two operations~$\op{l}$ and~$\op{r}$ according to  the \mbox{provenance of the first letter:}
\begin{gather*}
{\shuffle} = {\op{l}} + {\op{r}}
\quad\text{where}\quad
xX \op{l} yY = x (X \shuffle yY)
\quad\text{and}\quad
xX \op{r} yY = y (xX \shuffle Y).
\end{gather*}
Suitable adaptations of this definition endow with a dendriform structure any shuffle-like algebra, including C.~Malvenuto and C.~Reutenauer's algebra on permutations~\cite{MalvenutoReutenauer}.
Dendriform algebras are closely related to Catalan combinatorics since the free dendriform algebra is J.-L.~Loday and M.~Ronco's algebra on binary trees~\cite{LodayRonco}.

Two natural generalizations of dendriform algebras were recently studied, further splitting the shuffle product into four partial shuffles according to the provenance of:
\begin{compactenum}[(i)]
\item the first and last letters, defining a quadri-algebra structure of~\cite{AguiarLoday, Foissy}, or
\item the first two letters, defining a $2$-twistiform algebra structure of~\cite{Pilaud-brickAlgebra}.
\end{compactenum}
The objective of this paper is to unify and largely extend these constructions and to clarify the underlying combinatorics.

\bigskip
\parabf{Operads}
%
Operads provide a good algebraic formalism to abstract and compare different types of algebras.
Here, we adopt a resolutely combinatorial perspective on operads, based on symbolic manipulations of syntax trees.
In a world with more than one operation, syntax trees play the role of monomials in classical commutative associative algebra.
Substituting variables in a monomial then translates into grafting syntax trees. The linear relations between the operations of the algebras translate to linear relations between syntax trees.
For instance, the three conditions
{\small
\[
%\hspace{-2cm}
a \! \op{l} \! (b \! \op{l} \! c) \! + \! a \! \op{l} \! (b \! \op{r} \! c) \! = \! (a \! \op{l} \! b) \! \op{l} \! c
\quad
a \! \op{r} \! (b \! \op{l} \! c) \! = \! (a \! \op{r} \! b) \! \op{l} \! c
\quad
a \! \op{r} \! (b \! \op{r} \! c) \! = \! (a \! \op{l} \! b) \! \op{r} \! c \! + \! (a \! \op{r} \! b) \! \op{r} \! c
%\hspace{-2cm}
\]
}
defining a dendriform algebra translate into the operadic relations
\[
\compoR{l}{l} + \compoR{l}{r} = \compoL{l}{l}
\qquad\qquad\;
\compoR{r}{l} = \compoL{r}{l}
\qquad\qquad\;
\compoR{r}{r} = \compoL{l}{r} + \compoL{r}{r}.
\]
The dendriform operad is nothing else but the vector space generated by syntax trees labeled by~$\{\op{l}, \op{r}\}$ modulo the application of these relations anywhere inside the trees.
Remarkably, the Catalan number~$\smash {C_p \eqdef \frac{1}{p+1} \binom{2p}{p}}$ appears here in two unrelated ways: trivially, there are~$2^{p-1}C_{p-1}$ syntax trees of arity~$p$ and more subtly, there are~$C_p$ linearly independent syntax trees of arity~$p$ modulo dendriform relations.
While this enumeration can be shown with elementary methods, it is enlighten by Koszul duality.

%\enlargethispage{.2cm}
An operad~$\Operad$ is Koszul when it admits a quadratic presentation whose relations can be oriented into a convergent rewriting system.
When this happens, the orthogonal of the relations for a suitable scalar product defines the Koszul dual operad~$\Operad^\koszul$ of~$\Operad$.
For instance, the Koszul dual of the dendriform operad is the diassociative operad defined~by
\[
\compoR{l}{l} = \compoR{l}{r} = \compoL{l}{l}
\qquad\qquad\;
\compoR{r}{l} = \compoL{r}{l}
\qquad\qquad\;
\compoR{r}{r} = \compoL{l}{r} = \compoL{r}{r}.
\]
The combinatorics of two Koszul dual operads are strongly interconnected, as is enumeratively illustrated by their Hilbert series.
The Hilbert series~$\smash{\displaystyle \Hilbert_{\Operad}(t) \eqdef \sum\nolimits_{p \ge 1} \dim \Operad(p) \, t^p}$ of an operad~$\Operad$ records the dimensions of the vector spaces of syntax trees (modulo relations) graded by their arity.
The Hilbert series of two Koszul dual operads turn out to be Lagrange inverses: $\Hilbert_{\Operad}(-\Hilbert_{\Operad^\koszul}(-t)) = t$.
For instance, the dendriform and diassociative Hilbert series are~$\smash{\Hilbert_\Dend(t) = {\displaystyle \sum}_{p \ge 1} C_p t^p = \frac{1-\sqrt{1-4t}}{2t}-1}$ and~$\smash{\Hilbert_\Dias(t) = {\displaystyle \sum}_{p \ge 1} p t^p = \frac{t}{1-t^2}}$.

\bigskip
\parabf{Contribution}
%
We observe that further splitting the shuffle product according to the provenance of the first $k$ letters defines a Koszul operad whose Koszul dual has Hilbert series~$\smash{{\displaystyle \sum}_{p \ge 1} p^k \, t^p = \frac{\EulPol{k}(t)}{(1-t)^{k+1}}}$ (where $\smash{\EulPol{k}(t) = {\displaystyle \sum}_{\sigma \in \fS_k} t^{\des(\sigma)+1}}$ is the $k$th Eulerian polynomial).
Our main tool to study this pair of Koszul dual operads is the signaletic interpretation of their relations: we consider syntax trees labeled by operations in~$\{\op{l}, \op{r}\}^k$ modulo relations defined by the destinations of $k$ cars (or bikes for ecological reasons) traversing the trees following the operations as traffic signals.
We study these operads through their free algebras, that we combinatorially realize in terms of multipermutations and multiposets avoiding certain patterns.
We refer to~\cite{HivertPilaud} for much more \mbox{details and proofs}.

\section{Background on operads}

\subsection{Operads}

An operad is an algebraic structure abstracting a type of algebras.
We give here the formal definitions needed in this paper.
We refer to~\cite{LodayVallette} for classical references on operads, and to~\cite{Chapoton-operads, Giraudo-nonsymmetricOperadsCombinatorics} for more combinatorial approches.

\begin{definition}
A (non-symmetric) \defn{operad} is a vector space of \defn{operations}~$\smash{\displaystyle \Operad = \bigoplus\nolimits_{p \ge 1} \! \Operad(p)}$ endowed with a \defn{unit}~$\one \in \Operad(1)$ and \defn{partial compositions} ${\circ_i : \Operad(p) \otimes \Operad(q) \to \Operad(p+q-1)}$ for all~$p,q \ge 1$ and~$i \in [p]$ such that for all ${\operation[p] \in \Operad(p), \, \operation[q] \in \Operad(q), \, \operation[r] \in \Operad(r)}$:
\[
\begin{array}{@{}l@{\qquad\qquad}c@{\qquad\qquad}l@{}}
\text{(\defn{unitality})} & \one \circ_1 \operation[p] = \operation[p] = \operation[p] \circ_i \one & \text{for all } i \in [p], \\
\text{(\defn{series composition})} & (\operation[p] \circ_i \operation[q]) \circ_{i+j-1} \operation[r] = \operation[p] \circ_i (\operation[q] \circ_j \operation[r]) & \text{for all } i \in [p], \; j \in [q], \\
\text{(\defn{parallel composition})} & (\operation[p] \circ_i \operation[q]) \circ_{j+q-1} \operation[r] = (\operation[p] \circ_j \operation[r]) \circ_i \operation[q] & \text{for all } i < j \in [p].
\end{array}
\]
\end{definition}

Operad morphisms are maps which commute with the compositions, operad ideals are subspaces stable by compositions, and operad quotients are defined naturally.

\begin{definition}
The \defn{Hilbert series} of~$\Operad$ is the power series~$\displaystyle \Hilbert_{\Operad}(t) \eqdef \sum\nolimits_{p \ge 1} \dim \Operad(p) \, t^p$. % encoding the dimensions of~$\Operad(p)$ for~$p \ge 1$.
\vspace{-.2cm}
\end{definition}

\begin{definition}
An \defn{algebra over~$\Operad$} is a vector space~$\algebra$ with a map~${\Operad(p) \otimes \algebra^{\otimes p} \to \algebra}$ respecting compositions: for~$\operation[p] \! \in \! \Operad(p)$, $\operation[q] \! \in \! \Operad(q)$, $a_1 \otimes \dots \otimes a_{p+q-1} \! \in \! \algebra^{\otimes p+q-1}$ and~${i \! \in \! [p]}$,
\(
(\operation[p] \circ_i \operation[q]) (a_1 \otimes \dots \otimes a_{p+q-1}) = \operation[p] (a_1 \otimes \dots \otimes a_{i-1} \otimes \operation[q] (a_i \otimes \dots \otimes a_{i+q-1}) \otimes a_{i+q} \otimes \dots \otimes a_{p+q-1}).
\)
\end{definition}


\subsection{Syntax trees, free operads, presentations, and rewriting systems}

Operads are about ways to compose operations.
To manipulate these compositions and the relations between them, we need the fundamental tool of syntax trees.
We only deal with (and restrict our presentation to) binary operads (generated by binary operations).

\begin{definition}
A \defn{binary syntax tree} over a set~$\Operations$ is a rooted planar binary tree~$\tree$ whose vertices are labeled by~$\Operations$. The \defn{arity} of~$\tree$ is its number of leaves. Let~$\Syntax(p)$ denote the set of syntax trees of arity~$p$ and~$\smash{\displaystyle \Syntax \eqdef \bigsqcup\nolimits_{p\ge 1} \Syntax(p)}$. 
\end{definition}

\begin{definition}
For a set~$\Operations$, the \defn{free binary operad} is~$\smash{\displaystyle \Free \eqdef \bigoplus\nolimits_{p \ge 1} \Free(p)}$ where:
\begin{compactitem}
\item $\Free(p)$ is the vector space generated by binary syntax trees on~$\Operations$~of~arity~$p$,
\item $\circ_i$ is the linear map defined on two binary syntax trees~$\operation[s]$ and~$\operation[t]$ by grafting the root of~$\operation[t]$ on the $i$-th leaf of~$\operation[s]$, and extended by linearity to~$\Free$, and
\item the unit is the tree with no internal node and only one leaf.
\end{compactitem}
\end{definition}

\begin{definition}
A \defn{presentation} of a binary operad~$\Operad$ is a pair~$(\Operations, \Relations)$ where~$\Relations$ is a subspace of~$\Free$ such that~$\Operad$ is isomorphic to the quotient operad~$\Free/\langle \Relations \rangle$. The elements of~$\Operations$ are the \defn{generators} while the elements of~$\Relations$ are the \defn{relations} of the presentation. The operad~$\Operad$ is said \defn{quadratic} if the relations~$\Relations$ only involves trees with two nodes. % (\ie of arity~$3$).
\end{definition}

\begin{definition}
A \defn{quadratic rewriting rule} is a pair $(\tree[s], \operation[q])$ with a syntax tree~$\tree[s]$ in $\!\Syntax(3)$ and a linear combination $\operation[q]$ in $\Free(3)$. A \defn{quadratic rewriting system} over~$\Operations$ is a set of quadratic rewriting rules. A tree~$\tree\in\Syntax$ \defn{rewrittes} into an element~${\operation[p]\in\Free}$ if there exists an integer $i$, a tree $\tree[u]$ of arity at least $i$, a rule~$(\tree[s], \operation[q])$ of the system, and a triple of trees $(\tree[l]_1, \tree[l]_2, \tree[l]_3)$ such that $\tree = \tree[u] \circ_i \big(\tree[s] \circ (\tree[l]_1, \tree[l]_2, \tree[l]_3)\big)$ and $\operation[p] = \tree[u] \circ_i \big(\operation[q] \circ (\tree[l]_1, \tree[l]_2, \tree[l]_3)\big)$ (where~$\tree[s] \circ (\tree[l]_1, \tree[l]_2, \tree[l]_3) \eqdef ((\tree[s] \circ_3 \tree[l]_3) \circ_2 \tree[l]_2) \circ_1 \tree[l]_1$ is the grafting of~$\tree[l]_1, \tree[l]_2, \tree[l]_3$ at the three leaves~of~$\tree[s]$).
\end{definition}

\medskip
\begin{example}
An example of application of the rewriting rule~$\smash{\bigg(\compoR{l}{l} , \compoL{l}{l} + \compoR{l}{r}\bigg)}$~is:

\[
	\begin{tikzpicture}[baseline=-1.2cm, inner sep=2pt, level/.style={sibling distance = 20mm/#1, level distance = .8cm/sqrt(sqrt(#1))}]
		\node [rectangle, draw] {$\op{r}$}
			child {node [rectangle, draw, fill=red!50] {$\op{l}$}
				child {node [rectangle, draw] {$\op{r}$}
					child {node {\phantom{1}}}
					child {node {\phantom{1}}}
				}
				child {node [rectangle, draw, fill=red!50] {$\op{l}$}
					child {node [rectangle, draw] {$\op{l}$}
						child {node {\phantom{1}}}
						child {node {\phantom{1}}}
					}
					child {node [rectangle, draw] {$\op{r}$}
						child {node {\phantom{1}}}
						child {node [rectangle, draw] {$\op{r}$}
							child {node {\phantom{1}}}
							child {node {\phantom{1}}}
						}
					}
				}
			}
			child {node [rectangle, draw] {$\op{l}$}
				child {node [rectangle, draw] {$\op{r}$}
					child {node {\phantom{1}}}
					child {node {\phantom{1}}}
				}
				child {node {\phantom{1}}}
			}
		;
	\end{tikzpicture}
	\longrightarrow
	\begin{tikzpicture}[baseline=-1.2cm, inner sep=2pt, level/.style={sibling distance = 20mm/#1, level distance = .8cm/sqrt(sqrt(#1))}]
		\node [rectangle, draw] {$\op{r}$}
			child {node [rectangle, draw, fill=red!50] {$\op{l}$}
				child {node [rectangle, draw, fill=red!50] {$\op{l}$}
					child {node [rectangle, draw] {$\op{r}$}
						child {node {\phantom{1}}}
						child {node {\phantom{1}}}
					}
					child {node [rectangle, draw] {$\op{l}$}
						child {node {\phantom{1}}}
						child {node {\phantom{1}}}
					}
				}
				child {node [rectangle, draw] {$\op{r}$}
					child {node {\phantom{1}}}
					child {node [rectangle, draw] {$\op{r}$}
						child {node {\phantom{1}}}
						child {node {\phantom{1}}}
					}
				}
			}
			child {node [rectangle, draw] {$\op{l}$}
				child {node [rectangle, draw] {$\op{r}$}
					child {node {\phantom{1}}}
					child {node {\phantom{1}}}
				}
				child {node {\phantom{1}}}
			}
		;
	\end{tikzpicture}
	+
	\begin{tikzpicture}[baseline=-1.2cm, inner sep=2pt, level/.style={sibling distance = 20mm/#1, level distance = .8cm/sqrt(sqrt(#1))}]
		\node [rectangle, draw] {$\op{r}$}
			child {node [rectangle, draw, fill=red!50] {$\op{l}$}
				child {node [rectangle, draw] {$\op{r}$}
					child {node {\phantom{1}}}
					child {node {\phantom{1}}}
				}
				child {node [rectangle, draw, fill=red!50] {$\op{r}$}
					child {node [rectangle, draw] {$\op{l}$}
						child {node {\phantom{1}}}
						child {node {\phantom{1}}}
					}
					child {node [rectangle, draw] {$\op{r}$}
						child {node {\phantom{1}}}
						child {node [rectangle, draw] {$\op{r}$}
							child {node {\phantom{1}}}
							child {node {\phantom{1}}}
						}
					}
				}
			}
			child {node [rectangle, draw] {$\op{l}$}
				child {node [rectangle, draw] {$\op{r}$}
					child {node {\phantom{1}}}
					child {node {\phantom{1}}}
				}
				child {node {\phantom{1}}}
			}
		;
	\end{tikzpicture}
\]
\vspace{-.7cm}
\end{example}

\begin{definition}
A \defn{normal form} is a tree that is not rewritable, which means that it does not contain any pattern~$\tree[s]$ of a rewriting rule~$(\tree[s], \operation[q])$.
A rewriting system is \defn{convergent} when any syntax tree rewrites as a unique linear combination of normal forms.
\end{definition}

Any convergent rewriting system defines a presentation where the relation space~$\Relations$ is spanned by $\tree[s] - \operation[q]$ for all rules~$(\tree[s], \operation[q])$ in the system. In this case, the quotient $\Free/\langle \Relations \rangle$ can be identified with the linear span of the normal forms of the rewriting system.

\subsection{Koszulity and Koszul duality}

The only Koszul operads considered in this paper are set operads (\ie where the right hand side of each rewriting rule consists in a single tree) and their Koszul duals (defined below).
We therefore skip the technical definition of Koszul operads and only present a criterion valid in the context of set operads, borrowed from~\cite{DotsenkoKhoroshkin}, that we take as definition.

\begin{definition}
A set operad~$\Operad$ is \defn{Koszul} if it admits a quadratic presentation whose relations can be oriented into a convergent rewriting system. Moreover, the set of normal forms of the rewriting system is called a \defn{Poincar\'e\,--\,Birkhoff\,--\,Witt basis} of~$\Operad$.
\end{definition}

We now define Koszul duality.
We endow the homogeneous component of degree~$3$ of the free operad~$\Free$ with a scalar product~$\dotprod{\cdot}{\cdot}$ defined by $\dotprod{ \, \operation[a] \circ_1 \operation[b] \, }{ \, \operation[a] \circ_1 \operation[b] \, } \eqdef 1$ and $\dotprod{ \, \operation[a] \circ_2 \operation[b] \, }{ \, \operation[a] \circ_2 \operation[b] \, } \eqdef -1$, while $\dotprod{ \, \operation[a] \circ_i \operation[b] \, }{ \, \operation[c] \circ_j \operation[d] \, } \eqdef 0$ in all other situations.

\begin{definition}
The \defn{Koszul dual} of a quadratic operad~$\Operad$ presented by~$(\Operations, \Relations)$ is the quadratic operad~$\Operad^\koszul$ presented by~$(\Operations, \Relations^\koszul)$, where~$\Relations^\koszul$ is the orthogonal complement of~$\Relations$ for~$\dotprod{\cdot}{\cdot}$.
The Koszul dual of a Koszul operad~is~Koszul.
\end{definition}

\begin{theorem}
\label{thm:HilbertKoszulLagrange}
The Hilbert series of two Koszul dual Koszul operads~$\Operad$ and~$\Operad^\koszul$ are related by Lagrange inversion:
\(
\Hilbert_{\Operad}(-\Hilbert_{\Operad^\koszul}(-t)) = t.
\)
\end{theorem}

%%

\section{Signaletic and citelangis operads}
\label{sec:signaleticOperads}

\setlength{\fboxsep}{1.5pt}

\subsection{Signaletic interpretation of the diassociative operad}

\parpic(5cm,2.5cm)(-13pt, 25pt)[r][b]{
	\begin{tikzpicture}[baseline=-1.2cm, inner sep=2pt, level/.style={sibling distance = 27mm/#1, level distance = .8cm/sqrt(sqrt(#1))}]
		\node [rectangle, draw, xshift=11cm] (root) {$\op{la}$}
			child {node [rectangle, draw] (l) {$\op{ra}$}
				child {node [rectangle, draw] (ll) {$\op{l}$}
					child {node (lll) {\;\;1}}
					child {node [rectangle, draw] (llr) {$\op{r}$}
						child {node (llrl) {\;\;2}}
						child {node (llrr) {3\;\;}}
					}
				}
				child {node [rectangle, draw] (lr) {$\op{la}$}
					child {node (lrl) {\;\;4}}
					child {node [rectangle, draw] (lrr) {$\op{l}$}
						child {node (lrrl) {\;\;5}}
						child {node (lrrr) {6\;\;}}
					}
				}
			}
			child {node [rectangle, draw] (r) {$\op{r}$}
				child {node [rectangle, draw] (rl) {$\op{r}$}
					child {node (rll) {\;\;7}}
					child {node (rlr) {8\;\;}}
				}
				child {node [rectangle, draw] (rr) {$\op{r}$}
					child {node [rectangle, draw] (rrl) {$\op{l}$}
						child {node (rrll) {\;\;9}}
						child {node (rrlr) {10\;\;}}
					}
					child {node (rrr) {11\;\;}}
				}
			}
		;
		\draw[join=round, line cap=round, line width = 3pt, red, opacity=.5, ->] ($(root) + (0,.5)$) -- (root.center) -- (l.center) -- (lr.center) -- (lrl.center);
	\end{tikzpicture}
}
Consider that a syntax tree~$\tree$ on the operators~$\{\op{l}, \op{r}\}$ is an arborescent road where each branching node is occupied by a traffic signal~$\boxed{\op{l}}$ or~$\boxed{\op{r}}$. A car arrives at the root of~$\tree$ and drives through the tree~$\tree$ following at each branching node the direction indicated by the traffic signal. The car ends at a certain leaf of~$\tree$ that we call the \defn{destination} of~$\tree$. This procedure is illustrated above. Observe that the diassociative relations are compatible with the destination:

\medskip
\centerline{$
\begin{tikzpicture}[baseline=-.3cm, inner sep=2pt, level/.style={sibling distance = .6cm, level distance = .5cm}]
	\node [rectangle, draw] (root) {$\op{la}$}
		child {node (l) {1}}
		child {node [rectangle, draw] (r) {$\op{l}$}
			child {node (rl) {2}}
			child {node (rr) {3}}
		}
	;
	\draw[join=round, line cap=round, line width = 3pt, red, opacity=.5, ->] ($(root) + (0,.5)$) -- (root.center) -- (l.center);
\end{tikzpicture}
=
\begin{tikzpicture}[baseline=-.3cm, inner sep=2pt, level/.style={sibling distance = .6cm, level distance = .5cm}]
	\node [rectangle, draw] (root) {$\op{la}$}
		child {node (l) {1}}
		child {node [rectangle, draw] (r) {$\op{r}$}
			child {node (rl) {2}}
			child {node (rr) {3}}
		}
	;
	\draw[join=round, line cap=round, line width = 3pt, red, opacity=.5, ->] ($(root) + (0,.5)$) -- (root.center) -- (l.center);
\end{tikzpicture}
=
\begin{tikzpicture}[baseline=-.3cm, inner sep=2pt, level/.style={sibling distance = .6cm, level distance = .5cm}]
	\node [rectangle, draw] (root) {$\op{la}$}
		child {node [rectangle, draw] (l) {$\op{la}$}
			child {node (ll) {1}}
			child {node (lr) {2}}
		}
		child {node (r) {3}}
	;
	\draw[join=round, line cap=round, line width = 3pt, red, opacity=.5, ->] ($(root) + (0,.5)$) -- (root.center) -- (l.center) -- (ll.center);
\end{tikzpicture}
%
\qquad\quad
%
\begin{tikzpicture}[baseline=-.3cm, inner sep=2pt, level/.style={sibling distance = .6cm, level distance = .5cm}]
	\node [rectangle, draw] (root) {$\op{ra}$}
		child {node (l) {1}}
		child {node [rectangle, draw] (r) {$\op{la}$}
			child {node (rl) {2}}
			child {node (rr) {3}}
		}
	;
	\draw[join=round, line cap=round, line width = 3pt, red, opacity=.5, ->] ($(root) + (0,.5)$) -- (root.center) -- (r.center) -- (rl.center);
\end{tikzpicture}
=
\begin{tikzpicture}[baseline=-.3cm, inner sep=2pt, level/.style={sibling distance = .6cm, level distance = .5cm}]
	\node [rectangle, draw] (root) {$\op{la}$}
		child {node [rectangle, draw] (l) {$\op{ra}$}
			child {node (ll) {1}}
			child {node (lr) {2}}
		}
		child {node (r) {3}}
	;
	\draw[join=round, line cap=round, line width = 3pt, red, opacity=.5, ->] ($(root) + (0,.5)$) -- (root.center) -- (l.center) -- (lr.center);
\end{tikzpicture}
%
\qquad\quad
%
\begin{tikzpicture}[baseline=-.3cm, inner sep=2pt, level/.style={sibling distance = .6cm, level distance = .5cm}]
	\node [rectangle, draw] (root) {$\op{ra}$}
		child {node (l) {1}}
		child {node [rectangle, draw] (r) {$\op{ra}$}
			child {node (rl) {2}}
			child {node (rr) {3}}
		}
	;
	\draw[join=round, line cap=round, line width = 3pt, red, opacity=.5, ->] ($(root) + (0,.5)$) -- (root.center) -- (r.center) -- (rr.center);
\end{tikzpicture}
=
\begin{tikzpicture}[baseline=-.3cm, inner sep=2pt, level/.style={sibling distance = .6cm, level distance = .5cm}]
	\node [rectangle, draw] (root) {$\op{ra}$}
		child {node [rectangle, draw] (l) {$\op{l}$}
			child {node (ll) {1}}
			child {node (lr) {2}}
		}
		child {node (r) {3}}
	;
	\draw[join=round, line cap=round, line width = 3pt, red, opacity=.5, ->] ($(root) + (0,.5)$) -- (root.center) -- (r.center);
\end{tikzpicture}
=
\begin{tikzpicture}[baseline=-.3cm, inner sep=2pt, level/.style={sibling distance = .6cm, level distance = .5cm}]
	\node [rectangle, draw] (root) {$\op{ra}$}
		child {node [rectangle, draw] (l) {$\op{r}$}
			child {node (ll) {1}}
			child {node (lr) {2}}
		}
		child {node (r) {3}}
	;
	\draw[join=round, line cap=round, line width = 3pt, red, opacity=.5, ->] ($(root) + (0,.5)$) -- (root.center) -- (r.center);
\end{tikzpicture}$.}
\medskip

\noindent
This shows that two equivalent syntax trees have the same destination. The reverse statement can be shown using normal forms as will be generalized in \cref{thm:signaleticOperadsQuadratic}.

\begin{proposition}[\cite{Loday-dialgebras}]
Two syntax trees on~$\{\op{l}, \op{r}\}$ with the same arity represent the same operation in the diassociative operad if and only if they have the same destination.
\end{proposition}

\subsection{Signaletic operads}

%\enlargethispage{.2cm}
This signaletic interpretation motivates two generalizations of the diassociative operad. Namely, fix an integer~$k \ge 1$, consider a syntax tree~$\tree$ on the operators~$\Operations_k \eqdef \{\op{l}, \op{r}\}^k$, and assume that $k$ cars arrive at the root of~$\tree$. These $k$ cars drive through the tree~$\tree$ following the directions indicated by the traffic signal at each branching node in two~ways:
\begin{compactitem}
\item \defn{Parallel}: The $k$ cars all start together at the root of~$\tree$, and the $i$-th car always follows the indication given by the $i$-th letter of the traffic signal at each branching node.
\item \defn{Series}: The $k$ cars start one after the other at the root of~$\tree$, and each car always follows the indication given by the leftmost remaining letter of the traffic signal at each branching node and erases it.
\end{compactitem}

\begin{figure}[!h]
	\centerline{
	\resizebox{\textwidth}{!}{
	\begin{tikzpicture}[baseline=-1.2cm, inner sep=2pt, level/.style={sibling distance = 45mm/#1, level distance = .8cm/sqrt(sqrt(#1))}]
		\node [rectangle, draw] (root) {$\op{la,rb,lc}$}
			child {node [rectangle, draw] (l) {$\op{la,r,rc}$}
				child {node [rectangle, draw] (ll) {$\op{ra,l,l}$}
					child {node (lll) {\;\;1}}
					child {node [rectangle, draw] (llr) {$\op{la,r,r}$}
						child {node (llrl) {\;\;2}}
						child {node (llrr) {3\;\;}}
					}
				}
				child {node [rectangle, draw] (lr) {$\op{r,r,lc}$}
					child {node (lrl) {\;\;4}}
					child {node [rectangle, draw] (lrr) {$\op{r,l,l}$}
						child {node (lrrl) {\;\;5}}
						child {node (lrrr) {6\;\;}}
					}
				}
			}
			child {node [rectangle, draw] (r) {$\op{l,rb,r}$}
				child {node [rectangle, draw] (rl) {$\op{r,l,r}$}
					child {node (rll) {\;\;7}}
					child {node (rlr) {8\;\;}}
				}
				child {node [rectangle, draw] (rr) {$\op{r,lb,r}$}
					child {node [rectangle, draw] (rrl) {$\op{r,lb,l}$}
						child {node (rrll) {\;\;9}}
						child {node (rrlr) {10\;\;}}
					}
					child {node (rrr) {11\;\;}}
				}
			}
		;
		\draw[join=round, line cap=round, line width = 3pt,   red, opacity=.5, ->] ($(root) + (-.25,.5)$) -- ($(root) + (-.25,0)$) -- ($(l) + (-.25,0)$) -- ($(ll) + (-.25,0)$) -- ($(llr) + (-.25,0)$) -- ($(llrl) + (-.25,0)$);
		\draw[join=round, line cap=round, line width = 3pt,  blue, opacity=.5, ->] ($(root) + (  0,.5)$) -- ($(root) + (  0,0)$) -- ($(r) + (  0,0)$) -- ($(rr) + (  0,0)$) -- ($(rrl) + (  0,0)$) -- ($(rrll) + (  0,0)$);
		\draw[join=round, line cap=round, line width = 3pt, green, opacity=.5, ->] ($(root) + ( .25,.5)$) -- ($(root) + ( .25,0)$) -- ($(l) + ( .25,0)$) -- ($(lr) + ( .25,0)$) -- ($(lrl) + ( .25,0)$);
	\end{tikzpicture}
	\;
	\begin{tikzpicture}[baseline=-1.2cm, inner sep=2pt, level/.style={sibling distance = 45mm/#1, level distance = .8cm/sqrt(sqrt(#1))}]
		\node [rectangle, draw] (root) {$\op{la,rb,lc}$}
			child {node [rectangle, draw] (l) {$\op{la,rc,r}$}
				child {node [rectangle, draw] (ll) {$\op{ra,l,l}$}
					child {node (lll) {\;\;1}}
					child {node [rectangle, draw] (llr) {$\op{la,r,r}$}
						child {node (llrl) {\;\;2}}
						child {node (llrr) {3\;\;}}
					}
				}
				child {node [rectangle, draw] (lr) {$\op{rc,r,l}$}
					child {node (lrl) {\;\;4}}
					child {node [rectangle, draw] (lrr) {$\op{rc,l,l}$}
						child {node (lrrl) {\;\;5}}
						child {node (lrrr) {6\;\;}}
					}
				}
			}
			child {node [rectangle, draw] (r) {$\op{lb,r,r}$}
				child {node [rectangle, draw] (rl) {$\op{rb,l,r}$}
					child {node (rll) {\;\;7}}
					child {node (rlr) {8\;\;}}
				}
				child {node [rectangle, draw] (rr) {$\op{r,l,r}$}
					child {node [rectangle, draw] (rrl) {$\op{r,l,l}$}
						child {node (rrll) {\;\;9}}
						child {node (rrlr) {10\;\;}}
					}
					child {node (rrr) {11\;\;}}
				}
			}
		;
		\draw[join=round, line cap=round, line width = 3pt,   red, opacity=.5, ->] ($(root) + (-.25,.5)$) -- ($(root) + (-.25,0)$) -- ($(l) + (-.25,0)$) -- ($(ll) + (-.25,0)$) -- ($(llr) + (-.25,0)$) -- ($(llrl) + (-.25,0)$);
		\draw[join=round, line cap=round, line width = 3pt,  blue, opacity=.5, ->] ($(root) + ( 0,.5)$) -- ($(root) + ( 0,0)$) -- ($(r) + (-.25,0)$) -- ($(rl) + (-.25,0)$) -- ($(rlr) + (-.25,0)$);
		\draw[join=round, line cap=round, line width = 3pt, green, opacity=.5, ->] ($(root) + ( .25,.5)$) -- ($(root) + ( .25,0)$) -- ($(l) + ( 0,0)$) -- ($(lr) + (-.25,0)$) -- ($(lrr) + (-.25,0)$) -- ($(lrrr) + (-.25,0)$);
	\end{tikzpicture}
	}
	}
	\caption{Traversing the syntax tree in parallel (left) or in series (right).}
	\label{fig:traversingTree}
\end{figure}

We call \defn{parallel} (resp.~\defn{series}) \defn{destination vector} of a syntax tree~$\tree$ the vector~$(\ell_1, \dots, \ell_k)$ whose $j$th coordinate records the destination~$\ell_j$ of the $j$th car after traversing~$\tree$ in parallel (resp.~series). Two syntax trees are \defn{parallel} (resp.~\defn{series}) \defn{signaletic equivalent} if they have the same parallel (resp.~series) destination vector. This relation is compatible with grafting.

\begin{proposition}
\label{prop:signaleticEquivalence}
The parallel (resp.~series) $k$-signaletic equivalence is compatible with grafting of syntax trees.
Namely, if we denote by~$\smash{\ind{p}^\parallel_j}, \smash{\ind{q}^\parallel_j}$ and~$\smash{\ind{r}^\parallel_j}$ (resp.~$\smash{\ind{p}^\series_j}, \smash{\ind{q}^\series_j}$ and~$\smash{\ind{r}^\series_j}$) the parallel (resp.~series) destination of the $j$th car in the syntax trees~$\tree[t]$, $\tree[s]$ and~$\tree \circ_i \tree[s]$, then
\[
\ind{r}^\parallel_j = 
\begin{cases}
\ind{p}^\parallel_j & \text{if } \ind{p}^\parallel_j < i, \\
\ind{p}^\parallel_j + \ind{q}^\parallel_j - 1 & \text{if } \ind{p}^\parallel_j = i, \\
\ind{p}^\parallel_j + q - 1 & \text{if } \ind{p}^\parallel_j > i,
\end{cases}
\qquad\text{and}\qquad
\ind{r}^\series_j = 
\begin{cases}
\ind{p}^\series_j & \text{if } \ind{p}^\series_j < i, \\
\ind{p}^\series_j + \ind{q}^\series_{|\set{\ell \le j}{\smash{\ind{p}^\series_\ell} = i}|} - 1 & \text{if } \ind{p}^\series_j = i, \\
\ind{p}^\series_j + q - 1 & \text{if } \ind{p}^\series_j > i.
\end{cases}
\]
\end{proposition}

\begin{definition}
\label{def:signaleticOperads}
The \defn{parallel} (resp.~\defn{series}) \defn{$k$-signaletic operad}~$\signaleticParallel$ (resp.~$\signaleticSeries$) is the quotient of the free operad on~$\Operations_k$ by the parallel (resp.~series) $k$-signaletic equivalence.
\end{definition}

By definition, the basis of the parallel (resp.~series) $k$-signaletic operad is given by syntax trees on~$\Operations_k$ modulo the parallel (resp.~series) $k$-signaletic equivalence, and the composition is given by grafting. Alternatively, we can represent this basis using destination vectors, and the composition is described by the rules of \cref{prop:signaleticEquivalence}. Since there are $p^k$ possible destination vectors in arity~$p$, we obtain the following expression for the Hilbert series of the $k$-signaletic operads in terms of Eulerian polynomials.

\begin{proposition}
\label{prop:HilbertSignaletic}
The Hilbert series of the $k$-signaletic operads~$\signaleticParallel$ and~$\signaleticSeries$ are given by
\[
\Hilbert_{\signaleticParallel}(t) = \Hilbert_{\signaleticSeries}(t) = \sum_{p \ge 1} p^k t^p = \frac{\EulPol{k}(t)}{(1-t)^{k+1}},
\]
where~$\EulPol{k}(t) \eqdef {\displaystyle \sum}_{p \ge 0} \EulNum{k}{p} t^p$ and~$\EulNum{k}{p}$ is the number of permutations of~$\fS_k$ with $p$ descents.
\end{proposition}

We now consider the relations in the $k$-signaletic operads, \ie the pairs of syntax trees with the same destination vectors. The next two definitions are justified in \cref{thm:signaleticOperadsQuadratic}.

\begin{definition}
\label{def:signaleticRelations}
The \defn{parallel} (resp.~\defn{series}) \defn{$k$-signaletic relations} are the quadratic relations of~$\signaleticParallel$ (resp.~$\signaleticSeries$). See \cref{exm:signaleticRelations}. %, that is all the relations of the form $\tree_1 = \tree_2$ where $\tree_1$ and $\tree_2$ are two syntax trees with two nodes sharing the same parallel (resp.~series) destination vector.
\end{definition}

\begin{definition}
A \defn{right parallel} (resp.~\defn{series}) \defn{$k$-signaletic comb} is a syntax tree~$\tree[c]$ on~$\Operations_k$~where:
\begin{compactitem}
\item the left child of each node of~$\tree[c]$ is empty, and
\item each signal not visited by a car in the parallel (resp.~series) traversal of~$\tree[c]$ points left.
\end{compactitem}
\end{definition}

We now consider the rewriting system defined by the rewriting rules~$(\tree[s],\tree[c])$ where~$\tree[s]$ and~$\tree[c]$ are two distinct quadratic trees with the same parallel (resp.~series) destination vector and~$\tree[c]$ is a right parallel (resp.~series) $k$-signaletic comb.
We can prove that all applications of this rewriting rule are increasing in a variant of the Tamari lattice on binary trees labeled by~$\Operations_k$, from which we deduce that this rewriting system is convergent and that its normal forms are precisely the right parallel (resp.~series) $k$-signaletic combs.
This yields the main result of this section.

\begin{theorem}
\label{thm:signaleticOperadsQuadratic}
The $k$-signaletic operads~$\signaleticParallel$ and~$\signaleticSeries$ are quadratic and Koszul. In particular, the parallel (resp.~series) $k$-signaletic relations give a presentation of~$\signaleticParallel$ (resp.~$\signaleticSeries$) and the right parallel (resp.~series) $k$-signaletic combs form a Poincar\'e\,--\,Birkhoff\,--\,Witt basis of~$\signaleticParallel$~(resp.~$\signaleticSeries$).
\end{theorem}

\begin{example}
\label{exm:signaleticRelations}
The $1$-signaletic relations are the diassociative relations given in \cref{sec:intro}.
The series $2$-signaletic relations are the next~$23$ relations, labeled by destination vectors:
\allowdisplaybreaks
\begin{gather*}
\compoR{l,l}{l,l} = \compoR{l,l}{l,r} = \compoR{l,l}{r,l} = \compoR{l,l}{r,r} = \compoL{l,l}{l,l} \;\; (11), \\
\compoR{l,r}{l,l} = \compoR{l,r}{l,r} = \compoL{l,r}{l,l} \;\; (12), \qquad
\compoR{l,r}{r,l} = \compoR{l,r}{r,r} = \compoL{l,l}{l,r} = \compoL{l,r}{l,r} \;\; (13), \\
\compoR{r,l}{l,l} = \compoR{r,l}{l,r} = \compoL{r,l}{l,l} \;\; (21), \quad
\compoR{r,r}{l,l} = \compoL{r,r}{l,l} \;\; (22), \quad
\compoR{r,r}{l,r} = \compoL{r,l}{l,r} = \compoL{r,r}{l,r} \;\; (23), \\
\compoR{r,l}{r,l} = \compoR{r,l}{r,r} = \compoL{l,l}{r,l} = \compoL{l,r}{r,l} \;\; (31), \qquad
\compoR{r,r}{r,l} = \compoL{r,l}{r,l} = \compoL{r,r}{r,l} \;\; (32), \\
\compoR{r,r}{r,r} = \compoL{l,l}{r,r} = \compoL{l,r}{r,r} = \compoL{r,l}{r,r} = \compoL{r,r}{r,r} \;\; (33).
\end{gather*}
\end{example}

%%

\subsection{Citelangis operads}
\label{subsec:citelangisOperads}

\begin{definition}
\label{def:citelangisOperads}
The \defn{parallel} (resp.~\defn{series}) \defn{$k$-citelangis operad}~$\citelangisParallel$ (resp.~$\citelangisSeries$) is the Koszul dual of the parallel (resp.~series) $k$-signaletic operad~$\signaleticParallel$ (resp.~$\signaleticSeries$).
\end{definition}

\begin{example}
\label{exm:citelangisRelations}
The $1$-citelangis relations are the dendriform relations given in \cref{sec:intro}.
The parallel $2$-citelangis relations are defining the quadri-algebras of~\cite{AguiarLoday, Foissy}.
The series $k$-citelangis relations are defining the $k$-twistiform algebras of~\cite{Pilaud-brickAlgebra}.
For instance, the series $2$-citelangis relations are the next~$9$ relations, labeled by destination vectors (${\op{m}} \eqdef {\op{l}} + {\op{r}}$):
\begin{gather*}
\compoR{l,l}{m,m} = \compoL{l,l}{l,l} \;\; (11), \qquad
\compoR{l,r}{l,m} = \compoL{l,r}{l,l} \;\; (12), \qquad
\compoR{l,r}{r,m} = \compoL{l,m}{l,r} \;\; (13), \\
\compoR{r,l}{l,m} = \compoL{r,l}{l,l} \;\; (21), \qquad
\compoR{r,r}{l,l} = \compoL{r,r}{l,l} \;\; (22), \qquad
\compoR{r,r}{l,r} = \compoL{r,m}{l,r} \;\; (23), \\
\compoR{r,l}{r,m} = \compoL{l,m}{r,l} \;\; (31), \qquad
\compoR{r,r}{r,l} = \compoL{r,m}{r,l} \;\; (32), \qquad
\compoR{r,r}{r,r} = \compoL{m,m}{r,r} \;\; (33).
\end{gather*}
\end{example}

By \cref{thm:signaleticOperadsQuadratic}, the $k$-citelangis operads~$\citelangisParallel$ and~$\citelangisSeries$ are both quadratic and Koszul. 
Moreover, \cref{thm:HilbertKoszulLagrange} has the following enumerative consequence.

\begin{corollary}
\label{coro:HilbertSeriesCitelangis}
The Hilbert series of the $k$-citelangis operads~$\citelangisParallel$ and~$\citelangisSeries$ coincide and satisfy:
\[
\EulPol{k}(-\Hilbert_{\citelangis}(-t)) = t(1+\Hilbert_{\citelangis}(-t))^{k+1}.
\]
The dimension~$d_k(p) \eqdef \dim(\citelangisParallel(p)) = \dim(\citelangisSeries(p))$ is thus given by the summation formula:
\[
d_k(p) = \frac{1}{p} \sum_{\substack{i, j_1, \dots, j_{k-1} \ge 0 \\ i + j' = p-1}} (-1)^{j+j'} \binom{(k+1)p}{i} \binom{p+j-1}{j} \binom{j}{j_1, \dots, j_{k-1}} \EulNum{k}{1}^{j_1} \cdots \EulNum{k}{k-1}^{j_{k-1}},
\]
where~$j = j_1 + \dots + j_{k-1}$ and~$j' = j_1 + \dots + (k-1) j_{k-1}$.
Alternatively, the dimension~$d_k(p)$ can be computed recursively from~$d_k(1) = 1$ by the formula:
\[
d_k(p) = \!\!\!\! \sum_{\substack{q_1, \dots, \, q_{k+1} \ge 0 \\ q_1 + \dots + q_{k+1} = p-1}} \!\!\!\! d_k(q_1) \cdots d_k(q_{k+1}) + \sum_{j=1}^{k-1} (-1)^{j+1} \, \EulNum{k}{j} \sum_{\substack{q_1, \dots, \, q_{j+1} \ge 1 \\ q_1 + \dots + q_{j+1} = p}} \!\!\!\! d_k(q_1) \cdots d_k(q_{j+1}).
\]
\end{corollary}

\begin{example}
The values of~$d_k(p)$ for~$k \in [5]$ and~$p \in [8]$ are given by:
	\[
	\begin{array}{l|r@{\;\;}r@{\;\;}r@{\;\;}r@{\;\;}r@{\;\;}r@{\;\;}r@{\;\;}r|c}
	\raisebox{-.1cm}{$k$} \backslash \, \raisebox{.1cm}{$p$}
	  & 1 &  2 &    3 &      4 &       5 &         6 &          7  &             8 & \text{OEIS ref} \\[.1cm]
	\hline
	1 & 1 &  2 &    5 &     14 &      42 &       132 &         429 &          1430 & \href{https://oeis.org/A000108}{A000108} \\
	2 & 1 &  4 &   23 &    156 &    1162 &      9192 &       75819 &        644908 & \href{https://oeis.org/A007297}{A007297} \\
	3 & 1 &  8 &  101 &   1544 &   26190 &    474144 &     8975229 &     175492664 & \href{https://oeis.org/A291536}{A291536} \\
	4 & 1 & 16 &  431 &  14256 &  525682 &  20731488 &   855780699 &   36512549680 & \text{---} \\
	5 & 1 & 32 & 1805 & 125984 & 9825222 & 820259712 & 71710602189 & 6481491238880 & \text{---}
	\end{array}
	\]
\end{example}

\begin{example}
For small~$k$, the equations of \cref{coro:HilbertSeriesCitelangis} become:
\begin{itemize}
\item $d_1(p) = \frac{1}{p} \binom{2p}{p-1} = \frac{1}{p+1} \binom{2p}{p} = C_p$ and~$\displaystyle d_1(p) = \sum_{\substack{a,b \ge 0 \\ a+b = p-1}} d_1(a) \, d_1(b)$,
\vspace{-.3cm}
\item $d_2(p) = \frac{1}{p} {\displaystyle \sum_i} \binom{3p}{i} \binom{2p-i-2}{p-i-1}$ and $\displaystyle d_2(p) = \!\!\!\! \sum_{\substack{a,b,c \ge 0 \\ a+b+c = p-1}} \!\!\!\! d_2(a) \, d_2(b) \, d_2(c) + \sum_{\substack{a,b \ge 1 \\ a+b = p}} d_2(a) \,d_2(b)$.
Thus, $d_2(p)$ counts the number of rooted non-crossing connected arc diagrams on~$p+1$ points.
To see the right summation formula, decompose the diagrams according on whether the leftmost arc incident to the root is an isthme (then the deletion of this arc decomposes the diagram into $3$ subdiagrams with at least one node) or not (then the deletion of this arc decomposes the diagram into $2$ subdiagrams with at least two nodes), as illustrated below.
\end{itemize}
\end{example}

%\begin{figure}[h]
	\centerline{
	\resizebox{\textwidth}{!}{
	$\raisebox{-.45\height}{\includegraphics[scale=.27]{decompositionConnectedCrossingFreeArcDiagram1}} = \raisebox{-.45\height}{\includegraphics[scale=.27]{decompositionConnectedCrossingFreeArcDiagram2}} + \raisebox{-.45\height}{\includegraphics[scale=.27]{decompositionConnectedCrossingFreeArcDiagram3}} + \raisebox{-.45\height}{\includegraphics[scale=.27]{decompositionConnectedCrossingFreeArcDiagram4}}$
	\qquad
	$\raisebox{-.45\height}{\includegraphics[scale=.27]{decompositionConnectedCrossingFreeArcDiagram5}} = \raisebox{-.45\height}{\includegraphics[scale=.27]{decompositionConnectedCrossingFreeArcDiagram6}} + \raisebox{-.45\height}{\includegraphics[scale=.27]{decompositionConnectedCrossingFreeArcDiagram7}}$
	}
	}

\section{Actions}

The shuffle algebra can be endowed with a dendriform structure~\cite{Loday-dialgebras} defined for the words~$xX$ and~$yY$ by~$xX \op{l} yY = x \big( X \shuffle yY \big)$ and~$xX \op{r} yY = y \big( xX \shuffle Y \big)$.
Replacing the shuffle by the shifted shuffle, one endows similarly the algebra~$\FQSym$ of permutations with a dendriform structure.
The resulting dendriform algebra is known to be free~\cite{Foissy, Vong}, and the dendriform subalgebra of~$\FQSym$ generated by the permutation~$1$ is known to be the free dendriform algebra on one generator~\cite{LodayRonco}.

Splitting the shuffle product according to the provenance of the first and last letters defines similarly a quadri-algebra (\aka parallel $2$-citelangis algebra) structure  on~$\FQSym$, see~\cite{AguiarLoday, Foissy}.
Again, this action is known to be free~\cite{Foissy, Vong}.
Unfortunately, it cannot be extended to define parallel $k$-citelangis algebras for~$k > 2$ since a word has only two ends!
But it extends to series $k$-citelangis algebras using the provenance of the first $k$ letters.

\subsection{Series $k$-citelangis action on $k$-permutations}


\begin{definition}
\label{def:messyCitelangisSeriesActionWords}
For~$\operation \in \{\op{l}, \op{r}\}^*$ and two words~$X$ and~$Y$ with~${|\operation| \le \min(|X|, |Y|)}$, define
\[
X \; \operation \; Y =
\begin{cases}
X \shuffle Y & \text{if } \operation = \varepsilon, \\
x (\underline{X} \; \underline{\operation} \; Y) & \text{if } \operation = \; \op{l} \!\underline{\operation} \text{ and } X = x\underline{X}, \\
y (X \; \underline{\operation} \; \underline{Y}) & \text{if } \operation = \; \op{r} \!\underline{\operation} \text{ and } Y = y\underline{Y}.
\end{cases}
\]
In other words, $X \; \operation \; Y$ is the shuffle of~$X$ and~$Y$, except that the~$i$-th letter of~$X \, \operation \, Y$ is forced to belong to~$X$ (resp.~to~$Y$) if the $i$-th letter of~$\operation$ is~$\op{l}$ (resp.~is~$\op{r}$). 
\end{definition}

It was shown in~\cite{Pilaud-brickAlgebra} that this defines a series $k$-citelangis algebra on words of size at least~$k$.
In order to transpose this action onto permutations, we observe that we need permutations whose length is at least~$k$ and whose blocks of $k$ consecutive values always remain sorted.
This motivates the following definition.

\begin{definition}
A \defn{$k$-permutation} of degree~$n$ is a permutation of the set~$\{\!\!\{ 1^{\{k\}}, \dots, n^{\{k\}}\}\!\!\}$ where each value has $k$ indistinguishable copies.
The \defn{shifted shuffle}~$\mu \shiftedShuffle \nu$ of two $k$-permu\-tations~$\mu$ and~$\nu$ of degrees~$m$ and~$n$ is the linear combination of all $k$-permutations of degree~$m+n$ whose first $m$ (resp.~last~$n$) values are ordered as in~$\mu$ (resp.~as in~$\nu$).
\end{definition}

Let~$\FQSym_k$ be the vector space generated by all $k$-permutations.
The shifted shuffle defines a graded algebra on~$\FQSym_k$ generalizing C.~Malvenuto and C.~Reutenauer's algebra on permutations~\cite{MalvenutoReutenauer}.
We now split the shuffle into $2^k$ operations as in~\cite{Pilaud-brickAlgebra}.

\begin{definition}
\label{def:messyCitelangisSeriesActionPermutations}
For~${\operation \in \Operations_k \eqdef \{\op{l}, \op{r}\}^k}$ and two $k$-permutations~$\mu$ and~$\nu$ of degree~$m$ and~$n$, consider the sum $\mu \, \operation \, \nu$ of all $k$-permutations~$\pi \in \mu \shiftedShuffle \nu$ such that for all~${i \in [k]}$, we have~$\pi_i \le m$ if~$\operation_i = {\op{l}}$ while~$\pi_i > m$ if~$\operation_i = {\op{r}}$.
\end{definition}

\begin{proposition}[\cite{Pilaud-brickAlgebra}]
\label{prop:messyCitelangisSeriesMultipermutations}
The algebra~$(\FQSym_k, \shiftedShuffle)$, endowed with the operators of \cref{def:messyCitelangisSeriesActionPermutations}, defines a series $k$-citelangis algebra.
The shifted shuffle product~$\shiftedShuffle$ of~$\FQSym_k$ is given~by~$\op{m}\!\!^k$.
\end{proposition}

\subsection{Fully $k$-cuttable $k$-permutations}

This section makes a combinatorial detour to introduce $k$-cuts in $k$-permutations, which are both needed to study the freeness of~$\FQSym_k$ and interesting in their own right.

\begin{definition}
\label{def:krootedCutMultipermutation}
A \defn{$k$-cut} of a $k$-permutation~$\sigma$ of degree~$n$ is a value~$\gamma \in [n-1]$ such that~$\sigma = \mu \nu \omega$ where~$\mu$, $\nu$ and~$\omega$ are words with~$|\mu| = k$ and~$\nu_i \le \gamma < \omega_j$ for all~${i \in [|\nu|]}$ and~$j \in [|\omega|]$.
A $k$-permutation is \defn{$k$-cuttable} if it admits a $k$-cut, %, and \defn{$k$-uncuttable} otherwise.
and \defn{fully $k$-cuttable} if its restriction to any interval (equivalently, any subset) of~$[n]$ of size at least $2$ is $k$-cuttable.
\end{definition}

For instance, the $2$-permutation~$31421324$ (resp.~$31213244$, resp.~$363121244556$) is \mbox{$2$-uncuttable} (resp.~$2$-cuttable but not fully $2$-cuttable, resp.~fully $2$-cuttable).
For~$k \le 2$, fully $k$-cuttable $k$-permutations are characterized by pattern avoiding conditions.

\begin{proposition}
\begin{compactenum}
\item A\,$1$-permutation is fully\,$1$-cuttable if\,and\,only\,if it avoids the pattern\,$231$.
\item A $2$-permutation is fully $2$-cuttable if and only if it avoids ${b \cdot b' \cdot c \cdot a}$ with~$a \le b , b' \le c$.
\end{compactenum}
\end{proposition}

More generally, the following statement provides a necessary and a sufficient pattern avoiding conditions, although these two conditions do not match for~$k > 2$.
 

\begin{proposition}
Let~$k \ge 1$ and~$\sigma$ be a $k$-permutation.
\begin{compactitem}
\item \label{item:fullykrootedCuttablePatternsNecessary}
If~$\sigma$ if fully $k$-cuttable, it contains no pattern~$b_1 \cdots b_k \cdot c \cdot a$ with~$a \le b_i \le c$~for~$i \in [k]$,
\item \label{item:fullykrootedCuttablePatternsSufficient}
If~$\sigma$ is not fully $k$-cuttable, it contains a pattern~$a_1 \cdots a_k \cdot b \cdot a$ with~$a < b$ and~$a_i \le b$ for~$i \in [k]$, and a pattern~$b_1 \cdots b_k \cdot b \cdot a$ with~$a < b$ and~$a \le b_i$ for~$i \in [k]$.
\end{compactitem}
\end{proposition}

In fact, this family fulfills the following property, classical in pattern avoidance.

\begin{theorem}
Fully $k$-cuttable $k$-permutations form a $k$-permutation class (stable by restriction).
\end{theorem}

\subsection{Freeness}

To show the freeness of~$\FQSym_k$, we study the evaluation of syntax trees on permutations.

\begin{definition}
\label{def:seriesPermutationEvaluation}
Let~$\EvalPermSeries(\tree ; \sigma_1, \dots, \sigma_p)$ be the evaluation of a syntax tree~$\tree \in \Syntax[\Operations_k]$ of arity~$p$ on $p$ $k$-permutations~${\sigma_1, \dots, \sigma_p}$ using the operations of \cref{def:messyCitelangisSeriesActionPermutations}. 
The \defn{series permutation evaluation} of~$\tree$ is then~$\EvalPermSeries(\tree) \eqdef \EvalPermSeries(\tree ; 1^{\{k\}}, \dots, 1^{\{k\}})$.
\end{definition}

One difficulty to understand the $k$-citelangis structure of~$\FQSym_k$ is that~$\EvalPermSeries(\tree)$ is a big linear combination of $k$-permutations.
We will understand this full combination in \cref{subsec:kposets} using multiposets.
At the moment, we overpass this difficulty as follows.

\begin{definition}
Let~$\LexMin(F)$ be the lexicographic minimal $k$-permutation~with non-zero coefficient in~$F$.
The \defn{lexmin series permutation evaluation} of~$\tree$ is~$\LexMin(\EvalPermSeries(\tree))$.
\end{definition}

\begin{proposition}
\label{prop:characterizationTidySeriesPermutationEvaluations}
The lexmin series permutation evaluations of the syntax trees of~$\Syntax[\Operations_k]$ are precisely the fully $k$-cuttable $k$-permutations.
\end{proposition}

These lexmin series permutation evaluations actually endow $\FQSym_k$ with a structure of algebra over yet another operad called \defn{tidy series $k$-citelangis operad} in~\cite{HivertPilaud} that  generalizes the duplicial operad.
While unreported in this extended abstract for space reasons, this operad can be defined with the same ideas as in \cref{sec:signaleticOperads}.
Namely, it is the Koszul dual of the quotient of the free operad on~$\Operations_k$ by the relations that identify two tidy syntax trees with the same destination vectors and identify all messy syntax trees to~$0$.
Here, a syntax tree is called \defn{tidy} if all signals not encountered by a car during the series traversal points to the left, and \defn{messy} otherwise.
The combinatorial properties of $k$-cuts in $k$-permutations enable us to prove the following statement.

\begin{theorem}
Any $k$-permutation~$\tau$ can be expressed as~$\tau = \LexMin(\EvalPermSeries(\tree ; \sigma_1, \dots, \sigma_p))$ for some syntax tree~$\tree \in \Syntax[\Operations_k]$ of arity~$p$ and some $k$-uncuttable permutations~$\sigma_1, \dots, \sigma_p$.
Moreover, this expression is unique up to the tidy series $k$-citelangis relations.
In other words, the tidy series $k$-citelangis algebra~$\FQSym_k$ is free on $k$-uncuttable $k$-permutations.
\end{theorem}

Finally, a triangularity argument pulls back freeness to the series $k$-citelangis operad.

\begin{theorem}
\label{thm:freeMessyCitelangisSeries}
The series $k$-citelangis algebra~$\FQSym_k$ is free on $k$-uncuttable $k$-permutations.
\end{theorem}

\subsection{Series $k$-citelangis operations on $k$-posets}
\label{subsec:kposets}

\parpic(5.8cm,2.5cm)(-10pt, 28pt)[r][b]{
	$\begin{tikzpicture}[baseline={([yshift=-.8ex]current bounding box.center)}, inner sep=2pt, level/.style={sibling distance=.7cm, level distance = .7cm}, blue]
		\node {$2$} [grow' = up]
			child {node {$1$}
				child {node {$1$}}
				child {node {$2$}}
			}
		;
	\end{tikzpicture}
	\!\!\! \op{r,l} \!\!\!
	\begin{tikzpicture}[baseline={([yshift=-.8ex]current bounding box.center)}, inner sep=2pt, level/.style={sibling distance=.7cm, level distance = .7cm}, red]
		\node {$3$} [grow' = up]
			child {node {$3$}
				child {node {$1$}
					child {node {$2$}
						child {node {$1$}}
						child {node {$2$}}
					}
				}
				child {node {$4$}
					child {node {$4$}}
				}
			}
		;
	\end{tikzpicture}
	= \!\!
	\begin{tikzpicture}[baseline={([yshift=-.8ex]current bounding box.center)}, inner sep=2pt, level 2/.style={sibling distance=1.5cm}, level/.style={sibling distance=.7cm, level distance = .7cm}]
		\node {\red $5$} [grow' = up]
			child [redNode] {node {\blue $2$}
				child [blueNode] {node {$1$}
					child {node {$1$}}
					child {node {$2$}}
				}
				child [redNode] {node {$5$}
					child {node {$3$}
						child {node {$4$}
							child {node {$3$}}
							child {node {$4$}}
						}
					}
					child {node {$6$}
						child {node {$6$}}
					}
				}
			}
		;
	\end{tikzpicture}$
}
To conclude, we provide a description of the series permutation evaluations of \cref{def:seriesPermutationEvaluation} in terms of operations on the following family of posets.

\begin{definition}
A \defn{$k$-poset} of degree~$n$ is a partial order~$\le$ on~$\{\!\!\{ 1^{\{k\}}, \dots, n^{\{k\}}\}\!\!\}$, such that the $k$ copies of each value form a chain in~$\le$.
A $k$-poset~$\le$ is \defn{$k$-rooted} if it has a \defn{$k$-root}, \ie a chain formed by $k$ elements which are smaller than all others.
For~$j \le k$, we denote by~$\Root_j(\le)$ the first $j$ elements of~$\le$ and by $\le_{\star j}$ the subposet of~$\le$ induced by~$\{\!\!\{ 1^{\{k\}}, \dots, n^{\{k\}}\}\!\!\} \ssm \Root_j(\le)$.
\end{definition}

Examples of $2$-posets are represented above. We now define $2^k$ operations on $k$-posets.

\begin{definition}
\label{def:operationsPosets}
For~${\operation \in \Operations_k \eqdef \{\op{l}, \op{r}\}^k}$ with~$\ell$ signals~$\op{l}$ and~$r$ signals~$\op{r}$, and two $k$-posets~$\le^\circ$ and $\le^\bullet$ of degrees~$m$ and~$n$, consider the $k$-poset of degree~$m+n$ defined by
\(
{{\le^\circ} \; \operation \; {\le^\bullet} = \big( \Root_\ell(\le^\circ) \; \operation \; \Root_r(\le^\bullet) \big) + \big( {\le^\circ_{\star\ell}} \sqcup {\overline{\le^\bullet}_{\star r}} \big)}
\),
where~$+$ and~$\sqcup$ denote the ordered sum and disjoint union of posets, and~$\overline{\le^\bullet}$ denotes the poset~$\le^\bullet$ where all values are shifted by~$m$.
Its first $m$ values are ordered as in~$\le^\circ$, its last $n$ values are ordered as in~$\le^\bullet$, and its $j$th element is weakly smaller then~$m$ if~$\operation_j = {\op{l}}$ and strictly larger than~$m$ if~$\operation_j = {\op{r}}$.
See the example above.
\end{definition}

\begin{definition}
\label{def:seriesPosetEvaluation}
Let~$\EvalPosetSeries(\tree ; \le_1, \dots, \le_p)$ be the evaluation of a syntax tree~$\tree \in \Syntax[\Operations_k]$ of arity~$p$ on $p$ $k$-posets~${\le_1, \dots, \le_p}$ using the operations of \cref{def:operationsPosets}. 
The \defn{series poset} \defn{evaluation} of~$\tree$ is~$\EvalPosetSeries(\tree) \eqdef \EvalPosetSeries(\tree ; I^{\{k\}}, \dots, I^{\{k\}})$, where~$I^{\{k\}}$ is the chain on $k$ copies~of~$1$.
\end{definition}

These series poset evaluations define yet another relevant operad called \defn{poset operad} in~\cite{HivertPilaud}. Here, they are just a tool to understand the series permutation evaluations.

\begin{lemma}
\label{lem:LinExtEvalPosetSeries}
For any syntax tree~$\tree \in \Syntax[\Operations_k]$, we have~$\EvalPermSeries(\tree) = \LinExt \big( \EvalPosetSeries(\tree) \big)$, where~$\LinExt(\le)$ denotes the sum of all linear extensions of a multiposet~$\le$.
\end{lemma}

%\enlargethispage{.2cm}
To conclude, we describe the series poset evaluations (compare to \cref{prop:characterizationTidySeriesPermutationEvaluations}).

\begin{definition}
\label{def:krootedCutPoset}
Let~$\le$ be a $k$-rooted $k$-poset of degree~$n$ and~$\gamma \in [n-1]$.
We say that $\gamma$ is a \defn{$k$-cut} of~$\le$ if we can write~$\{\!\!\{ 1^{\{k\}}, \dots, n^{\{k\}}\}\!\!\} = \Root_k(\le_M) \sqcup L \sqcup R$ such that, for all~$\ell \in L$ and~$r \in R$, we have~$\ell \le \gamma < r$ and~$\ell$ and~$r$ are incomparable for~$\le_M$.
We say that the $k$-rooted $k$-poset~$\le_M$ is \defn{$k$-cuttable} if it admits a $k$-rooted cut, and \defn{fully $k$-cuttable} if its restriction to any interval (equivalently, any subset) of~$[n]$ of size at least $2$ is $k$-cuttable.
\end{definition}

\begin{proposition}
\label{prop:characterizationSeriesPosetEvaluations}
The series poset evaluations of the syntax trees of~$\Syntax[\Operations_k]$ are precisely the fully $k$-cuttable $k$-posets.
\end{proposition}

%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way
\printbibliography

\end{document}
