# Encoding acyclic orientation of complete multipartite graphs

Walter Carballosa<EMAIL_ADDRESS>Jessica Khera<EMAIL_ADDRESS>Francisco
Reyes<EMAIL_ADDRESS>
###### Abstract

In this work we study the acyclic orientations of complete multipartite
graphs. We obtain an encoding of the acyclic orientations of the complete
$p$-partite graph with size of its parts $n:=n_{1},n_{2},\ldots,n_{p}$ via a
vector with $p$ symbols and length $n_{1}+n_{2}+\ldots+n_{p}$ when the parts
are fixed but not the vertices in each part. We also give a recursive way to
construct all acyclic orientations of a complete multipartite graph, this
construction can be done by computer easily in order $\mathcal{O}(n)$.
Besides, obtained codification of the acyclic orientations allows us to count
the number of non-isomorphic acyclic orientations of the complete multipartite
graphs. Furthermore, we obtain a closed formula for non-isomorphic acyclic
orientations of the complete multipartite graphs with a directed spanning
tree. In addition, we obtain a closed formula for the ordinary generating
functions for the number of strings in the alphabet
$\\{s_{1},s_{2},\ldots,s_{p}\\}$ with $k_{1}$ characters $s_{1}$, $k_{2}$
characters $s_{2}$, and so on with $k_{p}$ characters $s_{p}$ such that no two
consecutive characters are the same. Finally, we obtain a closed formula for
the number of acyclic orientation of a complete multipartite graph
$K_{n_{1},\ldots,n_{p}}$ with labelled vertices.

###### keywords:

Acyclic graphs , encoding graphs , Complete multipartite graphs , enumerating
graphs

###### MSC:

[2020] 05C20 , 05C30

##  1 Introduction

Throughout this paper, we will focus our attention on finite simple graphs
$G$, with $V(G)$ denoting the set of vertices of the graph and $E(G)$ denoting
the set of edges. A multipartite graph is a graph whose vertices can be
partitioned into distinct sets $V_{i}$ so that every edge of the graph
connects a vertex in $V_{i}$ to a vertex in $V_{j}$, with $i\neq j$. A
multipartite graph with $k$ parts is referred to as a $k$-partite graph, and
the complete $k$-partite graph is the graph with $k$ parts which contains an
edge between every pair of vertices from different parts. This is denoted
$K_{n_{1},n_{2},...,n_{k}}$, where each $n_{i}$ is the number of vertices
within part $V_{i}$.

An orientation of a graph is an assignment of a direction to each edge in some
way. An orientation of a graph is said to be _acyclic_ if the assignment does
not form any directed cycles. In an orientation of a graph a vertex is said to
be a _source_ if its in-degree is zero, and similarly, a vertex is said to be
a _sink_ if its out-degree is zero. We denote the multinomial coefficients by
${n\choose a_{1},a_{2},\dots,a_{k}}=\frac{n!}{a_{1}!\cdot a_{2}!\dots a_{k}!}$
where $n=\sum_{i=1}^{k}a_{i}$ and $a_{1},a_{2},\dots,a_{k}$ are nonnegative
integers. Given a graph $G$, we denote the chromatic number of $G$, by
$\chi(G)$. The chromatic number of a graph $G$ is the smallest number of
colors needed to color the vertices of $G$ so that no two adjacent vertices
share the same color. Similarly, $\chi_{G}$ denotes the chromatic polynomial
of $G$. The chromatic polynomial $\chi_{G}$ at a positive integer $\lambda$,
$\chi_{G}(\lambda)$, is defined by the number of $\lambda$-colorings of the
graph $G$.

Acyclic orientations of a graph have been widely studied since the last
century. One of the well-known result about acyclic orientation of a graph,
the Gallai-Hasse-Roy-Vitaver theorem [9, Theorem 3.13, p. 42], was discovered
(several times) during the 60’s by these four authors above. The theorem
states that the chromatic number of a connected graph equals one more than the
length of the longest path in an acyclic orientation chosen to minimize this
path length. In 1973, Stanley [14] obtains that the number of acyclic
orientation of a graph $G$ with order $n$ is $(-1)^{n}\chi_{G}(-1)$. In 1986,
Linial [8] used this result to prove that the number of acyclic orientation of
a graph is an #P-complete problem. In 1984, Johnson [6] investigated the
relationship between certain acyclic orientations and network reliability. In
that paper, Johnson describes how generating the acyclic orientations of a
network with a unique source can be used in computing its reliability. Other
constructive methods for listing the acyclic orientation of a graph $G$ were
investigated in [10, 11, 12, 13]. Squire’s algorithm in [13] requires
$\mathcal{O}(n)$ time per acyclic orientation generated. Acyclic orientations
of complete bipartite graphs were studied in [7] and [15], and here, in this
work, we extend to complete multipartite graphs.

In this paper we study the acyclic orientations of complete multipartite
graphs. In Section 2, we focus primarily on acyclic orientations with
unlabelled vertices. We obtain a recursive way to construct all acyclic
orientations of a complete multipartite graph with unlabelled vertices, and
this construction can be done easily with a computer in order $\mathcal{O}(n)$
supported on the encoding given by Theorem 2.5 that is shown in (2.2).
Additionally, Theorem 2.7 counts the number of non-isomorphic acyclic
orientations of the complete multipartite graphs; in particular, we obtain
that $B(n_{1},\ldots,n_{p})=\frac{{n_{1}+\ldots+n_{p}\choose
n_{1},\ldots,n_{p}}}{r_{1}!r_{2}!\ldots r_{s}!}$ where
$r_{1},r_{2},\ldots,r_{s}$ are the number of parts in $K_{n_{1},\ldots,n_{p}}$
grouped by the same size. Theorem 2.8 gives a closed formula for non-
isomorphic acyclic orientations of the complete multipartite graphs with a
directed spanning tree,
$\mathcal{C}(n_{1},\ldots,n_{p})=\displaystyle\frac{{n_{1}+\ldots+n_{p}\choose
n_{1},\ldots,n_{p}}}{r_{1}!\ldots
r_{s}!}\cdot\frac{(n_{1}+\ldots+n_{p})^{2}-(n_{1}^{2}+\ldots+n_{p}^{2})}{(n_{1}+\ldots+n_{p})^{2}-(n_{1}+\ldots+n_{p})}$.
In Section 3, we deal with the acyclic orientation of complete multipartite
graphs with labelled vertices. In this sense, we obtain a closed formula for
the ordinary generating functions
$\mathcal{F}(x_{1},x_{2},\ldots,x_{p}):=\displaystyle\sum_{k_{1},\ldots,k_{p}\in\mathbb{N}}X_{k_{1},k_{2},\ldots,k_{p}}\,x_{1}^{k_{1}}x_{2}^{k_{2}}\ldots
x_{p}^{k_{p}}$, where $X_{k_{1},\ldots,k_{p}}$ is the number of strings in the
alphabet $\\{s_{1},s_{2},\ldots,s_{p}\\}$ with $k_{1}$ characters $s_{1}$,
$k_{2}$ characters $s_{2}$, and so on, with $k_{p}$ characters $s_{p}$ such
that no two consecutive characters are the same. In Theorem 3.4, we obtain a
closed formula for the number of acyclic orientation of a complete
multipartite graph $K_{n_{1},\ldots,n_{p}}$ with labelled vertices. Finally,
we discuss the longest paths in acyclic orientations of complete multipartite
graphs. Proposition 3.5 gives that the length of the longest path in an
acyclic orientation $\mathcal{K}$ of a complete multipartite graph is the size
of the partition induced by $R_{\mathcal{K}}$ minus one. Furthermore, the
number of longest paths in $\mathcal{K}$ is given by the multiplication of the
sizes of each part of the partition induced by $R_{\mathcal{K}}$. Relation
$R_{\mathcal{K}}$ is defined on $V(K_{n_{1},\ldots,n_{p}})$ such that two
vertices are related by $R_{\mathcal{K}}$ if the two vertices are represented
in the code within a sub-string of consecutive and identical codes.

