# Generalized tableaux over arbitrary digraphs and their associated
differential equations

Luis Martínez University of the Basque Country (UPV/EHU),
Department of Mathematics, Spain
Antonio Vera López, University of the Basque Country (UPV/EHU),
Department of Mathematics, Spain
Antonio Vera Pérez, PLD Space, Nicolás Copérnico 7, Elche, Spain
Beatriz Vera Pérez, Catholic University of Murcia, Murcia, Spain
Olga Basova, University of the Basque Country (UPV/EHU),
Department of Mathematics, Spain Luis Martínez is supported by the UPV/EHU and
Basque Center of Applied Mathematics, grant US21/27.

###### Abstract

We revisit the concepts of acyclic orderings and number of acyclic orderings
of acyclic digraphs in terms of dispositions and counters for arbitrary
multidigraphs. We prove that when we add a sequence of nested directed paths
to a directed graph there is a unique polynomial such that the generatrix
function of the family of counters is the product of the polynomial and the
exponential function. We give an application, by considering a kind of
digraphs arranged in rows introduced by the authors in a previous paper,
called dispositional digraphs, in the particular case in which the digraph has
two rows, to obtain new families of linear differential equations of small
order whose coefficients are polynomials of small degree which admit
polynomial solutions. In particular, we obtain a new differential equation
associated to Catalan numbers, and the corresponding associated polynomials,
which are solution of this differential equation; we term them Catalan
differencial equation and Catalan polynomials, respectively. We prove that the
Catalan polynomials obtained when we connect the directed path to the second
vertex of the lower row of the digraph are orthogonal polynomials for an
appropriate weight function. We characterize the digraphs that maximize the
counter of connected dispositional digraphs and we find a new differential
equation associated to these digraphs. We introduce also dispositions and
counters in any multidigraph with non-strict inequalities in the dispositions,
and we find new differential equations associated to some of them.

Corresponding author: Luis Martínez
University of the Basque Country (UPV/EHU)
Faculty of Science and Technology, Department of Mathematics
Leioa, Spain, 48940
TEL: +34 946012651
Email<EMAIL_ADDRESS>
##  1 Introduction

Young Tableaux are an important mathematical concept. They have applications
to several areas of Combinatorics, since for instance Graph Theory
([2],[17],[20]), Matroid Theory ([9]), enumeration of matrices with non-
negative entries ([13]), longest increasing subsequences ([19]), and
tournaments ([30]).

They are applied also in pure Group Theory, for instance in Representation
Theory of Groups ([6],[12],[21]).

Their applications are not limited to pure mathematics, and Young Tableaux are
used also in other fields of science such as chemistry ([7],[15]), nuclear
physics ([4],[16],[18]), Population Genetics ([5]), or robotics ([8]).

In particular, Vera-López et al. introduced in [27] a class of tableaux
arranged in two rows related to a new generalization of Catalan numbers, and
they applied their results to advance in the study of Higman’s conjecture.
Vera-López, Martínez et al. enlarged the family of digraphs to which these
tableaux can be associated in [28], where they introduced dispositional
digraphs and their corresponding counters, relating them also to Higman’s
conjecture.

The motivation to write this paper was threefold. First, we wanted to deep in
the study of the mentioned dispositional digraphs, obtaining an structural
characterization of the connected ones for which their counter takes the
maximum value. Second, we wanted to generalize the kind of digraphs to which
these techniques can be applied, admitting any multidigraph and admitting two
scenarios, one in which we consider strict inequalities in the calculus of the
counters, and another one in which we consider non-strict inequalities. Third,
we wanted to associate differential equations to arbitrary digraphs, making
the equation depend on the selection of the digraph and of a given vertex, and
to give a method to obtain polynomial solutions of these equations.

Specifically, we present in this paper a connection of differential equations
with tableaux in which the latest ones are given with the maximum generality,
introducing these tableaux over arbitrary multidigraphs, and associating
recursively to them a number that we term the counter of the multidigraph. The
connection between both areas is established associating a polynomial to each
simple digraph with a distinguished vertex, which we call the companion
polynomial of the digraph (and consequently of the tableau) at the vertex.

This way we can obtain a library of differential equations with polynomial
solutions that are obtained from the counters of the corresponding associated
digraphs.

In Section 2 we first recall some basic definitions in graph theory, and after
that we give the general setting of these generalized tableaux and some
properties of counters, and we calculate the counter of some of these
digraphs. We introduce also staircase digraphs and prove that their counters
are maximal among the ones of connected dispositional digraphs.

In Section 3 we give our main result, that when we plug a sequence of directed
paths to a vertex of the digraph there exists a polynomial, which we call the
companion polynomial of the digraph at the vertex, so that the generatrix
function of the sequence of counters is the product of the polynomial and the
exponential function.

In Section 4 we introduce the connection of companion polynomials of digraphs
with differential equations, so that we can establish a library of
differential equations that can be solved in a discrete way using the counters
of directed graphs.

In Section 5 we study a family of new differential equations corresponding to
certain digraphs arranged in two rows, distinguishing among them a subfamily
that we call Catalan differential equation, and in Section 6 we analyze
another family of new differential equations corresponding to extremal
dispositional digraphs whose counters take the maximum value.

Finally, in Section 7 we present, again with the maximum generality, tableaux
in which the dispositions correspond to non-strict inequalities, and we obtain
new differential equations associated to some of their counters.

##  2 Dispositions and counters

###### Definition 1

A directed graph (or, more briefly, a digraph) is a pair $(V,A)$, where $V$ is
a set and $A\subseteq X\times X$. The cardinalities of $V$ and $A$ are called
the order and size, respectively, of the digraph. The elements of $V$ and $A$
are called vertices and arcs, respectively.

More generally, if we take a multiset contained in $X\times X$, that is, if we
contemplate the possibility of having multiple arcs, we will speak of a
multidigraph. Pairs of the form $(x,x)$ are called loops. We will say that a
multidigraph is simple if it has no loops and no arcs with multilicity greater
than $1$. In this case we say, more briefly, that it is a simple digraph.

###### Definition 2

A subdigraph of a digraph $(V,A)$ is a digraph $(V^{\prime},A^{\prime})$ with
$V^{\prime}\subseteq V$ and $A^{\prime}\subseteq A$. The subdigraph of $(V,A)$
induced by a subset $V^{\prime}$ of $V$ is the subdigraph
$(V^{\prime},A^{\prime})$ with

$A^{\prime}=\\{(u,v)\mid u,v\in V^{\prime},(u,v)\in A\\}.$

We will say that a subdigraph of $(V,A)$ is an induced subgraph if it is
induced by $V^{\prime}$ for some subset $V^{\prime}$ of $V$.

###### Definition 3

If $\mathfrak{G}=(V,A)$ is a digraph and $v\in V$, then $\mathfrak{G}-v$ will
denote the subdigraph induced by $V-\\{v\\}$.

###### Definition 4

The reverse of a digraph $\mathfrak{G}=(V,A)$ is the digraph
$\mathfrak{G}^{r}=(V,A^{\prime})$, where

$A^{\prime}=\\{(v,u)\mid(u,v)\in A\\}.$

###### Definition 5

A digraph with vertex set $\\{v_{1},\dots,v_{n}\\}$ and arc set
$\\{(v_{1},v_{2}),\dots,(v_{n-1},v_{n})\\}$ is called a directed path of order
$n$, and is denoted by $P_{n}$.

###### Definition 6

A digraph with vertex set $\\{v_{1},\dots,v_{n}\\}$ and an empty arc set is
called an empty digraph of order $n$, and is denoted by $E_{n}$.

###### Definition 7

A directed closed walk in a digraph $\mathfrak{G}=(V,A)$ is a sequence of
vertices and arcs

$v_{1},(v_{1},v_{2}),v_{2},\dots,v_{n-1},(v_{n-1},v_{n}),v_{n},(v_{n},v_{1}),v_{1}$

In practice the arcs are understood and only the vertices are indicated, and
the final vertex, which is the same as the initial one, is ommitted, and one
writes just $v_{1},\dots,v_{n}$

Obviously, any vertex $v_{i}$ can be taken to be the initial vertex of the
directed closed walk.

###### Definition 8

Let $\mathfrak{G}=(V,A)$ be a digraph, $\mathfrak{R}$ an equivalence relation
on $V$, $\overline{V}$ the quotient set formed by the equivalence classes and,
for $v\in V$, let $\overline{v}$ be the equivalence class represented by $v$.
The quotient digraph $\mathfrak{G}/\mathfrak{R}$ of $\mathfrak{G}$ by the
relation $\mathfrak{R}$ is the digraph $(\overline{V},\overline{A})$, where

$\overline{A}=\\{(\overline{u},\overline{v})\mid(u,v)\in A\\},$

in which the loops are removed and multiple arcs with multiplicity greater
than $1$ are substituted by a single arc.

###### Proposition 1

Let $\mathfrak{G}=(V,A)$ be a digraph. The relation on $V$ defined by

$u\mathfrak{R}v\text{ if }u\text{ and }v\text{ are in a directed closed walk}$

is an equivalence relation.

Proof. If $v\in V$ then $v$ and $v$ are in the trivial directed closed walk
formed just by $v$. If $u,v$ are in a directed closed walk, then also $v,u$
are in that directed closed walk. If $u,v$ are in a directed closed walk
$\mathfrak{W}_{1}$ and $v,w$ are in a directed closed walk $\mathfrak{W}_{2}$,
then $u,w$ are in the directed closed walk obtained concatenating both
directed closed walks by the vertex $v$.

If $\mathfrak{R}$ is as in the previous proposition, it is evident that
$\mathfrak{G}/\mathfrak{R}$ is a digraph without non-trivial directed closed
walks. It is called in the literature the strong component digraph ([1]).

###### Definition 9

If $\mathfrak{G}_{1}=(V_{1},A_{1})$ and $\mathfrak{G}_{2}=(V_{2},A_{2})$ are
digraphs such that $|V_{1}\cap V_{2}|\leq 1$ then

$\mathfrak{G}_{1}+\mathfrak{G}_{2}=(V_{1}\cup V_{2},A_{1}\cup A_{2}).$

Observe that the order of $\mathfrak{G}_{1}+\mathfrak{G}_{2}$ can be
$|V_{1}|+|V_{2}|$ or $|V_{1}|+|V_{2}|-1$, depending on if $V_{1}$ and $V_{2}$
are disjoint or they share a vertex.

###### Definition 10

Let $\mathfrak{G}=(V,A)$ be a multidigraph of order $n$. A disposition in
$\mathfrak{G}$ is a biyective mapping $f:V\longrightarrow\\{1,\dots,n\\}$ such
that $f(v_{1})>f(v_{2})$ whenever $(v_{1},v_{2})\in A$.

If $\mathfrak{G}$ is as above, then the set of dispositions will be denoted by
$\Sigma(\mathfrak{G})$, and its cardinality by $\sigma(\mathfrak{G})$. The
number $\sigma(\mathfrak{G})$ will be called the counter of $\mathfrak{G}$.

We will call Young tableaux over the multidigraph $\mathfrak{G}$ to the
triplet

$(\mathfrak{G},\Sigma(\mathfrak{G}),\sigma(\mathfrak{G})).$

Note that some authors (and in particular the authors of the present paper in
[28]) use the reverse ordering $f(v_{1})<f(v_{2})$ in the definition of
dispositions (in [1] Bang-Jensen and Gutin call them acyclic orderings and
mention that they are often called topological sortings. It is worthy to note
also that, when viewing an acyclic digraph as a partial order, acyclic
orderings of the digraph correspond bijectively to ‘linear extensions’ of the
corresponding partial order). We think that Definition 10 is more intuitive,
since the arrow symbol in the arcs resembles the inequality sign. Besides, in
the end there is no difference with respect to the value of the counter
because, as we will see later in Proposition 5, the counter of a digraph is
the same as the one of its reverse.

If the multidigraph $\mathfrak{G}=(V,A)$ has a loop at vertex $v$, then no
disposition exists, because as $(v,v)\in A$, if $f$ was a disposition we would
have $f(v)>f(v)$. Consequently, $\sigma(\mathfrak{G})=0$ in this case.

Also, if $a\in A$ is a multiarc with multiplicity $m>1$, then it is obvious
that if we replace the $m$ parallel arcs by a single arc the counter does not
change.

Hence, from now on we will consider simple digraphs, that is, multidigraphs
without loops or multiple arcs (we will omit, by abuse of notation, the term
‘simple’, and we will say just ‘digraphs’).

###### Definition 11

If $\mathfrak{G}=(V,A)$ is a digraph, we will say that a vertex $u\in V$ is a
minimum point of $\mathfrak{G}$ if it does not exists any $v\in V-\\{u\\}$
with $(u,v)\in A$. We will denote by $\min(\mathfrak{G})$ the set of minimum
points of $\mathfrak{G}$. Similarly, we will say that a vertex $v\in V$ is a
maximum point of $\mathfrak{G}$ if it does not exists any $u\in V-\\{v\\}$
with $(u,v)\in A$. We will denote by $\max(\mathfrak{G})$ the set of maximum
points of $\mathfrak{G}$.

In the theory of digraphs minimum points and maximum points are usually called
sinks and sources, respectively ([1]).

###### Theorem 1

  1. 1.

$\sigma(\mathfrak{G})=\sum_{u\in\min(\mathfrak{G})}\sigma(\mathfrak{G}-u).$

  2. 2.

$\sigma(\mathfrak{G})=\sum_{v\in\max(\mathfrak{G})}\sigma(\mathfrak{G}-v).$

We will use the following lemma to prove the theorem. Before stating the
lemma, we will establish the following notation: if $\mathfrak{G}=(V,A)$ is a
digraph of order $n$, and if $v\in V$ is a maximum point and $f$ is a
disposition of $\mathfrak{G}-\\{v\\}$, then $f+(v\to n)$ is the mapping from
$V$ to $\\{1,\dots,n\\}$ defined by $(f+(v\to n))(w)=f(w)$ whenever $w\not=v$
and $(f+(v\to n))(v)=n$, and if $D$ is a set of dispositions of
$\mathfrak{G}-\\{v\\}$, then

$D+(v\to n)=\\{f+(v\to n)\mid f\in D\\}.$

We define similarly $f+(u\to 1)$ when $u$ is a minimum point by $(f+(u\to
1))(w)=f(w)+1$ whenever $w\not=u$ and $(f+(u\to 1))(u)=1$, and

$D+(u\to 1)=\\{f+(u\to 1)\mid f\in D\\}.$

###### Lemma 1

If $\mathfrak{G}$ is a digraph of order $n$, then

  1. 1.

$\Sigma(\mathfrak{G})=\dot{\bigcup}_{u\in\min(\mathfrak{G})}(\Sigma(\mathfrak{G}-u)+(u\to
1)).$

  2. 2.

$\Sigma(\mathfrak{G})=\dot{\bigcup}_{v\in\max(\mathfrak{G})}(\Sigma(\mathfrak{G}-v)+(v\to
n)).$

Proof. We will prove it for the set of maximum points, being the proof similar
for minimum points. If $f\in\Sigma(\mathfrak{G}-v)$, then $f+(v\to
n)\in\Sigma(\mathfrak{G})$ because, as $v$ is a maximum point, $f+(v\to n)$ is
a disposition in $\mathfrak{G}$. Reciprocally, if $f$ is a disposition in
$\mathfrak{G}$, as $f$ is biyective, there is a unique vertex $v$ such that
$f(v)=n$, and $v$ must be obviously a maximum point. Besides,
$f=f^{\star}+(v\to n)$, where $f^{\star}$ is the restriction of $f$ to
$V-\\{v\\}$. This proves that

$\Sigma(\mathfrak{G})=\bigcup_{v\in\max(\mathfrak{G})}(\Sigma(\mathfrak{G}-v)+(v\to
n)).$

