%% 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]{FPSAC2018}
\articlenumber{58}
%% 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}
\usepackage[utf8]{inputenc}

\usepackage{tikz}
\usetikzlibrary{calc}

\usepackage{chngcntr}

\newtheorem{definition}{Definition}[section]% Counter `Definition` depends on `subsection` …

%\renewcommand*{\thedefinition}{% Output of `Definition` counter:
%  \ifnum\value{subsection}<1 % if `subsection` counter is less than 1 (mostly `\subsection` not yet used in this `\section`)
%    \thesection% show \thesection, e.g., 1
%  \else% otherwise
%    \thesection% show \thesubsection, e.g., 1.1
%  \fi
%  .\arabic{definition}% followed by "." and Arabic number of Definition
%}

\newtheorem{theorem}[definition]{Theorem}
\newtheorem{exemple}[definition]{Example}
\newtheorem{prop}[definition]{Proposition}
\newtheorem{remarque}[definition]{Remark}
\newtheorem*{prob*}{Problem}
\newtheorem*{application*}{Application}



\newenvironment{Sproof}{%
  \renewcommand{\proofname}{Sketch of proof}\proof}{\endproof}

%% define your title in the usual way
\title{Enumerative Combinatorics of Prographs}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Christophe Cordero\thanks{\href{mailto:Christophe.Cordero@u-pem.fr}{Christophe.Cordero@u-pem.fr}}\addressmark{1}}