##  2 Encoding acyclic orientations of complete multipartite graphs

In this Section, we deal with encoding the acyclic orientations of the
complete multipartite graphs with labelled parts but unlabelled vertices. The
encoding we obtain allows us to count the number of non-isomorphic acyclic
orientations of the complete multipartite graphs and for non-isomorphic
acyclic orientations of the complete multipartite graphs with a directed
spanning tree (_i.e._ , an acyclic orientation with a unique source).

######  Lemma 2.1.

In every acyclic orientation of a complete multipartite graph there are both
source and sink vertices.

Furthermore, all sources (sinks, respectively) are vertices in the same part
of the multipartite graph, whenever there are more than one source (sink,
respectively).

###### Proof.

Let us consider $K_{n_{1},n_{2},\ldots,n_{p}}$, a complete $p$-partite graph,
$n_{i}\geq 1$ for every $1\leq i\leq p$. We show here below a proof for the
existence of a source. Note that the existence of a sink is analogous since by
reversing the orientations in any acyclic orientation of a graph, the
resulting orientation is still acyclic and a source in the reversed
orientation is a sink in the original orientation. First, we claim the result
is true for $p=2$.

Claim 1: _There is a source in every acyclic orientation of $K_{n_{1},n_{2}}$
for every $n_{1},n_{2}\geq 1$_.

We prove this by induction on $n_{1}+n_{2}\geq 2$. Note that there is a source
in an acyclic orientation of $K_{1,1}$. Assume now that there is a source for
every acyclic orientation of $K_{n_{1},n_{2}}$ with $n_{1}+n_{2}=n\geq 2$.
Consider an acyclic orientation of $G:=K_{n_{1}^{*},n_{2}^{*}}$ with order
$n_{1}^{*}+n_{2}^{*}=n+1$ and a vertex $v$ in Part 1 (Part with size
$n_{1}^{*}$). If one of the parts of $G$ has only one vertex, $G$ is a star;
and consequently, we have either the central vertex of the Star is a source or
one of the other vertices is. Assume, $n_{1}^{*},n_{2}^{*}>1$. Hence, there is
a source by assumption in the orientation obtained by removing $v$ from $G$,
_i.e._ , in $G^{\prime}:=G-\\{v\\}$. If one of its sources is a vertex in Part
1, the result is done. So, we can assume the source in $G^{\prime}$ is a
vertex in Part 2. Denote that vertex, $w$. Note that if the orientation
assigned to edge $vw$ is oriented from $w$ to $v$, then $w$ is a source in
$G$, and the result is given. Assume the orientation assigned to edge $vw$ is
oriented from $v$ to $w$. There is a source by assumption in the orientation
obtained by removing $w$ from $G$, _i.e._ , in $G^{\prime\prime}:=G-\\{w\\}$.
If one of the source in $G^{\prime\prime}$ is a vertex in Part 2, the result
is done. We can assume the source in $G^{\prime\prime}$ is a vertex in Part 1.
Denote that vertex, $v^{\prime}$. If $v$ is a source of $G^{\prime\prime}$,
then $v$ is a source in $G$. Thus, assume $v$ is not a source in
$G^{\prime\prime}$ and there exists a vertex $w^{\prime}$ in Part 2 such that
edge $vw^{\prime}$ is oriented from $w^{\prime}$ to $v$ creating a cycle $v\to
w\to v^{\prime}\to w^{\prime}$ which is impossible. Therefore, either $w$ or
$v$ is a source in $G$. Note that could be more than one source, but in that
case all the sources are in the same part.

Claim 2: _There is a source in every acyclic orientation of
$K_{n_{1},n_{2},n_{3}}$ for every $n_{1},n_{2},n_{3}\geq 1$_.

Let $A,B,C$ be the three parts of $K_{n_{1},n_{2},n_{3}}$ with corresponding
sizes $n_{1},n_{2},n_{3}$, respectively. Let $\mathcal{K}$ be an acyclic
orientation of $K_{n_{1},n_{2},n_{3}}$. Consider $A-B$ ($B-C$ and $C-A$,
respectively) the acyclic orientation in $K_{n_{1},n_{2}}$ ($K_{n_{2},n_{3}}$
and $K_{n_{3},n_{1}}$, respectively) considering only Parts $A\cup B$ ($B\cup
C$ and $C\cup A$, respectively). By Claim 1, there is a source in each of
$A-B$, $B-C$ and $C-A$. Since $\mathcal{K}$ is an acyclic orientation, the
orientation of the sources cannot be all three $A\to B$, $B\to C$ and $C\to
A$; nor its corresponding inverse orientations. However, two of its sources
(out of the three sub-orientations) must have consecutive orientations by the
Pigeonhole Principle. Without loss of generality we can assume that there is a
source in $A-B$ that is a vertex in Part $A$ and a source in $B-C$ that is a
vertex in Part $B$, see Figure 1. Thus, the source of $A-B$ in Part $A$ is
also a source in $C-A$; otherwise, there is a cycle in $\mathcal{K}$ with
length three.

$A$$B$$C$ Figure 1: Two sources in consecutive orientations $A\to B$ and $B\to
C$ for visualizing the argument in Claim 2.

Claim 3: _There is a source in every acyclic orientation of
$K_{n_{1},n_{2},\ldots,n_{p}}$ for every $n_{1},n_{2},\ldots,n_{p}\geq 1$ and
$p\geq 2$_.

Claims 1 and 2 give the result for $p=2,3$. Assume now that Claim 3 is true
for some $p\geq 3$. Consider $G:=K_{n_{1},\ldots,n_{p},n_{p+1}}$ and let
$\mathcal{K}$ be an acyclic orientation of $G$. Let $P_{i}$ be the part of
$K_{n_{1},\ldots,n_{p},n_{p+1}}$ with corresponding sizes $n_{i}$, for every
$1\leq i\leq p+1$. Hence, there is a source by assumption in the orientation
$\mathcal{K}^{\prime}$ obtained by removing the part $P_{p+1}$ from $G$,
_i.e._ , in $G^{\prime}:=G-P_{p+1}$. Without loss of generality we can assume
that such sources are vertices in $P_{1}$. Similarly, there is a source by
assumption in the orientation $\mathcal{K}^{\prime\prime}$ obtained by
removing the part $P_{1}$ from $G$, _i.e._ , in $G^{\prime\prime}:=G-P_{1}$.
So, without loss of generality we can assume that the sources in
$G^{\prime\prime}$ are vertices in $P_{2}$. Consider now the acyclic
orientation $\mathcal{K}^{\prime\prime\prime}$ obtained from $G$ by removing
all edges with both endpoints in $P_{3}\cup P_{4}\cup\ldots\cup P_{p+1}$. Note
that this is an acyclic orientation of a complete tripartite graph
$K_{n_{1},n_{2},n_{3}+\ldots+n_{p}+n_{p+1}}$. Thus, by Claim 2 there is a
source in $\mathcal{K}^{\prime\prime\prime}$ that is a vertex in either
$P_{1}$ or $P_{2}$. Therefore, this is a source of $\mathcal{K}$, too.

Finally, arguments above give that if there are more than one source (sink,
respectively) then all sources (sinks, respectively) are vertices in the same
part of the complete multipartite graph. ∎

Lemma 2.1 has the following direct consequences.

######  Corollary 2.2.

In every acyclic orientation of a non-empty graph there are both source and
sink vertices.

###### Proof.

Let $\mathcal{K}$ be an acyclic orientation of a given graph $G(V,E)$. It is
well-known that an acyclic orientation induces a partial ordering $<$ on the
vertices of $G$, defined by two vertices $v_{1},v_{2}\in V$ which satisfy
$v_{1}<v_{2}$ if and only if there is a directed path from $v_{1}$ to $v_{2}$
along the edges of the orientation. Let’s consider a listing $\mathcal{L}$ of
the vertices of $G$ that preserve the partial ordering above induced by the
acyclic orientation. Clearly, such a listing provides to $V$ with a total
order. Hence, we can complete an acyclic orientation $\mathcal{K}^{\prime}$ of
$K_{n}\simeq K_{\underbrace{1,\ldots,1}_{n}}$ from $\mathcal{K}$ by adding new
directed edges according to ordering in $\mathcal{L}$, _i.e._ , adding
$(v_{1},v_{2})$ to $\mathcal{K}^{\prime}$ if $v_{1}$ precedes $v_{2}$ in
$\mathcal{L}$. Thus, by Lemma 2.1 there are both source and sink vertices in
$\mathcal{K}^{\prime}$ that also are source and sink, respectively, in
$\mathcal{K}$ after removing the same directed edges. ∎