It is obvious that the union is disjoint, because if
$f\in(\Sigma(\mathfrak{G}-v_{1})+(v_{1}\to
n))\cap(\Sigma(\mathfrak{G}-v_{2})+(v_{2}\to n))$ with $v_{1}\not=v_{2}$, then
$f(v_{1})=n$ and $f(v_{2})=n$, and this contradicts the injectivity of $f$.

Now we will prove the theorem:

Proof. It is a direct consequence of the lemma (which allows us in passing to
obtain all the dispositions in an iterative way), using the fact that the
cardinality of a disjoint union of finite sets is the sum of the cardinalities
of the sets.

###### Proposition 2

If $\mathfrak{G}$ is a digraph, then $\sigma(\mathfrak{G})>0$ if and only if
$\mathfrak{G}$ has no non-trivial directed closed walk.

Proof. If $\mathfrak{G}$ had a non-trivial directed closed walk
$v_{1},\dots,v_{n}$ and $f$ was a disposition we would conclude that
$f(v_{1})>f(v_{1})$, which leads to a contradiction, and thus
$\sigma(\mathfrak{G})=0$. Conversely, we will prove by induction on the order
$n$ of $\mathfrak{G}$ that if $\mathfrak{G}$ has no non-trivial directed
closed walk, then $\sigma(\mathfrak{G})>0$. It is trivially true if $n=1$,
because in that case $\sigma(\mathfrak{G})=1$. Let us suppose that it is true
when the order is $n-1$, and let $n>1$. Since $\mathfrak{G}$ has no non-
trivial directed closed walk, $\min(\mathfrak{G})\not=\emptyset$, and now the
result follows from Theorem 1 by using the inductive hypothesis.

If $\mathfrak{G}$ has no non-trivial directed closed walk, then the transitive
clausure of the relation associated to the graph is a partial order, and the
dispositions and counters can be interpreted in terms of
$(P,\omega)$-partitions ([3],[23]).

###### Proposition 3

If $\mathfrak{G}^{\prime}=(V,A^{\prime})$ is a subdigraph of a digraph
$\mathfrak{G}=(V,A)$, then

$\sigma(\mathfrak{G})\leq\sigma(\mathfrak{G}^{\prime}).$

Proof. Let $n$ be the order of $\mathfrak{G}$. If
$f:V\longrightarrow\\{1,\dots,n\\}$ is a disposition in $\mathfrak{G}$, then
$f$ is also a disposition in $\mathfrak{G}^{\prime}$.

###### Proposition 4

$\sigma(P_{n})=1\ \forall n\in\mathbb{N}$.

Proof. We will prove it by induction in $n$. It is obvious for $n=1$. Let us
suppose that it is true for $n-1$. By Theorem 1,
$\sigma(P_{k})=\sigma(P_{k-1})$, and now the result follows from the inductive
hypothesis.

###### Proposition 5

If $\mathfrak{G}$ is a digraph, then
$\sigma(\mathfrak{G})=\sigma(\mathfrak{G}^{r})$.

Proof. It can be immediately proved by induction on the order of
$\mathfrak{G}$, using Theorem 1 and having into account that
$\min(\mathfrak{G})=\max(\mathfrak{G}^{r})$ and
$\max(\mathfrak{G})=\min(\mathfrak{G}^{r})$.

###### Theorem 2

If $\mathfrak{G}=(V,A)$ is a digraph and
$\mathfrak{G}_{1}=(V_{1},A_{1}),\dots,\mathfrak{G}_{r}=(V_{r},A_{r})$ are the
connected components of the underlying undirected graph, of orders
$n_{1},\dots,n_{r}$, respectively, then

$\sigma(\mathfrak{G})=\binom{n_{1}+\dots+n_{r}}{n_{1},\dots,n_{r}}\sigma(\mathfrak{G}_{1})\cdots\sigma(\mathfrak{G}_{r}).$

Proof. First, let us observe that, if we generalize Definition 10 changing
$\\{1,\dots,n\\}$ to any set $S$ of $n$ natural numbers, where $n$ is the
order of $\mathfrak{G}$, then the counter $\sigma(\mathfrak{G})$ does not
change, because Theorem 1 continues being true. Let us put
$S=\\{1,\dots,n_{1}+\dots+n_{r}\\}$. If $f:V\longrightarrow S$ is a
disposition in $\mathfrak{G}$ and if $S_{i}=f(V_{i})$ for $i=1,\dots,r$, then
$f_{|V_{i}}$ is a disposition in $\mathfrak{G}_{i}$ for every $i$, and the
sets $S_{1},\dots,S_{r}$ form a partition of $S$. Reciprocally, if
$S_{1},\dots,S_{r}$ is a partition of $S$ with $|S_{i}|=n_{i}\ \forall
i\in\\{1,\dots,r\\}$, and if $f_{i}:V_{i}\longrightarrow S_{i}$ is a
disposition in $\mathfrak{G}_{i}\ \forall i\in\\{1,\dots,r\\}$, then it is
obvious that the mapping $f:V\longrightarrow S$ defined by $f(v)=f_{i}(v)$
where $i$ is the only index satisfying that $v\in S_{i}$, is a disposition in
$\mathfrak{G}$. Now the conclusion of the theorem follows immediately.

###### Corollary 1

$\sigma(E_{n})=n!\ \forall n\in\mathbb{N}$.

Proof. The digraph $E_{n}$ has $n$ connected components, and the counter of
each one of them is $1$.

###### Definition 12

Let $S=\\{\mathfrak{G}_{i}\\}_{i\in\mathbb{Z}^{+}}$, where
$\mathbb{Z}^{+}=\\{i\in\mathbb{Z}\mid i\geq 0\\}$, be a sequence of digraphs
such that $\mathfrak{G}_{i}$ is a subdigraph of $\mathfrak{G}_{i+1}$ for every
$i$. We will call generatrix function of $S$ to

$F_{S}(X)=\sum_{i=0}^{\infty}\frac{\sigma(\mathfrak{G}_{i})}{i!}X^{i}.$

###### Proposition 6

$F_{\\{P_{i+1}\\}_{i\in\mathbb{Z}^{+}}}(X)=\exp(X)$.

Proof. Use Proposition 4 and the MacLaurin expansion of the exponential
function.

###### Definition 13

A tree is a conected acyclic graph. A rooted tree is a tree in which a vertex
is selected. This vertex is called the root of the rooted tree.

We can give a natural orientation to the edges of a rooted tree, where the
origin of the arc is the vertex of the edge that is closest to the root, so
that we can associate a digraph to the tree. If $\mathfrak{T}$ is a rooted
tree with root $v$, then $\mathfrak{T}-v$ is the disjoint union of $k$ rooted
trees $\mathfrak{T}_{1},\dots,\mathfrak{T}_{k}$, where $k$ is the degree of
$v$ and where, if $\\{v_{1},\dots,v_{k}\\}$ is the neighbourhood of $v$ in
$\mathfrak{T}$, then $v_{i}$ is the root of $\mathfrak{T}_{i}$. We will call
$\mathfrak{T}_{1},\dots,\mathfrak{T}_{k}$ the descendants of $\mathfrak{T}$.

###### Proposition 7

If $\mathfrak{T}$ is a rooted tree with $k$ descendants
$\mathfrak{T}_{1},\dots,\mathfrak{T}_{k}$ of orders $n_{1},\dots,n_{k}$,
respectively, then

$\sigma(\mathfrak{T})=\binom{n_{1}+\dots+n_{k}}{n_{1},\dots,n_{k}}\sigma(\mathfrak{T}_{1})\cdot\dots\cdot\sigma(\mathfrak{T}_{k}).$

Proof. Use Theorem 1 and, after that, Theorem 2 with the digraph associated to
$\mathfrak{T}-v$.

###### Corollary 2

Let $q\geq 2$ be a natural number. Let $\mathfrak{T}^{(q)}$ denote the $q$-ary
tree and, for $n\in\mathbb{N}$, let $\mathfrak{T}^{(q)}_{n}$ denote the
$n$-level of $\mathfrak{T}^{(q)}$. Then,

$\sigma(\mathfrak{T}^{(q)}_{1})=1$

and

$\sigma(\mathfrak{T}^{(q)}_{n+1})=\binom{\frac{q(q^{n}-1)}{q-1}}{\frac{q^{n}-1}{q-1},\dots,\frac{q^{n}-1}{q-1}}\sigma(\mathfrak{T}^{(q)}_{n})^{q}$

for $n\in\mathbb{N}$.

For $q=2$ the numbers obtained in the previous corollary correspond to
sequence A056972 in Sloane’s on-line encyclopedia of integer sequences ([29]).

For $q=3$ they correspond to sequence A273723.

We introduce now a family of directed graphs, the staircase digraphs:

###### Definition 14

Let $n\in\mathbb{N}$. We define the staircase digraph $\mathfrak{S}_{n}$ to be
the digraph with vertex set $V_{n}=\\{v_{1},\dots,v_{n}\\}$ and arc set
$A_{n}=\\{(v_{1},v_{2}),(v_{3},v_{2}),(v_{3},v_{4}),(v_{5},v_{4}),\dots\\}=\\{(v_{2i+1},v_{2i+2})\mid
0\leq i\leq\lfloor\frac{n-2}{2}\rfloor\\}\cup\\{(v_{2i-1},v_{2i-2})\mid 2\leq
i\leq\lfloor\frac{n+1}{2}\rfloor\\}$.

We will denote by $s_{n}$ the counter of $\mathfrak{S}_{n}$.

We show the staircase digraph $\mathfrak{S}_{5}$ in the following figure:

Figure 1: Staircase digraph of order $5$

The following result holds trivially and its proof will be omitted.

###### Proposition 8

$\min(\mathfrak{S}_{n})=\\{v_{2i}\mid 1\leq
i\leq\lfloor\frac{n}{2}\rfloor\\}=V_{n}\cap\\{v_{i}\mid i\in 2\mathbb{N}\\},$
$\max(\mathfrak{S}_{n})=\\{v_{2i+1}\mid 0\leq
i\leq\lfloor\frac{n-1}{2}\rfloor\\}=V_{n}\cap\\{v_{i}\mid i\in
1+2\mathbb{N}\\}.$

By convenience we will consider also the case $n=0$. In this case
$\mathfrak{S}_{0}$ is the void digraph and $\sigma(\mathfrak{S}_{0})=1$,
because the only disposition is the void mapping (this may sound strange at
first sight, but it will be justified when we study the generating function of
this family of digraphs, and it is also a convey for the case $i=\frac{n}{2}$
in the first part of the following theorem and for $i=0$ or $i=\frac{n-1}{2}$
in the second part).

###### Theorem 3

If $n\geq 2$, then

$s_{n}=\sum_{1\leq i\leq\lfloor\frac{n}{2}\rfloor}{n-1\choose
2i-1}s_{2i-1}s_{n-2i},$

and if $n\geq 1$, then

$s_{n}=\sum_{0\leq i\leq\lfloor\frac{n-1}{2}\rfloor}{n-1\choose
2i}s_{2i}s_{n-2i-1}.$

Proof. Use the previous proposition and Theorems 1 and 2.

The first 7 values of $s_{n}$, for $n$ from $0$ to $6$, are $1,1,1,2,5,16,61$.

For arbitrary $n$, they corresponds to sequence A000111 in [29], and they are
the Euler zigzag numbers. It is known by a result of André that the sequence
gives half the number of alternating permutations (this follows also
immediately from the definition of dispositions, because half of the
alternating permutations correspond to dispositions in $\mathfrak{S}_{n}$, and
the other half to dispositions in $\mathfrak{S}^{r}_{n}$). Euler zigzag
numbers have also interesting connections with quantum mechanics
([10],[11],[25])

The fact that the counters of staircase digraphs are the Euler zigzag numbers
has the following interpretation in terms of generatrix functions:

###### Theorem 4

$F_{\\{\mathfrak{S}_{i}\\}_{i\in\mathbb{Z}^{+}}}(X)=\sec(X)+\tan(X)$

By summing the two expressions for $s_{n}$ obtained in Theorem 3 we get the
following formula mentioned in [29]:

If $n\geq 1$, then

$2s_{n+1}=\sum_{k=0}^{n}{n\choose k}s_{k}s_{n-k}$

We introduced in [28] dispositional digraphs in the following way:

###### Definition 15

Let $m$ be a natural number and consider $n$ non-negative integers
$a_{1},\dots,a_{n}$ such that $a_{1}+\cdots+a_{n}=m$ and $n-1$ integer numbers
$b_{2},...,b_{n}$. We define the dispositional directed graph

$\mathcal{G}([a_{1},0],[a_{2},b_{2}],\dots,[a_{n},b_{n}])$ (1)

to be the digraph with $m$ vertices arranged vertically in $n$ rows of lengths
$a_{1},...,a_{n}$, respectively, where for each $i>1$ the $i$-th row is
shifted $b_{i}$ places to the right with respect to the previous one if
$b_{i}>0$, shifted $-b_{i}$ places to the left if $b_{i}<0$, and no shifted if
$b_{i}=0$. Moreover, the arcs go from each vertex to its neighbour on the
right in the same row, if there is any, and to its neighbour below in the next
row, if there is any.

Dispositional digraphs, and their associated counters, include a large number
of tableaux, such as, for example, Young tableaux of skew shape ([24]), which
are the classical Young tableaux, and also Young tableaux of shifted strips
with constant width ([3],[26],[28]).

Staircase digraphs are dispositional digraphs. In fact, if $n=2k$, then
$\mathfrak{S}_{n}$ is

$\mathcal{G}([2,0],[2,-1],\dots,[2,-1]),$

where $[2,-1]$ is repeated $k-1$ times, and if $n=2k+1$, then
$\mathfrak{S}_{n}$ is

$\mathcal{G}([1,0],[2,-1],\dots,[2,-1]),$

where $[2,-1]$ is repeated $k$ times. Moreover, all of them correspond to
Young tableaux of skew shape.

Next, we will prove that the connected dispositional digraphs with maximum
counter are precisely the staircase digraphs. This states and solves the
extremal directed graph theory problem of characterizing the structure of
connected induced subdigraphs of a given order $m$ of the cartesian product of
two directed paths with the maximum number of acyclic orderings (we would like
to settle also as an open problem the question of determining the connected
induced subdigraphs of a given order $m$ of the cartesian product of $k$
directed paths with the maximum number of acyclic orderings for a given $k\geq
3$ and determine the corresponding number of acyclic orderings):

###### Theorem 5

If

$\mathfrak{G}=\mathcal{G}([a_{1},0],[a_{2},b_{2}],\dots,[a_{n},b_{n}])$ (2)

is a dispositional digraph of order $m=a_{1}+\dots+a_{n}$ such that its
underlying undirected graph is connected, then $\sigma(\mathfrak{G})\leq
s_{m}$. Besides, the equality holds if and only if $\mathfrak{G}$ is
isomorphic to $\mathfrak{S}_{m}$ or to $\mathfrak{S}^{r}_{m}$.

We will use the following lemma:

###### Lemma 2

If $j\in\mathbb{Z}^{+}$, then

$s_{j}\leq{j\choose i}s_{i}s_{j-i}\ \forall i\in\\{0,\dots,j\\}.$

Proof. Use Theorem 2 and Proposition 3 with $\mathfrak{S}_{j}$ and the
subdigraph obtained removing the $i$-th arc.

Now we will prove the theorem.

Proof. Let $\mathfrak{U}(\mathfrak{G})$ be the underlying undirected graph
associated to $\mathfrak{G}$. If $v$ is a cut-vertex of
$\mathfrak{U}(\mathfrak{G})$ that is also a minimum point of $\mathfrak{G}$,
then its out-degree is $0$, by definition of minimum point, and its in-degree
could, in principle, be $1$ or $2$, because $\mathfrak{U}(\mathfrak{G})$ is
connected and hence the total degree of $v$ is positive. Let us suppose, for
the sake of contradiction, that it is $1$.