%% then use \addressmark to match authors to institutions here
%\address{\addressmark{1}Institut Gaspard Monge, Université Paris-Est Marne-la-Vallée, Champs-Sur-Marne, France}
\address{\addressmark{1}Universit\'e Paris-Est,
    LIGM (UMR $8049$), CNRS, ENPC, ESIEE Paris, UPEM, F-$77454$,
    Marne-la-Vall\'ee, France}

%% put the date of submission here
\received{November 14}

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

%% 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)
\resume{Nous exhibons une bijection entre les prographes r\'eduits et des
familles de chemins tridimensionnels color\'es. Par une \'etude classique
des chemins, nous obtenons des relations de r\'ecurrence et des formules
closes pour les prographes r\'eduits.}

\abstract{We exhibit a bijection between reduced prographs and families of three-dimensional colored lattice paths. By a classical study of the lattice paths, we obtain recurrence relations and closed formulas for reduced prographs.}

%% put your French abstract here, or comment this out if you don't have one

%% put your keywords here, or comment this out if you don't have them yet
\keywords{Enumerative combinatorics, lattice path, prograph}

%% 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

\usepackage[backend=bibtex]{biblatex}
\addbibresource{58-Cordero.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands


\newcommand{\bloc}[4][]{
\draw[fill=white] (#2) rectangle (#3);
\node[#1] at ($.5*(#2)+.5*(#3)$) {#4};
}


\begin{document}

\setlength{\abovedisplayskip}{5pt}
\setlength{\belowdisplayskip}{5pt}

\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}

Prographs are planar assemblies of abstract operators with multiple inputs and outputs. They can model electronic circuits, algebraic computations, or rewriting systems~\cite{La09}. We also proved thanks to computer experiments and the OEIS~\cite{OEIS} that prographs made of only one sort of operator with two inputs and three outputs can model the biological notion of tandem duplication trees~\cite{Ga05}.

We wish to count, according to their number of operators, all prographs having a fixed number of inputs and outputs and using only operators belonging to a given set.
The main difficulty in enumerating prographs arises from their definition. Indeed, prographs are defined as objects obtained from base operators and two building operations~\cite{Bu16, Ma65}. However, there exist relations between these operations, implying that the natural grammar for generating the prographs is ambiguous.

In order to circumvent this ambiguity, we present a canonical expression of any reduced prograph in the grammar, where reduced prographs are prographs made of operators with at least one input and one output. These canonical expressions are inspired from a reduced prograph traversal introduced by Borie in~\cite{Bo17}. By a direct encoding of canonical expressions into paths, we obtain a bijection between reduced prographs and families of three-dimensional colored paths. The classical combinatorial study of these paths yields recurrence relations and closed formulas for reduced prographs.
 
In Section 1, we recall basic definitions about prographs and set our combinatorial problem. Section 2 is devoted to the bijection between reduced prographs and families of three-dimensional colored paths. Finally, in Section 3, we compute recurrence relations and closed formulas for the paths and thus for reduced prographs.


\section{Prographs}

A generator is an operator with a fixed number of inputs and outputs. We represent a generator $x$ with $e$ inputs and $s$ outputs by
\begin{equation*}
\begin{tikzpicture}[scale = 0.8, baseline = {([yshift=-.8ex]current bounding box.center)}]
  \bloc{0,0}{1,0.5}{$x$}
  \draw(0.1,0)--(0.1,-0.25);
  \draw(0.1,0.5)--(0.1,0.75);
  
  \draw(0.9,0)--(0.9,-0.25);
  \draw(0.9,0.5)--(0.9,0.75);
  
  \node at (0.53,0.65) {$\cdots$};
  \node at (0.53,-0.15) {$\cdots$};
  
  \node at (0.5,1.1) {$s$};
  \draw (0,0.75) arc(180:90:.1) -- (0.4, 0.85) arc(-90:0:.1);
  \draw (1,0.75) arc(0:90:.1) -- (0.6, 0.85) arc(270:180:.1);
  
  \node at (0.5,-0.61) {$e$};
  \draw (0,-0.25) arc(-180:-90:.1) -- (0.4, -0.35) arc(90:0:.1);
  \draw (1,-0.25) arc(0:-90:.1) -- (0.6, -0.35) arc(-270:-180:.1);
 
\end{tikzpicture} \, .
\end{equation*}

\begin{remarque}
In the cases we consider, generators always have at least one input and one output.
\end{remarque}

Let us see how we build prographs from a set of generators. First of all, the wire $|$ is a prograph with one input and one output and a generator with $e$ inputs and $s$ outputs is a prograph with $e$ inputs and $s$ outputs. Then, given two prographs
\begin{equation*}
\begin{tikzpicture}[scale = 1, baseline = {([yshift=-.8ex]current bounding box.center)}]
  \bloc{0,0}{1,0.5}{$P$}
  \draw(0.1,0)--(0.1,-0.25);
  \draw(0.1,0.5)--(0.1,0.75);
  
  \draw(0.9,0)--(0.9,-0.25);
  \draw(0.9,0.5)--(0.9,0.75);
  
  \node at (0.53,0.65) {$\cdots$};
  \node at (0.53,-0.15) {$\cdots$};
  
  \node at (0.5,1.1) {$s$};
  \draw (0,0.75) arc(180:90:.1) -- (0.4, 0.85) arc(-90:0:.1);
  \draw (1,0.75) arc(0:90:.1) -- (0.6, 0.85) arc(270:180:.1);
  
  \node at (0.5,-0.61) {$e$};
  \draw (0,-0.25) arc(-180:-90:.1) -- (0.4, -0.35) arc(90:0:.1);
  \draw (1,-0.25) arc(0:-90:.1) -- (0.6, -0.35) arc(-270:-180:.1);
 
\end{tikzpicture} \hspace{10 pt} \text{and} \hspace{10 pt}
\begin{tikzpicture}[scale = 1, baseline = {([yshift=-.8ex]current bounding box.center)}]
  \bloc{0,0}{1,0.5}{$P'$}
  \draw(0.1,0)--(0.1,-0.25);
  \draw(0.1,0.5)--(0.1,0.75);
  
  \draw(0.9,0)--(0.9,-0.25);
  \draw(0.9,0.5)--(0.9,0.75);
  
  \node at (0.53,0.65) {$\cdots$};
  \node at (0.53,-0.15) {$\cdots$};
  
  \node at (0.55,1.15) {$s'$};
  \draw (0,0.75) arc(180:90:.1) -- (0.4, 0.85) arc(-90:0:.1);
  \draw (1,0.75) arc(0:90:.1) -- (0.6, 0.85) arc(270:180:.1);
  
  \node at (0.55,-0.62) {$e'$};
  \draw (0,-0.25) arc(-180:-90:.1) -- (0.4, -0.35) arc(90:0:.1);
  \draw (1,-0.25) arc(0:-90:.1) -- (0.6, -0.35) arc(-270:-180:.1);
 
\end{tikzpicture} \, ,
\end{equation*} 
we have two binary operations, denoted by $\star$ and $\circ$, to build another prograph. The operation~$\star$ performs a concatenation as follows:
\begin{equation*}
\begin{tikzpicture}[scale =1, baseline = {([yshift=-.8ex]current bounding box.center)}]
  \bloc{0,0}{1,0.5}{$P$}
  \draw(0.1,0)--(0.1,-0.25);
  \draw(0.1,0.5)--(0.1,0.75);
  
  \draw(0.9,0)--(0.9,-0.25);
  \draw(0.9,0.5)--(0.9,0.75);
  
  \node at (0.53,0.65) {$\cdots$};
  \node at (0.53,-0.15) {$\cdots$};
  
  \node at (0.5,1.1) {$s$};
  \draw (0,0.75) arc(180:90:.1) -- (0.4, 0.85) arc(-90:0:.1);
  \draw (1,0.75) arc(0:90:.1) -- (0.6, 0.85) arc(270:180:.1);
  
  \node at (0.5,-0.61) {$e$};
  \draw (0,-0.25) arc(-180:-90:.1) -- (0.4, -0.35) arc(90:0:.1);
  \draw (1,-0.25) arc(0:-90:.1) -- (0.6, -0.35) arc(-270:-180:.1);
 
\end{tikzpicture} \,  \star \, 
\begin{tikzpicture}[scale = 1, baseline = {([yshift=-.8ex]current bounding box.center)}]
  \bloc{0,0}{1,0.5}{$P'$}
  \draw(0.1,0)--(0.1,-0.25);
  \draw(0.1,0.5)--(0.1,0.75);
  
  \draw(0.9,0)--(0.9,-0.25);
  \draw(0.9,0.5)--(0.9,0.75);
  
  \node at (0.53,0.65) {$\cdots$};
  \node at (0.53,-0.15) {$\cdots$};
  
  \node at (0.55,1.15) {$s'$};
  \draw (0,0.75) arc(180:90:.1) -- (0.4, 0.85) arc(-90:0:.1);
  \draw (1,0.75) arc(0:90:.1) -- (0.6, 0.85) arc(270:180:.1);
  
  \node at (0.55,-0.62) {$e'$};
  \draw (0,-0.25) arc(-180:-90:.1) -- (0.4, -0.35) arc(90:0:.1);
  \draw (1,-0.25) arc(0:-90:.1) -- (0.6, -0.35) arc(-270:-180:.1);
 
\end{tikzpicture} \, := \, \begin{tikzpicture}[scale = 1, baseline = {([yshift=-.8ex]current bounding box.center)}]
  \draw[dashed, red] (-0.1,-0.25) rectangle (2.2,0.75);
  \bloc{0,0}{1,0.5}{$P$}
  \draw(0.1,0)--(0.1,-0.35);
  \draw(0.1,0.5)--(0.1,0.85);
  
  \draw(0.9,0)--(0.9,-0.35);
  \draw(0.9,0.5)--(0.9,0.85);
  
  \node at (0.53,0.62) {$\cdots$};
  \node at (0.53,-0.15) {$\cdots$};
  
  \def \d {1.1}
  \bloc{\d + 0,0}{\d + 1,0.5}{$P'$}
  \draw(\d +  0.1,0)--(\d + 0.1,-0.35);
  \draw(\d + 0.1,0.5)--(\d + 0.1,0.85);
  
  \draw(\d + 0.9,0)--(\d + 0.9,-0.35);
  \draw(\d + 0.9,0.5)--(\d + 0.9,0.85);
  
  \node at (\d + 0.53,0.62) {$\cdots$};
  \node at (\d + 0.53,-0.15) {$\cdots$};
  
  
  \node at (1.1,1.25) {$s + s'$};
  \draw (0,0.85) arc(180:90:.1) -- (1.05 - 0.1, 0.95) arc(-90:0:.1);
  \draw (\d + 1,0.85) arc(0:90:.1) -- (1.05 + 0.1, 0.95) arc(270:180:.1);
  
  
  \draw (0,-0.35) arc(-180:-90:.1) -- (1.05 - 0.1, -0.45) arc(90:0:.1);
  \draw (\d + 1,-0.35) arc(0:-90:.1) -- (1.05 + 0.1, -0.45) arc(-270:-180:.1); 
  \node at (1.1,-0.69) {$e + e'$};
\end{tikzpicture}
\end{equation*}
hence building a third prograph with $e+e'$ inputs and $s+s'$ outputs. The operation $\circ$ is a partial operation, $P \circ P'$ is defined as follows if and only if $s = e'$:

\begin{equation*}
\begin{tikzpicture}[scale = 1, baseline = {([yshift=-.8ex]current bounding box.center)}]
  \bloc{0,0}{1,0.5}{$P$}
  \draw(0.1,0)--(0.1,-0.25);
  \draw(0.1,0.5)--(0.1,0.75);
  
  \draw(0.9,0)--(0.9,-0.25);
  \draw(0.9,0.5)--(0.9,0.75);
  
  \node at (0.53,0.65) {$\cdots$};
  \node at (0.53,-0.15) {$\cdots$};
  
  \node at (0.5,1.15) {$s = e'$};
  \draw (0,0.75) arc(180:90:.1) -- (0.4, 0.85) arc(-90:0:.1);
  \draw (1,0.75) arc(0:90:.1) -- (0.6, 0.85) arc(270:180:.1);
  
  \node at (0.5,-0.61) {$e$};
  \draw (0,-0.25) arc(-180:-90:.1) -- (0.4, -0.35) arc(90:0:.1);
  \draw (1,-0.25) arc(0:-90:.1) -- (0.6, -0.35) arc(-270:-180:.1);
 
\end{tikzpicture} \,  \circ \, 
\begin{tikzpicture}[scale = 1, baseline = {([yshift=-.8ex]current bounding box.center)}]
  \bloc{0,0}{1,0.5}{$P'$}
  \draw(0.1,0)--(0.1,-0.25);
  \draw(0.1,0.5)--(0.1,0.75);
  
  \draw(0.9,0)--(0.9,-0.25);
  \draw(0.9,0.5)--(0.9,0.75);
  
  \node at (0.53,0.65) {$\cdots$};
  \node at (0.53,-0.15) {$\cdots$};
  
  \node at (0.55,1.15) {$s'$};
  \draw (0,0.75) arc(180:90:.1) -- (0.4, 0.85) arc(-90:0:.1);
  \draw (1,0.75) arc(0:90:.1) -- (0.6, 0.85) arc(270:180:.1);
  
  \node at (0.5,-0.62) {$e' = s$};
  \draw (0,-0.25) arc(-180:-90:.1) -- (0.4, -0.35) arc(90:0:.1);
  \draw (1,-0.25) arc(0:-90:.1) -- (0.6, -0.35) arc(-270:-180:.1);
 
\end{tikzpicture} \,  :=  \, \begin{tikzpicture}[scale = 1, baseline = {([yshift=-.8ex]current bounding box.center)}]
  \draw[dashed, red] (-0.1,-0.22) rectangle (1.1,1.45);
  
  \bloc{0,0}{1,0.5}{$P$}
  \draw(0.1,0)--(0.1,-0.3);
  \draw(0.1,0.5)--(0.1,0.75);
  
  \draw(0.9,0)--(0.9,-0.3);
  \draw(0.9,0.5)--(0.9,0.75);
  
  \node at (0.53,0.6) {$\cdots$};
  \node at (0.53,-0.15) {$\cdots$};
  
  \node at (0.5,-0.63) {$e$};
  \draw (0,-0.3) arc(-180:-90:.1) -- (0.4, -0.4) arc(90:0:.1);
  \draw (1,-0.3) arc(0:-90:.1) -- (0.6, -0.4) arc(-270:-180:.1);
 
  \def \d {0.75}
  \bloc{0,\d + 0}{1,\d + 0.5}{$P'$}
  \draw(0.1,\d + 0)--(0.1,\d -0.25);
  \draw(0.1,\d + 0.5)--(0.1,\d + 0.8);
  
  \draw(0.9,\d +  0)--(0.9,\d -0.25);
  \draw(0.9,\d + 0.5)--(0.9,\d +  0.8);
  
  \node at (0.53,\d +  0.6) {$\cdots$};
  
  \node at (0.53,\d + 1.18) {$s'$};
  \draw (0,\d + 0.8) arc(180:90:.1) -- (0.4, \d + 0.90) arc(-90:0:.1);
  \draw (1,\d + 0.8) arc(0:90:.1) -- (0.6, \d + 0.90) arc(270:180:.1);
  
  
\end{tikzpicture} \, .
\end{equation*}
Thus we get a prograph with $e$ inputs and $s'$ outputs, where the first output of $P$ is connected to  the first input of $P'$ and so on.

\begin{remarque}
We restrict ourselves to prographs made of generators with at least one input and one output. We might call them reduced prographs but we simply call them prographs.
\end{remarque} 
 
\begin{definition}
For a set of generators $\mathbb{G}$ and a triple $(e,s,n) \in \mathbb{N}^3$, we write $PG_{e,s,n}(\mathbb{G})$ the set of prographs with $e$ inputs, $s$ outputs and using exactly $n$ generators from $\mathbb{G}$.
\end{definition}

\begin{exemple} The set 
\begin{equation*}
PG_{6,7,6}\left(\left\{ \begin{tikzpicture}[baseline = {([yshift=-.8ex]current bounding box.center)}]
  \bloc{0,0}{0.5,0.5}{$\blacklozenge$}
  \draw(0.25,0)--(0.25,-0.25);
  \draw(0.25,0.5)--(0.25,0.75);
\end{tikzpicture}\, ,
\begin{tikzpicture}[baseline = {([yshift=-.8ex]current bounding box.center)}]
  \bloc{0,0}{0.5,0.5}{$\diamondsuit$}
  \draw(0.25,0)--(0.25,-0.25);
  \draw(0.25,0.5)--(0.25,0.75);
\end{tikzpicture}\, ,
\begin{tikzpicture}[baseline = {([yshift=-.8ex]current bounding box.center)}]
  \bloc{0,0}{1,0.5}{$\spadesuit$}
  \draw(0.25,0)--(0.25,-0.25);
  \draw(0.75,0)--(0.75,-0.25);
  \draw(0.5,0.5)--(0.5,0.75);
\end{tikzpicture}\, ,
\begin{tikzpicture}[baseline = {([yshift=-.8ex]current bounding box.center)}]
  \bloc{0,0}{1,0.5}{$\clubsuit$}
  \draw(0.25,0)--(0.25,-0.25);
  \draw(0.75,0)--(0.75,-0.25);
  \draw(0.25,0.5)--(0.25,0.75);
  \draw(0.75,0.5)--(0.75,0.75);
\end{tikzpicture}\, ,
\begin{tikzpicture}[baseline = {([yshift=-.8ex]current bounding box.center)}]
  \bloc{0,0}{1.25,0.5}{$\heartsuit$}
  \draw(0.25,0)--(0.25,-0.25);
  \draw(1,0)--(1,-0.25);
   \draw(0.625,0)--(0.625,-0.25);
  \draw(0.2,0.5)--(0.2,0.75);
  \draw(1.05,0.5)--(1.05,0.75);
  \draw(0.48,0.5)--(0.48,0.75);
  \draw(0.77,0.5)--(0.77,0.75);
\end{tikzpicture}\, ,
\begin{tikzpicture}[baseline = {([yshift=-.8ex]current bounding box.center)}]
  \bloc{0,0}{1.25,0.5}{$\Box$}   
   \draw(0.2,0)--(0.2,-0.25);
  \draw(1.05,0)--(1.05,-0.25);
  \draw(0.48,0)--(0.48,-0.25);
  \draw(0.77,0)--(0.77,-0.25);
  
  \draw(0.2,0.5)--(0.2,0.75);
  \draw(1.05,0.5)--(1.05,0.75);
  \draw(0.48,0.5)--(0.48,0.75);
  \draw(0.77,0.5)--(0.77,0.75);
\end{tikzpicture} \right\}\right)
\end{equation*}
contains the prograph 
\begin{equation} \label{exemple}
\begin{tikzpicture}[scale = 1,baseline = {([yshift=-.8ex]current bounding box.center)}]
  \draw(-0.2,-0.25)--(-0.2,3);

  \bloc{0,0}{1,0.5}{$\spadesuit$}
  \draw(0.25,0)--(0.25,-0.25);
  \draw(0.75,0)--(0.75,-0.25);
  \draw(0.5,0.5)--(0.5,0.75);
  
   \def\x{1.2}
  \bloc{0+\x,0}{0.5+\x,0.5}{$\diamondsuit$}
  \draw(0.25+\x,0)--(0.25+\x,-0.25);
  \draw(0.25+\x,0.5)--(0.25+\x,0.75);
  
   \bloc{0.25,0.75}{2,1.25}{$\heartsuit$}
   \draw(2-0.1,0.75)--(2-0.1,-0.25);
  \draw(0.2+0.25,1.25)--(0.2+0.25,3);
  \draw(1.40,1.25)--(1.40,2.25);
  \draw(0.85,1.25)--(0.85,2.25);
  \draw(1.85,1.25)--(1.85,1.5);
  
  \bloc{1.75,1.5}{2.6,2}{$\clubsuit$}
  \draw(2.4,1.5)--(2.4,-0.25);
  \draw(2,2)--(2,2.25);
  \draw(2.4,2)--(2.4,3);
    
  
 \bloc{0.6,2.25}{2.25,2.75}{$\heartsuit$}
  \draw(2,2.75)--(2,3);
  \draw(1.23,2.75)--(1.23,3);
  \draw(1.61,2.75)--(1.61,3);
  \draw(0.85,2.75)--(0.85,3);
  
  \bloc{2.15,0}{0.5+2.15,0.5}{$\blacklozenge$}

\end{tikzpicture}
\end{equation}
that can be built by the expression 
\begin{equation*} 
\left(\, \begin{tikzpicture}[baseline = {([yshift=-.8ex]current bounding box.center)}]
  \draw(0.25,-0.25)--(0.25,0.75);
\end{tikzpicture} \star \begin{tikzpicture}[baseline = {([yshift=-.8ex]current bounding box.center)}]
  \bloc{0,0}{1,0.5}{$\spadesuit$}
  \draw(0.25,0)--(0.25,-0.25);
  \draw(0.75,0)--(0.75,-0.25);
  \draw(0.5,0.5)--(0.5,0.75);
\end{tikzpicture} \star \begin{tikzpicture}[baseline = {([yshift=-.8ex]current bounding box.center)}]
  \bloc{0,0}{0.5,0.5}{$\diamondsuit$}
  \draw(0.25,0)--(0.25,-0.25);
  \draw(0.25,0.5)--(0.25,0.75);
\end{tikzpicture} \star \begin{tikzpicture}[baseline = {([yshift=-.8ex]current bounding box.center)}]
  \draw(0.25,-0.25)--(0.25,0.75);
\end{tikzpicture} \star \begin{tikzpicture}[baseline = {([yshift=-.8ex]current bounding box.center)}]
  \bloc{0,0}{0.5,0.5}{$\blacklozenge$}
  \draw(0.25,0)--(0.25,-0.25);
  \draw(0.25,0.5)--(0.25,0.75);
\end{tikzpicture} \right) 
\circ \left( \, \begin{tikzpicture}[baseline = {([yshift=-.8ex]current bounding box.center)}]
  \draw(0.25,-0.25)--(0.25,0.75);
\end{tikzpicture} \star \begin{tikzpicture}[baseline = {([yshift=-.8ex]current bounding box.center)}]
  \bloc{0,0}{1.25,0.5}{$\heartsuit$}
  \draw(0.25,0)--(0.25,-0.25);
  \draw(1,0)--(1,-0.25);
   \draw(0.625,0)--(0.625,-0.25);
  \draw(0.2,0.5)--(0.2,0.75);
  \draw(1.05,0.5)--(1.05,0.75);
  \draw(0.48,0.5)--(0.48,0.75);
  \draw(0.77,0.5)--(0.77,0.75);
\end{tikzpicture} \star \begin{tikzpicture}[baseline = {([yshift=-.8ex]current bounding box.center)}]
  \draw(0.25,-0.25)--(0.25,0.75);
\end{tikzpicture} \, \right) \circ \left( \, \begin{tikzpicture}[baseline = {([yshift=-.8ex]current bounding box.center)}]
  \draw(0.25,-0.25)--(0.25,0.75);
  \node at (0.4,0.65) {\scriptsize{$4$}};
\end{tikzpicture} \hspace{-5pt} \star \begin{tikzpicture}[baseline = {([yshift=-.8ex]current bounding box.center)}]
  \bloc{0,0}{1,0.5}{$\clubsuit$}
  \draw(0.25,0)--(0.25,-0.25);
  \draw(0.75,0)--(0.75,-0.25);
  \draw(0.25,0.5)--(0.25,0.75);
  \draw(0.75,0.5)--(0.75,0.75);
\end{tikzpicture} \right)\circ \left( \, \begin{tikzpicture}[baseline = {([yshift=-.8ex]current bounding box.center)}]
  \draw(0.25,-0.25)--(0.25,0.75);
  \node at (0.4,0.65) {\scriptsize{$2$}};
\end{tikzpicture} \hspace{-5pt} \star \begin{tikzpicture}[baseline = {([yshift=-.8ex]current bounding box.center)}]
  \bloc{0,0}{1.25,0.5}{$\heartsuit$}
  \draw(0.25,0)--(0.25,-0.25);
  \draw(1,0)--(1,-0.25);
   \draw(0.625,0)--(0.625,-0.25);
  \draw(0.2,0.5)--(0.2,0.75);
  \draw(1.05,0.5)--(1.05,0.75);
  \draw(0.48,0.5)--(0.48,0.75);
  \draw(0.77,0.5)--(0.77,0.75);
\end{tikzpicture} \star \begin{tikzpicture}[baseline = {([yshift=-.8ex]current bounding box.center)}]
  \draw(0.25,-0.25)--(0.25,0.75);
\end{tikzpicture} \, \right)
\end{equation*}
where for any $n \geq 0$, $|^n := \underbrace{| \star \dots \star |}_{n}$. 
\end{exemple}



\begin{prob*}
Given a set of generators $\mathbb{G}$ and a triple $(e,s,n) \in \mathbb{N}^3$,  our goal is to count the prographs of $PG_{e,s,n}(\mathbb{G})$.
\end{prob*}

The main difficulty in counting prographs is that the grammar provided by their definition is ambiguous. Indeed, the operations $\star$ and $\circ$ are associative and are related by two relations, called unitary and rectangle relations.

The unitary relation states that for a prograph $P$ with $e$ inputs and $s$ outputs,
\begin{equation*} \label{unitaire}
P \circ |^s = P = |^e \circ P.
\end{equation*}
This formalizes the fact that connecting a wire does not change anything.

Rectangle relation states that for prographs $P_1, P_2, Q_1$ and $Q_2$ be such that $P_1 \circ P_2$ and $Q_1 \circ Q_2$ are well-defined,
\begin{equation*}\label{rectangle}
\left( P_1 \circ P_2 \right) \star \left(Q_1 \circ Q_2 \right) = \left( P_1 \star Q_1 \right) \circ \left(P_2 \star Q_2 \right).
\end{equation*}
This exhibits two ways to construct the prograph 
\begin{equation*}
\begin{tikzpicture}[scale = 1.2, baseline = {([yshift=-.8ex]current bounding box.center)}]
  \bloc{0,0}{1,0.5}{$P_1$}
  \draw(0.1,0)--(0.1,-0.25);
  \draw(0.1,0.5)--(0.1,0.75);
  
  \draw(0.9,0)--(0.9,-0.25);
  \draw(0.9,0.5)--(0.9,0.75);
  
  \node at (0.53,0.62) {$\cdots$};
  \node at (0.53,-0.15) {$\cdots$};
 
  \def \d {0.8}
  \bloc{0,\d + 0}{1,\d + 0.5}{$P_2$}
  \draw(0.1,\d + 0)--(0.1,\d -0.05);
  \draw(0.1,\d + 0.5)--(0.1,\d + 0.75);
  
  \draw(0.9,\d +  0)--(0.9,\d -0.05);
  \draw(0.9,\d + 0.5)--(0.9,\d +  0.75);  
  
  \node at (0.53,\d +  0.65) {$\cdots$};
  
  \def \e {1.1}
  
  \bloc{\e + 0,0}{\e + 1,0.5}{$Q_1$}
  \draw(\e + 0.1,0)--(\e + 0.1,-0.25);
  \draw(\e + 0.1,0.5)--(\e + 0.1,0.75);
  
  \draw(\e + 0.9,0)--(\e + 0.9,-0.25);
  \draw(\e + 0.9,0.5)--(\e + 0.9,0.75);
  
  \node at (\e + 0.53,0.62) {$\cdots$};
  \node at (\e + 0.53,-0.15) {$\cdots$};
 
  
  \bloc{\e + 0,\d + 0}{\e + 1,\d + 0.5}{$Q_2$}
  \draw(\e + 0.1,\d + 0)--(\e + 0.1,\d -0.25);
  \draw(\e + 0.1,\d + 0.5)--(\e + 0.1,\d + 0.75);
  
  \draw(\e + 0.9,\d +  0)--(\e + 0.9,\d -0.25);
  \draw(\e + 0.9,\d + 0.5)--(\e + 0.9,\d +  0.75);
  
  \node at (\e + 0.53,\d +  0.65) {$\cdots$};
\end{tikzpicture}
\end{equation*}
from the prographs $P_1, P_2, Q_1$ and $Q_2$.


\begin{exemple} Here is a small example of ambiguity: 
\begin{equation*}
\left(\begin{tikzpicture}[scale = 0.7, baseline = {([yshift=-.8ex]current bounding box.center)}]
  \bloc{0,0}{0.5,0.5}{}
  \draw(0.25,0)--(0.25,-0.25);
  \draw(0.25,0.5)--(0.25,0.75);
\end{tikzpicture} \hspace{2pt} \star \hspace{2pt} \begin{tikzpicture}[scale = 0.7, baseline = {([yshift=-.8ex]current bounding box.center)}]
  \draw(0.25,0.75)--(0.25,-0.25);
\end{tikzpicture} \hspace{2pt} \right) \circ \left( \hspace{2pt} \begin{tikzpicture}[scale = 0.7, baseline = {([yshift=-.8ex]current bounding box.center)}]
  \draw(0.25,0.75)--(0.25,-0.25);
\end{tikzpicture} \hspace{2pt} \star \hspace{2pt} \begin{tikzpicture}[scale = 0.7, baseline = {([yshift=-.8ex]current bounding box.center)}]
  \bloc{0,0}{0.5,0.5}{}
  \draw(0.25,0)--(0.25,-0.25);
  \draw(0.25,0.5)--(0.25,0.75);
\end{tikzpicture}\right) = \left(\hspace{2pt} \begin{tikzpicture}[scale = 0.7, baseline = {([yshift=-.8ex]current bounding box.center)}]
  \draw(0.25,0.75)--(0.25,-0.25);
\end{tikzpicture} \hspace{2pt} \star \hspace{2pt} \begin{tikzpicture}[scale = 0.7, baseline = {([yshift=-.8ex]current bounding box.center)}]
  \bloc{0,0}{0.5,0.5}{}
  \draw(0.25,0)--(0.25,-0.25);
  \draw(0.25,0.5)--(0.25,0.75);
\end{tikzpicture}\right) \circ \left(\begin{tikzpicture}[scale = 0.7, baseline = {([yshift=-.8ex]current bounding box.center)}]
  \bloc{0,0}{0.5,0.5}{}
  \draw(0.25,0)--(0.25,-0.25);
  \draw(0.25,0.5)--(0.25,0.75);
\end{tikzpicture} \hspace{2pt} \star \hspace{2pt} \begin{tikzpicture}[scale = 0.7, baseline = {([yshift=-.8ex]current bounding box.center)}]
  \draw(0.25,0.75)--(0.25,-0.25);
\end{tikzpicture} \hspace{2pt} \right) = \begin{tikzpicture}[scale = 0.7, baseline = {([yshift=-.8ex]current bounding box.center)}]
  \bloc{0,0}{0.5,0.5}{}
  \draw(0.25,0)--(0.25,-0.25);
  \draw(0.25,0.5)--(0.25,0.75);
\end{tikzpicture} \hspace{2pt} \star \hspace{2pt} \begin{tikzpicture}[scale = 0.7, baseline = {([yshift=-.8ex]current bounding box.center)}]
  \bloc{0,0}{0.5,0.5}{}
  \draw(0.25,0)--(0.25,-0.25);
  \draw(0.25,0.5)--(0.25,0.75);
\end{tikzpicture} \, .
\end{equation*}
\end{exemple}

To overcome this difficulty, we propose a canonical expression of any prograph in their grammar and use it to build a bijection.

\section{Bijection between prographs and some lattice paths}

\subsection{Canonical expressions}

For a prograph $P$, we denote by ${\downarrow}(P)$ its number of inputs and by ${\uparrow}(P)$ its number of outputs. Let a prograph $P$, a generator $x$ and $i \in \mathbb{N}_{\geq 1}$ such that $i + {\downarrow}(x) -1 \leq {\uparrow}(P)$ then we define a new operation $\circ_i$ as follows: 
\begin{equation} \label{rond_i}
P \circ_i x \, := \, \begin{tikzpicture}[scale = 0.8,baseline = {([yshift=-.8ex]current bounding box.center)}]
  \bloc{0,0}{2,1}{$P$}
  
  \draw(0.2,0)--(0.2,-0.4);
  \node at (1,-0.2) {$\cdots$};
  \draw(1.8,0)--(1.8,-0.4);
  
  \draw(0.1,1)--(0.1,2.3);
  \node at (0.4,1.1) {$...$};
  \draw(0.7,1)--(0.7,1.5);
  
  \node at (-0.1,1.4) {{\small $1$}};
  \node at (0.4,1.4) {{\small $i$}};
  
  \bloc{0.6,1.5}{0.6 + 1,1.5 + 0.5}{$x$};
  
  \node at (1.1,1.25) {$\cdots$};
  
  \draw(1.5,1)--(1.5,1.5);
  \node at (1.7,1.1) {$...$};
  \draw(1.9,1)--(1.9,2.3);
  
  \draw(0.7,2)--(0.7,2.3);
  \node at (1.1,2.1) {$\cdots$};
  \draw(1.5,2)--(1.5,2.3);
\end{tikzpicture} \, .
\end{equation}
A similar operation is used in \cite{La09}.

\begin{theorem} \label{Th_dec}For $e,s,n \in \mathbb{N}$ and $P \in PG_{e,s,n}(\mathbb{G})$, there exists a unique pair of sequences $((x_1, \dots, x_n),(i_1, \dots, i_n)) \in \mathbb{G}^n \times \mathbb{N}_{\geq 1}^n$
such that
\begin{equation} \label{pro_cano}
P = \left(  \cdots \left( \left( |^e \circ_{i_1} x_{1} \right) \circ_{i_2} x_{2} \right)  \cdots \right) \circ_{i_n} x_{n}.
\end{equation}
and for all $k \in [n-1]$, $i_{k} < i_{k+1} + {\downarrow}(x_{k+1})$. Such a decomposition is called canonical.
\end{theorem}

\begin{Sproof} We just show how to compute the canonical decomposition.\\
In \cite{Bo17}, Borie introduces a prograph traversal for the prographs of $PG_{1,1,n}\left(\left\{\begin{tikzpicture}[scale = 0.8, baseline = {([yshift=-.8ex]current bounding box.center)}]
  \bloc{0,0}{0.5,0.3}{}
  \draw(0.1,0)--(0.1,-0.25);
  \draw(0.4,0)--(0.4,-0.25);
  \draw(0.25,0.3)--(0.25,0.3 + 0.25);
\end{tikzpicture} \, , \, \begin{tikzpicture}[scale = 0.8, baseline = {([yshift=-.8ex]current bounding box.center)}]
  \bloc{0,0}{0.5,0.3}{}
  \draw(0.25,0)--(0.25,-0.25);
  \draw(0.1,0.3)--(0.1,0.3+0.25);
  \draw(0.4,0.3)--(0.4,0.3+0.25);
\end{tikzpicture} \right\}\right)$, where $n \in \mathbb{N}$. 
It is a depth-left first numbering of generators with the additional condition that a generator can be numbered only if all the generators connected to its inputs are already numbered. 

His traversal naturally runs on any prograph. For example, the generators of the prograph (\ref{exemple}) are numbered like this
\begin{equation} \label{exemple_num}
\begin{tikzpicture}[scale = 1.1, baseline = {([yshift=-.8ex]current bounding box.center)}]
  \draw(-0.2,-0.25)--(-0.2,3);

  \bloc{0,0}{1,0.5}{$1^\spadesuit$}
  \draw(0.25,0)--(0.25,-0.25);
  \draw(0.75,0)--(0.75,-0.25);
  \draw(0.5,0.5)--(0.5,0.75);
  
   \def\x{1.2}
  \bloc{0+\x,0}{0.5+\x,0.5}{$2^\diamondsuit$}
  \draw(0.25+\x,0)--(0.25+\x,-0.25);
  \draw(0.25+\x,0.5)--(0.25+\x,0.75);
  
   \bloc{0.25,0.75}{2,1.25}{$3^\heartsuit$}
   \draw(2-0.1,0.75)--(2-0.1,-0.25);
  \draw(0.2+0.25,1.25)--(0.2+0.25,3);
  \draw(1.40,1.25)--(1.40,2.25);
  \draw(0.85,1.25)--(0.85,2.25);
  \draw(1.85,1.25)--(1.85,1.5);
  
  \bloc{1.75,1.5}{2.6,2}{$5^\clubsuit$}
  \draw(2.4,1.5)--(2.4,-0.25);
  \draw(2,2)--(2,2.25);
  \draw(2.4,2)--(2.4,3);
    
  
 \bloc{0.6,2.25}{2.25,2.75}{$6^\heartsuit$}
  \draw(2,2.75)--(2,3);
  \draw(1.23,2.75)--(1.23,3);
  \draw(1.61,2.75)--(1.61,3);
  \draw(0.85,2.75)--(0.85,3);
  
  \bloc{2.15,0}{0.5+2.15,0.5}{$4^\blacklozenge$}

\end{tikzpicture} \, .
\end{equation} 
A generator appears in the canonical decomposition at the position given by the numbering. Then the index of the operation (\ref{rond_i}) corresponding to the generator is uniquely determined as the number of wires on its left plus one.

In our example (\ref{exemple}/\ref{exemple_num}), the prograph (\ref{exemple}) is canonically decomposed as
\begin{equation*}
 \left( \cdots \left( |^6 \circ_2 \spadesuit \right) \circ_3 \diamondsuit \Big) \circ_2 \heartsuit \Big) \circ_6 \blacklozenge \Big) \circ_5 \clubsuit \right) \circ_3 \heartsuit.
\end{equation*}
\end{Sproof}


\begin{remarque}
We deduce from Theorem \ref{Th_dec} a simple algorithm to generate prographs of $PG_{e,s,n}(\mathbb{G})$: we just have to generate their canonical decompositions.
\end{remarque}

The canonical decompositions are mostly sequences of inequalities and this type of constraints can be encoded by some lattice paths.

\subsection{Lattice paths}

\begin{definition}
A path is a pair $(p_\mathrm{i}, w_1 \cdots w_n) \in \mathbb{Z}^3 \times \left( \mathbb{Z}^3 \times \mathbb{N} \right)^n$, where $p_\mathrm{i}$ is the origin of the path and $w_1 \cdots w_n$ is the sequence of three-dimensional colored steps.

For a step $v \in \mathbb{Z}^3 \times \mathbb{N}$, we denote by $\gamma_1$, $\gamma_2$, $\gamma_3$ and $\gamma_c$ respectively the abscissa, the ordinate, the applicate and the color of the step $v$. Formally, $v = (\gamma_1(v), \gamma_2(v), \gamma_3(v), \gamma_c(v))$. We also write for any $v \in \mathbb{Z}^3, v = (\gamma_1(v), \gamma_2(v), \gamma_3(v))$. For any set $X$, we denote by $X^*$ the set $\bigsqcup\limits_{k \geq 0} X^k$ where $\sqcup$ denotes the disjoint union.
\end{definition}

\begin{definition}For $M \subset \left(\mathbb{Z}^3 \times \mathbb{N} \right)^*$ and $p_\mathrm{i},p_\mathrm{f} \in \mathbb{Z}^3$, we denote by $\mathcal{L}(M,p_\mathrm{i},p_\mathrm{f})$ the set of paths $(p_\mathrm{i}, w_1 \cdots w_n)$ such that
\begin{enumerate}
\item $ w_1 \cdots w_n \in M$;
\item $\gamma_j(p_\mathrm{i}) + \sum\limits_{\ell = 1}^{n} \gamma_j(w_\ell) = \gamma_j(p_\mathrm{f})$ for any $j = 1, 2, 3$;
\item for $k \in [0 , n], 1 \leq \gamma_2(p_\mathrm{i}) + \sum\limits_{\ell = 1}^{k} \gamma_2(w_\ell) \leq \gamma_3(p_\mathrm{i}) + \sum\limits_{\ell = 1}^{k} \gamma_3(w_\ell)$.
\end{enumerate}
\end{definition}

In other words, $\mathcal{L}(M, p_\mathrm{i}, p_\mathrm{f})$ is the set of paths from $ p_\mathrm{i} $ to $ p_\mathrm{f} $ whose sequence of steps belongs to $ M $ and such that in any point of the paths the ordinate is between $ 1 $ and the applicate.

\begin{exemple} We draw the color $0$ with red (simple line) and the color $1$ with blue (double lines). The set 
\begin{equation*}
 \mathcal{L}\left( \left\{
\begin{bmatrix}0 \\ 1 \\ 0 \\ 0\end{bmatrix},
\begin{bmatrix}1 \\ -1 \\ -1 \\ 0\end{bmatrix},
\begin{bmatrix}1 \\ 0 \\ 0 \\ 0\end{bmatrix},
\begin{bmatrix}1 \\ 0 \\ 0 \\ 1\end{bmatrix},
\begin{bmatrix}1 \\ -2 \\ 1 \\ 0\end{bmatrix},
\begin{bmatrix}1 \\ -1 \\ 0 \\ 0\end{bmatrix} \right\}^* , \begin{bmatrix}0 \\ 1 \\ 6\end{bmatrix}, \begin{bmatrix}6 \\ 7 \\ 7\end{bmatrix}\right)
\end{equation*}
contains the path
\begin{equation} \label{chemin}
\left(\begin{bmatrix}0 \\ 1 \\ 6\end{bmatrix} , \,
\begin{bmatrix}0 \\ 1 \\ 0 \\ 0\end{bmatrix}^2 \hspace{-4pt}
\begin{bmatrix}1 \\ -1 \\ -1 \\ 0\end{bmatrix} \hspace{-4pt}
\begin{bmatrix}0 \\ 1 \\ 0 \\ 0\end{bmatrix} \hspace{-4pt}
\begin{bmatrix}1 \\ 0 \\ 0 \\ 0\end{bmatrix} \hspace{-4pt}
\begin{bmatrix}0 \\ 1 \\ 0 \\ 0\end{bmatrix} \hspace{-4pt}
\begin{bmatrix}1 \\ -2 \\ 1 \\ 0\end{bmatrix} \hspace{-4pt}
\begin{bmatrix}0 \\ 1 \\ 0 \\ 0\end{bmatrix}^4 \hspace{-4pt}
\begin{bmatrix}1 \\ 0 \\ 0 \\ 1\end{bmatrix} \hspace{-4pt}
\begin{bmatrix}1 \\ -1 \\ 0 \\ 0\end{bmatrix} \hspace{-4pt}
\begin{bmatrix}1 \\ -2 \\ 1 \\ 0\end{bmatrix} \hspace{-4pt}
\begin{bmatrix}0 \\ 1 \\ 0 \\ 0\end{bmatrix}^4 \right)
\end{equation}
drawn as 
\begin{equation} \label{chemin_graphique}
\begin{tikzpicture}[scale = 0.6, baseline = {([yshift=-.8ex]current bounding box.center)}]
\foreach \a in {0,...,7}{
     \draw[help lines]
     (\a,0,0) -- (\a,0,-7)
     (0,0,-\a) -- (7,0,-\a)
     % 
     (0,\a,0) -- (0,\a,-7)
     (0,0,-\a) -- (0,7,-\a)
     %
     (0,\a,-7) -- (7,\a,-7)
     (\a,0,-7) -- (\a,7,-7)
     ;
   }
   
	\draw[->, black, very thick] (0,0,0) -- (0,7,0);
	\draw[->, black, very thick] (0,0,0) -- (7,0,0);   
	\draw[->, black, very thick] (0,0,0) -- (0,0,-7); 
	
	\draw (7,0,0) node[below] {$x$};
	\draw (0,7,0) node[left] {$y$};
	\draw (0,0,-7) node[left] {$z$};
	
	\draw (0,0,0) node[below left = -0.05cm] {$0$};
	\draw (0,1,0) node[left] {$1$};
	\draw (1,0,0) node[below] {$1$};
	\draw (0,0,-1) node[above left = -0.1cm] {$1$};
   
   \draw[line width=1pt,red]
   (0,1,-6)
   -- ++(0,2,0)
   -- ++(1,-1,1)
   -- ++(0,1,0)
   -- ++(1,0,0)
   -- ++(0,1,0)
   -- ++(1,-2,-1)
   -- ++(0,4,0);
   
   \draw[line width=1pt,blue, double]
   (3,6,-6)
   -- ++(1,0,0);
   
   \draw[line width=1pt,red]
   (4,6,-6)
   -- ++(1,-1,0)
   -- ++(1,-2,-1)
   -- ++(0,4,0)
   ;
   
   \draw[dashed,red]
   (0,0,-6) -- (0,1,-6)
   (1,0,-5) -- (1,2,-5)
   (2,0,-5) -- (2,4,-5)
   (3,0,-6) -- (3,2,-6)
   (4,0,-6) -- (4,6,-6)
   (5,0,-6) -- (5,5,-6)
   (6,0,-7) -- (6,3,-7)
   
   
   
   (1,2,-7) -- (1,2,-5)
   (1,3,-7) -- (1,3,-5)
   (2,4,-7) -- (2,4,-5)
   (3,2,-7) -- (3,2,-6)
   (3,6,-7) -- (3,6,-6)
   (4,6,-7) -- (4,6,-6)
   (5,5,-7) -- (5,5,-6)
   
   (0,3,-5) -- (1,3,-5)
   (0,2,-5) -- (1,2,-5)
   (0,4,-5) -- (2,4,-5)
   (0,6,-6) -- (3,6,-6)
   ;
   

\end{tikzpicture} \, .
\end{equation}
\end{exemple}

$\hspace{-1.4pt}$The canonical decompositions are encoded by particular lattice paths, called propaths. 

\subsection{Propaths}

We denote by $\mathbb{G}$ the set of generators 
\begin{equation*}
\left\{
\begin{tikzpicture}[scale = 0.9, baseline = {([yshift=-.8ex]current bounding box.center)}]
  \bloc{0,0}{1,0.5}{$1$}
  \draw(0.1,0)--(0.1,-0.25);
  \draw(0.1,0.5)--(0.1,0.75);
  
  \draw(0.9,0)--(0.9,-0.25);
  \draw(0.9,0.5)--(0.9,0.75);
  
  \node at (0.53,0.65) {$\cdots$};
  \node at (0.53,-0.15) {$\cdots$};
  
  \node at (0.5,1.15) {$\beta_1$};
  \draw (0,0.75) arc(180:90:.1) -- (0.4, 0.85) arc(-90:0:.1);
  \draw (1,0.75) arc(0:90:.1) -- (0.6, 0.85) arc(270:180:.1);
  
  \node at (0.5,-0.65) {$\alpha_1$};
  \draw (0,-0.25) arc(-180:-90:.1) -- (0.4, -0.35) arc(90:0:.1);
  \draw (1,-0.25) arc(0:-90:.1) -- (0.6, -0.35) arc(-270:-180:.1);
 
\end{tikzpicture}\, , \dots,  \begin{tikzpicture}[scale = 0.9, baseline = {([yshift=-.8ex]current bounding box.center)}]
  \bloc{0,0}{1,0.5}{$m_1$}
  \draw(0.1,0)--(0.1,-0.25);
  \draw(0.1,0.5)--(0.1,0.75);
  
  \draw(0.9,0)--(0.9,-0.25);
  \draw(0.9,0.5)--(0.9,0.75);
  
  \node at (0.53,0.65) {$\cdots$};
  \node at (0.53,-0.15) {$\cdots$};
  
  \node at (0.5,1.15) {$\beta_1$};
  \draw (0,0.75) arc(180:90:.1) -- (0.4, 0.85) arc(-90:0:.1);
  \draw (1,0.75) arc(0:90:.1) -- (0.6, 0.85) arc(270:180:.1);
  
  \node at (0.5,-0.65) {$\alpha_1$};
  \draw (0,-0.25) arc(-180:-90:.1) -- (0.4, -0.35) arc(90:0:.1);
  \draw (1,-0.25) arc(0:-90:.1) -- (0.6, -0.35) arc(-270:-180:.1);
 
\end{tikzpicture} \, , \dots,  \begin{tikzpicture}[scale = 0.9, baseline = {([yshift=-.8ex]current bounding box.center)}]
  \bloc{0,0}{1,0.5}{$1$}
  \draw(0.1,0)--(0.1,-0.25);
  \draw(0.1,0.5)--(0.1,0.75);
  
  \draw(0.9,0)--(0.9,-0.25);
  \draw(0.9,0.5)--(0.9,0.75);
  
  \node at (0.53,0.65) {$\cdots$};
  \node at (0.53,-0.15) {$\cdots$};
  
  \node at (0.5,1.15) {$\beta_d$};
  \draw (0,0.75) arc(180:90:.1) -- (0.4, 0.85) arc(-90:0:.1);
  \draw (1,0.75) arc(0:90:.1) -- (0.6, 0.85) arc(270:180:.1);
  
  \node at (0.5,-0.65) {$\alpha_d$};
  \draw (0,-0.25) arc(-180:-90:.1) -- (0.4, -0.35) arc(90:0:.1);
  \draw (1,-0.25) arc(0:-90:.1) -- (0.6, -0.35) arc(-270:-180:.1);
 
\end{tikzpicture}\, , \dots,  \begin{tikzpicture}[scale = 0.9, baseline = {([yshift=-.8ex]current bounding box.center)}]
  \bloc{0,0}{1,0.5}{$m_d$}
  \draw(0.1,0)--(0.1,-0.25);
  \draw(0.1,0.5)--(0.1,0.75);
  
  \draw(0.9,0)--(0.9,-0.25);
  \draw(0.9,0.5)--(0.9,0.75);
  
  \node at (0.53,0.65) {$\cdots$};
  \node at (0.53,-0.15) {$\cdots$};
  
  \node at (0.5,1.15) {$\beta_d$};
  \draw (0,0.75) arc(180:90:.1) -- (0.4, 0.85) arc(-90:0:.1);
  \draw (1,0.75) arc(0:90:.1) -- (0.6, 0.85) arc(270:180:.1);
  
  \node at (0.5,-0.65) {$\alpha_d$};
  \draw (0,-0.25) arc(-180:-90:.1) -- (0.4, -0.35) arc(90:0:.1);
  \draw (1,-0.25) arc(0:-90:.1) -- (0.6, -0.35) arc(-270:-180:.1);
 
\end{tikzpicture}
\right\}.
\end{equation*}
where $\alpha_1, \dots, \alpha_d, \beta_1, \dots, \beta_d, m_1, \dots, m_d \in \mathbb{N}_{\geq 1}$ and we define $\omega$ by
\begin{equation*}
\begin{tabular}{cccc}
$\omega :$ & $\mathbb{G}$   & $ \longrightarrow$ & $\mathbb{Z}^3 \times \mathbb{N}$\\
& $\begin{tikzpicture}[scale = 1, baseline = {([yshift=-.8ex]current bounding box.center)}]
  \bloc{0,0}{1,0.5}{$j$}
  \draw(0.1,0)--(0.1,-0.25);
  \draw(0.1,0.5)--(0.1,0.75);
  
  \draw(0.9,0)--(0.9,-0.25);
  \draw(0.9,0.5)--(0.9,0.75);
  
  \node at (0.53,0.65) {$\cdots$};
  \node at (0.53,-0.15) {$\cdots$};
  
  \node at (0.5,1.15) {$\beta_i$};
  \draw (0,0.75) arc(180:90:.1) -- (0.4, 0.85) arc(-90:0:.1);
  \draw (1,0.75) arc(0:90:.1) -- (0.6, 0.85) arc(270:180:.1);
  
  \node at (0.5,-0.65) {$\alpha_i$};
  \draw (0,-0.25) arc(-180:-90:.1) -- (0.4, -0.35) arc(90:0:.1);
  \draw (1,-0.25) arc(0:-90:.1) -- (0.6, -0.35) arc(-270:-180:.1);
 
\end{tikzpicture}$   & $\mapsto$ & $(1,1 - \alpha_i, \beta_i - \alpha_i,j)$
\end{tabular}
\end{equation*}
We denote  by $U$ the step $(0,1,0,0)$, by $D$ the step $(0,-1,0,0)$ and by $\mathcal{W}$ the set of steps $\{ \omega(x) \, | \, x \in \mathbb{G}\}$.


\begin{definition}
We call $PP_{e,n,k,s}(\mathbb{G})$ the set $\mathcal{L}((U+ \mathcal{W})^*,(0, 1, e),(n, k, s))$. Its elements are called propaths.
\end{definition}

Propaths are refinements of prographs. 

\begin{theorem} \label{Th_PP_PG}
For $(e,s,n) \in \mathbb{N}^3$, we have $|PP_{e,n,s,s}(\mathbb{G})| = |PG_{e,s,n}(\mathbb{G})|$.
\end{theorem}

\begin{Sproof} Let $P \in PG_{e,s,n}(\mathbb{G})$, according to Theorem \ref{Th_dec} $P$ as a unique canonical decomposition of the form:
\begin{equation*} 
P = \left(  \cdots \left( \left( |^e \circ_{i_1} x_{1} \right) \circ_{i_2} x_{2} \right)  \cdots \right) \circ_{i_n} x_{n}.
\end{equation*}
Then our bijection maps this decomposition to the propath
\begin{equation*}
\left( (0, 1, e), \, U^{i_1 + {\downarrow}(x_1) - 1 -i_{0}} \omega(x_1) \cdots U^{i_n + {\downarrow}(x_n) - 1 -i_{n-1}} \omega(x_n) \, U^{s-i_n} \right) \in PP_{e,n,s,s}(\mathbb{G})
\end{equation*}
where $i_0 =1$. Intuitively, the propath abscissa encodes the number of generators, its ordinate encodes the indexes of the operations (\ref{rond_i}) in the decomposition, its applicate encodes the number of outputs and its colors allow to distinguish generators with the same number of inputs and outputs.
\end{Sproof}
For example, our bijection maps the (decomposition of the) prograph (\ref{exemple}) to the propath
\begin{equation*}
\left( (0, 1, 6), \, U^2 \, \omega(\spadesuit) \, U \, \omega(\diamondsuit) \, U \, \omega(\heartsuit) \, U^4 \,  \omega(\blacklozenge) \, \omega(\clubsuit) \, \omega(\heartsuit) \,U^4 \right)
\end{equation*}
which is equal to the path (\ref{chemin}).



Lattice paths are classical objects in combinatorics (see \cite{Kr15} for a summary). Let us now study propaths in order to obtain, thanks to Theorem \ref{Th_PP_PG}, recurrences and closed formulas for prographs.


\section{Recurrences and closed formulas}

\subsection{Recurrences formulas}

In order to simplify notation, we denote by $p(n,k,s)$ the number $|PP_{e,n,k,s}(\mathbb{G})|$, where $e \in \mathbb{N}_{\geq 1}$ is fixed.

\begin{prop} \label{Propo_rec}The number of propaths satisfies the
following recurrence relation:\\
$p(n, k, s) = \left\{
\begin{array}{l}
  1 \, \text{ if } n = 0 \text{, } k = 1 \text{ and } s = e ;\\
  p(n, k-1, s) + \sum\limits_{i = 1}^{d} m_i \, p(n-1, k-1+\alpha_i, s - \beta_i + \alpha_i)\\ \hspace{250pt}\text{ if }  n \geq 0 \text{ and } 1 \leq k \leq s ;\\
  0 \, \text{ otherwise}.\\
\end{array}
\right.$
\end{prop}

\begin{proof}
The recurrence relation is a direct translation of the following unambiguous grammar that generates the propaths: a propath belonging to $PP_{e,n,k,s}(\mathbb{G})$ is
\begin{itemize}
\item either the path reduced to the point $(0,1,e)$,
\item or a path belonging to $PP_{e,n,k-1,s}(\mathbb{G})$ concatenated to a step $U$,
\item or a path belonging to $PP_{e, n-1, k-1+\alpha_i, s - \beta_i + \alpha_i}(\mathbb{G})$ concatenated to a step\\$(1, 1-\alpha_i, \beta_i - \alpha_i, c) $ where $c$ is one of the $m_i$ colors.
\end{itemize}
\end{proof}

According to Theorem \ref{Th_PP_PG}, it is enough to specialize $k$ to $s$ in order to obtain a recurrence relation satisfied by prographs. The following theorem gets rid of the refinement parameter $k$, so it provides a recurrence relation directly on the prographs.

\begin{theorem} \label{Th_rec}Let $a_{n,s} := |PP_{e,n,s,s}(\mathbb{G})|
= |PG_{e,s,n}(\mathbb{G})|$. It satisfies the recurrence relation:\\
$a_{n,s} \hspace{-3pt} = \hspace{-3pt} \left\{
\begin{array}{ll}
  1 \, \text{ if  } n = 0  \text{ and } s = e; \\
  \hspace{-8pt} \sum\limits_{\ell = 1}^{n}(-1)^{\ell+1} \hspace{-12pt} \sum\limits_{c_1 + \dots + c_d = \ell}\hspace{-3pt}
  \begin{pmatrix}
  	\mbox{\footnotesize $ \ell $}\\
    \mbox{\footnotesize $c_1, \dots, c_d$}
  \end{pmatrix}  \hspace{-5pt}
  \begin{pmatrix} 
   \hspace{-2pt}\mbox{\footnotesize  $ s+\ell- \sum\limits_{i = 1}^{d}c_i
   \beta_i \hspace{-5pt}$ }\\
   \mbox{\footnotesize  $ \ell$}\\
  \end{pmatrix}  \hspace{-4pt}  m_1^{c_1}\hspace{-2pt}\dots m_d^{c_d}
  a_{n-\ell,\, s-\sum\limits_{i = 1}^{d}c_i (\beta_i - \alpha_i)} \text{
  if } n,s \hspace{-2pt}\geq 1;\\
  0 \, \text{ otherwise}.
\end{array}
\right.$
\end{theorem}
\begin{proof}
Let $n,s \geq 1$. For $\ell \in [0;n]$, we denote by $A_\ell$ the set
\begin{equation*}
\mathcal{L}\left( \left(U^* \mathcal{W} \right)^{n-\ell} \left(DD^* \mathcal{W} \right)^\ell U^*,(0,1,e),(n,s,s)\right).
\end{equation*}
We have $|A_n| = 0$, $a_{n,s} = |A_0|$ and $|A_\ell| = | A_\ell \sqcup A_{\ell+1} | - |A_{\ell+1}|$ for all $0 \leq \ell \leq n-1$. Thus by iteration, we obtain
\begin{equation*}
a_{n,s} = \sum\limits_{\ell = 1}^{n} (-1)^{\ell+1}| A_{\ell-1} \sqcup A_{\ell}|.
\end{equation*}
Moreover, for $\ell \in [n], A_{\ell-1} \sqcup A_{\ell}$ is equal to
\begin{equation*}
\mathcal{L}\left((U^* \mathcal{W})^{n-\ell} (U^* + DD^*)\mathcal{W} (DD^* \mathcal{W})^{\ell-1} U^*,(0,1,e),(n,s,s)\right).
\end{equation*}
So $|A_{\ell-1} \sqcup A_{\ell}|$ decomposes into
\begin{equation*}
\sum\limits_{j \geq 0} a_{n-\ell,j} \, \left|\mathcal{L}\left(D^*\mathcal{W} (DD^* \mathcal{W})^{\ell-1} D^*,(n-\ell,j,j),(n,1,s)\right)\right|.
\end{equation*}
Let us compute
\begin{equation} \label{L}
\left|\mathcal{L}\left(D^*\mathcal{W} (DD^* \mathcal{W})^{\ell-1} D^*,(n-\ell,j,j),(n,1,s)\right)\right|.
\end{equation}
To build the paths belonging to (\ref{L}), we choose at first $\ell$ steps in $\mathcal{W}$. For a composition $c_1 + \dots + c_d = \ell$ we take $c_i$ steps $(1,1-\alpha_i,\beta_i - \alpha_i, c)$ where $c$ is one of the $m_i$ colors. So there are 
\begin{equation*}
\binom{\ell}{c_1, \dots, c_d} m_1^{c_1}\dots m_d^{c_d}
\end{equation*} ways to choose the steps from $\mathcal{W}$. We now have to add the steps $D$. Let us denote by $b$ the number of steps $D$ that we have to add to obtain a path of (\ref{L}). Necessarily, $j = s - \sum\limits_{i = 1}^{d}c_i (\beta_i -  \alpha_i)$ and $b = \ell - 1 + s - \sum\limits_{i = 1}^{d}c_i \beta_i$.
The $\ell-1$ first steps from $\mathcal{W}$ in (\ref{L}) are followed by a step $D$, so we just have to place $s - \sum\limits_{i = 1}^{d}c_i \beta_i$ steps $D$ in $\ell+1$ zones; so there are $\begin{pmatrix} 
   \hspace{-2pt}\mbox{\footnotesize  $ s+\ell- \sum\limits_{i = 1}^{d}c_i
   \beta_i \hspace{-5pt}$ }\\
   \mbox{\footnotesize  $ \ell$}
  \end{pmatrix}  \hspace{-3pt}$ possibilities. Thus $|A_{\ell-1} \sqcup A_{\ell}|$ is equal to
\begin{equation*}
\sum\limits_{c_1 + \dots + c_d = \ell}  \binom{\ell}{c_1, \dots, c_d}  \begin{pmatrix} 
   \hspace{-2pt}\mbox{\footnotesize  $ s+\ell- \sum\limits_{i = 1}^{d}c_i \beta_i \hspace{-5pt}$ } \vspace{1pt}\\
   \mbox{\footnotesize  $ \ell$}
  \end{pmatrix}  \hspace{-3pt} m_1^{c_1}\dots m_d^{c_d}  \, a_{n-\ell,s-\sum\limits_{i = 1}^{d}c_i (\beta_i - \alpha_i)},
\end{equation*}hence the formula.
\end{proof}

\begin{application*} The number of outputs of the prographs made of generators $\left\{ \begin{tikzpicture}[scale = 0.6, baseline = {([yshift=-.8ex]current bounding box.center)}]
  \bloc{0,0}{1,0.5}{}
  \draw(0.3,0.5)--(0.3,0.85);
  \draw(0.7,0.5)--(0.7,0.85);
  \draw(0.5,0)--(0.5,-0.35);
  
\end{tikzpicture}\, , \, \begin{tikzpicture}[scale = 0.6, baseline = {([yshift=-.8ex]current bounding box.center)}]
  \bloc{0,0}{1,0.5}{}
  \draw(0.3,0)--(0.3,-0.35);
  \draw(0.7,0)--(0.7,-0.35);
  \draw(0.2,0.5)--(0.2,0.85);
  \draw(0.5,0.5)--(0.5,0.85);
  \draw(0.8,0.5)--(0.8,0.85);
  
\end{tikzpicture} \right\}$ are determined by their number of inputs and their number of generators. Indeed, when we add a generator, we increase the number of outputs by one. Thus, the enumeration of these prographs with a single input amounts to studying the number
\begin{equation*}
a_n := \left|PG_{1,n+1,n}\left(\left\{ \begin{tikzpicture}[scale = 0.6, baseline = {([yshift=-.8ex]current bounding box.center)}]
  \bloc{0,0}{1,0.5}{}
  \draw(0.3,0.5)--(0.3,0.85);
  \draw(0.7,0.5)--(0.7,0.85);
  \draw(0.5,0)--(0.5,-0.35);
  
\end{tikzpicture}\, , \, \begin{tikzpicture}[scale = 0.6, baseline = {([yshift=-.8ex]current bounding box.center)}]
  \bloc{0,0}{1,0.5}{}
  \draw(0.3,0)--(0.3,-0.35);
  \draw(0.7,0)--(0.7,-0.35);
  \draw(0.2,0.5)--(0.2,0.85);
  \draw(0.5,0.5)--(0.5,0.85);
  \draw(0.8,0.5)--(0.8,0.85);
  
\end{tikzpicture} \right\}\right)\right|,
\end{equation*}where $n \geq 0$.

The sequence $\left(a_n \right)_{n \geq 0}$ is equal to Heinz's sequence, entry $A224776$ of \cite{OEIS}. Indeed, they satisfy the same recurrence relation and the same initial case (see Proposition \ref{Propo_rec} and $A224776$ of \cite{OEIS}). According to Theorem \ref{Th_rec}, we can add that Heinz's sequences satisfies
\begin{align*}
a_{n} = \left\{
\begin{array}{ll}
  1  & \text{if  } n = 0; \\
  \sum\limits_{k = 1}^{n} (-1)^{k+1} q(n,k) a_{n-k} & \text{if } n\geq 1;\\
  0  & \text{otherwise}.
\end{array}
\right.
\end{align*}
where $q(n,k) = \sum\limits_{\ell = 1}^{k} \binom{n+1+\ell-2k}{k} \binom{k}{\ell}$. The sequence $\left( q(n+2k-1,k) \right)_{k \geq 0}$ is known as the crystal ball sequence for the $n$-dimensional cubic lattice \cite{Co97}.
\end{application*}


\subsection{Closed formulas}

In this section, we restrict ourselves to the case $d = 1$. Which means that the set of generators $\mathbb{G}$ is
\begin{equation*}
\left\{
\begin{tikzpicture}[scale = 1, baseline = {([yshift=-.8ex]current bounding box.center)}]
  \bloc{0,0}{1,0.5}{$1$}
  \draw(0.1,0)--(0.1,-0.25);
  \draw(0.1,0.5)--(0.1,0.75);
  
  \draw(0.9,0)--(0.9,-0.25);
  \draw(0.9,0.5)--(0.9,0.75);
  
  \node at (0.53,0.65) {$\cdots$};
  \node at (0.53,-0.15) {$\cdots$};
  
  \node at (0.5,1.15) {$\beta$};
  \draw (0,0.75) arc(180:90:.1) -- (0.4, 0.85) arc(-90:0:.1);
  \draw (1,0.75) arc(0:90:.1) -- (0.6, 0.85) arc(270:180:.1);
  
  \node at (0.5,-0.65) {$\alpha$};
  \draw (0,-0.25) arc(-180:-90:.1) -- (0.4, -0.35) arc(90:0:.1);
  \draw (1,-0.25) arc(0:-90:.1) -- (0.6, -0.35) arc(-270:-180:.1);
 
\end{tikzpicture}\, , \dots,  \begin{tikzpicture}[scale = 1, baseline = {([yshift=-.8ex]current bounding box.center)}]
  \bloc{0,0}{1,0.5}{$m$}
  \draw(0.1,0)--(0.1,-0.25);
  \draw(0.1,0.5)--(0.1,0.75);
  
  \draw(0.9,0)--(0.9,-0.25);
  \draw(0.9,0.5)--(0.9,0.75);
  
  \node at (0.53,0.65) {$\cdots$};
  \node at (0.53,-0.15) {$\cdots$};
  
  \node at (0.5,1.15) {$\beta$};
  \draw (0,0.75) arc(180:90:.1) -- (0.4, 0.85) arc(-90:0:.1);
  \draw (1,0.75) arc(0:90:.1) -- (0.6, 0.85) arc(270:180:.1);
  
  \node at (0.5,-0.65) {$\alpha$};
  \draw (0,-0.25) arc(-180:-90:.1) -- (0.4, -0.35) arc(90:0:.1);
  \draw (1,-0.25) arc(0:-90:.1) -- (0.6, -0.35) arc(-270:-180:.1);
 
\end{tikzpicture} 
\right\}
\end{equation*}
In this case the number of outputs of a prograph is determined by the other parameters. Indeed, the prographs with $e$ inputs and $n$ generators from the set $\mathbb{G}$ necessarily have $ e + (\beta - \alpha) n$ outputs, because a generator from $\mathbb{G}$ removes $\alpha$ outputs and creates $\beta$ outputs. So in this section we study the terms
\begin{equation*}
a_n := \left|PP_{e, \, n, \, e + (\beta - \alpha) n, \, e + (\beta - \alpha) n}(\mathbb{G})\right| = \left|PG_{e, \, e + (\beta - \alpha) n, \, n}(\mathbb{G})\right|.
\end{equation*}
\begin{exemple} We discovered thanks to the OEIS \cite{OEIS} that for $m = 1,\, \alpha = 2,\, \beta = 3$ and $e = 2$ the prographs are in bijection with tandem duplication trees \cite{Ga05}. Precisely, for all $n \geq 0$,
\begin{equation*}
\left|PG_{2,2+n,n}\left(\left\{ \begin{tikzpicture}[scale = 0.6, baseline = {([yshift=-.8ex]current bounding box.center)}]
  \bloc{0,0}{1,0.5}{}
  \draw(0.3,0)--(0.3,-0.35);
  \draw(0.7,0)--(0.7,-0.35);
  \draw(0.2,0.5)--(0.2,0.85);
  \draw(0.5,0.5)--(0.5,0.85);
  \draw(0.8,0.5)--(0.8,0.85);
  
\end{tikzpicture} \right\}\right)\right|
\end{equation*} is equal to the number of rooted tandem duplication trees on $n+1$ gene segments. Indeed, they satisfy the same recurrence relation and the same initial case (see Proposition \ref{Propo_rec} and \cite{Ga03}).
\end{exemple}

\begin{theorem} 
$a_n = m^n det\left(\binom{e - i(\alpha-1)+(j-1)(\beta -1)}{i-j+1}_{(i,j) \in [n]^2}\right)$.
\end{theorem}

\begin{proof}
In the particular case $d = 1$, Theorem \ref{Th_rec} can be reformulated in terms of matrices as follows: $A [a_0, \dots, a_n]^t = [1, 0, \dots, 0]^t$, where $A_{i,j} = (-1)^{i-j}m\binom{e + (i+1)(\alpha -1) + j(\beta -1)}{i-j}$.\\
According to Cramer's rule, $a_n = \frac{A_{n+1}}{det(A)}$, where $A_{n+1}$ is the matrix $A$ 
whose last column is replaced by the vector $[1, 0, \dots, 0]$. Knowing that $det(A) = 1$, by developing according to the last column we get $a_n = (-1)^n B$, where $B$ is the determinant of $\left((-1)^{i-j}m\binom{e - i(\alpha-1)+(j-1)(\beta -1)}{i-j+1}_{(i,j) \in [n]^2}\right)$.
Multiplying all odd index lines and all even index columns of the determinant $B$ by $-1$ gives the formula.
\end{proof}


\begin{theorem}
$a_n = m^n \sum\limits_{k \geq 1} (-1)^{n+k} \sum\limits_{\substack{t_1 + \dots + t_k = n\\t_i \neq 0}} \prod\limits_{j = 1}^{k} \binom{(\beta-\alpha ) \left(t_1 + \dots + t_{j-1}  \right)+e-(\alpha-1)t_j}{t_j}$.
\end{theorem} 

\begin{proof}
For $i \in [n-1]$ we denote by $A_i$ the set 
\begin{equation*}
\mathcal{L}\left( \left( \left(D^* + U^* \right) \mathcal{W} \right)^{i} DD^* \mathcal{W} \left( \left(D^* + U^* \right) \mathcal{W} \right)^{n-i-1} U^*, (0,1,e), (n,s,s)\right)
\end{equation*} and by $E$ the set
\begin{equation*}
\mathcal{L}\left( \left( \left(D^* + U^* \right) \mathcal{W} \right)^{n} U^*, (0,1,e), (n,s,s) \right).
\end{equation*}
We have $a_n = \left|\bigcap\limits_{i = 1}^{n-1} A_i\right| = |E|-\left|\bigcup\limits_{i = 1}^{n-1} A_i\right|$ and according to the inclusion–exclusion principle
\begin{equation*}
\left|\bigcup\limits_{k = 1}^{n-1} A_k\right| = \sum\limits_{k \geq 1}^{n-1} (-1)^{k-1} \Omega_k,
\end{equation*}
where $\Omega_k$ is the cardinality of the $k$-tuple-wise intersection of sets $A_1,\dots,A_{n-1}$.

If for $k \in [n-1]$ we denote by $ A_{t_1, \dots, t_{k}}$ the set
\begin{equation*}
\mathcal{L} \left(U^* \, [\mathcal{W},DD^*]^{t_1} \left(DD^* + U^* \right)[ \mathcal{W},DD^*]^{t_2} \cdots [ \mathcal{W},DD^*]^{t_{k}}\,U^*, (0,1,e),(n,s,s) \right)
\end{equation*}
where for $v \in \mathbb{N}_{\geq 1}$, $[\mathcal{W},DD^*]^{v}$ is $(\mathcal{W} DD^*)^{v-1} \mathcal{W}$, then $\Omega_k$ can be rewritten as
\begin{equation*}
\sum\limits_{\substack{t_1 + \dots + t_{n-k} = n\\t_i \neq 0}} | A_{t_1, \dots, t_{n-k}} |
\end{equation*}
and $E$ as $A_{\underbrace{1,\dots, 1}_{n}}$. Moreover, by the change of variable $k \leftarrow n-k$, we obtain
\begin{equation*}
a_n = \sum\limits_{k = 1}^{n} (-1)^{n+k}  \sum\limits_{\substack{t_1 + \dots + t_k = n\\t_i \neq 0}} |A_{t_1, \dots, t_{k}}|.
\end{equation*}
But $|A_{t_1, \dots, t_{k}}|$ is equal to
\begin{equation*}
\prod\limits_{j = 1}^{k} \left|\mathcal{L}\left( D^* [W,DD^*]^{t_j} D^*, p(j), p(j+1) \right)\right|
\end{equation*}
where $p(j) = \left(\sum\limits_{\ell = 1}^{j-1} t_\ell, e + \sum\limits_{\ell = 1}^{j-1} t_\ell (\beta - \alpha),e + \sum\limits_{\ell = 1}^{j-1} t_\ell (\beta - \alpha)\right)$
so with a computation similar to (\ref{L}) we obtain that $|A_{t_1, \dots, t_{k}}|$ equals
\begin{equation*}
\prod\limits_{j = 1}^{k} \binom{e+ (\beta-\alpha ) \left(t_1 + \dots + t_{j-1}  \right)-(\alpha-1)t_j}{t_j}.
\end{equation*} 
\end{proof}


\section*{Conclusion and perspectives}

We believe that prographs can encode or model structures that are not captured by the classical combinatorics on trees. To measure the expressive power of prographs, we propose to study their generating series. Formally, given a set of generators $\mathbb{G}$, we wonder in which class (rational, algebraic, D-finite, D-algebraic,$\dots$ \cite{Stanley}) the series
\begin{equation} \label{serie}
\varphi(\mathbb{G}) := \sum\limits_{e, n, s \geq 0} \left| PG_{e,s,n}(\mathbb{G}) \right| x^n y^e z^s = \sum\limits_{e, n, s \geq 0} \left| PP_{e,n,s,s}(\mathbb{G}) \right|  x^n y^e z^s
\end{equation}
belongs to. We noticed that the families of paths in bijection with prographs are part of the paths studied by \cite{MBM00} and we computed a functional equation satisfied by (\ref{serie}). A study of the singularities of (\ref{serie}) might conclude that it is not D-finite in most cases.


Another generalization that we have not explored is the extension of the combinatorial study to prographs made of generators without inputs or outputs.



\acknowledgements{I thank Samuele Giraudo for introducing me to the
subject and for his supervision. I would like to thank Mireille
Bousquet-M\'elou for her comments on path enumeration. I also thank Nicolas Borie and of course my thesis director Jean-Christophe Novelli for his feedback.}

%% 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}