######  Corollary 2.3.

Let $G$ be an undirected graph without isolated vertices and let $\mathcal{G}$
be an acyclic orientation of $G$. Then, $\mathcal{G}$ has a directed spanning
tree if and only if $\mathcal{G}$ has a unique source.

###### Proof.

Note that if there is a spanning tree in $\mathcal{G}$ then the root of the
spanning tree is the only one source. Assume now that there is only one source
in $\mathcal{G}$ and there does not exist a directed spanning tree in
$\mathcal{G}$. Denote $v$ the source in $\mathcal{G}$. Consider the largest
directed tree in $\mathcal{G}$ with root $v$, denoted $\mathcal{T}$. Since
$\mathcal{T}$ is not a spanning tree, there is a non-empty collection of
vertices in $G$ not included in $\mathcal{T}$, _i.e._ , $V(G)\setminus
V(\mathcal{T})\neq\emptyset$. Thus, since $G$ has no isolated vertices, every
isolated vertex in $\mathcal{R}:=\langle V(G)\setminus V(\mathcal{T})\rangle$
is a source in $\mathcal{G}$, but this is a contradiction. If $\mathcal{R}$
has no isolated vertices, by Corollary 2.2, $\mathcal{R}$ has a source $w\neq
v$ that is also a source of $\mathcal{G}$. This is the contradiction we were
looking for, therefore this completes the proof. ∎

For every collection of natural numbers $n_{1},n_{2},\ldots,n_{p}$, with
$p\geq 2$, we define the number of acyclic orientations of a complete
multipartite graph with fixed parts with respective sizes
$n_{1},n_{2},\ldots,n_{p}$ and unlabelled vertices, by
$\mathcal{A}(n_{1},n_{2},\ldots,n_{p})$. We define
$\mathcal{A}(n_{1},n_{2},\ldots,n_{p})$ such that one or more parts of the
multipartite graph may be zero. This notation will be convenient. For
instance, $\mathcal{A}(0,1,2)$ actually represents the number of acyclic
orientations of a complete bipartite graph $K_{1,2}$ since the first part of
the tripartite graph is empty. In the same way, $\mathcal{A}(1,0,2)$,
$\mathcal{A}(0,1,0,0,2)$ and many others also represent $\mathcal{A}(1,2)$.
Note that $\mathcal{A}(0,0,n)$ represents the number of acyclic orientations
of a tripartite graph with at most one non-null (third) part with $n$
vertices, _i.e._ , the empty graph $E_{n}$, and consequently,
$\mathcal{A}(0,0,n)=1$ for all natural numbers $n$. For obvious reasons
$\mathcal{A}(n_{1},n_{2},\ldots,n_{p})$ is symmetric with respect to the
permutation of their entries.

######  Proposition 2.4.

$\mathcal{A}(n_{1},n_{2},\ldots,n_{p})$ satisfies

$\mathcal{A}(n_{1},n_{2},\ldots,n_{p})=\mathcal{A}(n_{1}-1,n_{2},\ldots,n_{p})+\mathcal{A}(n_{1},n_{2}-1,\ldots,n_{p})+\ldots+\mathcal{A}(n_{1},n_{2},\ldots,n_{p}-1).$
(2.1)

with initial values $\mathcal{A}(n_{1},n_{2},\ldots,n_{p})=0$ if $n_{i}=-1$
for some $1\leq i\leq p$, and $\mathcal{A}(0,\ldots,0)=1$.

###### Proof.

Consider a complete multipartite graph $K_{n_{1},\ldots,n_{p}}$ and let
$\mathcal{K}$ be one of its acyclic orientations. By Lemma 2.1 there is at
least one source in $\mathcal{K}$ and all its sources are vertices in the same
part. Let $v$ be one of the sources in $\mathcal{K}$. Without loss of
generality we can assume that $v$ is a vertex in Part 1, $n_{1}\geq 1$. Note
that the acyclic orientation $\mathcal{K}^{\prime}$ obtained by removing $v$
and the edges started at $v$ from $\mathcal{K}$ we obtain an acyclic
orientation of $K_{n_{1}-1,n_{2},\ldots,n_{p}}$. Since the arbitrary choice of
the source may run over all parts, one at the time, and the parts of
$K_{n_{1},\ldots,n_{p}}$ are fixed, we obtain

$\mathcal{A}(n_{1},n_{2},\ldots,n_{p})=\mathcal{A}(n_{1}-1,n_{2},\ldots,n_{p})+\mathcal{A}(n_{1},n_{2}-1,\ldots,n_{p})+\ldots+\mathcal{A}(n_{1},n_{2},\ldots,n_{p}-1).$

the initial values of the recursive formula (2.1) follows from the natural
meaning of $\mathcal{A}(0,\ldots,0)$, _i.e._ , the number of acyclic
orientations in a multipartite graph with empty parts of vertices
$K_{0,\ldots,0}$. Clearly, from a part with no vertices there are no source to
remove from, so $\mathcal{A}(n_{1},n_{2},\ldots,n_{p})=0$ if $n_{i}=-1$ for
some $1\leq i\leq p$. ∎

$x_{1}$$x_{2}$$y_{1}$$y_{2}$$z_{1}$ Figure 2: An acyclic orientation of
$K_{2,2,1}$ (5-wheel graph) with consecutive sources:
$x_{1},y_{1},x_{2},y_{2}$ respectively

Figure 2 shows the sequence of sources in an acyclic orientation of the
$5$-wheel graph, a complete tripartite graph $K_{2,2,1}$, providing a general
view for whatever acyclic orientations of a multipartite graph. Proposition
2.4 gives a direct procedure to generate all acyclic orientations of a
multipartite graph, as well as encoding each orientation in an easy way.
Define $[n]:=\\{0,1,2,\ldots,n-1\\}$ for every natural number $n$.

######  Theorem 2.5.

There is a one-to-one correspondence from the set of all acyclic orientations
of a complete multipartite graph with at most $p$ fixed parts and $[p^{N}]$,
where $N$ is the order of $G$. This correspondence assigns to each acyclic
orientation with an $N$-vector code in $[p]^{N}$.

###### Proof.

Consider a complete multipartite graph $G=K_{n_{0},n_{1},\ldots,n_{p-1}}$ with
$p\geq 2$ parts labelled $0,1,2,\ldots,p-1$ where part $i$ has exactly $n_{i}$
unlabelled vertices for $i\in[p]$. Let $\mathcal{L}$ be the set of all non-
null acyclic orientations of complete multipartite graphs that are subgraphs
of $G$, $\overline{\mathcal{L}}:=\mathcal{L}\cup\\{K_{0}\\}$ and let $N$ be
the order of $G$ (_i.e._ , $N=n_{0}+n_{1}+\ldots+n_{p-1}$). Conveniently
consider that all vertices in an empty graph is both a source and a sink.
Define the function $s:\mathcal{L}\to[p]$ as $s(\mathcal{K})=i$ if the sources
of $\mathcal{K}$ are vertices in the part $i$. Define the function
$f:\mathcal{L}\to\overline{\mathcal{L}}$ as $f(\mathcal{K})$ is the acyclic
orientation $\mathcal{K}^{\prime}$ obtained from $\mathcal{K}$ by removing one
of the sources of $\mathcal{K}$. Let’s consider $\mathcal{K}$ a non-null
acyclic orientation of $G$. Clearly, the functions $s$ and $f$ are well
defined.