If there is an arc $(w,v)$, where $w$ is the preceeding vertex of $v$ in its
row, then we have the situation depicted in Figure 2 (a), and we deduce that
$\mathfrak{U}(\mathfrak{G})-v$ is connected, what contradicts that $v$ is a
cut-vertex.

If there is an arc $(w,v)$, where $w$ is the preceeding vertex of $v$ in its
column, then we have the situation shown in Figure 2 (b), and thus
$\mathfrak{U}(\mathfrak{G})-v$ is connected and we get again a contradiction.

(a)

(b)

Figure 2: In-degree 1. the oval in each part represents the dispositional
digraph induced by $V(\mathfrak{G})-\\{v\\}$

Therefore, the in-degree of $v$ is $2$ and the out-degree of $v$ is $0$, and
we are in the situation displayed in Figure 3 (a), so that
$\mathfrak{U}(\mathfrak{G})-v$ has two connected components, one of them
formed by the vertices in the rows above $v$, and the other one formed by the
columns to the left of $v$.

In a similar way, if $v$ is a cut-vertex of $\mathfrak{U}(\mathfrak{G})$ that
is also a maximum point of $\mathfrak{G}$, then we are in the situation
depicted in Figure 3 (b), and $\mathfrak{U}(\mathfrak{G})-v$ has two connected
components, one of them formed by the vertices in the columns to the right of
$v$, and the other one formed by the rows below $v$.

(a)

(b)

Figure 3: In-degree 2. the ovals in each part represent the connected
components of $V(\mathfrak{G})-\\{v\\}$

Let $CV$ be the set of cut-vertices of $\mathfrak{U}(\mathfrak{G})$ and

$S=(\min(\mathfrak{G})\cup\max(\mathfrak{G}))\cap CV.$

For each one of these vertices exactly one of the two configurations described
in Figure 3 holds.

If $v\in S$, we will call $\mathfrak{C}_{1}(v)$ to the connected component
containing the leftmost vertex in the first row, $\mathfrak{C}_{2}(v)$ to the
other connected component, and $c(v)$ to $|\mathfrak{C}_{1}(v)|$.

We can order lexicographically the vertices of $S$ so that if $v_{1}$ and
$v_{2}$ are distinct vertices in $S$, then $v_{1}\prec v_{2}$ if $v_{1}$ is in
a row upper than $v_{2}$ or if $v_{1}$ and $v_{2}$ are in the same row but
$v_{1}$ is in a column to the left of $v_{2}$ (of course, there can be at most
two vertices of $S$ in the same row). Obviously, if $v_{1}\prec v_{2}$, then
$c(v_{1})<c(v_{2})$.

Let $N=\\{c(v)\mid v\in S\\}$.

By Theorem 1,

$2\sigma(\mathfrak{G})=\sum_{u\in\min(\mathfrak{G})}\sigma(\mathfrak{G}-u)+\sum_{v\in\max(\mathfrak{G})}\sigma(\mathfrak{G}-v).$

This equals

$\sum_{u\in
S}\sigma(\mathfrak{G}-u)+\sum_{v\in(\min(\mathfrak{G})\cup\max(\mathfrak{G}))-CV}\sigma(\mathfrak{G}-v).$

By Theorem 2, the first summand equals

$\sum_{u\in S}{m-1\choose
c(u)}\sigma(\mathfrak{C}_{1}(u))\sigma(\mathfrak{C}_{2}(u)),$

and this is, by the inductive hypothesis, at most

$\sum_{n\in N}{m-1\choose n}s_{n}s_{m-1-n}.$

Now, by the inductive hypothesis,

$2\sigma(\mathfrak{G})\leq\sum_{n\in N}{m-1\choose
n}s_{n}s_{m-1-n}+|(\min(\mathfrak{G})\cup\max(\mathfrak{G}))-CV|s_{m-1}$

and, by Lemma 2, if $\\{1,\dots,m\\}-N=\\{n_{1},\dots,n_{k}\\}$, then

$2\sigma(\mathfrak{G})\leq\sum_{n\in N}{m-1\choose
n}s_{n}s_{m-1-n}+\sum_{i=1}^{|(\min(\mathfrak{G})\cup\max(\mathfrak{G}))-S|}{m-1\choose
n_{i}}s_{n_{i}}s_{m-1-n_{i}},$

and this is at most

$\sum_{i=0}^{m-1}{n\choose i}s_{i}s_{m-1-i},$

and the equality holds if and only if
$\min(\mathfrak{G})\cup\max(\mathfrak{G})=\\{1,\dots,m\\}$. In this case
maximum and minimum points alternate and go trough all the vertices of
$\mathfrak{G}$, and $\mathfrak{G}$ is isomorphic to $\mathfrak{S}_{m}$ or to
$\mathfrak{S}^{r}_{m}$.

The condition that the underlying undirected graph is connected is essential
and cannot be avoided. For instance, if we take the empty digraph $E_{5}$,
which is dispositional and not connected then $\sigma(E_{5})=120$, but
$s_{5}=16$. In fact, it is obvious, by Proposition 3, that the maximum value
that the counter of a digraph of order $n$ can have is $n!$, and it is clear
that the equality holds if and only if the digraph is isomorphic to $E_{n}$.

The condition that the digraph is dispositional is also esential. If we take
the star digraph shown in the following figure,

Figure 4: Star digraph of order $5$

which is connected but is not dispositional, then by part 2 of Theorem 1 we
obtain that its counter is $4!=24$, but $s_{5}=16$.

##  3 Companion polynomial of a digraph

Before stating the main theorem of this section we will establish some
notation. Given a digraph $\mathfrak{G}=(V,A)$ of order $n$, a vertex $v$ of
$V$ and a nonnegative integer $i$, we take $i+1$ vertices
$z_{0},z_{1},\dots,z_{i}$ with $z_{0}=v$ and
$V\cap\\{z_{1},\dots,z_{i}\\}=\emptyset$, and we define $P_{i+1}$ to be the
directed path $\\{z_{0},z_{1},\dots,z_{i}\\}$ with $i+1$ vertices and arcs
$(z_{0},z_{1}),\dots,(z_{i-1},z_{i})$, and we also define
$\mathfrak{G}_{i}=\mathfrak{G}+P_{i+1}$. Note that when $i=0$ the digraph
$\mathfrak{G}_{0}$ is just $\mathfrak{G}$.

In this way we get a head, which is formed by the digraph $\mathfrak{G}$, and
a tail, which is the infinite path with vertices $z_{0},z_{1},\dots$ whose
induced graph on $\\{z_{0},\dots,z_{i}\\}$ is $P_{i+1}$, as is shown in the
next two figures:

Figure 5: Digraph $\mathfrak{G}$ Figure 6: Digraph $\mathfrak{G}$ with
infinite path adjoined

###### Theorem 6

Let $\mathfrak{G}=(V,A)$ be a digraph of order $n$, and let $v\in V$. Then
there exists a unique polynomial $T_{\mathfrak{G},v}(X)\in\mathbb{Q}[X]$ with
$\deg(T_{\mathfrak{G},v}(X))\leq n-1$ such that

$F_{\\{\mathfrak{G}_{i}\\}_{i\in\mathbb{Z}^{+}}}(X)=T_{\mathfrak{G},v}(X)\exp(X).$

Besides, the polynomials $T_{\mathfrak{G},v}(X)$ satisfy the recurrence
relation

$T_{P_{1},v}(X)=1$

and

$\frac{d}{dX}T_{\mathfrak{G},v}(X)=\sum_{w\in\min(\mathfrak{G})-\\{v\\}}(T_{\mathfrak{G}-w,v}(X)+\frac{d}{dX}T_{\mathfrak{G}-w,v}(X))$

with

$T_{\mathfrak{G},v}(0)=\sigma(\mathfrak{G})$

Proof. First, observe that

$\min(\mathfrak{G}_{i})=S\cup(\min(\mathfrak{G})-\\{v\\})\ \forall
i\in\mathbb{Z}^{+},$ (3)

where

$S=\begin{cases}\emptyset,&\text{if }i=0\text{ and
}v\not\in\min(\mathfrak{G}),\\\ z_{i},&\text{in other case}.\\\ \end{cases}$

We will prove the theorem by induction on the order $n$ of $\mathfrak{G}$.
When $n=1,\mathfrak{G}=P_{1}$ and $v$ is the only vertex of the digraph, and
it follows from Proposition 6 that the result holds with $T_{P_{1},v}(X)=1$.

Let us suppose that what we want to prove is true for digraphs of order $n-1$,
and let us consider a digraph $\mathfrak{G}$ of order $n\geq 2$. If
$\min(\mathfrak{G})-\\{v\\}=\emptyset$, then

$\sigma(\mathfrak{G}_{i})=\sigma(\mathfrak{G})\ \forall i\in\mathbb{Z}^{+},$

and therefore

$F_{\\{\mathfrak{G}_{i}\\}_{i\in\mathbb{Z}^{+}}}(X)=\sum_{i=0}^{\infty}\frac{\sigma(\mathfrak{G})}{i!}X^{i}=\sigma(\mathfrak{G})\sum_{i=0}^{\infty}\frac{X^{i}}{i!}=\sigma(G)\exp(X).$

If $\min(\mathfrak{G})-\\{v\\}\not=\emptyset$ then, since the independent term
of the Maclaurin expansion of $\exp(X)$ is non-zero, there exists a unique
formal series

$T_{\mathfrak{G},v}(X)=\sum_{i\in\mathbb{Z}^{+}}t_{i}X^{i}$

in $\mathbb{Q}[X]$ such that

$F_{\\{\mathfrak{G}_{i}\\}_{i\in\mathbb{Z}^{+}}}(X)=T_{\mathfrak{G},v}(X)\exp(X).$
(4)

We will prove that in the end $T_{\mathfrak{G},v}(X)$ is a polynomial of
degree at most $n-1$.

Using (3) and part 1 of Theorem 1 we obtain that

$\sigma(\mathfrak{G}_{j})=\sigma(\mathfrak{G}_{j-1})+\sum_{w\in\min(\mathfrak{G})-\\{v\\}}\sigma((\mathfrak{G}-w)+P_{j+1})\forall
j\in\mathbb{Z}^{+},$

where we convey that

$\sigma(\mathfrak{G}_{-1})=\begin{cases}\sigma(\mathfrak{G}-\\{v\\}),&\text{if
}v\in\min(\mathfrak{G}),\\\ 0,&\text{in other case}.\\\ \end{cases}$

If $i$ is a non-negative integer and $0\leq j\leq i$, by multiplying by
$\frac{X^{j}}{j!}$ in this identity and summing over $j$ we get

$\sum_{j=0}^{i}\frac{\sigma(\mathfrak{G}_{j})}{j!}X^{j}=\sigma(\mathfrak{G}_{-1})+\sum_{j=1}^{i}\frac{\sigma(\mathfrak{G}_{j-1})}{j!}X^{j}+\sum_{w\in\min(\mathfrak{G})-\\{v\\}}\sum_{j=0}^{i}\frac{\sigma((\mathfrak{G}-w)+P_{j+1})}{j!}X^{j}.$
(5)

It follows from (5) that

$F_{\\{\mathfrak{G}_{i}\\}_{i\in\mathbb{Z}^{+}}}(X)=\sigma(\mathfrak{G}_{-1})+\sum_{i\in\mathbb{Z}^{+}}\frac{\sigma(\mathfrak{G}_{i})}{(i+1)!}X^{i+1}+\sum_{w\in\min(\mathfrak{G})-\\{v\\}}F_{\\{(G-w)+P_{i+1}\\}_{i\in\mathbb{Z}^{+}}}(X).$
(6)

Obviously,

$\frac{d}{dX}\sum_{i\in\mathbb{Z}^{+}}\frac{\sigma(\mathfrak{G}_{i})}{(i+1)!}X^{i+1}=F_{\\{\mathfrak{G}_{i}\\}_{i\in\mathbb{Z}^{+}}}(X)$
(7)

and, by the inductive hypothesis, for each $w\in\min(\mathfrak{G})-\\{v\\}$,
the identity

$F_{\\{(\mathfrak{G}-w)+P_{i+1}\\}_{i\in\mathbb{Z}^{+}}}(X)=T_{\mathfrak{G}-w,v}(X)\exp(X)$
(8)

holds, where $T_{\mathfrak{G}-w,v}(X)$ is a polynomial of degree at most
$n-2$. Deriving in (6) and using (7) and (8), we get

$\frac{d}{dX}F_{\\{\mathfrak{G}_{i}\\}_{i\in\mathbb{Z}^{+}}}(X)=F_{\\{\mathfrak{G}_{i}\\}_{i\in\mathbb{Z}^{+}}}(X)+\sum_{w\in\min(\mathfrak{G})-\\{v\\}}(T_{\mathfrak{G}-w,v}(X)+\frac{d}{dX}T_{\mathfrak{G}-w,v}(X))\exp(X)$

and, by (4), we obtain

$\frac{d}{dX}F_{\\{\mathfrak{G}_{i}\\}_{i\in\mathbb{Z}^{+}}}(X)=(T_{\mathfrak{G},v}(X)+\sum_{w\in\min(\mathfrak{G})-\\{v\\}}(T_{\mathfrak{G}-w,v}(X)+\frac{d}{dX}T_{\mathfrak{G}-w,v}(X)))\exp(X).$
(9)

On the other hand, deriving in (4) we have

$\frac{d}{dX}F_{\\{\mathfrak{G}_{i}\\}_{i\in\mathbb{Z}^{+}}}(X)=(T_{\mathfrak{G},v}(X)+\frac{d}{dX}T_{\mathfrak{G},v}(X))\exp(X),$
(10)

and we conclude from (9) and (10), by simplifying the summand
$T_{\mathfrak{G},v}(X)\exp(X)$ and then simplifying the factor $\exp(X)$ that

$\frac{d}{dX}T_{\mathfrak{G},v}(X)=\sum_{w\in\min(\mathfrak{G})-\\{v\\}}(T_{\mathfrak{G}-w,v}(X)+\frac{d}{dX}T_{\mathfrak{G}-w,v}(X)).$

It holds that

$T_{\mathfrak{G},v}(0)=\sigma(\mathfrak{G}_{0})=\sigma(\mathfrak{G}).$

Finally, observe that $\deg(T_{\mathfrak{G},v}(X))\leq n-1$, because for each
$w\in\min(\mathfrak{G})-\\{v\\}$ we have that
$\deg(T_{\mathfrak{G}-w,v}(X)+\frac{d}{dX}T_{\mathfrak{G}-w,v}(X))\leq n-2$,
and therefore the degree of its primitives is at most $n-1$.

We will call to $T_{\mathfrak{G},v}(X)$ the companion polynomial of
$\mathfrak{G}$ with respect to the vertex $v$.

We can observe that whenever $v\in\min(\mathfrak{G})$ the sum in the
recurrence equation goes over $\min(\mathfrak{G})-\\{v\\}$, while when
$v\not\in\min(\mathfrak{G})$ it goes over $\min(\mathfrak{G})$.

It is important to stress that the companion polynomial not only depends on
the digraph, but also depends on the vertex of the digraph. For instance, if
we take the directed path $P_{2}$ with vertex set $\\{v_{1},v_{2}\\}$ and arc
set $\\{(v_{1},v_{2})\\}$, then $T_{P_{2},v1}=X+1$, but $T_{P_{2},v2}=1$. This
same example also shows that if $\mathfrak{G}$ is a digraph of order $n$, then
the degree of $T_{\mathfrak{G},v}(X)$ can be strictly less than $n-1$.

A similar analysis can be done plugging the directed path in reverse order,
that is, if for any nonnegative integer $i$ we take $i+1$ vertices
$z_{0},z_{1},\dots,z_{i}$ with $z_{0}=v$ and
$V\cap\\{z_{1},\dots,z_{i}\\}=\emptyset$ and we consider the directed path
$P^{\star}_{i+1}$ with $i+1$ vertices $\\{z_{0},z_{1},\dots,z_{i}\\}$ and arcs
$(z_{i},z_{i-1}),\dots,(z_{1},z_{0})$, we can define the digraph
$\mathfrak{G}^{\star}_{i}=\mathfrak{G}+P^{\star}_{i+1}$, in the way shown in
the following two figures:

Figure 7: Digraph $\mathfrak{G}$ Figure 8: Digraph $\mathfrak{G}$ with
infinite path adjoined in reverse order

Now we have the following theorem, dual of Theorem 6:

###### Theorem 7

Let $\mathfrak{G}=(V,A)$ be a digraph of order $n$, and let $v\in V$. Then
there exist a unique polynomial
$T^{\star}_{\mathfrak{G},v}(X)\in\mathbb{Q}[X]$ with
$\deg(T^{\star}_{\mathfrak{G},v}(X))\leq n-1$ such that

$F_{\\{\mathfrak{G}^{\star}_{i}\\}_{i\in\mathbb{Z}^{+}}}(X)=T^{\star}_{\mathfrak{G},v}(X)\exp(X).$

Besides, the polynomials $T^{\star}_{\mathfrak{G},v}(X)$ satisfy the
recurrence relation

$T^{\star}_{P_{1},v}(X)=1$

and

$\frac{d}{dX}T^{\star}_{\mathfrak{G},v}(X)=\sum_{w\in\max(\mathfrak{G})-\\{v\\}}(T^{\star}_{\mathfrak{G}-w,v}(X)+\frac{d}{dX}T^{\star}_{\mathfrak{G}-w,v}(X))$

with

$T^{\star}_{\mathfrak{G},v}(0)=\sigma(\mathfrak{G})$

Proof. Use Theorem 6 with $\mathfrak{G}^{r}$ and Proposition 5, and the fact
that $\min(\mathfrak{G}^{r})=\max(\mathfrak{G})$.

##  4 Some differential equations associated to companion polynomials of
digraphs

We will begin establishing the fundamental connection of companion polynomials
of digraphs with Laguerre equation:

We will consider, for each $j\in\mathbb{Z}^{+}$, the directed path $P_{j+1}$
with vertex set $\\{v_{1},\dots,v_{j+1}\\}$ and arc set
$\\{(v_{1},v_{2}),\dots,(v_{j},v_{j+1})\\}$. If we consider the companion
polynomial $T_{j}(X)=T(P_{j+1},v_{1})(X)$ then we will obtain a recurrence
relation for the polynomials $T_{j}(X)$ in the following proposition:

###### Proposition 9

$T_{0}(X)=1$

and, for $j\geq 1$,

$\frac{d}{dX}T_{j}(X)=\frac{d}{dX}T_{j-1}(X)+T_{j-1}(X)\text{ and
}T_{j}(0)=1.$

Proof. By induction on $i$. The base of the induction is obvious, and the step
is proved by using Theorem 6, having into account that
$\min(P_{j+1})=\\{v_{j+1}\\}$ and $P_{j+1}-v_{j+1}=P_{j}$.

###### Theorem 8

$T_{j}(X)=L_{j}(-X)\forall j\in\mathbb{Z}^{+}$, where $L_{j}$ is the $j$-th
Laguerre polynomial.

Proof. It is well-known that Laguerre polynomials form a Sheffer sequence
([22, Chapter 16]) in which

$L_{0}(X)=1\text{ and
}\frac{d}{dX}L_{j}(X)=\frac{d}{dX}L_{j-1}(X)-L_{j-1}(X)\forall j\geq
1,L_{j}(0)=1\ \forall j\geq 1.$ (11)

Since

$T_{0}(X)=L_{0}(-X)=1$

and also

$\frac{d}{dX}(L_{j}(-X))=-(\frac{d}{dX}L_{j})(-X)$

and

$\frac{d}{dX}(L_{j-1}(-X))=-(\frac{d}{dX}L_{j-1})(-X),$

the recurrence relation of Proposition 9 is the same that the corresponding
one in (11).

Laguerre polynomials are solutions of Laguerre’s equation

$xy^{\prime\prime}+(1-x)y^{\prime}+ny=0.$

This equation has nonsingular solutions only if $n$ is a non-negative integer.
They are orthogonal polynomials with respect to the inner product

$<f,g>=\int_{0}^{\infty}f(x)g(x)exp(-x)\ dx.$

Laguerre polynomials have important applications in quantum mechanics, where
they are used in the description of the static Wigner functions of oscillator
systems, in the 3D isotropic harmonic oscillator and in Morse potential, as
well as in the Schrodinger equation for the hydrogen-like atom.

We will give now an alternative characterization of Laguerre polynomials. We
will call it the tabloidal form of $L_{j}(X)$:

###### Theorem 9

$L_{j}(X)=(\sum_{i=0}^{\infty}\frac{\binom{i+j}{i}}{i!}(-X)^{i})\exp(X)\forall
j\in\mathbb{Z}^{+}.$

Proof. Following the notation before Theorem 6, if $j\in\mathbb{Z}^{+}$,
$P_{j+1}$ is the directed path on the vertices $v_{1},\dots,v_{j+1}$ and
$P_{i+1}$ is the directed path on the vertices $v_{1},z_{1},\dots,z_{i}$, it
follows from part 2 of Theorem 1 that
$\sigma(P_{j+1}+P_{i+1})=\sigma((P_{j+1}-\\{v_{1}\\})+(P_{i+1}-\\{v_{1}\\}))$,
and since $(P_{j+1}-\\{v_{1}\\})+(P_{i+1}-\\{v_{1}\\})$ has two connected
components which are paths of lengths $j$ and $i$, respectively, then we
deduce from Theorem 2, using that the counter of a directed path is $1$, that

$\sigma(P_{j+1}+P_{i+1})=\binom{i+j}{i}.$

Now, we deduce from Theorem 6 that

$\sum_{i=0}^{\infty}\frac{\binom{i+j}{i}}{i!}X^{i}=T_{j}(X)exp(X),$

and the result follows immediately from this identity and Theorem 8.

The directed path is not the only digraph whose companion polynomial satisfies
Laguerre’s equation:

###### Theorem 10

If $\mathfrak{G}$ is a digraph of order $n$ associated to a rooted tree with
root $v$, then

$T_{\mathfrak{G},v}(X)=\sigma(\mathfrak{G})L_{n-1}(-X).$

Proof. We will prove it by induction on $n$. It is obvious if $n=1$. Let us
suppose that $n>1$ and that it is true for $n-1$. Then,
$\min(\mathfrak{G})-\\{v\\}=\min(\mathfrak{G})$, and for any
$w\in\min(\mathfrak{G})$ the digraph $G-w$ is associated to a rooted tree with
root $v$.

Now, by Theorem 6 and the induction hypothesis we have

$\frac{d}{dX}T_{\mathfrak{G},v}(X)=\sum_{w\in\min(\mathfrak{G})}(\sigma(\mathfrak{G}-w)L_{n-2}(-X)+\sigma(\mathfrak{G}-w)\frac{d}{dX}L_{n-2}(-X)).$

By Theorem 1, this equals

$\sigma(\mathfrak{G})L_{n-2}(-X)+\sigma(\mathfrak{G})\frac{d}{dX}L_{n-2}(-X).$

Factoring out $\sigma(\mathfrak{G})$, we obtain

$\sigma(\mathfrak{G})(L_{n-2}(-X)+\frac{d}{dX}L_{n-2}(-X))$

and, by Proposition 9, this is

$\sigma(\mathfrak{G})\frac{d}{dX}L_{n-1}(-X).$

Finally, the desired equality follows from the fact that both polynomials in
the statement of this theorem have the same independent term.

Now we will derive from empty digraphs a particular case of generalized
Laguerre equation.

We will consider, for each $j\in\mathbb{Z}^{+}$, the empty graph $E_{j+1}$
with vertex set $\\{v_{1},\dots,v_{j+1}\\}$ and an empty arc set. If we
consider the companion polynomial $T_{j}(X)=T(E_{j+1},v_{1})(X)$ then we will
obtain a recurrence relation for the polynomials $T_{j}(X)$ in the following
proposition:

###### Proposition 10

$T_{0}(X)=1$

and, for $j\geq 1$,

$\frac{d}{dX}T_{j}(X)=j(\frac{d}{dX}T_{j-1}(X)+T_{j-1}(X))\text{ and
}T_{j}(0)=(j+1)!.$

Proof. By induction on $j$. The base of the induction is obvious, and the step
is proved by using Theorem 6, having into account that
$\min(E_{j+1})=\\{v_{1},\dots,v_{j+1}\\}$ and that for $k\in\\{2,\dots,j+1\\}$
it holds that $E_{j+1}-v_{k}=E_{j}$ (with a different labeling of the
vertices, of course), and using also Corollary 1.

In what follows we will put for every $j\in\mathbb{Z}^{+}$

$T_{j}(X)=\sum_{k}a_{j,k}X^{k},$ (12)

and we will convey that $a_{j,k}=0$ when $k<0$ and when $k>j$.

###### Lemma 3

$ka_{j,k}=j(ka_{j-1,k}+a_{j-1,k-1})\ \forall j\in\mathbb{N},\forall
k\in\mathbb{Z}.$

Proof. We have by Proposition 10 that

$\frac{d}{dX}T_{j}(X)=j(\frac{d}{dX}T_{j-1}(X)+T_{j-1}(X)).$ (13)

We deduce from (12) that

$T_{j-1}(X)=\sum_{k}a_{j-1,k}X^{k}.$ (14)

By taking derivatives in (12) and in (14) we obtain

$\frac{d}{dX}T_{j}(X)=\sum_{k}ka_{j,k}X^{k-1}=\sum_{k}(k+1)a_{j,k+1}X^{k}$
(15)

and

$\frac{d}{dX}T_{j-1}(X)=\sum_{k}ka_{j-1,k}X^{k-1}=\sum_{k}(k+1)a_{j-1,k+1}X^{k}.$
(16)

Now we deduce from (13),(14),(15) and (16) that

$(k+1)a_{j,k+1}=j((k+1)a_{j-1,k+1}+a_{j-1,k}),$

and reindexing the $k+1$ we get the desired result.

###### Lemma 4

$a_{j,1}=\frac{j(j+1)!}{2}\ \forall j\in\mathbb{Z}^{+}.$

Proof. We will prove it by induction on $j$. For $j=0$, it holds trivially.
Let us suppose that it is true for $j-1$. By the previous lemma,

$a_{j,1}=j(a_{j-1,1}+a_{j-1,0})$

and since by Proposition 10

$a_{j-1,0}=j!$

and by the inductive hypothesis

$a_{j-1,1}=\frac{(j-1)j!}{2},$

we obtain that

$a_{j,1}=j(\frac{(j-1)j!}{2}+j!)=j\cdot j!(\frac{j+1}{2})=\frac{j(j+1)!}{2}.$

###### Lemma 5

$k(k+1)a_{j,k}=(j+1-k)a_{j,k-1}\ \forall j\in\mathbb{Z}^{+},\forall
k\in\mathbb{Z}$

Proof. If $k\leq 0$ the equality holds obviously. We will prove the result by
induction on $j$. For $j=0$ it is trivially true. Let us suppose that it is
true for $j-1$. For $k=1$ the result follows from the previous lemma. For
$k>1$, by multiplying by $k-1$ we obtain that what we want to prove is
equivalent to

$(k^{2}-1)ka_{j,k}=(j+1-k)(k-1)a_{j,k-1},$

and by Lemma 3, this is the same as

$(k^{2}-1)j(ka_{j-1,k}+a_{j-1,k-1})=(j+1-k)j((k-1)a_{j-1,k-1}+a_{j-1,k-2}).$
(17)

After symplifying $j$ and regrouping terms we can see that (17) is equivalent
to

$(k^{2}-1)ka_{j-1,k}+(2k-j)(k-1)a_{j-1,k-1}=(j+1-k)a_{j-1,k-2}.$ (18)

By the induction hypothesis,

$k(k+1)a_{j-1,k}=(j-k)a_{j-1,k-1},$

and hence

$(k^{2}-1)ka_{j-1,k}=(k-1)(j-k)a_{j-1,k-1},$

and therefore (18) is equivalent to

$(k-1)ka_{j-1,k-1}=(j+1-k)a_{j-1,k-2},$

and this is true by induction hypothesis.

###### Theorem 11

$a_{j,k}={j\choose k}{j+1\choose k+1}(j-k)!\ \forall j,k\in\mathbb{Z}^{+}.$

Proof. It is easily proved by induction on $k$ using the previous lemma and
the fact that, by Proposition 10,

$a_{j,0}=(j+1)!$

In next corollary $L^{(1)}_{j}(X)$ is the $j$-th generalized Laguerre
polynomial corresponding to $\alpha=1$ in the family of generalized Laguerre
polynomials $L^{(\alpha)}_{j}(X)$.

###### Corollary 3

$T_{j}(-X)=j!L^{(1)}_{j}(X)\ \forall j\in\mathbb{Z}^{+}.$

Proof.

$T_{j}(-X)=\sum_{k=0}^{j}\frac{j!}{k!(j-k)!}{j+1\choose
k+1}(j-k)!(-1)^{k}X^{k}=j!\sum_{k=0}^{j}{j+1\choose
k+1}\frac{(-1)^{k}}{k!}X^{k}=j!L^{(1)}_{j}(X).$

###### Corollary 4

The family of polynomials $T_{j}(X)$ satisfy the differential equation

$X\frac{d^{2}Y}{dX^{2}}+(2+X)\frac{dY}{dX}-jY=0.$

Proof. Generalized Laguerre polynomials $L^{(1)}_{j}(Z)$ satisfy the
differential equation

$Z\frac{d^{2}Y}{dZ^{2}}+(2-Z)\frac{dY}{dZ}+jY=0,$

and obviously polynomials proportional to them also satisfy it. Now we make
the change of variable $X=-Z$.

We will give, in a similar way as we did with directed paths, the tabloidal
form of $L^{(1)}_{j}(X)$:

###### Theorem 12

$L^{(1)}_{j}(X)=(\sum_{i=0}^{\infty}{i+j+1\choose
j}\frac{1}{i!}(-X)^{i})\exp(X)\forall j\in\mathbb{Z}^{+}.$

Proof. It follows the line of the proof of Theorem 9, having into account that
in this case, by Theorem 2,

$\sigma(E_{j+1}+P_{i+1})={i+j+1\choose
i+1,1,\dots,1}=\frac{(i+j+1)!}{(i+1)!}.$

At this point we need a systematic way to associate a differential equation to
a digraph with a distinguished vertex. We will do this through the use of the
companion polynomial. First we will establish a way to obtain a Laguerre-like
differential equation from a polynomial.

###### Theorem 13

If $P\in\mathbb{Q}[X]$ and $\deg(P)=n$, then $P$ can be expressed in a unique
way as a linear combination of

$L_{n}(X),X\frac{d}{dX}L_{n}(X),\dots,X^{n}\frac{d^{n}}{dX^{n}}L_{n}(X).$

Proof. Since

$X^{i}\frac{d^{i}}{dX^{i}}L_{n}(X)=\sum_{j=0}^{n-i}{n\choose
i+j}\frac{(-1)^{i+j}}{j!}X^{i+j}\ \forall i\in\mathbb{Z}^{+},$

the matrix formed by the coefficients of these polynomials is triangular, and
its determinant is

$(-1)^{\lfloor(n+1)/2\rfloor}{n\choose 0}{n\choose 1}\cdot\dots\cdot{n\choose
n},$

where $\lfloor\rfloor$ denotes the integer part, and therefore it is non-zero.

Observe that if $n,i\in\mathbb{Z}^{+}$, we can put

$\frac{d^{i}}{dX^{i}}L_{n}(X)=A_{n,i}(X)L_{n}(X)+B_{n,i}(X)\frac{d}{dX}L_{n}(X),$
(19)

where $A_{n,i}(X),B_{n,i}(X)$ are rational fractions (with denominator
$X^{n-1}$ when $n\geq 1$). More specifically, we have:

###### Proposition 11

The coefficients $A_{n,i}(X),B_{n,i}(X)$ satisfy the following recurrence
relations:

$A_{n,0}(X)=1,B_{n,0}(X)=0$

and, if $i\geq 1$, then

$A_{n,i}(X)=\frac{d}{dX}A_{n,i-1}(X)-\frac{n}{X}B_{n,i-1}(X),$
$B_{n,i}(X)=A_{n,i-1}(X)+\frac{d}{dX}B_{n,i-1}(X)+\frac{X-1}{X}B_{n,i-1}(X).$

Proof. Use the fact that

$\frac{d^{2}}{dX^{2}}L_{n}(X)=\frac{-n}{X}L_{n}(X)+\frac{X-1}{X}\frac{d}{dX}L_{n}(X).$
(20)

###### Theorem 14

If $P[X]\in\mathbb{Q}[X]$ and $\deg(P[X])=n$, then $P$ can be expressed as

$P(X)=Q(X)L_{n}(X)+R(X)\frac{d}{dX}L_{n}(X),$

where $Q(X),R(X)$ are polynomials in $\mathbb{Q}[X]$ of degrees at most $n-1$
and $n$, respectively.

Proof. It is an immediate consequence of Theorem 13 and the comment before the
previous proposition.

In the next theorem we will use prime notation for first and second
derivatives.

###### Theorem 15

If $Y=P(X)$ is a polynomial of degree $n$ in $\mathbb{Q}[X]$ and $Q(X),R(X)$
are as in the previous theorem, then
$XY^{\prime\prime}(R(X)(nR(X)-XQ^{\prime}(X))+Q(X)(XR^{\prime}(X)+(X-1)R(X))+XQ(X)^{2})+Y^{\prime}(R(X)(X(XQ^{\prime\prime}(X)-2nR^{\prime}(X))-n(X-2)R(X))-Q(X)(X(2XQ^{\prime}(X)+XR^{\prime\prime}(X)+2(X-1)R^{\prime}(X))+(X^{2}-2X+2)R(X))+(1-X)XQ(X)^{2})+Y(Q(X)(X(3nR^{\prime}(X)-XQ^{\prime\prime}(X)+(X-1)Q^{\prime}(X))+n(X-2)R(X))+R(X)(X((1-X)Q^{\prime\prime}(X)-nR^{\prime\prime}(X))+(-(3n+2)X+X^{2}+2)Q^{\prime}(X)+n(X-2)R^{\prime}(X))+X(R^{\prime}(X)(2nR^{\prime}(X)-XQ^{\prime\prime}(X))+Q^{\prime}(X)(XR^{\prime\prime}(X)+2(X-1)R^{\prime}(X))+2XQ^{\prime}(X)^{2})+nXQ(X)^{2}+(n-1)nR(X)^{2})$

Proof. Derivate twice in the expression for $P(X)$ obtained in the previous
theorem, using (20), and eliminate $L_{n}(X)$ and $\frac{d}{dX}L_{n}(X)$ after
that.

We will call the previous differential equation the laguerrean differential
equation associated to $P(X)$, and we will denote it by $\mathfrak{L}(P(X))$.
It is of the form

$U(X)Y^{\prime\prime}+V(X)Y^{\prime}+W(X)=0,$

with $U(X),V(X),W(X)$ polynomials in $\mathbb{Q}[X]$. Of course, when
$P(X)=L_{n}(X)$, the laguerrean is just Laguerre’s equation. The laguerrean
just defined is very general, because $P(X)$ is an arbitrary polynomial, but
the problem is that the degree of $U(X),V(X),W(X)$ is very high. Fortunately,
for families of companion polynomials of digraphs evaluated in $-X$ we will
find families of differential equations in which the degrees of
$U(X),V(X),W(X)$ are low, and therefore are more close to Laguerre polynomials
and Laguerre equation. Besides, the families of polynomials that we will find
are sometimes orthogonal.

##  5 Differential equation associated to a dispositional digraph with two
lines

For $n_{1},n_{2}\in\mathbb{Z}^{+}$ with $n_{1}\leq n_{2}$, let
$\mathfrak{G}_{n_{1},n_{2}}$ be the digraph shown in the following figure:

Figure 9: Digraph $\mathfrak{G}_{n_{1},n_{2}}$

with $n_{1}$ vertices $u_{1},\dots,u_{n_{1}}$ in the upper row and $n_{2}$
vertices $v_{1},\dots,v_{n_{2}}$ in the lower row.

It corresponds to the dispositional digraph
$\mathcal{G}([n_{2},0],[n_{1},0])$.

If $r\in\\{1,\dots,n_{2}\\}$, we can take the vertex $v=v_{r}$, and we
consider for $i\in\mathbb{Z}^{+}$ the corresponding digraphs
$(\mathfrak{G}_{n_{1},n_{2}})_{i}$ obtained by plugging a directed path
$P_{i+1}$ at vertex $v$ as we described in Section 3. We show in the following
figure the case when $r=2$,

Figure 10: Digraphs $(\mathfrak{G}_{n_{1},n_{2}})_{i}$ for $v=v_{2}$

###### Theorem 16

If $0\leq n_{1}\leq n_{2}$ and $n_{2}\geq r$, then

$T_{\mathfrak{G}_{n_{1},n_{2}},v}(X)=\sigma(\mathfrak{G}_{n_{1},n_{2}})\sum_{i\in\mathbb{Z}^{+}}f(n_{1},n_{2},r,i)X^{i}\
\frac{d^{i}L_{n_{1}+n_{2}-r}}{dX^{i}}(-X),$

where the $f(n_{1},n_{2},r,i)$ satisfy the following recurrence relations:

  1. 1.

$f(n_{1},n_{2},r,i)=0$ for $i>\min\\{n_{1},r-1\\}$

  2. 2.

$f(n_{1},n_{2},r,i)=\frac{n_{1}(n_{1}-n_{2}-2)(n_{1}+n_{2}-r-i)}{(n_{1}-n_{2}-1)(n_{1}+n_{2})(n_{1}+n_{2}-r)}f(n_{1}-1,n_{2},r,i)+\frac{(n_{1}-n_{2})(n_{2}+1)(n_{1}+n_{2}-r-i)}{(n_{1}-n_{2}-1)(n_{1}+n_{2})(n_{1}+n_{2}-r)}f(n_{1},n_{2}-1,r,i)$,
for $1\leq n_{1}\leq n_{2}-1$, $n_{2}\geq r+1$, $i\leq\min\\{n_{1},r-1\\}$

  3. 3.

$f(n_{1},r,r,i)=\frac{(i-n_{1})(n_{1}-r-2)}{r^{2}+r+n_{1}(1-n_{1})}f(n_{1}-1,r,r,i)+\frac{r^{2}+(1-n_{1})r-n_{1}}{i!(r^{2}+r+n_{1}(1-n_{1}))}$,
for $1\leq n_{1}\leq r,i\leq n_{1}$

  4. 4.

$f(0,n_{2},r,0)=1$, for $n_{2}\geq r$

  5. 5.

$f(n_{1},n_{1},r,i)=\frac{2n_{1}-r-i}{2n_{1}-r}f(n_{1}-1,n_{1},r,i)$, for
$n_{1}>r$, $i\leq r-1$.

Proof. Let

$U(n_{1},n_{2},r,X)=\sigma(\mathfrak{G}_{n_{1},n_{2}})\sum_{i\in\mathbb{Z}^{+}}f(n_{1},n_{2},r,i)X^{i}\
\frac{d^{i}L_{n_{1}+n_{2}-r}}{dX^{i}}(-X),$

where the values $f(n_{1},n_{2},r,i)$ are determined by the recurrence
relations described in the statement of this theorem.

First, we will prove by induction on $n_{1}+n_{2}$ that $f(n_{1},n_{2},r,0)=1\
\forall n_{1},n_{2},r$. It is trivially true for $n_{1}+n_{2}=1$. Let us
assume, by induction hypothesis, that it holds for
$n^{\prime}_{1}+n^{\prime}_{2}=n_{1}+n_{2}-1$. Then it holds also for
$n^{\prime}_{1}+n^{\prime}_{2}=n_{1}+n_{2}$, because under the conditions
indicated in the second recurrence relation in the statement of this theorem
we have

$\frac{n_{1}(n_{1}-n_{2}-2)(n_{1}+n_{2}-r)}{(n_{1}-n_{2}-1)(n_{1}+n_{2})(n_{1}+n_{2}-r)}+\frac{(n_{1}-n_{2})(n_{2}+1)(n_{1}+n_{2}-r)}{(n_{1}-n_{2}-1)(n_{1}+n_{2})(n_{1}+n_{2}-r)}=1,$

under the conditions of the third one,

$\frac{-n_{1}(n_{1}-r-2)}{r^{2}+r+n_{1}(1-n_{1})}+\frac{r^{2}+(1-n_{1})r-n_{1}}{(r^{2}+r+n_{1}(1-n_{1}))}=1,$

under the conditions of the fourth one we get also $1$, and under the
conditions of the fifth one,

$\frac{2n_{1}-r}{2n_{1}-r}=1.$

Next, we will prove that $U(n_{1},n_{2},r,X)$ and $\frac{\partial
U(n_{1},n_{2},r,X)}{\partial X}$ satisfy the recurrence obtained in Theorem 6.
We need to distinguish the possible casses that can occur. Since the proof is
very similar in all cases, we will show it only for $r+1\leq n_{1}\leq
n_{2}-1$ and $0\leq i\leq r-1$. In this case,
$\min(\mathfrak{G}_{n_{1},n_{2}})-\\{v\\}=\\{u_{n_{1}},v_{n_{2}}\\}$.

If $n\in\mathbb{Z}^{+}$ and $0\leq i\leq n$, then

$\frac{d^{i}L_{n}}{dX^{i}}(-X)=\sum_{j=0}^{n}\frac{n!(-1)^{i}}{j!(n-j)!(j-i)!}X^{j-i}.$

(Obviously, by convention we will agree that a quotient in which the factorial
of a negative number appears in the denominator is $0$, so that the index $j$
in the summation goes from $i$ to $n$). We deduce from the previous identity,
using the obvious formula

$\sigma(\mathfrak{G}_{n_{1},n_{2}})={n_{1}+n_{2}\choose
n_{1}}-{n_{1}+n_{2}\choose n_{1}-1},$ (21)

that

$\begin{split}\frac{\partial U(n_{1},n_{2},r,X)}{\partial
X}-U(n_{1}-1,n_{2},r,X)-U(n_{1},n_{2}-1,r,X)-\frac{\partial
U(n_{1}-1,n_{2},r,X)}{\partial X}-\\\ \frac{\partial
U(n_{1},n_{2}-1,r,X)}{\partial
X}=\sum_{j=0}^{n_{1}+n_{2}-r-1}\sum_{i=0}^{r-1}\frac{(-1)^{i}(n_{1}+n_{2}-r-1)!}{j!(j-i+1)!(n_{1}+n_{2}-r-j-1)!}\\\
((i-n_{1}-n_{2}+r)(\sigma(\mathfrak{G}_{n_{1}-1,n_{2}})f(n_{1}-1,n_{2},r,i)+\sigma(\mathfrak{G}_{n_{1},n_{2}-1})f(n_{1},n_{2}-1,r,i))-\\\
(n_{1}+n_{2}-r)\sigma(\mathfrak{G}_{n_{1},n_{2}})f(n_{1},n_{2},r,i))X^{j}\end{split}$
(22)

Now we obtain from (21) and the second recurrence relation in the statement of
this theorem that all the coefficients of the powers of $X$ in the right-hand
side in (22) are zero, and therefore that

$\frac{\partial U(n_{1},n_{2},r,X)}{\partial
X}=U(n_{1}-1,n_{2},r,X)+U(n_{1},n_{2}-1,r,X)+\frac{\partial
U(n_{1}-1,n_{2},r,X)}{\partial X}+\frac{\partial
U(n_{1},n_{2}-1,r,X)}{\partial X},$

as desired. This proves that for every $n_{1},n_{2},r$ there exists
$c_{n_{1},n_{2},r}\in\mathbb{Q}$ such that
$U(n_{1},n_{2},r,X)=T_{\mathfrak{G}_{n_{1},n_{2}},v}(X)+c_{n_{1},n_{2},r}$.
Substituting $X$ by $0$, and having into account that by Theorem 6 we have
that $T_{\mathfrak{G}_{n_{1},n_{2}},v}(0)=\sigma(\mathfrak{G}_{n_{1},n_{2}})$
and that $X^{i}\ \frac{d^{i}L_{n_{1}+n_{2}-r}}{dX^{i}}(0)=0\ \forall i>0$, we
get

$\sigma(\mathfrak{G}_{n_{1},n_{2}})f(n_{1},n_{2},r,0)L_{n_{1}+n_{2}-r}(0)=\sigma(\mathfrak{G}_{n_{1},n_{2}})+c_{n_{1},n_{2},r}$

and, since $f(n_{1},n_{2},r,0)=1$ and $L_{n_{1}+n_{2}-r}(0)=1$, we obtain that
$c_{n_{1},n_{2},r}=0\ \forall n_{1},n_{2},r$, and we are done.

We will study the associated differential equations for the cases when
$r=2,3$:

###### Proposition 12

For $r=2$ it holds that

$T_{\mathfrak{G}_{n_{1},n_{2}},v}(X)=\begin{cases}1&\text{if
}n_{1}=0,n_{2}=2,\\\ ({n_{1}+n_{2}\choose n_{1}}-{n_{1}+n_{2}\choose
n_{1}-1})(L_{n_{1}+n_{2}-2}(-X)+\frac{(n_{1}n_{2}+n_{1})X\frac{dL_{n_{1}+n_{2}-2}}{dX}(-X)}{(n_{1}+n_{2})(n_{1}+n_{2}-1)(n_{1}+n_{2}-2)})&\text{elsewhere.}\end{cases}$

Proof. It is easy to check by doing elementary algebraic operations that the
values satisfy the recurrence relations of Theorem 16.

Hereinafter, we will use the Pochhammer symbol $(z)_{n}$ to denote the product

$z(z+1)(z+2)\cdot\dots\cdot(z+n-1).$

We will use the previous proposition to obtain differential equations
satisfied by $T_{\mathfrak{G}_{n_{1},n_{2}},v}(X)$.

###### Theorem 17

For $r=2$, let

$\alpha(n_{1},n_{2})=(n_{1}+n_{2}-2)_{3}(n_{1}+n_{2}-1)_{2},$
$\beta(n_{1},n_{2})=n_{1}(n_{2}+1)(n_{1}^{2}+n_{2}^{2}+n_{1}n_{2}-2n_{1}-n_{2}),$

and

$\gamma(n_{1},n_{2})=(n_{1}+n_{2}-2)_{3}(n_{1}^{3}+n_{2}^{3}+3n_{1}^{2}n_{2}+3n_{1}n_{2}^{2}-3n_{1}^{2}-3n_{2}^{2}-7n_{1}n_{2}+n_{1}+2n_{2}).$

Then the polynomials $T_{\mathfrak{G}_{n_{1},n_{2}},v}(X)$ satisfy the
following differential equation for every $n_{1},n_{2}$ with $0\leq n_{1}\leq
n_{2}$ and $n_{2}\geq 2$:

$(\alpha X+\beta X^{2})Y^{\prime\prime}+(\alpha+\alpha X+\beta
X^{2})Y^{\prime}-(\gamma+(n_{1}+n_{2}-2)\beta X)Y=0.$

Proof. Use Proposition 12 and Theorem 15.

For instance, for $n_{1}=2,n_{2}=3$ we have that

$T_{\mathfrak{G}_{2,3},v}(X)=\frac{1}{2}X^{3}+\frac{11}{2}X^{2}+13X+5,$

and the associated differential equation, after factoring out $48$, is

$(25X+2X^{2})Y^{\prime\prime}+(25+25X+2X^{2})Y^{\prime}-(65+6X)Y=0$