Now, we encode each acyclic orientation of $G$ as follows. Thus, we
recursively define the code function $C:\overline{\mathcal{L}}\to[p]^{*}$ for
$\mathcal{K}$ as

$C(\mathcal{K})=\left\\{\begin{aligned}
s(\mathcal{K}).C\left(f(\mathcal{K})\right),&\text{ if }\mathcal{K}\text{ is
non-null}\\\ \lambda,&\text{ if }\mathcal{K}\text{ is
null}\end{aligned}\right.$ (2.2)

where $\lambda$ is the empty string, . denotes the concatenation of strings,
and $[p]^{*}$ denotes the set of all strings in the alphabet
$\\{0,1,2,\ldots,p-1\\}$. Note that code function is well defined.
Specifically, the code for an acyclic orientation of $G$ will be a string in
$[p]^{*}$ with length $N$ since it concatenates one (source) vertex at the
time until the null graph appears. ∎

12345$n_{0}$$n_{1}$ Figure 3: An acyclic orientation of $K_{2,3}$ with
sequences of sources $(2,3,1,4,5)$ or $(2,3,1,5,4)$, and code $0.1.0.1.1$

Figure 3 shows the encoding of an acyclic orientation of $K_{2,3}$. Table 1
shows all acyclic orientations of $K_{2,2}$ with its corresponding codes.
Encoding given in Theorem 2.5 allows to obtain a closed formula for
$\mathcal{A}(n_{1},n_{2},\ldots,n_{p})$, see Theorem 2.6.

$x_{1}$$y_{1}$$x_{2}$$y_{2}$ | $x_{1}$$y_{1}$$x_{2}$$y_{2}$ | $x_{1}$$y_{1}$$x_{2}$$y_{2}$ | $x_{1}$$y_{1}$$x_{2}$$y_{2}$
---|---|---|---
$0.1.0.1$ | $0.1.0.1$ | $0.1.0.1$ | $0.1.0.1$
$x_{1}$$y_{1}$$x_{2}$$y_{2}$ | $x_{1}$$y_{1}$$x_{2}$$y_{2}$ | $x_{1}$$y_{1}$$x_{2}$$y_{2}$ | $x_{1}$$y_{1}$$x_{2}$$y_{2}$
$1.0.1.0$ | $1.0.1.0$ | $1.0.1.0$ | $1.0.1.0$
$x_{1}$$y_{1}$$x_{2}$$y_{2}$ | $x_{1}$$y_{1}$$x_{2}$$y_{2}$ | $x_{1}$$y_{1}$$x_{2}$$y_{2}$ | $x_{1}$$y_{1}$$x_{2}$$y_{2}$
$0.1.1.0$ | $0.1.1.0$ | $1.0.0.1$ | $1.0.0.1$
$x_{1}$$y_{1}$$x_{2}$$y_{2}$ | $x_{1}$$y_{1}$$x_{2}$$y_{2}$ | $x_{1}$$y_{1}$$x_{2}$$y_{2}$ | $x_{1}$$y_{1}$$x_{2}$$y_{2}$
$0.0.1.1$ | $1.1.0.0$ | $\lambda$ | $\lambda$
Table 1: All orientations of $K_{2,2}$ with labeled vertices and their
corresponding codes

######  Theorem 2.6.

$\mathcal{A}(n_{1},n_{2},\ldots,n_{p})={n_{1}+n_{2}+\ldots+n_{p}\choose
n_{1},n_{2},\ldots,n_{p}}:=\frac{(n_{1}+n_{2}+\ldots+n_{p})!}{n_{1}!n_{2}!\ldots
n_{p}!}.$ (2.3)

###### Proof.

The result is a direct consequence of counting the number of codes as in
Theorem 2.5, _i.e._ , numbers in the numerical system of base $p$ with length
$n_{1}+n_{2}+\ldots+n_{p}$ and with exactly $n_{1}$ digits $0$, $n_{2}$ digits
$1$, …, $n_{p}$ digits $p-1$. ∎

We can also obtain the result above by proving that (2.3) satisfies the
recurrence given in Proposition 2.4. Let us now denote by
$\mathcal{B}(n_{1},n_{2},\ldots,n_{p})$ the number of non-isomorphic acyclic
orientations of the complete multipartite graph
$K_{n_{1},n_{2},\ldots,n_{p}}$. The encoding given in Theorem 2.5 allows us to
obtain the number of non-isomorphic acyclic orientations of complete
multipartite graphs, see Theorem 2.7.

$n_{0}$$n_{1}$ | $n_{0}$$n_{1}$ | $n_{0}$$n_{1}$
---|---|---
$0.0.1.1$ | $0.1.1.0$ | $0.1.0.1$
Table 2: All non-isomorphic acyclic orientations of $K_{2,2}$ with unlabeled
vertices and their corresponding codes

######  Theorem 2.7.

$\mathcal{B}(n_{1},n_{2},\ldots,n_{p})=\frac{{n_{1}+n_{2}+\ldots+n_{p}\choose
n_{1},n_{2},\ldots,n_{p}}}{r_{1}!r_{2}!\ldots r_{s}!}$

where ${n_{1}+n_{2}+\ldots+n_{p}\choose n_{1},n_{2},\ldots,n_{p}}$ is the
multinomial coefficient and $r_{1},r_{2},\ldots,r_{s}$ are the number of parts
in $K_{n_{1},n_{2},\ldots,n_{p}}$ grouping by the same size (i.e. $r_{i}$ for
$i\in\\{1,...,s\\}$ suggests there are $r_{i}$ many parts that contain the
same fixed number of vertices).

###### Proof.

Let $\mathcal{K}_{1},\mathcal{K}_{2}$ be two isomorphic acyclic orientations
of a multipartite graph $G$. Note that every isomorphism
$\sigma:V(\mathcal{K}_{1})\to V(\mathcal{K}_{2})$ matches all vertices of each
part of $\mathcal{K}_{1}$ with all vertices in a part of $\mathcal{K}_{2}$;
otherwise, $\sigma$ doesn’t preserve adjacency. Therefore,
$\mathcal{A}(n_{1},\ldots,n_{k})=\mathcal{B}(n_{1},\ldots,n_{k})$ if
$n_{i}\neq n_{j}$ when $i\neq j$ since the vertices in each part are
unlabelled. Then $\sigma$ matches all sources of $\mathcal{K}_{1}$ with the
sources of $\mathcal{K}_{2}$. Moreover, if we remove all sources from both
$\mathcal{K}_{1}$ and $\mathcal{K}_{2}$ obtaining $\mathcal{K}_{1}^{\prime}$
and $\mathcal{K}_{2}^{\prime}$, respectively, then $\sigma$ matches the
sources of $\mathcal{K}_{1}^{\prime}$ and $\mathcal{K}_{2}^{\prime}$ as well.
We can repeat this removing procedure until a null-graph is obtained. Hence,
the codes assigned to $\mathcal{K}_{1}$ and $\mathcal{K}_{2}$ by Theorem 2.5
match each other except by a possible permutation within of the parts with the
same size. Besides, if there are exactly $r_{1}$ parts with the same size in
$G$, we have $r_{1}!$ different codes associated to isomorphic acyclic
orientations when the (digits) codes assigned to the $r_{1}$ equal-size parts
are permuted and kept the same places for the other digits. Therefore, by
grouping the parts of $G$ with the same size we obtain the result. ∎

From Theorem 2.7, we have that $\mathcal{B}(2,2)=3$. Table 2 shows all 3 non-
isomorphic acyclic orientations of $K_{2,2}$ with their corresponding codes.
Note that by swapping the digits $0$’s and $1$’s we obtain isomorphic acyclic
orientations due to both parts have the same size. Permuting vertices within
each part also obtains an isomorphic orientation. Let us denote by
$\mathcal{C}(n_{1},n_{2},\ldots,n_{p})$ the number of non-isomorphic acyclic
orientations of complete multipartite graph $K_{n_{1},n_{2},\ldots,n_{p}}$
containing a directed spanning tree. Similarly, we can obtain the number of
non-isomorphic acyclic orientations of complete multipartite graphs containing
a directed spanning tree, see Theorem 2.8.

######  Theorem 2.8.

Let $n_{1},\ldots,n_{p}$ be $p$ positive integer numbers and
$N=n_{1}+\ldots+n_{p}$. We have

$\mathcal{C}(n_{1},\ldots,n_{p})=\displaystyle\frac{{N\choose
n_{1},\ldots,n_{p}}}{r_{1}!\ldots
r_{s}!}\cdot\frac{N^{2}-\sum_{r=1}^{p}(n_{r})^{2}}{N(N-1)}.$

where $r_{1},r_{2},\ldots,r_{s}$ are the number of parts in
$K_{n_{1},n_{2},\ldots,n_{p}}$ grouping by the same size.

###### Proof.

The result is a direct consequence of counting the number of codes as in
Theorem 2.5, _i.e._ , numbers in the numerical system of base $p$ with length
$N:=n_{1}+n_{2}+\ldots+n_{p}$ and with exactly $n_{1}$ digits $0$, $n_{2}$
digits $1$, …, $n_{p}$ digits $p-1$ such that the first two digits are
distinct. That is

$\displaystyle\sum_{1\leq i<j\leq
p}2\,\mathcal{A}(\ldots,n_{i}-1,\ldots,n_{j}-1,\ldots)=\frac{\mathcal{A}(n_{1},\ldots,n_{p})}{N(N-1)}\,\sum_{1\leq
i<j\leq p}\,2n_{i}n_{j}$

Then, considering the isomorphic directed graphs obtained by permuting the
parts with the same size, we obtain

$\mathcal{C}(n_{1},\ldots,n_{p})=\displaystyle\frac{\mathcal{A}(n_{1},\ldots,n_{p})}{r_{1}!\ldots
r_{s}!}\,\frac{N^{2}-\sum_{r=1}^{p}(n_{r})^{2}}{N(N-1)}.$

∎

##  3 Acyclic orientations of a complete multipartite graph with labelled
vertices

In this section we deal with the number of acyclic orientation of a complete
multipartite graph with labelled vertices. Note that using the coding in (2.2)
we can also obtain the poly-Bernoulli numbers $B_{n_{1},n_{2}}$, _i.e._ ,
number of acyclic orientation of a labelled complete bipartite graph
$K_{n_{1},n_{2}}$ with size of each part $n_{1}$ and $n_{2}$, respectively,
see Proposition 3.1. It is well-known that poly-Bernoulli number also counts,
for instance, the lonesum matrices [4] and Callan permutations [3] among other
things. The closed formula below was given by Arakawa and Kaneko in [1].

######  Proposition 3.1.

The number of acyclic orientation of a labelled vertices complete bipartite
graph $K_{n_{1},n_{2}}$ with size of each part $n_{1}$ and $n_{2}$,
respectively, is

$B_{n_{1},n_{2}}=\displaystyle\sum_{m=0}^{\min\\{n_{1},n_{2}\\}}\,(m!)^{2}\,{n_{1}+1\brace
m+1}\,{n_{2}+1\brace m+1},$ (3.4)

where ${r\brace s}$ denotes the Stirling number of the second kind.

###### Proof.

Without loss of generality we can assume that $n_{1}\leq n_{2}$. Notice that
we may count the number of acyclic orientations of $K_{n_{1},n_{2}}$ by
grouping them according to $m\geq 1$, the number of groups of $0$’s codes
(code $0$ associated to part with size $n_{1}$) separated by at least a code
$1$. In this case, the number of groups of $1$’s codes separated by at least a
code $0$ must be either $m-1$, $m$ or $m+1$. We recall ${r\brace s}$ is the
number of partitions of a set with $r$ elements into $s$ parts is ${r\brace
s}$, and the well-known identity

${r+1\brace s}=s{r\brace s}+{r\brace s-1}\qquad\text{for all }r,s\geq 0.$

Thus we count it by consider the number of partitions of the $n_{1}$ elements
in Part 1 and the number of partitions of the $n_{2}$ elements in Part 2;
follow by multiplying by the corresponding factorial given by the permutation
of the distinct groups in the partition of each part. Then, we have

$\displaystyle\displaystyle\sum_{m=1}^{n_{1}}\left(m!(m-1)!{n_{1}\brace
m}{n_{2}\brace m-1}+2\,m!m!{n_{1}\brace m}{n_{2}\brace m}+m!(m+1)!{n_{1}\brace
m}{n_{2}\brace m+1}\right)$ $\displaystyle=$
$\displaystyle\sum_{m=1}^{n_{1}}m!(m-1)!{n_{1}\brace m}\left({n_{2}\brace
m-1}+m\,{n_{2}\brace m}\right)+\sum_{m=1}^{n_{1}}(m!)^{2}\,{n_{1}\brace
m}\left({n_{2}\brace m}+(m+1)\,{n_{2}\brace m+1}\right)$ $\displaystyle=$
$\displaystyle\sum_{m=1}^{n_{1}}m!(m-1)!{n_{1}\brace m}{n_{2}+1\brace
m}+\sum_{m=1}^{n_{1}}(m!)^{2}\,{n_{1}\brace m}{n_{2}+1\brace m+1}$
$\displaystyle=$ $\displaystyle\sum_{m=0}^{n_{1}-1}(m+1)!m!{n_{1}\brace
m+1}{n_{2}+1\brace m+1}+\sum_{m=1}^{n_{1}}(m!)^{2}\,{n_{1}\brace
m}{n_{2}+1\brace m+1}$ $\displaystyle=$
$\displaystyle\sum_{m=0}^{n_{1}}(m+1)!m!{n_{1}\brace m+1}{n_{2}+1\brace
m+1}+\sum_{m=0}^{n_{1}}(m!)^{2}\,{n_{1}\brace m}{n_{2}+1\brace m+1}$
$\displaystyle=$
$\displaystyle\sum_{m=0}^{n_{1}}(m!)^{2}\left((m+1)\,{n_{1}\brace
m+1}+{n_{1}\brace m}\right){n_{2}+1\brace m+1}$ $\displaystyle=$
$\displaystyle\sum_{m=0}^{n_{1}}(m!)^{2}{n_{1}+1\brace m+1}{n_{2}+1\brace
m+1}$ $\displaystyle=$ $\displaystyle\,B_{n_{1},n_{2}}.$

∎

In order to obtain the result for the number of acyclic orientation of a
labelled multipartite graph with $p\geq 3$ parts in a similar way, we define
$X_{k_{1},k_{2},\ldots,k_{p}}$ by the number of strings in the alphabet
$\mathcal{S}:=\\{s_{1},s_{2},\ldots,s_{p}\\}$ with $k_{1}$ characters $s_{1}$,
$k_{2}$ characters $s_{2}$, and so on with $k_{p}$ characters $s_{p}$ such
that no two consecutive characters are the same. We define
$X^{(i)}_{k_{1},k_{2},\ldots,k_{p}}$ by the number of strings in $\mathcal{S}$
with $k_{1}$ characters $s_{1}$, $k_{2}$ characters $s_{2}$, and so on with
$k_{p}$ characters $s_{p}$ such that there are no two consecutive identical
characters and the first character is $s_{i}$ for $1\leq i\leq p$. Clearly, we
have

$X_{k_{1},\ldots,k_{p}}=X^{(1)}_{k_{1},\ldots,k_{p}}+X^{(2)}_{k_{1},\ldots,k_{p}}+\ldots+X^{(p)}_{k_{1},\ldots,k_{p}}.$
(3.5)

Note that for some $p$-tuples $(k_{1},\ldots,k_{p})\in\mathbb{N}^{p}$, we have
$X_{k_{1},\ldots,k_{p}}=0$, for instance, $X_{2,0,\ldots,0}=0$ since we cannot
alternate two characters $s_{1}$ and no other characters without leaving two
consecutive characters $s_{1}$. Moreover, $X_{k_{1},\ldots,k_{p}}>0$ if and
only if $(k_{1},\ldots,k_{p})\in\mathbb{T}$ where

$\mathbb{T}:=\left\\{(k_{1},\ldots,k_{p})\in\mathbb{N}^{p}\,:\,\max\\{k_{1},k_{2},\ldots,k_{p}\\}\leq\frac{1+\sum_{i=1}^{p}k_{i}}{2}\right\\}.$

Hence, we have

$X^{(j)}_{k_{1},k_{2},\ldots,k_{p}}\,=\displaystyle\sum_{i=1}^{p}\,X^{(i)}_{k_{1},\ldots,k_{j}-1,\ldots,k_{p}}\,-\,X^{(j)}_{k_{1},\ldots,k_{j}-1,\ldots,k_{p}}\,+\chi_{\\{e_{j}\\}}(k_{1},k_{2},\ldots,k_{p})$
(3.6)

for all $k_{1},k_{2},\ldots,k_{p}\in\mathbb{N}$ and $1\leq j\leq p$ where
$e_{j}$ represents the $j^{th}$ canonical vector of $\mathbb{R}^{p}$ and
$\chi_{A}$ is the indicator of $A$. For obvious reasons consider
$X_{k_{1},k_{2},\ldots,k_{p}}=X^{(j)}_{k_{1},k_{2},\ldots,k_{p}}=0$ if
$k_{i}<0$ for some $1\leq i\leq p$ and for every $1\leq j\leq p$. Note that,
on the one hand, if $X^{(1)}_{k_{1},k_{2},\ldots,k_{p}}>0$, by removing the
first character (a $s_{1}$) from each string counted in
$X^{(1)}(k_{1},k_{2},\ldots,k_{p})$ we obtain a string counted in
$X^{(j)}_{k_{1}-1,k_{2},\ldots,k_{p}}$ for some $2\leq j\leq p$, except when
$(k_{1},k_{2},\ldots,k_{p})=(1,0,\ldots,0)$ where we consider that the empty
string $\lambda$ did not count. Besides, by adding a character $s_{1}$ to the
front of each string counted in $X^{(j)}_{k_{1}-1,k_{2},\ldots,k_{p}}$ for
$2\leq j\leq p$ we obtain distinct strings in
$X^{(1)}_{k_{1},k_{2},\ldots,k_{p}}$; analogously, we obtain the corresponding
relations for $X^{(j)}_{k_{1},k_{2},\ldots,k_{p}}$ for $2\leq j\leq p$,
respectively. On the other hand, if $X^{(1)}_{k_{1},k_{2},\ldots,k_{p}}=0$,
then we have either $k_{1}>1+\sum_{i=2}^{p}k_{i}$ and consequently
$X^{(j)}_{k_{1}-1,k_{2},\ldots,k_{p}}=0$ for $2\leq j\leq p$, or there are
more characters $s_{j}$ than the other characters for some $2\leq j\leq p$
making $X^{(i)}_{k_{1}-1,k_{2},\ldots,k_{p}}=0$ for every $2\leq i\leq p$. We
can obtain analogous equations to (3.6).

Now we define a $p$-variables ordinary generating function

$\mathcal{F}(x_{1},\ldots,x_{p}):=\displaystyle\sum_{k_{1},\ldots,k_{p}\in\mathbb{N}}X_{k_{1},\ldots,k_{p}}\,x_{1}^{k_{1}}x_{2}^{k_{2}}\cdot\ldots\cdot
x_{p}^{k_{p}}.$

Note that $\mathcal{F}(k_{1},\ldots,k_{p})$ converges absolutely on
$|x_{1}|+\ldots+|x_{p}|<1$ since $0\leq
X_{k_{1},\ldots,k_{p}}\leq{k_{1}+\ldots+k_{p}\choose k_{1},\ldots,k_{p}}$ for
all $k_{1},\ldots,k_{p}\in\mathbb{N}$.

######  Proposition 3.2.

We have

$\mathcal{F}(x_{1},\ldots,x_{p})=\displaystyle\frac{\frac{x_{1}}{x_{1}+1}+\ldots+\frac{x_{p}}{x_{p}+1}}{1-\left(\frac{x_{1}}{x_{1}+1}+\ldots+\frac{x_{p}}{x_{p}+1}\right)}.$

###### Proof.

Since $\mathcal{F}(x_{1},\ldots,x_{p})$ converges absolutely in a domain
including
$\Omega:=\\{(x_{1},\ldots,x_{p})\in\mathbb{R}^{p}\,:\,|x_{1}|+\ldots+|x_{p}|<1\\}$.
We may reorder its terms of summation without affecting the sum. Define now

$\mathcal{F}^{(j)}(x_{1},\ldots,x_{p}):=\displaystyle\sum_{k_{1},\ldots,k_{p}\in\mathbb{N}}X^{(j)}_{k_{1},\ldots,k_{p}}\,x_{1}^{k_{1}}x_{2}^{k_{2}}\ldots
x_{p}^{k_{p}}\quad\text{for every }1\leq j\leq p.$

Now by performing the summation of (3.6) for every
$(k_{1},\ldots,k_{p})\in\mathbb{N}^{p}$, we obtain

$\mathcal{F}^{(j)}(x_{1},\ldots,x_{p})=x_{j}\,\displaystyle\sum_{i=1}^{p}\mathcal{F}^{(i)}(x_{1},\ldots,x_{p})-x_{j}\,\mathcal{F}^{(j)}(x_{1},\ldots,x_{p})+x_{j}\quad\text{for
every }1\leq j\leq p.$ (3.7)

Note that we can re-write (3.7) as follows

$(x_{j}+1)\,\mathcal{F}^{(j)}(x_{1},\ldots,x_{p})=x_{j}\,\mathcal{F}(x_{1},\ldots,x_{p})+x_{j}\quad\text{for
every }1\leq j\leq p.$ (3.8)

Note that $x_{1},\ldots,x_{p}\neq-1$ since $|x_{1}|+\ldots+|x_{p}|<1$. So, we
can rewrite (3.8) as follows

$\mathcal{F}^{(j)}(x_{1},\ldots,x_{p})=\frac{x_{j}}{x_{j}+1}\,\mathcal{F}(x_{1},\ldots,x_{p})+\frac{x_{j}}{x_{j}+1}\quad\text{for
every }1\leq j\leq p.$ (3.9)

Indeed, by adding the equations involved in (3.9) we obtain

$\mathcal{F}(x_{1},\ldots,x_{p})=\displaystyle\frac{\frac{x_{1}}{x_{1}+1}+\ldots+\frac{x_{p}}{x_{p}+1}}{1-\frac{x_{1}}{x_{1}+1}-\ldots-\frac{x_{p}}{x_{p}+1}}=\sum_{n\geq
1}\left(\frac{x_{1}}{x_{1}+1}+\ldots+\frac{x_{p}}{x_{p}+1}\right)^{n}$ (3.10)

∎

Note that $\mathcal{F}(x_{1},\ldots,x_{p})$ converges (absolutely) if and only
if
$\displaystyle\left|\frac{x_{1}}{x_{1}+1}+\ldots+\frac{x_{p}}{x_{p}+1}\right|<1$.
Indeed, we have that $\mathcal{F}(x_{1},\ldots,x_{p})$ converges absolutely on

$\Omega:=\left\\{(x_{1},\ldots,x_{p})\in\mathbb{R}^{p}\,:\,\displaystyle|x_{1}|+\ldots+|x_{p}|<1\,,\,\left|\frac{x_{1}}{x_{1}+1}+\ldots+\frac{x_{p}}{x_{p}+1}\right|<1\right\\}.$

Note that there is a $p$-dimension ball centered at the origin included in
$\Omega$. Now, using the closed formula of $\mathcal{F}$, we can obtain a
closed formula for $X_{k_{1},\ldots,k_{p}}$, see the following result.

######  Theorem 3.3.

For every $k_{1},\ldots,k_{p}\in\mathbb{N}^{+}$ we have

$X_{k_{1},\ldots,k_{p}}=(-1)^{k_{1}+\ldots+k_{p}}\displaystyle\sum_{r_{1}=1}^{k_{1}}\ldots\sum_{r_{p}=1}^{k_{p}}{r_{1}+\ldots+r_{p}\choose
r_{1},\ldots,r_{p}}\prod_{1\leq i\leq p}(-1)^{r_{i}}{k_{i}-1\choose r_{i}-1}.$
(3.11)

###### Proof.

$X_{k_{1},\ldots,k_{p}}$ is the coefficient of
$x_{1}^{k_{1}}x_{2}^{k_{2}}\ldots x_{p}^{k_{p}}$ in
$\mathcal{F}(x_{1},\ldots,x_{p})$. We also have

$\frac{z}{z+1}=\displaystyle\sum_{n\geq 1}(-1)^{n-1}z^{n}\qquad\text{ for
every }|z|<1.$

Moreover, using the Taylor polynomial of $\frac{z}{z+1}$ with Peano’s form of
remainder, we have

$\frac{z}{z+1}=z-z^{2}+z^{3}-\ldots-(-z)^{k}\,+\,\mathcal{O}(z^{k+1})\quad\text{for
every }k\geq 1.$

Note that $D(k,r)$ is also the coefficient of $z^{k}$ in
$\left(z-z^{2}+z^{3}-\ldots-(-z)^{k}\right)^{r}$. Thus, from (3.10) we have

$\mathcal{F}(x_{1},\ldots,x_{p})=\sum_{n\geq
1}\big{(}x_{1}-\ldots-(-x_{1})^{k_{1}}+\mathcal{O}(x_{1}^{k_{1}+1})\,+\,\ldots\,+\,x_{p}-\ldots-(-x_{p})^{k_{p}}+\mathcal{O}(x_{p}^{k_{p}+1})\big{)}^{n}$

Thus, we have that $X_{x_{1},\ldots,k_{p}}$ is the coefficient of
$x_{1}^{k_{1}}x_{2}^{k_{2}}\ldots x_{p}^{k_{p}}$ in

$\displaystyle\sum_{n=p}^{k_{1}+\ldots+k_{p}}\big{(}x_{1}-\ldots-(-x_{1})^{k_{1}}\,+\,x_{2}-\ldots-(-x_{2})^{k_{2}}\,+\,\ldots\,+\,x_{p}-\ldots-(-x_{p})^{k_{p}}\big{)}^{n}$
$\displaystyle=$
$\displaystyle\sum_{n=p}^{k_{1}+\ldots+k_{p}}\sum_{r_{1}+\ldots+r_{p}=n}{n\choose
r_{1},\ldots,r_{p}}\big{(}x_{1}-\ldots-(-x_{1})^{k_{1}}\big{)}^{r_{1}}\big{(}x_{2}-\ldots-(-x_{2})^{k_{2}}\big{)}^{r_{2}}\ldots\big{(}x_{p}-\ldots-(-x_{p})^{k_{p}}\big{)}^{r_{p}}$

Then, by adding the coefficients of $x_{1}^{k_{1}}x_{2}^{k_{2}}\ldots
x_{p}^{k_{p}}$ for each $n$ we obtain

$X_{k_{1},\ldots,k_{p}}=\displaystyle\sum_{n=1}^{k_{1}+\ldots+k_{p}}\sum_{r_{1}+\ldots+r_{p}=n}{n\choose
r_{1},\ldots,r_{p}}D(k_{1},r_{1})\,D(k_{2},r_{2})\,\ldots\,D(k_{p},r_{p})$

Now, we can use combinatorial arguments to obtain a recurrence relation
involving $\\{D(k,r)\\}_{k\geq r}$ and initial conditions that allow to solve
$\\{D_{k,r}\\}_{k\geq r}$. Note that we have trivial relations on the double
indices sequence that could work as initial conditions

$D(k,0)=0,\,\forall k\in\mathbb{N},\quad D(k,r)=0,\text{ if }k<r,\quad
D(k,1)=(-1)^{k-1},\,\forall k>0,\quad D(k,k)=1,\,\forall k>0.$ (3.12)

Using the fact that

$\big{(}z-z^{2}+z^{3}-z^{4}+\ldots-(-z)^{k}\big{)}^{r+1}=\big{(}z-z^{2}+z^{3}-z^{4}+\ldots-(-z)^{k}\big{)}^{r}\,\big{(}z-z^{2}+z^{3}-z^{4}+\ldots-(-z)^{k}\big{)},$

we can also obtain the following recurrence relation that could be used to
obtain $D(k,r)$ for whatever pair $(k,r)$ whenever $k\geq r$

$D(k,r+1)=D(k-1,r)-D(k-2,r)+D(k-3,r)-...(-1)^{r-1}D(k-r,r).$ (3.13)

Hence, we have that (3.12) and (3.13) give an iterative way to solve
$\\{D_{k,r}\\}_{k\geq r}$. Moreover, subtracting (3.13) from the identity
$D(k,r)=D(k,r)$, we obtain

$D(k+1,r+1)=D(k,r)-D(k,r+1)$ (3.14)

Let $E(a,b)$ be the sequence that verifies

$D(k,r):=(-1)^{k+r}E(k-1,k-r)$

Then, from (3.12) we have the following initial conditions for $E(a,b)$

$E(a-1,a)=0,\quad E(a,-b)=0,\quad E(a,a)=1,\quad E(a,0)=1,\qquad\forall
a\in\mathbb{N},\forall b>0.$ (3.15)

Besides, we obtain the following recurrence relation for $E(a,b)$ from (3.14)

$E(a+1,b)=E(a,b)+E(a,b-1)\quad\text{for every }a,b\in\mathbb{N}.$ (3.16)

Then, uniqueness of $E(a,b)$ satisfying (3.15) and (3.16) gives

$E(a,b)={a\choose b}\quad\text{for every }a,b\in\mathbb{N}.$

∎

Indeed, we have some identities involving
$\left\\{X_{k_{1},\ldots,k_{p}}\right\\}$ due to combinatorial arguments. For
instance, since $X_{k_{1},\ldots,k_{p}}=0$ if
$(k_{1},\ldots,k_{p})\notin\mathbb{T}$, we have, _e.g._ ,

$X_{k+2,k}=\displaystyle\sum_{n=1}^{2k+2}(-1)^{n}\sum_{r=0}^{n}{n\choose
r}\,{k+1\choose k+2-r}\,{k-1\choose k-n+r}=0\qquad\text{for every
}k\in\mathbb{N}.$

and since $X_{k,k}=2$ for $k>0$ and $X_{k,k+1}=1$ for $k\geq 0$ we also have

$\displaystyle\sum_{n=1}^{2k+1}(-1)^{n+1}\sum_{r=0}^{n}{n\choose r}\,{k\choose
k+1-r}\,{k-1\choose k-n+r}=1\quad\text{for every }k\in\mathbb{N}$

and

$\displaystyle\sum_{n=1}^{2k}(-1)^{n}\sum_{r=0}^{n}{n\choose r}\,{k-1\choose
k-r}\,{k-1\choose k-n+r}\,=\,2\quad\text{for every }k\in\mathbb{N}^{+}.$

The following result shows a closed formula of the number of acyclic
orientation of a complete multipartite graphs with labelled vertices, see
Theorem 3.4.

######  Theorem 3.4.

The number of acyclic orientation of a complete multipartite graph
$K_{n_{1},n_{2},\ldots,n_{p}}$ with labelled vertices and $p$ parts with sizes
of the parts $n_{1},n_{2},\ldots,n_{p}$, respectively, is

$B_{n_{1},n_{2},\ldots,n_{p}}=\displaystyle\sum_{k_{1}\leq
n_{1}}\sum_{k_{2}\leq n_{2}}\ldots\sum_{k_{p}\leq n_{p}}k_{1}!k_{2}!\ldots
k_{p}!{n_{1}\brace k_{1}}{n_{2}\brace k_{2}}\ldots{n_{p}\brace
k_{p}}\,X_{k_{1},\ldots,k_{p}}$ (3.17)

where ${r\brace s}$ denotes the Stirling number of the second kind.

###### Proof.

Notice that we can use the same argument as in Proposition 3.1. We may count
the number of acyclic orientations of $K_{n_{1},n_{2},\ldots,n_{p}}$ by
grouping them according to $k_{i-1}$, the number of groups of $i$’s codes
(code $i$ associated to part with size $n_{i+1}$) separated by at least
another group of code in $[p]$. Then, consider the distinct ways to obtain
$k_{i}$ groups out of $n_{i}$ codes $i-1$, _i.e._ , ${n_{i}\brace k_{i}}$, and
its corresponding permutation of the $k_{i}$ groups, _i.e._ , $k_{i}!$. ∎

The length of the longest path in an acyclic orientation of a labelled
complete multipartite graph was discussed in [7]. In this direction, we have
the following result below. In an acyclic orientation of a complete
multipartite graph, the longest directed paths always start from the part that
includes the sources, and end at the part that includes the sinks. Note that a
longest path cannot start from another part of the multipartite graph since a
source makes it one edge longer. Analogously, a sink could make a path one
edge longer if it doesn’t end in the part that includes the sinks. Moreover,
the codification (2.2), given in Theorem 2.5, gives a partition on the
vertices of $\mathcal{K}$ induced by the equivalence relation
$R_{\mathcal{K}}$ defined by:

_Two vertices are related by $R_{\mathcal{K}}$ if they are sources in some
subsequent acyclic orientation obtained during the sources removing
decomposition, i.e., if the two vertices are represented in the code within a
sub-string of consecutive and identical codes._

Notice that since the code assigned to $\mathcal{K}$ is unique when you fix
the code assigned of each part, _i.e._ , unique unless you consider
permutation of their parts. Then, we may verify that $R_{\mathcal{K}}$ is an
equivalence relation on the set of vertices of the complete multipartite
graph. Indeed, the code of $\mathcal{K}$ induces a total order
$\prec_{\mathcal{K}}$ in the partition
$V(K_{n_{1},n_{2},\ldots,n_{p}})/R_{\mathcal{K}}$ given by the order of
appearance on the code of $\mathcal{K}$. Note that
$|V(K_{n_{1},n_{2},\ldots,n_{p}})/R_{\mathcal{K}}|=k_{1}+k_{2}+\ldots+k_{p}$
whenever one of the codifications given by (2.2) of $\mathcal{K}$ is counted
in $X_{k_{1},k_{2},\ldots,k_{p}}$.

######  Proposition 3.5.

The length of the longest path in an acyclic orientation $\mathcal{K}$ of a
complete multipartite graph $K_{n_{1},n_{2},\ldots,n_{p}}$ is the size of the
partition induced by $R_{\mathcal{K}}$ minus one, i.e.,
$|V(K_{n_{1},n_{2},\ldots,n_{p}})/R_{\mathcal{K}}|-1$.

Furthermore, the number of longest paths in $\mathcal{K}$ is given by the
multiplication of the sizes of each part of the partition induced by
$R_{\mathcal{K}}$.

12345$n_{0}$$n_{1}$$n_{2}$ | 12345$n_{0}$$n_{1}$$n_{2}$
---|---
$0.0.0.1.2$ |
12345$n_{0}$$n_{1}$$n_{2}$ | 12345$n_{0}$$n_{1}$$n_{2}$
$0.2.0.1.0$ |
Table 3: Two acyclic orientations of $K_{3,1,1}$ and their corresponding
longest paths.

###### Proof.

Consider now a path $\mathcal{P}$ in $\mathcal{K}$. Notice that $\mathcal{P}$
contains at most 1 (one) vertex of each part of the partition; otherwise,
there is not a directed path joining them. Moreover, a path containing
vertices in each part of the given partition
$V_{K_{n_{1},n_{2},\ldots,n_{p}}}/R_{\mathcal{K}}$ contains the maximum number
of vertices and therefore, is one of the longest directed paths in
$\mathcal{K}$. Note that such a $\mathcal{P}$ is one of the longest paths in
$\mathcal{K}$. Therefore, a longest path includes $k_{1}+\ldots+k_{p}$
vertices, and consequently, its length is $k_{1}+\ldots+k_{p}-1$.

Indeed, the number of longest paths in $\mathcal{K}$ is given by the
multiplication of the size of each part of the partition induced by $R$ since
we may choose a random vertex from each element of
$V_{K_{n_{1},n_{2},\ldots,n_{p}}}/R$, see Table 3. ∎

Notice that we may use Proposition 3.5 to investigate the distribution of the
longest paths in the acyclic orientations of a complete multipartite graphs.
Proposition 3.5 and Gallai-Hasse-Roy-Vitaver theorem give the trivial result

$\chi(k_{n_{1},\ldots,k_{p}})=\displaystyle\min_{\mathcal{K}}|V(K_{n_{1},n_{2},\ldots,n_{p}})/R_{\mathcal{K}}|=p.$

Note that for any acyclic orientation $\mathcal{K}$ of a general graph $G$ we
can similarly define $R_{\mathcal{K}}$ as

_Two vertices are related by $R_{\mathcal{K}}$ if they are sources in some
subsequent acyclic orientation obtained during the sources removing
decomposition._

Moreover, we may define a unique code for each acyclic orientation
$\mathcal{K}$ of a graph $G$ if we establish certain priority in the parts of
graph $G$. Another recommendation is to select a partition in $G$ associated
to the chromatic number of $G$.

## Acknowledgements

The first author was supported by a grant from Agencia Estatal de
Investigación (PID2019-106433GB-I00 /AEI/10.13039/501100011033), Spain.

## References

  * [1] T. Arakawa and M. Kaneko, On poly-Bernoulli numbers, Comment. Math. Univ. St. Pauli 48 (2) (1999), 159–167.
  * [2] A. Ayyer, D. Hathcock, and P. Tetal, Toppleable permutations, excedances and acyclic orientations, Combinatorial Theory 2(1) (2022), #10.
  * [3] B. Bényi and P. Hajnal, Combinatorics of poly-Bernoulli numbers, Studia Sci. Math. Hung. 52 (4) (2015), 537–558.
  * [4] C. Brewbaker, A combinatorial interpretation of the poly-Bernoulli numbers and two Fermat analogues, Integers 8 (1) (2008) #A02.
  * [5] B.H. Hwang, W.S. Junk, K.J. Lee, J. Oh and S.H. Yu, Acyclic orientation polynomials and the sink theorem for chromatic symmetric functions, Journal of Combinatorial Theory, Series B 149 (2021), 52–75.
  * [6] R. Johnson, Network reliability and acyclic orientations, Networks 14 (1984), 489–505.
  * [7] J. Khera, E. Lundberg and S. Melczer, Asymptotic enumeration of lonesum matrices, Advances in Applied Mathematics 123 (2021), #102118.
  * [8] N. Linial, Hard enumeration problems in geometry and combinatorics, SIAM J. Algorithmic Discrete Methods 7 (1986), 331–335.
  * [9] J. Nešetřil, P. Ossona de Mendez, Sparsity: Graphs, Structures, and Algorithms (2012), Algorithms and Combinatorics, vol. 28, Heidelberg: Springer.
  * [10] G. Pruesse and F. Ruskey, The prism of the acyclic orientation graph is hamiltonian, Electronic Journal of Combinatorics 2 (1995), #R5.
  * [11] C.D. Savage, M.B. Squire and D.B. West, Gray code results for acyclic orientations, Congressus Numerantium 96 (1993), 185–204.
  * [12] M.B. Squire, Two New Gray Codes for Acyclic Orientations, technical report 94-14, North Carolina State University, 1994.
  * [13] M.B. Squire, Generating the Acyclic Orientations of a Graph, Journal of Algorithms 26 (1998), 275–290.
  * [14] R.P. Stanley, Acyclic orientations of graphs, Discrete Mathematics 5 (1973), 171–178.
  * [15] D. West, Acyclic orientations of complete bipartite graphs, Discrete Mathematics 138 (1995), 393–396.