The differential equations in the previous theorem generalize Laguerre
equation, in the sense that, if we do in $Y(X)$ the change of variable $Y=-Z$
then the obtained equation when $n_{1}=0$ is (up to a constant factor which
does not change essentially the equation) Laguerre equation.

When $n_{1}=n_{2}$ we have that
$\sigma(\mathfrak{G}_{n_{1},n_{2}})={2n_{1}\choose n_{1}}-{2n_{1}\choose
n_{1}-1}=C_{n_{1}}$, the $n_{1}$-th Catalan number. In this case the
differential equation is simpler than in the general case:

###### Theorem 18

If $n\geq 2$, then the polynomials $T_{\mathfrak{G}_{n,n},v}(X)$ satisfy the
differential equation

$(3(n+1)X^{2}+8(2n-1)^{2}X)Y^{\prime\prime}+$

$(3(n+1)X^{2}+8(2n-1)^{2}X+8(2n-1)^{2})Y^{\prime}+$

$(6(n+1)(-n+1)X-4(2n-1)(8n^{2}-13n+3))Y=0.$

Proof. Use Theorem 17 and simplify the factor $n^{2}(n-1)$.

So, we will call the differential equation of the previous theorem the Catalan
differential equation, and the associated polynomials
$C^{\star}_{n}(X)=T_{\mathfrak{G}_{n,n},v}(X)$ the Catalan polynomials (Do not
confuse with the concept of $(q,t)$-Catalan polynomials $C_{n}(q,t)$ ([31]),
which generalize classical Catalan numbers).

Catalan polynomials for $i$ from $2$ to $6$ and their graphical
representations, as well as the associated Catalan differential equations, are
given next:

For $i=2$,

$C^{\star}_{2}(X)=\frac{X^{2}}{2}+3X+2$

Figure 11: Graph of $C^{\star}_{2}(X)$

Catalan differential equation associated to $C^{\star}_{2}(X)$:

$\left(9\,{X}^{2}+72\,X\right){\it
Y^{\prime\prime}}+\left(9\,{X}^{2}+72\,X+72\right){\it
Y^{\prime}}-\left(108+18\,X\right)Y=0$

For $i=3$,

$C^{\star}_{3}(X)=\frac{X^{4}}{8}+\frac{7X^{3}}{3}+12X^{2}+18X+5$

Figure 12: Graph of $C^{\star}_{3}(X)$

Catalan differential equation associated to $C^{\star}_{3}(X)$:

$\left(12\,{X}^{2}+200\,X\right){\it
Y^{\prime\prime}}+\left(12\,{X}^{2}+200\,X+200\right){\it
Y^{\prime}}-\left(720+48\,X\right)Y=0$

For $i=4$,

$C^{\star}_{4}(X)=\frac{X^{6}}{80}+\frac{59X^{5}}{120}+\frac{20X^{4}}{3}+\frac{115X^{3}}{3}+\frac{185X^{2}}{2}+79X+14$

Figure 13: Graph of $C^{\star}_{4}(X)$

Catalan differential equation associated to $C^{\star}_{4}(X)$:

$\left(15\,{X}^{2}+392\,X\right){\it
Y^{\prime\prime}}+\left(15\,{X}^{2}+392\,X+392\right){\it
Y^{\prime}}-\left(2212+90\,X\right)Y=0$

For $i=5$,

$C^{\star}_{5}(X)=\frac{X^{8}}{1440}+\frac{17X^{7}}{360}+\frac{49X^{6}}{40}+\frac{931X^{5}}{60}+\frac{1225X^{4}}{12}+343X^{3}+539X^{2}+322X+42$

Figure 14: Graph of $C^{\star}_{5}(X)$

Catalan differential equation associated to $C^{\star}_{5}(X)$:

$\left(18\,{X}^{2}+648\,X\right){\it
Y^{\prime\prime}}+\left(18\,{X}^{2}+648\,X+648\right){\it
Y^{\prime}}-\left(4968+144\,X\right)Y=0$

For $i=6$,

$C^{\star}_{6}(X)=\frac{X^{10}}{40320}+\frac{157X^{9}}{60480}+\frac{123X^{8}}{1120}+\frac{171X^{7}}{70}+\frac{623X^{6}}{20}+\frac{2331X^{5}}{10}+1008X^{4}+2388X^{3}+2781X^{2}+1278X+132$

Figure 15: Graph of $C^{\star}_{6}(X)$

Catalan differential equation associated to $C^{\star}_{6}(X)$:

$\left(21\,{X}^{2}+968\,X\right){\it
Y^{\prime\prime}}+\left(21\,{X}^{2}+968\,X+968\right){\it
Y^{\prime}}-\left(9372+210\,X\right)Y=0$

We will prove next that Catalan polynomials are orthogonal, changing the sign
of the independent variable, with respect to the inner product
$<f,g>=\int_{0}^{+\infty}f(X)g(X)\exp(-X)\ dX$.

###### Theorem 19

For any $i\not=j$,

$\int_{0}^{+\infty}C^{\star}_{i}(-X)C^{\star}_{j}(-X)\exp(-X)\ dX=0.$

We will use several lemmas to prove the theorem:

###### Lemma 6

For all $i,j,n\in\mathbb{Z}^{+}$,

$\int_{0}^{+\infty}X^{i}\frac{d^{j}}{dX^{j}}L_{n}(X)\exp(-X)\
dX=\begin{cases}(-1)^{n}(n-j+1)_{j}(i-n+1)_{n-j}(n+1)_{i-n},&\text{ if }j\leq
n\\\ 0,&\text{ otherwise}\end{cases}$

Proof. It can be done by induction on $n$, using the recurrence relation

$L_{n+1}^{(\alpha)}(X)=\frac{(2n+1+\alpha-X)L_{n}^{(\alpha)}(X)-(n+\alpha)L_{n-1}^{(\alpha)}(X)}{n+1}$

for the generalized Laguerre polynomials $L_{n}^{(\alpha)}(X)$, and having
into account that

$\frac{d^{j}}{dX^{j}}L_{n}(X)=\begin{cases}(-1)^{j}L_{n-j}^{(j)}(X),&\text{ if
}j\leq n\\\ 0,&\text{otherwise}\end{cases}$

###### Lemma 7

$\int_{0}^{+\infty}X^{i}\frac{d^{j}}{dX^{j}}L_{n}(X)\exp(-X)\ dX=0$

whenever $j\leq i<n$.

Proof. It is a consequence of the previous lemma, because in this case
$(i-n+1)_{n-j}=0$.

###### Lemma 8

$\int_{0}^{+\infty}X^{j+k}\frac{d^{j}}{dX^{j}}L_{n}(X)\frac{d^{k}}{dX^{k}}L_{m}(X)\exp(-X)\
dX=0$

whenever $|m-n|>\max\\{j,k\\}$

Proof. It can be easily deduced from the previous lemma.

Now the proof of the theorem follows directly from Lemma 8 and Proposition 12.

Although $T_{\mathfrak{G}_{n_{1},n_{2}},v}(X)$ is defined only for $n_{2}\geq
2$, if we put $C^{\star}_{1}(X)=1$ (which is consistent with the form of the
$T_{\mathfrak{G}_{n_{1},n_{2}},v}(X)$ in Theorem 16 and with the fact that
$f(n_{1},n_{2},r,0)=1$ stated at the beginning of its proof), then it is easy
to prove that, in fact, the family

$B=\\{C^{\star}_{1}(-X),C^{\star}_{2}(-X),C^{\star}_{3}(-X),\dots\\}$

is orthogonal.

Next, we will prove the inextendibility of the family of Catalan polynomials.
Since the polynomials
$C^{\star}_{1}(-X),C^{\star}_{2}(-X),C^{\star}_{3}(-X),\dots$ are orthogonal,
the family $B$ is free. We will prove that it is maximal when subjected to the
orthogonality condition:

###### Theorem 20

The family $B$ is a maximal orthogonal family.

Proof. Let us supposse that $B\subsetneq B^{\prime}$, where $B^{\prime}$ is
orthogonal, and let $P(X)\in B^{\prime}-B$. Then, $P(X)$ is of odd degree,
because $B$ generates the set of polynomials of even degree. But, if $P(X)$ is
of degree $2n+1$ and $P(X)=\displaystyle\sum_{i=0}^{2n+1}a_{i}X^{i}$ then we
have, by Lemmas 6 and 7, and by Proposition 12, that

$\int_{0}^{+\infty}P(X)C^{\star}_{n+2}(-X)\exp(-X)\
dX=\frac{-a_{2n+1}C_{n+2}(n+3)(2n+1)!}{2(2n+3)}\not=0,$

and we get a contradiction.

Thus, despite the fact that in linear algebra a free family can always be
extended to a base, we see that when we take orthogonality into account the
situation is different if we want the extension to remain orthogonal.

Now we will analyze the case $r=3$. The proofs are similar to the ones for
$r=2$ and will be omitted.

###### Proposition 13

For $r=3$ it holds that

$T_{\mathfrak{G}_{n_{1},n_{2}},v}(X)=\begin{cases}1&\text{if
}n_{1}=0,n_{2}=3,\\\ X+1&\text{if }n_{1}=0,n_{2}=4,\\\ X+3&\text{if
}n_{1}=1,n_{2}=3,\\\ \begin{split}({n_{1}+n_{2}\choose
n_{1}}-{n_{1}+n_{2}\choose n_{1}-1})(L_{n_{1}+n_{2}-3}(-X)+\\\
\frac{2n_{1}(n_{2}+1)(n_{1}^{2}+3n_{1}n_{2}+n_{2}^{2}-5n_{1}-6n_{2}+6)XL^{\prime}_{n_{1}+n_{2}-3}(-X)}{(n_{1}+n_{2}-3)_{4}(n_{1}+n_{2}-3)}+\\\
\frac{2(n_{1}-1)_{2}(n_{2})_{2}X^{2}L^{\prime\prime}_{n_{1}+n_{2}-3}(-X)}{(n_{1}+n_{2}-4)_{5}(n_{1}+n_{2}-3)})\end{split}&\text{elsewhere.}\end{cases}$

###### Theorem 21

For $r=3$, let

$\alpha(n_{1},n_{2})=(n_{1}+n_{2}-4)_{5}(n_{1}+n_{2}-3)_{4}$,

$\beta(n_{1},n_{2})=2n_{1}(n_{2}+1)(n_{1}^{6}+7n_{1}^{5}(n_{2}-2)+n_{1}^{4}(15n_{2}^{2}-72n_{2}+77)+n_{1}^{3}(16n_{2}^{3}-119n_{2}^{2}+279n_{2}-208)+n_{1}^{2}(15n_{2}^{4}-107n_{2}^{3}+333n_{2}^{2}-490n_{2}+276)+n_{1}(7n_{2}^{5}-67n_{2}^{4}+227n_{2}^{3}-384n_{2}^{2}+352n_{2}-144)+n_{2}(n_{2}^{5}-15n_{2}^{4}+74n_{2}^{3}-156n_{2}^{2}+144n_{2}-48))$,

$\gamma(n_{1},n_{2})=2(-1+n_{1})_{2}(n_{2})_{2}(-2+n_{1}+n_{2})(-3n_{1}+n_{1}^{2}+(-1+n_{2})n_{2})$,

$\delta(n_{1},n_{2})=2n_{1}(n_{2}+1)(n_{1}^{6}+7n_{1}^{5}(n_{2}-2)+n_{1}^{4}(15n_{2}^{2}-73n_{2}+77)+n_{1}^{3}(16n_{2}^{3}-120n_{2}^{2}+285n_{2}-208)+n_{1}^{2}(15n_{2}^{4}-108n_{2}^{3}+338n_{2}^{2}-501n_{2}+276)+n_{1}(7n_{2}^{5}-68n_{2}^{4}+231n_{2}^{3}-390n_{2}^{2}+358n_{2}-144)+n_{2}(n_{2}^{5}-15n_{2}^{4}+75n_{2}^{3}-159n_{2}^{2}+146n_{2}-48))$,

$\epsilon=(-4+n_{1}+n_{2})_{5}(6n_{1}-29n_{1}^{2}+27n_{1}^{3}-9n_{1}^{4}+n_{1}^{5}+18n_{2}-78n_{1}n_{2}+91n_{1}^{2}n_{2}-38n_{1}^{3}n_{2}+5n_{1}^{4}n_{2}-39n_{2}^{2}+97n_{1}n_{2}^{2}-60n_{1}^{2}n_{2}^{2}+10n_{1}^{3}n_{2}^{2}+29n_{2}^{3}-38n_{1}n_{2}^{3}+10n_{1}^{2}n_{2}^{3}-9n_{2}^{4}+5n_{1}n_{2}^{4}+n_{2}^{5})$,

$\zeta=2n_{1}(n_{2}+1)(n_{1}+n_{2}-4)(n_{1}^{6}+n_{1}^{5}(7n_{2}-13)+n_{1}^{4}(15n_{2}^{2}-68n_{2}+67)+n_{1}^{3}(16n_{2}^{3}-114n_{2}^{2}+249n_{2}-171)+n_{1}^{2}(15n_{2}^{4}-102n_{2}^{3}+302n_{2}^{2}-414n_{2}+216)+n_{1}(7n_{2}^{5}-63n_{2}^{4}+203n_{2}^{3}-327n_{2}^{2}+282n_{2}-108)+n_{2}(n_{2}^{5}-14n_{2}^{4}+65n_{2}^{3}-130n_{2}^{2}+114n_{2}-36)).$

Then the polynomials $T_{\mathfrak{G}_{n_{1},n_{2}},v}(X)$ satisfy the
following differential equation for every $n_{1},n_{2}$ with $0\leq n_{1}\leq
n_{2}$ and $n_{2}\geq 3$:

$(\alpha X+\beta X^{2}+\gamma X^{3})Y^{\prime\prime}+(\alpha+\alpha X+\delta
X^{2}+\gamma X^{3})Y^{\prime}-(\epsilon+\zeta X+(n_{1}+n_{2}-3)\gamma
X^{2})Y=0$

Just as it was the case for $r=2$, when $n_{1}=n_{2}=n$ the differential
equation takes a simpler form. In this case the factor $4(n-2)_{3}(n-1)_{2}$
can be cancelled, and we get

$((72-384n+704n^{2}-512n^{3}+128n^{4})X+(48-25n-42n^{2}+31n^{3})X^{2}+(2n+2n^{2})X^{3})Y^{\prime\prime}+(72-384n+704n^{2}-512n^{3}+128n^{4}+(72-384n+704n^{2}-512n^{3}+128n^{4})X+(48-27n-44n^{2}+31n^{3})X^{2}+(2n+2n^{2})X^{3})Y^{\prime}-2((-72+558n-1438n^{2}+1560n^{3}-744n^{4}+128n^{5})+(-72+90n+37n^{2}-94n^{3}+31n^{4})X+(-3n-n^{2}+2n^{3})X^{2})Y=0$

We will call the diferential equation of the previous theorem the Catalan
differential equation of order $3$, and the associated polynomials $C^{\star
3}_{n}=T_{\mathfrak{G}_{n,n},v}$ the Catalan polynomials of order $3$.

The property of orthogonality of Catalan polynomials which held for $r=2$ is
no longer true for $r=3$; for instance,

$\int_{0}^{+\infty}C^{\star 3}_{3}(-X)C^{\star 3}_{4}(-X)\exp(-X)\ dX=4$

##  6 Staircase differential equations

We will consider, for $n\in\mathbb{N}$, the staircase digraph
$\mathfrak{S}_{n}$, the vertex $v=v_{1}$, and the companion polynomial
$T_{\mathfrak{S}_{n},v}(X)$. In this section we will do a numerical study of
the first polynomials and their associated differential equations.

###### Proposition 14

If we call $f(n,i)$ to $\sigma(\mathfrak{S}_{n}+P_{i+1})$, then $f(n,i)$
satisfies the recurrence relation

$f(n,i)=\frac{f(n,i-1)+\sum_{j=0}^{n-1}{n+i-1\choose
i+j}f(j,i)s_{n-1-j}}{2}\text{ whenever }n\geq 2,i\geq 1,$

with the initial conditions

$f(0,i)=1$

$f(1,i)=1$

$f(n,0)=s_{n}$

where the $s_{n-1-j}$ and the $s_{n}$ are the corresponding Euler zigzag
numbers.

Proof. Use Theorem 1 for both the minimum points and the maximum points, and
sum the obtained identities.

Note that the initial condition $f(1,i)=1$ in the previous proposition might
seem redundant at first glance, but it really is not, and the result is false
if we remove it.

As a consequence of the previous proposition, the following result can be
easily obtained inductively:

###### Proposition 15

$f(n,i)=(-1)^{\lfloor\frac{i}{2}\rfloor}s_{n+i}+\sum_{j=0}^{\lfloor\frac{i}{2}\rfloor-1}(-1)^{j}{n+i\choose
i-2j-1}s_{n+2j+1}\ \forall n\in\mathbb{N},\forall i\in\mathbb{Z}^{+}$

Now, if $T_{\mathfrak{S}_{n},v}(X)=\displaystyle\sum_{i=0}^{n-1}a_{n,i}X^{i}$,
then the $a_{n,i}$ can be obtained from the previous proposition and the facts
that $a_{n,0}=s_{n}$ and that, from the definition of companion polynomial, we
have that

$a_{n,i}=\frac{f(n,i)}{i!}-\sum_{k=0}^{i-1}\frac{a_{n,k}}{(i-k)!}\ \forall
i\geq 1.$

We will show in the following proposition the values for $i\leq 5$:

###### Proposition 16

$a_{n,0}=s_{n}$

$a_{n,1}=s_{n+1}-s_{n}$

$a_{n,2}=\frac{1}{2}\left(s_{n}+ns_{n+1}-s_{n+2}\right)$

$a_{n,3}=\frac{1}{12}\left(\left(n^{2}-n\right)s_{n+1}-2s_{n}+6s_{n+2}-2s_{n+3}\right)$

$a_{n,4}=\frac{1}{144}\left(\left(n^{3}-3n^{2}+2n\right)s_{n+1}+6s_{n}-36s_{n+2}-6ns_{n+3}+6s_{n+4}\right)$

$a_{n,5}=\frac{1}{2880}\left(\left(12n-12n^{2}\right)s_{n+3}+\left(n^{4}-6n^{3}+11n^{2}-6n\right)s_{n+1}-24s_{n}+240s_{n+2}-120s_{n+4}+24s_{n+5}\right)$

Note that the independent terms $a_{n,0}$ are just the Euler zigzag numbers.
It is obvious from the definition of companion polynomial that $i!a_{n,i}$ is
always an integer. We will call to

$s_{n,i}=i!a_{n,i}$

the generalized zigzag number of order $i$. We will give now the first $15$
ones for $i$ up to $5$:

For
$i=0:1,1,1,2,5,16,61,272,1385,7936,50521,353792,2702765,22368256,199360981$

For
$i=1:0,0,1,3,11,45,211,1113,6551,42585,303271,2348973,19665491,176992725,1704396331$

For
$i=2:0,0,0,1,8,49,308,2031,14352,108833,885676,7715951,71760856,710303697,7460451204$

For
$i=3:0,0,0,0,2,25,238,2100,18594,169431,1610158,16042070,167927762,1847548053,21351747870$

For
$i=4:0,0,0,0,0,5,96,1276,15104,172319,1967392,22887002,273977600,3392750041,43582823456$

For
$i=5:0,0,0,0,0,0,16,427,7600,115791,1654336,23112848,322993424,4573319530,66117354592$

It is an immediate consequence ot Theorem 13 that for every $n\in\mathbb{N}$
there exists $n$ rational numbers $g(n,0),\dots,g(n,n-1)$ such that

$T_{\mathfrak{S}_{n},v}(X)=\sum_{i=0}^{n-1}g(n,i)X^{i}\frac{d^{i}}{dX^{i}}L_{n-1}(-X)$
(23)

The first $6$ polynomials can be obtained from Proposition 16. They are shown
next along with the tuples $(g(n,0),\dots,g(n,n-1))$:

For $n=1$,

$1$ $(1)$

For $n=2$,

$X+1$

$(1,0)$

For $n=3$,

$\frac{1}{2}\,{X}^{2}+3\,X+2$

$(2,\frac{1}{2},0)$

For $n=4$,

$\frac{1}{3}\,{X}^{3}+4\,{X}^{2}+11\,X+5$

$(5,\frac{4}{3},\frac{1}{6},0)$

For $n=5$,

${\frac{5\,{X}^{4}}{24}}+{\frac{25\,{X}^{3}}{6}}+{\frac{49\,{X}^{2}}{2}}+45\,X+16$

$(16,{\frac{19}{4}},\frac{5}{6},\frac{1}{12},0)$

For $n=6$,

$\frac{2}{15}\,{X}^{5}+4\,{X}^{4}+{\frac{119\,{X}^{3}}{3}}+154\,{X}^{2}+211\,X+61$

$(61,{\frac{94}{5}},{\frac{37}{10}},\frac{1}{2},\frac{1}{24},0)$

Now we will analyze their associated differential equations. We conclude from
(23) and (19) that
$T_{\mathfrak{S}_{n},v}(-X)=\sum_{i=0}^{n-1}g(n,i)(-X)^{i}\frac{d^{i}}{dX^{i}}L_{n-1}(X)=$

$\sum_{i=0}^{n-1}g(n,i)(-X)^{i}(A_{n-1,i}(X)L_{n-1}(X)+B_{n-1,i}(X)\frac{d}{dX}L_{n-1}(X))=Q_{n}(X)L_{n-1}(X)+R_{n}(X)\frac{d}{dX}L_{n-1}(X)$,
where

$Q_{n}(X)=\sum_{i=0}^{n-1}g(n,i)(-X)^{i}A_{n-1,i}(X)$

and

$R_{n}(X)=\sum_{i=0}^{n-1}g(n,i)(-X)^{i}B_{n-1,i}(X).$

Now, since $(-X)^{i}A_{n-1,i}(X)$ and $(-X)^{i}B_{n-1,i}(X)$ are polynomials,
then the Laguerrean differential equation
$\mathfrak{L}(T_{\mathfrak{S}_{n},v}(-X))$ is of the form

$P_{1,n}(X)\frac{d^{2}Y}{dX^{2}}+P_{2,n}(X)\frac{dY}{dX}+P_{3,n}(X)Y(X)=0,$

where $P_{1,n}(X),P_{2,n}(X),P_{3,n}(X)$ are polynomials. Finally, the
differential equation associated to $y(X)=T_{\mathfrak{S}_{n},v}(X)$ is

$P_{1,n}(-X)\frac{d^{2}Y}{dX^{2}}-P_{2,n}(-X)\frac{dY}{dX}+P_{3,n}(-X)Y(X)=0.$

The $Q_{n}(X),R_{n}(X)$ and the differential equations satisfied by the
$T_{\mathfrak{S}_{n},v}(X)$ (after simplifying $X$) are shown next For $n$
from $2$ to $6$:

For $n=2$,

$Q_{2}(X)=1,R_{2}(X)=0$

$XY^{\prime\prime}+(X+1)Y^{\prime}-Y=0$

For $n=3$,

$Q_{3}(X)=2,R_{3}(X)=\frac{-1}{2}\,X$

$\frac{1}{2}(X+8)XY^{\prime\prime}+\frac{1}{2}\left(X^{2}+8X+8\right)Y^{\prime}-(X+6)Y=0$

For $n=4$,

$Q_{4}(X)=5-\frac{1}{2}\,X,R_{4}(X)=\frac{-3}{2}\,X+\frac{1}{6}\,{X}^{2}$

$\frac{1}{3}\left(X^{2}+17X+75\right)XY^{\prime\prime}+\frac{1}{3}\left(X^{3}+16X^{2}+75X+75\right)Y^{\prime}-\left(X^{2}+14X+55\right)Y=0$

For $n=5$,

$Q_{5}(X)=16-4\,X+\frac{1}{3}\,{X}^{2},R_{5}(X)={\frac{-23}{4}}\,X+\frac{4}{3}\,{X}^{2}-\frac{1}{12}\,{X}^{3}$

$\frac{1}{12}(5X^{3}+130X^{2}+1073X+3072)XY^{\prime\prime}+\frac{1}{12}(5X^{4}+120X^{3}+943X^{2}+3072X+3072)Y^{\prime}-$

$\frac{1}{3}(5X^{3}+110X^{2}+789X+2160)Y=0$

For $n=6$,

$Q_{6}(X)=61-{\frac{99}{4}}\,X+{\frac{25}{6}}\,{X}^{2}-{\frac{5}{24}}\,{X}^{3},R_{6}(X)=-{\frac{95}{4}}\,X+{\frac{497}{60}}\,{X}^{2}-{\frac{25}{24}}\,{X}^{3}+\frac{1}{24}\,{X}^{4}$

$\frac{1}{15}(10X^{4}+370X^{3}+4763X^{2}+25957X+55815)XY^{\prime\prime}+$

$\frac{1}{15}(10X^{5}+340X^{4}+4023X^{3}+21194X^{2}+55815X+55815)Y^{\prime}-$

$\frac{1}{3}(10X^{4}+320X^{3}+3593X^{2}+17778X+38613)Y=0$

We can see that the situation of the differential equation associated to the
staircase digraph is completely different to the ones obtained from
dispositional digraphs with two lines, for which the companion polynomial can
be decomposed in terms of a few number of derivatives of Laguerre polynomials
and, in consequence, the degrees of the coefficients of
$Y^{\prime\prime},Y^{\prime}$ and $Y$ are low.

##  7 Non-strict dispositions in digraphs

In this section we will consider dispositions and counters in which the
inequalities need not to be strict. In this case the transitive clausure of
the digraphs needs not to define an order relation in order the counter to be
non-zero, and we have an additional parameter indicating the cardinality of
the set of assigned values.

###### Definition 16

Let $\mathfrak{G}=(V,A)$ be a directed graph, and let $i$ be a natural number.
A non-strict disposition of size $i$ in $\mathfrak{G}$ is a mapping
$f:V\longrightarrow\\{1,\dots,i\\}$ such that $f(v_{1})\geq f(v_{2})$ whenever
$(v_{1},v_{2})\in A$.

If $\mathfrak{G}$ and $i$ are as above, then the set of non-strict
dispositions of size $i$ will be denoted by $\Sigma^{ns}_{i}(\mathfrak{G})$,
and its cardinality by $\sigma^{ns}_{i}(\mathfrak{G})$. When $i$ is the order
of the digraph we will write just $\Sigma^{ns}(\mathfrak{G})$ and
$\sigma^{ns}(\mathfrak{G})$. The number $\sigma^{ns}(\mathfrak{G})$ will be
called the non-strict counter of $\mathfrak{G}$.

We will call non-strict Young tableaux over the digraph $\mathfrak{G}$ to the
triplet

$(\mathfrak{G},\Sigma^{ns}(\mathfrak{G}),\sigma^{ns}(\mathfrak{G})).$

###### Theorem 22

Let $\mathfrak{G}$ be a digraph and let $i\in\mathbb{N}$. If $\mathfrak{R}$ is
the equivalence relation given in Proposition 1 and $\overline{\mathfrak{G}}$
is the quotient digraph $\mathfrak{G}/\mathfrak{R}$, then

$\sigma^{ns}_{i}(\mathfrak{G})=\sigma^{ns}_{i}(\mathfrak{\overline{G}})$

Proof. If $u,v\in V$ and $u,v$ are in a closed walk $z_{1},z_{2},\dots,z_{n}$,
and if $f:V\longrightarrow\\{1,\dots,i\\}$ is a non-strict disposition of size
$i$ in $\mathfrak{G}$, then

$f(z_{1})\geq f(z_{j})\geq f(z_{1})\ \forall j\in\\{1,\dots,n\\},$

and therefore $f(u)=f(v)$. So, the mapping
$\overline{f}:\overline{V}\longrightarrow\\{1,\dots,i\\}$ defined by
$\overline{f}(\overline{v})=f(v)$ is well-defined, because the value $f(v)$
does not depends on the representant in the equivalence class, and it is a
non-strict disposition of size $i$ in $\overline{\mathfrak{G}}$.

Reciprocally, if

$\overline{f}:\overline{V}\longrightarrow\\{1,\dots,i\\}$

is a non-strict disposition of size $i$ in $\overline{\mathfrak{G}}$, then we
will prove that the mapping

$f:V\longrightarrow\\{1,\dots,i\\}$

defined by $f(v)=\overline{f}(\overline{v})$ is a non-strict disposition of
size $i$ in $\mathfrak{G}$. If $(u,v)\in A$, then
$(\overline{u},\overline{v})\in\overline{A}$ by definition of quotient
digraph, and $\overline{f}(\overline{u})\geq\overline{f}(\overline{v})$
because $\overline{f}$ is a disposition, and hence $f(u)\geq f(v)$.

Now, it is easy to prove that, if $\mathfrak{D}$ and $\overline{\mathfrak{D}}$
are the sets of non-strict dispositions of size $i$ in $\mathfrak{G}$ and
$\overline{\mathfrak{G}}$, respectively, then the mappings
$\delta_{1}:\mathfrak{D}\longrightarrow\overline{\mathfrak{D}}$ and
$\delta_{2}:\overline{\mathfrak{D}}\longrightarrow\mathfrak{D}$ defined by
$\delta_{1}(f)=\overline{f}$ and $\delta_{2}(\overline{f})=f$, respectively,
are inverses one of each other.

Hence, we can assume without loosing generality that the digraph has not
directed cycles.

###### Theorem 23

If $\mathfrak{G}$ has not directed cycles, then

$\sigma^{ns}_{i}(\mathfrak{G})=\sum_{1\leq j\leq i}\ \
\sum_{\emptyset\subsetneq
S\subseteq\text{min}(\mathfrak{G})}(-1)^{|S|+1}\sigma^{ns}_{j}(\mathfrak{G}-S),$

and

$\sigma^{ns}_{i}(\mathfrak{G})=\sum_{1\leq j\leq i}\ \
\sum_{\emptyset\subsetneq
S\subseteq\text{max}(\mathfrak{G})}(-1)^{|S|+1}\sigma^{ns}_{j}(\mathfrak{G}-S).$

Proof. It is an easy consequence of the inclusion-exclusion principle.

The formulas in the previous theorem are the non-strict versions of the ones
in Theorem 1, and provide us the recurrence relations with which non-strict
counters can be found.

###### Theorem 24

$\sigma^{ns}_{i}(K_{1})=i.$

Proof. If $K_{1}=(\\{v\\},\emptyset)$, then the dispositions of size $i$ in
$K_{1}$ are the mappings $f_{j}$ with $j\in\\{1,\dots,i\\}$ defined by
$f_{j}(v)=j$.

Theorems 22,23 and 24 let us to calculate the number of dispositions for any
digraph. Moreover, if we convey, as we did for strict dispositions, that the
counter of a digraph of order $0$ is $1$, then Theorem 24 follows from Theorem
23.

###### Proposition 17

For any natural number $m$,

$\sigma^{ns}_{i}(P_{n})=\binom{i+n-1}{n}=CR_{i,n}.$

Proof. It is a classic problem in combinatorics. Beginning with a set with $n$
elements, we put $i-1$ separators so that the first separator separates the
$1$s and $2$s, and so on.

###### Example 1

If we consider the digraph $\mathfrak{G}$ in the following figure then by
Theorem 22, $\sigma^{ns}_{i}(\mathfrak{G})=\sigma^{ns}_{i}(P_{3})$, and by
Proposition 17, this equals $\binom{i+2}{3}$.

Figure 16: Directed path with directed cycle

The following theorem is the non-strict analogous of Theorem 2. Its proof
follows the line of that theorem, and will be omitted.

###### Theorem 25

If $\mathfrak{G}=(V,A)$ is a digraph of order $n$ and $i\in\mathbb{N}$, and

$\mathfrak{G}_{1}=(V_{1},A_{1}),\dots,\mathfrak{G}_{r}=(V_{r},A_{r})$

are the connected components of orders $n_{1},\dots,n_{r}$, respectively, of
the underlying undirected graph $\mathfrak{U}(\mathfrak{G})$, then

$\sigma^{ns}_{i}(\mathfrak{G})=\sigma^{ns}_{i}(\mathfrak{G}_{1})\cdots\sigma^{ns}_{i}(\mathfrak{G}_{r}).$

###### Corollary 5

For any natural numbers $n,i$,

$\sigma^{ns}_{i}(E_{n})=i^{n}.$

Proof. Use the previous theorem and Theorem 24.

We can define the non-strict generatrix function in a similar way as we did in
the strict case, both for the case when the size of the dispositions is a
fixed value and when it is equal to the number of vertices.

###### Definition 17

Let $S=\\{\mathfrak{G}_{i}\\}_{i\in\mathbb{Z}^{+}}$, where
$\mathbb{Z}^{+}=\\{i\in\mathbb{Z}\mid i\geq 0\\}$, be a sequence of digraphs
such that $\mathfrak{G}_{i}$ is a subdigraph of $\mathfrak{G}_{i+1}$ for every
$i$, and let $j\in\mathbb{N}$. We will call non-strict generatrix function of
size $j$ of $S$ to

$F^{ns}_{j,S}(X)=\sum_{i=0}^{\infty}\frac{\sigma^{ns}_{j}(\mathfrak{G}_{i})}{i!}X^{i}.$

###### Definition 18

Let $S=\\{\mathfrak{G}_{i}\\}_{i\in\mathbb{Z}^{+}}$ be a sequence of digraphs
such that $\mathfrak{G}_{i}$ is a subdigraph of $\mathfrak{G}_{i+1}$ for every
$i$. We will call non-strict generatrix function of $S$ to

$F^{ns}_{S}(X)=\sum_{i=0}^{\infty}\frac{\sigma^{ns}(\mathfrak{G}_{i})}{i!}X^{i}.$

###### Proposition 18

If $S=\\{P_{n}\\}_{n\in\mathbb{Z}^{+}}$ is a sequence of directed paths and
$j\in\mathbb{N}$, then

$F^{ns}_{j,S}(X)=\exp(X)L_{j-1}(-X),$

where $L_{j-1}$ is the corresponding Laguerre polynomial.

We will use the following lemma, in which, of course, the combinatorial
numbers in which the lower index is greater than the upper one are taken to be
$0$:

###### Lemma 9

If $a,b\in\mathbb{Z}^{+}$, then

$\sum_{s=0}^{\infty}{a\choose s}{b\choose s}={a+b\choose b}$

Proof. It is an immediate consequence of Chu-Vandermonde identity, which
states that

$\sum_{s=0}^{k}{m\choose s}{n-m\choose k-s}={n\choose k},$

by taking $m=a,n=a+b,k=b$.

Now we will prove the proposition:

Proof. On the one hand, by Proposition 17,

$F^{ns}_{j,S}(X)=\sum_{i=0}^{\infty}\frac{{j+i-1\choose i}}{i!}X^{i}$

On the other hand,

$\exp(X)L_{j-1}(-X)=\sum_{i=0}^{\infty}(\sum_{s=0}^{j-1}\frac{{j-1\choose
s}}{s!(i-s)!})X^{i},$

and the result follows from the previous lemma.

###### Proposition 19

If $S=\\{P_{n}\\}_{n\in\mathbb{Z}^{+}}$ is a sequence of directed paths, then

$F^{ns}_{S}(X)=\frac{1}{2}(1+\exp(2X)I_{0}(2X)),$

where $I_{0}$ is the modified Bessel function of the first kind.

We will need the next lemma:

###### Lemma 10

If $i\in\mathbb{Z}^{+}$, then

$\frac{1}{2}\sum_{s=0}^{\infty}\frac{2^{i-2s}}{(i-2s)!(s!)^{2}}=\begin{cases}\frac{1}{2}&\text{if
}i=0,\\\ \frac{{2i-1\choose i}}{i!}&\text{otherwise}\end{cases}$

Proof. It is obvious if $i=0$. Let us suppose that $i>0$. We have that

$(1+X)^{2i}=\sum_{k=0}^{2i}{2i\choose k}X^{k},$ (24)

and also

$(1+X)^{2i}=(1+(2X+X^{2}))^{i}=\sum_{s_{1}=0}^{i}{i\choose
s_{1}}(2X+X^{2})^{s_{1}}$

and, using the binomial theorem we obtain that the previous expression equals

$\sum_{s_{1}=0}^{i}\sum_{s_{2}=0}^{s_{1}}{i\choose s_{1}}{s_{1}\choose
s_{2}}2^{s_{1}-s_{2}}X^{s_{1}+s_{2}}$ (25)

Be equating the coefficient of $X^{i}$ in (24) and in (25) and rearranging the
indexes we get

${2i\choose i}=\sum_{s_{2}=0}^{i}{i\choose s_{2}}{i-s_{2}\choose
s_{2}}2^{i-2s_{2}}$

Since ${2i\choose i}=2{2i-1\choose i}$, we conclude that

${2i-1\choose i}=\sum_{s_{2}=0}^{i}{i\choose s_{2}}{i-s_{2}\choose
s_{2}}2^{i-2s_{2}-1},$

and the result follows trivially.

Now we will prove the proposition:

Proof. By Proposition 17,

$F^{ns}_{S}(X)=\sum_{i=0}^{\infty}\frac{{2i-1\choose i}}{i!}X^{i}$

On the other hand,

$\exp(2X)I_{0}(2X)=(\sum_{r=0}^{\infty}\frac{(2X)^{r}}{r!})(\sum_{s=0}^{\infty}(\frac{X^{s}}{s!})^{2})=\sum_{i=0}^{\infty}(\sum_{s=0}^{\infty}\frac{2^{i-2s}}{(i-2s)!(s!)^{2}})X^{i},$

and the result follows from the previous lemma.

Next we will analyze the non-strict counters of some dispositional digraphs
with two rows. Specifically, we will consider the same dispositional digraphs

$\mathfrak{G}_{n_{1},n_{2}}=\mathcal{G}([n_{2},0],[n_{1},0])$

with $n_{1}\leq n_{2}$ that we studied in Section 5. We will denote again the
vertices by $u_{1},\dots,u_{n_{1}},v_{1},\dots,v_{n_{2}}$.

The following proposition is immediate:

###### Proposition 20

$\min(\mathfrak{G}_{n_{1},n_{2}})=\begin{cases}\\{u_{n_{1}},v_{n_{2}}\\}&\text{
if }n_{1}<n_{2}\\\ \\{u_{n_{1}}\\}&\text{ if }n_{1}=n_{2}\end{cases}$

###### Proposition 21

$\sigma^{ns}_{i}(\mathfrak{G}_{n_{1},n_{2}})$ is

$\displaystyle\sum_{1\leq j\leq
i}[\sigma^{ns}_{j}(\mathfrak{G}_{n_{1}-1,n_{2}})+\sigma^{ns}_{j}(\mathfrak{G}_{n_{1},n_{2}-1})-\sigma^{ns}_{j}(\mathfrak{G}_{n_{1}-1,n_{2}-1})]$

when $n_{1}<n_{2}$ and is

$\displaystyle\sum_{1\leq j\leq
i}\sigma^{ns}_{j}(\mathfrak{G}_{n_{1}-1,n_{1}})$

when $n_{1}=n_{2}$, with the initial conditions

$\sigma^{ns}_{j}(\mathfrak{G}_{n_{1},0})=\sigma^{ns}_{j}(P_{n_{1}})=PR_{j,n_{1}}$

and

$\sigma^{ns}_{j}(\mathfrak{G}_{0,n_{2}})=\sigma^{ns}_{j}(P_{n_{2}})=PR_{j,n_{2}}$

Proof. Use Theorem 23 and Propositions 17 and 20.

The following result can now be easily proved inductively by using the
previous proposition, and the proof will be omitted.

###### Proposition 22

If $n_{1}\leq n_{2}$, then

$\sigma^{ns}_{i}(\mathfrak{G}_{n_{1},n_{2}})=\frac{in_{2}-(n_{1}-1)i+n_{1}}{(n_{2}+1)i}CR_{i,n_{1}}CR_{i,n_{2}}=(1+\frac{n_{1}(1-i)}{(n_{2}+1)i})CR_{i,n_{1}}CR_{i,n_{2}}$

To finish the paper, we will present some differential equations derived from
non-strict dispositions in digraphs.

###### Proposition 23

The generatrix function $F^{ns}_{S}(X)$ of Proposition 19 satisfies the
differential equation

$XY^{\prime\prime}+(1-4x)Y^{\prime}-2Y+1=0$

Proof. It is an easy consequence of that proposition.

As a consequence, we obtain:

###### Corollary 6

The function $\exp(2x)I_{0}(2x)$ satisfies the differential equation

$XY^{\prime\prime}+(1-4x)Y^{\prime}-2Y=0$

We note that the previous differential equation is formally very similar to
Laguerre’s equation, although the solution is not a polynomial, but it has a
discrete interpretation in terms of non-strict counters of digraphs.

In general, if we define for $n,m,k\in\mathbb{N}$

$F_{n,m,k}(X)=\exp(nx)I_{m}(kx),$

then it is easy to prove, by expanding the function as a power series, the
following:

###### Proposition 24

The function $F_{n,m,k}(X)$ satisfies the differential equation

$X^{2}Y^{\prime\prime}+(X-2nX^{2})Y^{\prime}+(-m^{2}-nX+(n^{2}-k^{2})X^{2})Y=0$

In particular, when $n=k$ the $X^{2}$ in the coefficient of $Y$ vanishes, and
we get that $F_{n,k,n}(X)$ satisfies the differential equation

$X^{2}Y^{\prime\prime}+(X-2nX^{2})Y^{\prime}-(m^{2}+nX)Y=0$

If, besides, $m=0$ the $X$ factor simplifies, and we get the differential
equation

$XY^{\prime\prime}+(1-2nX)Y^{\prime}-nY=0,$

which for $n=2$ is the one shown in Corollary 6.

It would be interesting to study if the functions $F_{n,m,k}(X)$ have a
combinatorial interpretation similar to the one that we presented in the
corollary.

Acknowledgements

We would like to thank Martin Milanič for helpful discussions.

## References

  * [1] J. Bang-Jensen, G.Z. Gutin, Digraphs, Theory, Algorithms and Applications, Second Edition, Springer (2010)
  * [2] W.H. Burge, Four correspondences between graphs and generalized young tableaux, Journal of Combinatorial Theory (A) 17, 12-30 (1974).
  * [3] B.T. Chan, Periodic P-partitions, European Journal of Combinatorics 107 (2023) 103599.
  * [4] S. Dubovichenko, A. V. Dzhazairov-Kakhramanov, Study of the neutron and proton capture reactions B-10,B-11(n, gamma), B-11(p, gamma), C-14(p, gamma), and N-15(p, gamma) at thermal and astrophysical energies, Int. J. Mod. Phys. E. 23 (2014) DOI: 10.1142/S0217732314501259.
  * [5] K. Eriksson, J. Sjöstrand, Limiting shapes of birth-and-death processes on Young diagrams. Advances in Applied Mathematics 48 (2012) 575-602.
  * [6] G. Frobenius, Über die Charaktere der symmetrischen Gruppe, Sitz. König.Preuss. Akad. Wissen. (1900) 516–534.
  * [7] S. Fujita, Stereochemistry and stereoisomerism characterized by the sphericity concept, Chemical Soc. Japan 74 (2001) 1585–1603.
  * [8] G.C. Haynes, F.R. Cohen, D.E. Koditschek, Gait transitions for quasi-static hexapedal locomotion on level ground, Springer Tracts in Advanced Robotics 70 (2011) 105–121.
  * [9] N.J.A. Harvey, Matroid intersection, pointer chasing, and young’s seminormal representation of $S_{n}$, SODA’08: Proceedings of the nineteenth annual ACM-SIAM symposium on discrete algorithms. January 2008. Pages 542-549.
  * [10] https://www.cryptographic.co.uk/zigzag.html
  * [11] Andrew Hodges and C. V. Sukumar, Bernoulli, Euler, permutations and quantum algebras, Proc. R. Soc. A (2007) 463, 2401-2414 doi:10.1098/rspa.2007.0001
  * [12] R.C. King, N.G.I. El-Sharkaway, Standard Young tableaux and weight multiplicities of the classical Lie groups, J. Phys. A: Math. Gen. 16 (1983) 3153–3177.
  * [13] D.E. Knuth, Permutations, matrices, and generalized young tableaux, Pacific Journal of Mathematics, Vol. 34, Nº 3 (1970).
  * [14] J.B. Lewis, Pattern avoidance for alternating permutations and reading words of tableaux, PhD Thesis, 2012.
  * [15] A.V. Luzanov, Spin-Free Quantum Chemistry: What one can gain from Fock’s cyclic symmetry, Int. J. Quantum Chem. 111 (2011) 4042–4066.
  * [16] M. Mathur, I. Raychowdhury, R. Anishetty, SU(N) irreducible Schwinger bosons, Journal of Mathematical Physics, Volume 51, Issue 9 (2010).
  * [17] R. Merris and T. Roby, The lattice of threshold graphs, Journal of Inequalities in Pure and Applied Mathematics, Volume 6, Issue 1, Article 2 (2005).
  * [18] V. G. Neudatchin, B.G. Struzhko, V.M. Lebedev, Supermultiplet potential model of interaction between the lightest clusters and a unified description of various nuclear reactions, Phys. Part. Nuclei 36 (2005) 468–497.
  * [19] M. Orlowski, M. Pachter, An algorithm for the determination of a longest increasing subsequence in a sequence, Computers & Mathematics with Applications, Volume 17, Issue 7, 1073-1075 (1989).
  * [20] J. Pappe, D. Paul, A. Schilling, The Burge correspondence and crystal graphs, European Journal of Combinatorics, V. 108, February 2023, 103640.
  * [21] R.A. Proctor, Young tableaux, Gelfand patterns, and branching rules for classical groups, J. Algebra 164 (1994) 299–360.
  * [22] S. Roman, Advanced Linear Algebra, Springer Verlag, 1992.
  * [23] R.P. Stanley, Ordered structures and partitions, Ph.D. thesis (Harvard University, 1971), written under the guidance of Professor Gian-Carlo Rota.
  * [24] R.P. Stanley, Enumerative Combinatorics, Volume 2, Cambridge University Press, 1999.
  * [25] C. V. Sukumar and Andrew Hodges, Quantum algebras and parity-dependent spectra, Proc. R. Soc. A (2007) 463, 2415-2427 doi:10.1098/rspa.2007.0003
  * [26] P. Sun, Enumeration of standard Young tableaux of shifted strips with constant width, The electronic journal of combinatorics, Volume 24, Issue 2 (2017).
  * [27] A. Vera-López, M.A. García-Sánchez, O. Basova, F.J. Vera-López, A generalization of Catalan numbers, Discrete Math. 332 (2014) 23-39.
  * [28] A. Vera, L. Martínez, A. Vera, B. Vera, O. Basova, Combinatorics related to Higman’s conjecture I: Parallelogramic digraphs and dispositions, Linear Algebra and its Applications, V. 530, Issue 1, 414-444 (2017).
  * [29] https://oeis.org/
  * [30] A. -A.A. Yutsis, Tournaments and generalized young tableaux, Mathematical notes of the Academy of Sciences of the USSR 27, 175-178 (1980)
  * [31] http://bergeron.math.uqam.ca/qt-catalan-polynomials-2/?lang=es