# Motzkin numbers and flag codes

Clementa Alonso-González111Dpt. de Matemàtiques, Universitat d’Alacant, Sant
Vicent del Raspeig, Ap. Correus 99, E – 03080 Alacant. and Miguel Ángel
Navarro-Pérez222Centro Universitario EDEM Escuela de Empresarios, Muelle de la
Aduana, s/n – Valencia

()

###### Abstract

_Motzkin numbers_ have been widely studied since they count many different
combinatorial objects. In this paper we present a new appearance of this
remarkable sequence in the network coding setting through a particular case of
multishot codes called flag codes. A flag code is a set of sequences of nested
subspaces (_flags_) of a vector space over the finite field
${\mathbb{F}}_{q}$. If the list of dimensions is $(1,\ldots,n-1)$, we speak
about a full flag code. The _flag distance_ is defined as the sum of the
respective subspace distances and can be represented by means of the so-called
_distance vectors_. We show that the number of distance vectors corresponding
to the full flag variety on ${\mathbb{F}}_{q}^{n}$ is exactly the $n$-th
Motzkin number. Moreover, we can identify the integer sequence that counts the
number of possible distance vectors associated to a full flag code with
prescribed minimum distance.

Keywords: Motzkin numbers, Motzkin paths, flag codes, flag distance, distance
vectors.

##  1 Introduction

Network coding is the most efficient way to send data across a network
modelled as a directed acyclic multigraph with multiple senders and receivers.
The key is that the intermediate nodes can perform random linear combinations
of the incoming inputs. This improves considerably the information flow
although it can also lead to error propagation and erasures (see [1]). To
solve this problem, in [10] the authors consider subspaces of
$\mathbb{F}_{q}^{n}$ as codewords and _subspace codes_ as collections of
subspaces. In particular, if all the subspaces have the same dimension, we
have _constant dimension codes_. Consult [19] to have an overview of the most
representative works in this subject.

On the other side, subspace codes can be considered as _one-shot subspace
codes_ since sending a codeword (a subspace) requires just a channel use. This
gives rise to the idea, first suggested in [15], of using the channel several
times to get _multishot subspace codes_. Under this approach codewords are
sequences of subspaces. In particular, it is possible to consider _constant
type flags_ , that is, sequences of nested subspaces with fixed dimensions as
it was proposed in [12]. In this seminal paper, collections of flags are
called _flag codes_ and they are presented as a generalization of constant
dimension codes. The recent works [4, 5, 6, 11] deal with different questions
related to the parameters and construction of flag codes.

In this paper we focus on the distance parameter associated to full flag
codes, that is, those whose sequence of dimensions is $(1,\ldots,n-1)$. As
usual in the multishot context, the distance between flags is computed as the
sum of the subspace distances corresponding to each shot, which provokes that
many different combinations of them can give the same flag distance value.
This fact was carefully pointed out in [4], where the authors introduce the
notion of _distance vector_ (associated to a given distance value) in order to
complete the information concerning the distance of pairs of flags. In this
framework, it naturally arises the question of knowing in how many different
ways the distance between a couple of flags can be distributed. We provide the
answer to this question by showing that the cardinality of the set of distance
vectors corresponding to the full flag variety on ${\mathbb{F}}_{q}^{n}$ is
given by the $n$-th Motzkin number.

Motzkin numbers have been widely investigated as they appear in a great
variety of combinatorial objects (see [17, 18] for more details). Here we look
at them in terms of certain lattice paths from $(0,0)$ to $(n,0)$ that consist
of horizontal steps $(1,0)$, up steps $(1,1)$ and down steps $(1,-1)$ and
never goes below the $x$-axis (Motzkin paths). Thus, we exhibit a
correspondence between distance vectors and Motzkin paths that results to be
crucial for our purposes. This idea has been inspired by the combinatorial
approach to flag codes developed in [3] and some interesting talks with Paulo
Almeida and Alessandro Neri.

The remain of the paper is organized as follows: in Section 2 we remember some
basic definitions and results on Motzkin numbers, subspace codes and flag
codes. In Section 3 we recall the concept of _distance vector_ associated to a
couple of flags and we pose the problem of counting such objects. In Section 4
we establish a bijection between the set of distance vectors associated to the
full flag variety on ${\mathbb{F}}_{q}^{n}$ and the set of Motzkin paths with
$n$ steps which permits to compute the cardinality of the former set as well
as the one of some important subsets of it. Moreover, we show that such a
bijection takes the flag distance associated to a distance vector to the area
under the corresponding Motzkin path. Finally, in Section 5 we propose some
open questions that could be addressed taking into account our work.

##  2 Preliminaries

In this section we briefly recall some basic background on Motzkin numbers,
subspace codes and flag codes.

###  2.1 Motzkin numbers

Let us consider the set of lattice paths in ${\mathbb{Z}}^{2}$ whose permitted
steps are the up diagonal step $(1,1)$ denoted by $U$, the down diagonal step
$(1,-1)$, denoted by $D$, and the horizontal step $(1,0)$, denoted by $H$. Let
$U(x,y)$ represent the set of all unrestricted lattice paths running from
$(0,0)$ to $(x,y)$ and using the steps $U,D$ and $H$.

######  Definition 2.1.

A _Motzkin path_ of length $n$ is a lattice path in $U(n,0)$ that never runs
below the $x$-axis. We denote by $\mathcal{M}_{n}$ the set of Motzkin paths of
length $n$. A _Dyck path_ is a Motzkin path that does not contain horizontal
steps. The set of Dyck paths of length $2n$ will be denoted by
$\mathcal{D}_{n}$.

It is clear that, if horizontal steps are not allowed, the length of a Motzkin
path (a Dyck path, in this case) must be even. On the other hand, it is well
known that the cardinality of the set $\mathcal{M}_{n}$ is the $n$-th Motzkin
number $M_{n}$ (sequence $A001006$ in [17]) and the cardinality of
$\mathcal{D}_{n}$ is the $n$-th Catalan number $C_{n}$ (sequence $A000108$ in
[17]). More precisely, we can compute $M_{0}=C_{0}=1$ and

$M_{n}=M_{n-1}+\sum_{k=0}^{n-2}M_{k}M_{n-k-2},\quad
C_{n}=\sum_{k=0}^{n-1}C_{k}C_{n-k-1}\quad(n\geqslant 1).$

The Motzkin numbers sequence, whose first ten terms are

$1,1,2,4,9,21,51,127,323,835,$

was introduced by Theodor Motzkin [14], while counting possible sets of
nonintersecting chords joining some of $n$ points on a circle. Since this
seminal paper it has been the subject of numerous studies over the last forty
years. See [2] and [7] for a couple of the earliest surveys where the authors
exhibit different combinatorial objects counted by this sequence, including
Motzkin paths.

A commonly used and concise way of representing a Motzkin path
$p\in\mathcal{M}_{n}$ is by its corresponding Motzkin word (see [8], for
instance).

######  Definition 2.2.

A Motzkin word of length $n$ is a sequence of $n$ letters in the alphabet
$\\{U,D,H\\}$, namely $p=p_{1}p_{2}\dots p_{n}$, with the constraint that the
number of occurrences of the letter $U$ is equal to the number of occurrences
of the letter $D$ and, for every $i\in\\{1,\ldots,n\\}$, the number of
occurrences of $U$ in the subword $p_{1}p_{2}\dots p_{i}$ is not smaller than
the one of $D$.

In the following, we will not distinguish between a Motzkin path and the
corresponding Motzkin word.

Figure 1: The Motzkin path $p=UUHUDDHDH$ in $\mathcal{M}_{9}$.

######  Remark 2.3.

Observe that if we see the letters $U$ and $D$ as an open and closed
parenthesis respectively, a Motzkin path is a word in $\\{U,H,D\\}$ such that
the subword on the letters $U$ and $D$ forms a balanced parenthesization, that
is, the pairs of parantheses on them are correctly matched. This viewpoint
will be useful for us in Section 4.

######  Example 2.4.

To the Motzkin path $p=UUHUDDHDH$ in Figure 1 it corresponds the
parenthesization $((()))$.

######  Definition 2.5.

The area of a Motzkin path $p$, denoted by $A(p)$, is the area of the region
above the $x$-axis and below the path $p$.

######  Remark 2.6.

For the Motzkin path in Figure 1 we have $A(p)=12$. It is clear that for any
$p\in\mathcal{M}_{n}$, it holds $0\leqslant
A(p)\leqslant\lfloor\frac{n^{4}}{4}\rfloor$. In fact, if we denote by
$\mathcal{M}_{n}(k)$ the set of Motzkin paths with length $n$ and area $k$
with $0\leqslant k\leqslant\lfloor\frac{n^{4}}{4}\rfloor$, the cardinality of
that set, denoted $T(n,k)$, is given by the sequence $A129181$ in [17]. As far
as we know, at the moment there is not a recurrence formula to calculate this
sequence. We present here a table that covers it for values
$n\in\\{0,1,\dots,8\\}$.

$n$ $k$ |  0 |  1 |  2 |  $3$ |  4 |  $5$ |  6 |  $7$ |  $8$ |  9 |  $10$ |  $11$ |  12 |  $13$ |  $14$ |  $15$ |  16
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
0 |  $1$ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
1 |  $1$ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
2 |  $1$ |  $1$ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
3 |  $1$ |  $2$ |  $1$ |  |  |  |  |  |  |  |  |  |  |  |  |  |
4 |  $1$ |  $3$ |  $3$ |  $1$ |  $1$ |  |  |  |  |  |  |  |  |  |  |  |
5 |  $1$ |  $4$ |  $6$ |  $4$ |  $3$ |  $2$ |  $1$ |  |  |  |  |  |  |  |  |  |
6 |  $1$ |  $5$ |  $10$ |  $10$ |  $8$ |  $7$ |  $5$ |  $3$ |  $1$ |  $1$ |  |  |  |  |  |  |
7 |  $1$ |  $6$ |  $15$ |  $20$ |  $19$ |  $18$ |  $16$ |  $12$ |  $8$ |  $6$ |  $3$ |  $2$ |  $1$ |  |  |  |
8 |  $1$ |  $7$ |  $21$ |  $35$ |  $40$ |  $41$ |  $41$ |  $36$ |  $29$ |  $23$ |  $18$ |  $12$ |  $9$ |  $5$ |  $3$ |  $1$ |  $1$
Table 1: First terms of the sequence $A129181$.

Of special interest is the set of Motzkin paths that never touch the $x$-axis
in intermediate steps or the set of Motzkin paths that do no have horizontal
steps on the $x$-axis .

######  Definition 2.7.

A return of a Motzkin path $p\in\mathcal{M}_{n}$ is a point of $p$ different
from $(0,0)$ and $(n,0)$ and belonging to the $x$-axis. We say that $p$ is an
irreducible or elevated Motzkin path if it does not have returns. We denote by
$\mathcal{E}_{n}$ the set of elevated Motzkin paths in $\mathcal{M}_{n}$. Its
cardinality is the integer $E_{n}$ given by

$E_{0}=E_{1}=0,\quad E_{n}=M_{n-2},\quad n\geqslant 2.$ (1)

######  Example 2.8.

The lattice path $p=UUHUDDHD$ is an elevated Motzkin path in
$\mathcal{E}_{8}$.

In terms of its Motzkin word, a Motzkin path is elevated if the number of
occurrences of $U$ is greater than the number of occurrences of $D$ in every
subword $p_{1}\dots p_{i}$, for $1\leqslant i\leqslant n-1$. On the other
hand, a Motzkin path with returns contains at least a subword of the form
either $DU$ or $DH$.

######  Definition 2.9.

A Motzkin path of length $n$ without horizontal steps on the $x$-axis will be
called a Riordan path of length $n$. The set of Riordan paths of length $n$ is
denoted by $\mathcal{R}_{n}$. The cardinality of $\mathcal{R}_{n}$ is given by
the Riordan numbers $R_{n}$. In [17] these numbers correspond to the sequence
$A005043$.

######  Remark 2.10.

In the literature related to Motzkin paths there are many papers that deal
with the problem of counting variations of them in terms of the appearance of
different elements such as returns, horizontal steps, peaks (subwords of the
form $UD$) and valleys (subwords of the form $DU$), for instance. In Section 4
we will consider some of them (elevated Motzkin paths and Riordan paths) as
translation of particular situations coming from the context of flag codes.

###  2.2 Subspace codes and flag codes

Consider a prime power $q$ and a positive integer $n\geqslant 2$. Let
${\mathbb{F}}_{q}$ be the finite field with $q$ elements. The set of subspaces
of the vector space ${\mathbb{F}}_{q}^{n}$ can be seen as a metric space by
using different metrics. Among them, here we will use the so-called _injection
distance._

######  Definition 2.11.

The _injection distance_ between two subspaces
$\mathcal{U},\mathcal{V}\subseteq{\mathbb{F}}_{q}^{n}$ is defined as

$d_{I}(\mathcal{U},\mathcal{V})=\max\\{\dim(\mathcal{U}),\dim(\mathcal{V})\\}-\dim(\mathcal{U}\cap\mathcal{V}).$
(2)

In particular, if $\mathcal{U},\mathcal{V}$ have the same dimension, say
$1\leqslant k<n$, then we have

$d_{I}(\mathcal{U},\mathcal{V})=k-\dim(\mathcal{U}\cap\mathcal{V})=\dim(\mathcal{U}+\mathcal{V})-k.$
(3)

Hence, if for any $1\leqslant k<n$ we denote by $\mathcal{G}_{q}(k,n)$ the
_Grassmannian_ , that is, the set of $k$-dimensional subspaces of
${\mathbb{F}}_{q}^{n}$, we can consider error-correcting codes in
$\mathcal{G}_{q}(k,n)$ as follows.

######  Definition 2.12.

A _constant dimension code_ $\mathcal{C}$ of length $n$ and dimension $k$ is a
nonempty subset of $\mathcal{G}_{q}(k,n)$. The _minimum distance_ of
$\mathcal{C}$ is defined as

$d_{I}(\mathcal{C})=\min\\{d_{I}(\mathcal{U},\mathcal{V})\ |\
\mathcal{U},\mathcal{V}\in\mathcal{C},\ \mathcal{U}\neq\mathcal{V}\\}$

whenever $|\mathcal{C}|\geqslant 2$. In case $|\mathcal{C}|=1$, we put
$d_{I}(\mathcal{C})=0$.

Note that the minimum distance of a code $\mathcal{C}$ is an integer such that

$0\leqslant
d_{I}(\mathcal{C})\leqslant\left\\{\begin{array}[]{lll}k&\text{if}&2k\leqslant
n,\\\ n-k&\text{if}&2k\geqslant n.\end{array}\right.$ (4)

######  Remark 2.13.

Another frequent metric used when working with subspace codes of
${\mathbb{F}}_{q}^{n}$ is the _subspace distance_. It is given by

$d_{S}(\mathcal{U},\mathcal{V})=\dim(\mathcal{U}+\mathcal{V})-\dim(\mathcal{U}\cap\mathcal{V}).$
(5)

Observe that, if $\mathcal{U},\mathcal{V}\in\mathcal{G}_{q}(k,n)$, then
$d_{S}(\mathcal{U},\mathcal{V})=2(k-\dim(\mathcal{U}\cap\mathcal{V}))=2d_{I}(\mathcal{U},\mathcal{V}).$
Hence, in the context of constant dimension codes, the injection distance and
the subspace distance are equivalent metrics. Consult [19] and the references
therein for more information on this class of codes.

Let us now consider flags on ${\mathbb{F}}_{q}^{n}$ with the same type, that
is, sequences of nested subspaces of ${\mathbb{F}}_{q}^{n}$ whose list of
dimensions is fixed. In this way we get flag codes (of constant type). This
idea was first proposed in [12]. Let us recall the basics on this family of
codes.

######  Definition 2.14.

A flag $\mathcal{F}=(\mathcal{F}_{1},\ldots,\mathcal{F}_{r})$ on
$\mathbb{F}_{q}^{n}$ is a sequence of ${\mathbb{F}}_{q}$-vector subspaces of
$\mathbb{F}_{q}^{n}$ satisfying

$\\{0\\}\subsetneq\mathcal{F}_{1}\subsetneq\cdots\subsetneq\mathcal{F}_{r}\subsetneq\mathbb{F}_{q}^{n}.$

The type of $\mathcal{F}$ is the vector
$(\dim(\mathcal{F}_{1}),\dots,\dim(\mathcal{F}_{r}))$. If it equals
$(1,2,\ldots,n-1),$ we say that $\mathcal{F}$ is a full flag. We say that
$\mathcal{F}_{i}$ is the $i$-th subspace of $\mathcal{F}$.

The set of all the flags on $\mathbb{F}_{q}^{n}$ of a fixed type vector
$(t_{1},\dots,t_{r})$ is said to be the _flag variety_
$\mathcal{F}_{q}((t_{1},\ldots,t_{r}),n)$ or the _full flag variety_
$\mathcal{F}_{q}(n)$, if the type vector is $(1,\dots,n-1)$. The distance
defined in (2) can be extended to the flag variety as follows: given two flags
$\mathcal{F}=(\mathcal{F}_{1},\dots,\mathcal{F}_{r})$ and
$\mathcal{F}^{\prime}=(\mathcal{F}^{\prime}_{1},\dots,\mathcal{F}^{\prime}_{r})$
in $\mathcal{F}_{q}((t_{1},\ldots,t_{r}),n)$, the _(injection) flag distance_
between them is the value

$d_{f}(\mathcal{F},\mathcal{F}^{\prime})=\sum_{i=1}^{r}d_{I}(\mathcal{F}_{i},\mathcal{F}^{\prime}_{i}).$
(6)

######  Remark 2.15.

The subspace distance $d_{S}$ defined in (5) can also be extended to the flag
variety. Given $\mathcal{F}$ and $\mathcal{F}^{\prime}$ as above, the sum of
subspace distances

$\sum_{i=1}^{r}d_{S}(\mathcal{F}_{i},\mathcal{F}^{\prime}_{i})=2d_{f}(\mathcal{F},\mathcal{F}^{\prime})$
(7)

is an equivalent distance to $d_{f}$. In this paper we will always work with
the injection flag distance and we will simply write flag distance.

######  Definition 2.16.

A _flag code_ of type $(t_{1},\dots,t_{r})$ on ${\mathbb{F}}_{q}^{n}$ is a
nonempty subset $\mathcal{C}\subseteq\mathcal{F}_{q}((t_{1},\dots,t_{r}),n)$.
Its minimum distance is given by

$d_{f}(\mathcal{C})=\min\\{d_{f}(\mathcal{F},\mathcal{F}^{\prime})\ |\
\mathcal{F},\mathcal{F}^{\prime}\in\mathcal{C},\
\mathcal{F}\neq\mathcal{F}^{\prime}\\}$

when $|\mathcal{C}|\geqslant 2$. If $|\mathcal{C}|=1$, we put
$d_{f}(\mathcal{C})=0$.

For each dimension $t_{i}$ in the type vector of a flag code $\mathcal{C}$, we
can consider the constant dimension code in the Grassmannian
$\mathcal{G}_{q}(t_{i},n)$ consisting of the set of the $i$-th subspaces of
flags in $\mathcal{C}$. This set is called the _$i$ -projected code_ of
$\mathcal{C}$ and we denote it by $\mathcal{C}_{i}$. It is clear that
$|\mathcal{C}_{i}|\leqslant|\mathcal{C}|$ for every $i=1,\dots,r$. Moreover,
if given an index $1\leqslant i\leqslant r$ we have that
$|\mathcal{C}_{i}|=|\mathcal{C}|$, we can deduce that for any couple of flags
$\mathcal{F},\mathcal{F}^{\prime}\in\mathcal{C}$ we have that
$\mathcal{F}_{i}\neq\mathcal{F}_{i}^{\prime}$. This fact leads to the
following definition.

######  Definition 2.17.

We say that two flags $\mathcal{F}$ and $\mathcal{F}^{\prime}$ of type
$(t_{1},\dots,t_{r})$ on ${\mathbb{F}}_{q}^{n}$ _collapse_ at their $i$-th
subspace if $\mathcal{F}_{i}=\mathcal{F}^{\prime}_{i}$. On the other hand, two
different flags $\mathcal{F}$ and $\mathcal{F}^{\prime}$ are said to be
_disjoint_ if they do not collapse at any subspace, i.e., if
$\mathcal{F}_{i}\neq\mathcal{F}^{\prime}_{i},$ for every $1\leqslant
i\leqslant r$. Similarly, a flag code
$\mathcal{C}\subseteq\mathcal{F}_{q}((t_{1},\dots,t_{r}),n)$ is disjoint if it
consists of disjoint flags. In terms of the projected codes, a flag code
$\mathcal{C}$ is disjoint if, and only if,
$|\mathcal{C}_{1}|=\dots=|\mathcal{C}_{r}|=|\mathcal{C}|$.

##  3 Distance vectors: how to spread the flag distance

In sight of the flag distance definition given in (6), one realizes that a
fixed distance value could possibly be obtained by adding different subspace
distances combinations. This fact is reflected in the following example.

######  Example 3.1.

Let $\\{e_{1},e_{2},e_{3},e_{4},e_{5},e_{6}\\}$ be the standard basis of the
${\mathbb{F}}_{q}$-vector space ${\mathbb{F}}_{q}^{6}$. Consider the flag code
$\mathcal{C}$ of type $(1,3,5)$ on ${\mathbb{F}}_{q}^{6}$ given by the set of
flags:

$\begin{array}[]{ccc}\mathcal{F}^{1}&=&(\langle e_{1}\rangle,\langle
e_{1},e_{2},e_{3}\rangle,\langle e_{1},e_{2},e_{3},e_{4},e_{5}\rangle),\\\
\mathcal{F}^{2}&=&(\langle e_{5}\rangle,\langle
e_{4},e_{5},e_{6}\rangle,\langle e_{1},e_{2},e_{4},e_{5},e_{6}\rangle),\\\
\mathcal{F}^{3}&=&(\langle e_{6}\rangle,\langle
e_{4},e_{5},e_{6}\rangle,\langle e_{2},e_{3},e_{4},e_{5},e_{6}\rangle),\\\
\mathcal{F}^{4}&=&(\langle e_{2}\rangle,\langle
e_{2},e_{5},e_{6}\rangle,\langle
e_{2},e_{3},e_{4},e_{5},e_{6}\rangle).\par\end{array}$

Observe that it holds:

$d_{f}(\mathcal{C})=d_{f}(\mathcal{F}^{2},\mathcal{F}^{3})=1+0+1=2=1+1+0=d_{f}(\mathcal{F}^{3},\mathcal{F}^{4}).$

We can follow that, even if the pairs $\mathcal{F}^{2},\mathcal{F}^{3}$ and
$\mathcal{F}^{3},\mathcal{F}^{4}$ are both at distance $2$, the first one
presents a collapse in the second subspace, that is,
$\mathcal{F}_{2}^{2}=\mathcal{F}_{2}^{3}$, whereas the second pair collapses
at the third one. As a consequence, to totally capture the relative position
of two flags, it is necessary to provide more precise information beyond the
distance in absolute terms. In [4] the authors deal with this question by
defining _distance vectors_. Let us recall this definition.

######  Definition 3.2.

Given two different flags $\mathcal{F},\mathcal{F}^{\prime}$ of type
$t=(t_{1},\dots,t_{r})$ on ${\mathbb{F}}_{q}^{n}$, their associated _distance
vector_ is

$\textbf{d}(\mathcal{F},\mathcal{F}^{\prime})=(d_{I}(\mathcal{F}_{1},\mathcal{F}_{1}^{\prime}),\dots,d_{I}(\mathcal{F}_{r},\mathcal{F}_{r}^{\prime}))\in{\mathbb{Z}}^{r}.$

Notice that the sum of the components of
$\textbf{d}(\mathcal{F},\mathcal{F}^{\prime})$ is the flag distance
$d_{f}(\mathcal{F},\mathcal{F}^{\prime})$ defined in (6). Given a positive
integer $n\geqslant 2$ and a type vector $t=(t_{1},\dots,t_{r})$, we denote by
$D^{(t,n)}$ the maximum possible value of the flag distance in
$\mathcal{F}_{q}(t,n)$ that, as a consequence of (4), is

$D^{(t,n)}=\left(\sum_{t_{i}\leqslant\left\lfloor\frac{n}{2}\right\rfloor}t_{i}+\sum_{t_{i}>\left\lfloor\frac{n}{2}\right\rfloor}(n-t_{i})\right).$
(8)

In particular, the set $\\{0,1,\dots,D^{(t,n)}\\}$ contains all the possible
values for the flag distance in $\mathcal{F}_{q}(t,n)$. When working with the
full type vector, we simply write

$D^{n}=\left\lfloor\frac{n^{2}}{4}\right\rfloor=\left\\{\begin{array}[]{cccl}\frac{n^{2}}{4}&\text{if}&n&\text{is
even},\\\ &&&\\\\[-10.00002pt] \frac{n^{2}-1}{4}&\text{if}&n&\text{is
odd}\end{array}\right.$ (9)

to denote the maximum possible distance between full flags on
${\mathbb{F}}_{q}^{n}$.

######  Definition 3.3.

Let $d$ be an integer such that $0\leqslant d\leqslant D^{(t,n)}$. We define
_the set of distance vectors associated to $d$ for the flag variety
$\mathcal{F}_{q}(t,n)$_ as

$\mathcal{D}(d,t,n)=\\{\textbf{d}(\mathcal{F},\mathcal{F}^{\prime})\ |\
\mathcal{F},\mathcal{F}^{\prime}\in\mathcal{F}_{q}(t,n),\
d_{f}(\mathcal{F},\mathcal{F}^{\prime})=d\\}\subseteq{\mathbb{Z}}^{r}.$

On the other hand, the set of _distance vectors for the flag variety
$\mathcal{F}_{q}(t,n)$_ is

$\mathcal{D}(t,n)=\\{\textbf{d}(\mathcal{F},\mathcal{F}^{\prime})\ |\
\mathcal{F},\mathcal{F}^{\prime}\in\mathcal{F}_{q}(t,n)\\}\subseteq{\mathbb{Z}}^{r}.$

and it holds

$\mathcal{D}(t,n)=\bigcup_{d}\mathcal{D}(d,t,n),$

where $d$ takes all the integers between $0\leqslant d\leqslant D^{(t,n)}$.
When working with the full flag variety, we drop the type vector and simply
write $\mathcal{D}(d,n)$ and $\mathcal{D}(n),$ respectively.

At this point we propose several important questions: how many possible
distance vectors could correspond to a given couple of arbitrary flags
$\mathcal{F}$, $\mathcal{F}^{\prime}$ on ${\mathbb{F}}_{q}^{n}$, that is, what
is the cardinality of $\mathcal{D}(n)$? In particular, what happens if these
flags do not collapse? What if they never share two consecutive subspaces?
What if $\mathcal{F}$, $\mathcal{F}^{\prime}$ belong to a flag code with
prescribed minimum distance? We address these questions in the following
section.

##  4 The bijection

In the remain of the paper we will always work with full flag codes. More
precisely, we will show that the number of distance vectors associated to the
full flag variety $\mathcal{F}_{q}(n)$ is given by the Motzkin number $M_{n}$.

Let us first recall those properties that characterize distance vectors. The
following result is based on [3, Th. 3.8] and [4, Th. 3.9]. For completeness
here we include a shorter proof adapted to the full type case.

######  Theorem 4.1.

Consider integers $\delta_{1},\dots,\delta_{n-1}\geqslant 0$ and put
$\delta_{0}=\delta_{n}=0$. Then $(\delta_{1},\dots,\delta_{n-1})$ is a
distance vector in $\mathcal{D}(n)$ if, and only if,

$\delta_{i}\in\\{\delta_{i-1}-1,\delta_{i-1},\delta_{i-1}+1\\},$ (10)

for all $1\leqslant i\leqslant n$.

###### Proof.

Suppose that $(\delta_{1},\dots,\delta_{n-1})$ is a distance vector. Then,
there exists a pair of full flags
$\mathcal{F},\mathcal{F}^{\prime}\in\mathcal{F}_{q}(n)$ satisfying
$\delta_{j}=d_{I}(\mathcal{F}_{j},\mathcal{F}^{\prime}_{j})$, for every
$1\leqslant j\leqslant n-1$. Let us see that
$\delta_{i}\in\\{\delta_{i-1}-1,\delta_{i-1},\delta_{i-1}+1\\}.$ Note that
$\delta_{1},\delta_{n-1}\in\\{0,1\\}$ given that $\delta_{1},\delta_{n-1}$
are, respectively, distances between lines and hyperplanes of
${\mathbb{F}}_{q}^{n}$. Moreover, since $\delta_{0}=\delta_{n}=0$, the stated
condition holds for both $i=1,n$. Consider now any index $2\leqslant
i\leqslant n-1$. Note that

$\dim(\mathcal{F}_{i-1}+\mathcal{F}^{\prime}_{i-1})\leqslant\dim(\mathcal{F}_{i}+\mathcal{F}^{\prime}_{i})\leqslant\dim(\mathcal{F}_{i-1}+\mathcal{F}^{\prime}_{i-1})+2.$

Hence,
$\dim(\mathcal{F}_{i}+\mathcal{F}^{\prime}_{i})=\dim(\mathcal{F}_{i-1}+\mathcal{F}^{\prime}_{i-1})+k,$
with $k\in\\{0,1,2\\}$, and we have

$\begin{array}[]{rcl}\delta_{i}=d_{I}(\mathcal{F}_{i},\mathcal{F}^{\prime}_{i})&=&\dim(\mathcal{F}_{i}+\mathcal{F}_{i})-i\\\
&=&\dim(\mathcal{F}_{i-1}+\mathcal{F}^{\prime}_{i-1})+k-i\\\
&=&\dim(\mathcal{F}_{i-1}+\mathcal{F}^{\prime}_{i-1})-(i-1)+(k-1)\\\
&=&d_{I}(\mathcal{F}_{i-1},\mathcal{F}^{\prime}_{i-1})+(k-1)\\\
&=&\delta_{i-1}+(k-1),\end{array}$

where $k-1\in\\{-1,0,1\\}.$

For the converse, assume that $(\delta_{1},\dots,\delta_{n-1})$ is a vector
satisfying (10). This condition, along with the fact that
$\delta_{0}=\delta_{n}=0$, implies $\delta_{i}\leqslant\min\\{i,n-i\\}$, i.e.,
every $\delta_{i}$ is an admissible value for the injection distance between
$i$-dimensional subspaces of ${\mathbb{F}}_{q}^{n}$. Using induction, we build
flags $\mathcal{F},\mathcal{F}^{\prime}$ in $\mathcal{F}_{q}(n)$ with
$\mathbf{d}(\mathcal{F},\mathcal{F}^{\prime})=(\delta_{1},\dots,\delta_{n-1})$.
First of all, by means of (10), it is clear that $\delta_{1}\in\\{0,1\\}$. If
$\delta_{1}=0$, just take $\mathcal{F}_{1}=\mathcal{F}^{\prime}_{1}$.
Otherwise, consider any two different lines
$\mathcal{F}_{1},\mathcal{F}^{\prime}_{1}$. Assume now that for some
$1\leqslant i<n-1$, we have found nested subspaces
$\mathcal{F}_{1}\subsetneq\dots\subsetneq\mathcal{F}_{i}$ and
$\mathcal{F}^{\prime}_{1}\subsetneq\dots\subsetneq\mathcal{F}^{\prime}_{i}$
such that
$\delta_{j}=d_{I}(\mathcal{F}_{j},\mathcal{F}^{\prime}_{j})=\dim(\mathcal{F}_{j}+\mathcal{F}^{\prime}_{j})-j,$
for every $1\leqslant j\leqslant i$. Let us give convenient
$u,u^{\prime}\in{\mathbb{F}}_{q}^{n}$ and subspaces
$\mathcal{F}_{i+1}=\mathcal{F}_{i}+\left\langle u\right\rangle$,
$\mathcal{F}^{\prime}_{i+1}=\mathcal{F}^{\prime}_{i}+\left\langle
u^{\prime}\right\rangle$ such that
$\delta_{i+1}=d_{I}(\mathcal{F}_{i+1},\mathcal{F}^{\prime}_{i+1})$ by
distinguishing three situations.

  * •

$\boldsymbol{\delta_{i+1}=\delta_{i}}$. In this case, notice that
$\dim(\mathcal{F}_{i}+\mathcal{F}^{\prime}_{i})-i=\delta_{i}=\delta_{i+1}\leqslant
n-(i+1).$ Thus, $\dim(\mathcal{F}_{i}+\mathcal{F}^{\prime}_{i})\leqslant n-1$
and we can choose
$u\in{\mathbb{F}}_{q}^{n}\setminus(\mathcal{F}_{i}+\mathcal{F}^{\prime}_{i})$
to form $\mathcal{F}_{i+1}=\mathcal{F}_{i}+\left\langle u\right\rangle$. Now,
if $\delta_{i}\neq 0$, we can take
$u^{\prime}\in(\mathcal{F}_{i}+\mathcal{F}^{\prime}_{i})\setminus\mathcal{F}^{\prime}_{i}$
and $\mathcal{F}^{\prime}_{i+1}=\mathcal{F}^{\prime}_{i}+\left\langle
u^{\prime}\right\rangle$. In case $\delta_{i}=0$, then $\delta_{i+1}=0$ and we
just put
$\mathcal{F}^{\prime}_{i+1}=\mathcal{F}_{i+1}=\mathcal{F}_{i}+\left\langle
u\right\rangle$. Note that, in any case,
$\mathcal{F}_{i+1},\mathcal{F}^{\prime}_{i+1}$ are subspaces of dimension
$i+1$ with

$\dim(\mathcal{F}_{i+1}+\mathcal{F}^{\prime}_{i+1})=\dim(\mathcal{F}_{i}+\mathcal{F}^{\prime}_{i}+\left\langle
u\right\rangle)=\dim(\mathcal{F}_{i}+\mathcal{F}^{\prime}_{i})+1=\delta_{i}+i+1.$

As a consequence,
$\delta_{i+1}=\delta_{i}=\dim(\mathcal{F}_{i+1}+\mathcal{F}^{\prime}_{i+1})-(i+1)$
as desired.

  * •

$\boldsymbol{\delta_{i+1}=\delta_{i}+1}$. Hence,
$\dim(\mathcal{F}_{i}+\mathcal{F}^{\prime}_{i})-i=\delta_{i}=\delta_{i+1}-1\leqslant
n-(i+1)-1=n-i-2$ and $\dim(\mathcal{F}_{i}+\mathcal{F}^{\prime}_{i})\leqslant
n-2$. This allows us to choose two linearly independent vectors
$u,u^{\prime}\in{\mathbb{F}}_{q}^{n}$ such that

$\dim(\mathcal{F}_{i}+\mathcal{F}^{\prime}_{i}+\langle u\rangle+\langle
u^{\prime}\rangle)=\dim(\mathcal{F}_{i}+\mathcal{F}^{\prime}_{i})+2.$

The subspaces $\mathcal{F}_{i+1}=\mathcal{F}_{i}+\langle u\rangle$ and
$\mathcal{F}^{\prime}_{i+1}=\mathcal{F}^{\prime}_{i}+\langle
u^{\prime}\rangle$ satisfy the required condition.

  * •

$\boldsymbol{\delta_{i+1}=\delta_{i}-1}$. In this situation, notice that
$\delta_{i}\geqslant 1$ and then
$\mathcal{F}_{i}\neq\mathcal{F}^{\prime}_{i}$. Therefore, we can find nonzero
vectors $u\in\mathcal{F}^{\prime}_{i}\setminus\mathcal{F}_{i}$ and
$u^{\prime}\in\mathcal{F}_{i}\setminus\mathcal{F}^{\prime}_{i}$ to form two
$(i+1)$-dimensional subspaces $\mathcal{F}_{i+1}=\mathcal{F}_{i}+\langle
u\rangle$ and $\mathcal{F}^{\prime}_{i+1}=\mathcal{F}^{\prime}_{i}+\langle
u^{\prime}\rangle$ with
$d_{I}(\mathcal{F}_{i+1},\mathcal{F}^{\prime}_{i+1})=\delta_{i+1}$.

∎

The previous theorem turns out to be the key to establish our bijection
between the set of distance vectors corresponding to the full flag variety
$\mathcal{F}_{q}(n)$ and the set of Motzkin paths of length $n$.

######  Theorem 4.2.

Given a positive integer $n\geqslant 2$, there is a bijection between the set
of distance vectors $\mathcal{D}(n)$ and the set of Motzkin paths
$\mathcal{M}_{n}$.

###### Proof.

Recall that in this paper we do not distinguish between a Motzkin path and the
corresponding Motzkin word. Consider
$(\delta_{1},\ldots,\delta_{n-1})\in\mathcal{D}(n)$ and put
$\delta_{0}=\delta_{n}=0$. In light of Theorem 4.1, for any
$i\in\\{1,\dots,n\\}$, it holds

$\delta_{i}-\delta_{i-1}\in\\{-1,0,1\\}.$

Consider the following map:

$\begin{array}[]{cccc}\Psi:&\mathcal{D}(n)&\longrightarrow&\mathcal{M}_{n}\\\
&(\delta_{1},\dots,\delta_{n-1})&\longmapsto&p_{1}\dots p_{n},\end{array}$
(11)

where, for every $1\leqslant i\leqslant n$, we take

$p_{i}=\left\\{\begin{array}[]{cccc}U&\text{ if
}&\delta_{i}-\delta_{i-1}=&1,\\\ H&\text{ if }&\delta_{i}-\delta_{i-1}=&0,\\\
D&\text{ if }&\delta_{i}-\delta_{i-1}=&-1.\end{array}\right.$ (12)

Let us see that the word $\Psi((\delta_{1},\dots,\delta_{n-1}))$ is a Motzkin
word. To do so, assume that, for some $1\leqslant i\leqslant n$, in the
subword $p_{1}\dots p_{i}$, the letter $D$ appears more times than $U$. This
means that, up to the $i$-th step, the difference $\delta_{j}-\delta_{j-1}=-1$
occurs more times than $\delta_{j}-\delta_{j-1}=1$. As a result, we have that
$\delta_{i}=\sum_{j=1}^{i}\delta_{j}-\delta_{j-1}<0,$ which is a
contradiction. Similarly, since
$\sum_{j=1}^{n}\delta_{j}-\delta_{j-1}=\delta_{n}-\delta_{0}=0$, the number of
occurrences of both $U$ and $D$ coincides.

On the other hand, given $p\in\mathcal{M}_{n}$, we have that $p=p_{1}\dots
p_{n}$ is a sequence of $n$ letters $p_{i}\in\\{U,H,D\\}$, for $i=1,\dots,n$
such that, in particular, $p_{1}\in\\{U,H\\}$ and $p_{n}\in\\{H,D\\}$. Now,
for $i=1,\dots,n$, we consider the following associated values: $u_{i}$ (resp.
$h_{i}$, $d_{i}$) is the number of occurrences of an $U$ (resp. $H$, $D$) step
at or before $p_{i}$. Note that $d_{1}=0$ and $u_{n}=d_{n}$. Moreover, for
every $1\leqslant i\leqslant n$, it holds $u_{i}+h_{i}+d_{i}=i$ and
$u_{i}\geqslant d_{i}$. From these values, we define a map
$\Phi:\mathcal{M}_{n}\rightarrow\mathcal{D}(n)$ as follows:

$\Phi(p_{1}\dots p_{n})=(u_{1}-d_{1},u_{2}-d_{2},\dots,u_{n-1}-d_{n-1}).$ (13)

As a consequence of the definition of $u_{i},h_{i},d_{i}$, we have that

$(u_{i}-d_{i})-(u_{i-1}-d_{i-1})=\left\\{\begin{array}[]{rcl}1&\text{if}&p_{i}=U,\\\
0&\text{if}&p_{i}=H,\\\ -1&\text{if}&p_{i}=D,\end{array}\right.$

with $2\leqslant i\leqslant n$. As $u_{1}-d_{1}\in\\{0,1\\}$, by means of
Theorem 4.1, $\Phi(p_{1}\dots p_{n})$ is a distance vector.

Finally, we prove that $\Phi$ and $\Psi$ are mutually inverse. To do so,
consider $(\delta_{1},\dots,\delta_{n-1})\in\mathcal{D}(n)$. Let us see that,
if $\Phi\circ\Psi((\delta_{1},\dots,\delta_{n-1}))=\Phi(p_{1}p_{2}\dots
p_{n})=(u_{1}-d_{1},u_{2}-d_{2},\dots,u_{n-1}-d_{n-1})$ (defined as in (13)
and (12)), then $\delta_{i}=u_{i}-d_{i}$, for all $i\in\\{1,\dots,n-1\\}$. We
work by induction on $n$. Clearly, if $\delta_{1}=1$ (resp. $\delta_{1}=0$),
then $p_{1}=U$ (resp. $p_{1}=H$) and $u_{1}-d_{1}=1=\delta_{1}$ (resp.
$u_{1}-d_{1}=0=\delta_{1}$ ). Assume that the result is true, for $k<n-1$,
that is, $\delta_{k}=u_{k}-d_{k}$. We now that
$\delta_{k+1}-\delta_{k}\in\\{-1,0,1\\}$. Suppose, for instance, that
$\delta_{k+1}-\delta_{k}=1$. Then $p_{k+1}=U$ and, as $\delta_{k}=u_{k}-d_{k}$
by induction hypothesis, we have
$u_{k+1}-d_{k+1}=(u_{k}-d_{k})+1=\delta_{k}+1$. Thus,
$u_{k+1}-d_{k+1}=\delta_{k+1}$ as desired. The cases where
$\delta_{k+1}-\delta_{k}=0$ or $\delta_{k+1}-\delta_{k}=-1$ are analogous.

Take now $p_{1}p_{2}\dots p_{n}$ a Motzkin word of length $n$ such that
$\Psi\circ\Phi(p_{1}p_{2}\dots p_{n})=p_{1}^{\prime}p_{2}^{\prime}\dots
p_{n}^{\prime}$. Let us see that $p_{i}=p_{i}^{\prime}$, for any
$i\in\\{1,\dots,n\\}$. Let us work again by induction on $n$. It is clear
that, if $p_{1}=U$ ( resp. $p_{1}=H$) then $u_{1}-d_{1}=1$ (resp.
$u_{1}-d_{1}=0$) and $p_{1}^{\prime}=U=p_{1}$ (resp.
$p_{1}^{\prime}=H=p_{1}$). Assume that $p_{k}=p_{k}^{\prime}$ for $k<n$. If
$p_{k+1}^{\prime}=U$, then $u_{k+1}-d_{k+1}-(u_{k}-d_{k})=1$ which means that
$p_{k+1}=U=p_{k+1}^{\prime}$. The cases $p_{k+1}^{\prime}=H$ or
$p_{k+1}^{\prime}=D$ go analogously. Hence $\Psi$ is a bijection as we wanted
to show. ∎

######  Example 4.3.

To the distance vector $v=(1,2,2,3,2,1,1,0)$ it corresponds the Motzkin path
$\Psi(v)=UUHUDDHDH$ represented in Figure 1. For it, we have
$u_{6}=3,h_{6}=1,d_{6}=2$, for instance. In fact,
$\Phi\circ\Psi(v)=(1-0,2-0,2-0,3-0,3-1,3-2,3-2,3-3)=v$.

We can now provide the answer to the first question proposed in Section 3.

######  Corollary 4.4.

The number of distance vectors in $\mathcal{D}(n)$ is the $n$-th Motzkin
number $M_{n}$.

######  Remark 4.5.

Note that in our work [3], given a pair of full flags $\mathcal{F}$ and
$\mathcal{F}^{\prime}$ on ${\mathbb{F}}_{q}^{n}$, we defined their _distance
path_ $\Gamma(\mathcal{F},\mathcal{F}^{\prime})$ as the polygonal path in
$\mathbb{Z}^{2}$ from $(0,0)$ to $(n,0)$ whose intermediate vertices are the
points $(i,d_{I}(\mathcal{F}_{i},\mathcal{F}^{\prime}_{i}))$ for every
$0<i<n$. Therefore, by virtue of Theorem 4.1, our distance paths are Motzkin
paths and conversely.

###  4.1 Distance vectors corresponding to disjoint flags

Recall from Section 2 that a couple of flags
$\mathcal{F},\mathcal{F}^{\prime}$ on ${\mathbb{F}}_{q}^{n}$ are disjoint if
they do not share any subspace, that is, if they do not present collapses at
any dimension. On the other hand, if $\mathcal{F},\mathcal{F}^{\prime}$
collapse at dimension $i$, that is $\mathcal{F}_{i}=\mathcal{F}_{i}^{\prime}$,
then the $i$-th component in $\textbf{d}(\mathcal{F},\mathcal{F}^{\prime})$ is
equal to zero.

By means of (13), for a distance vector
$v=(\delta_{1},\dots,\delta_{n-1})\in\mathcal{D}(n)$ such that $\delta_{i}=0$,
we have that $u_{i}=d_{i}$. Graphically, the Motzkin path $\Psi(d)$ intersects
the $x$-axis at the point $(i,0)$. In other words, two full flags collapsing
at dimension $i$ induce a Motzkin path in which the point $(i,0)$ is a return.
This fact enables us to state the following result. Its proof can be easily
obtained by using the maps $\Psi$ and $\Phi$ defined in the proof of Theorem
4.2, which are still bijections when restricted to $\mathcal{E}_{n}$ and the
set of distance vectors in $\mathcal{D}(n)$ without null components.

######  Proposition 4.6.

Given a positive integer $n\geqslant 2$, there is a bijection between the set
of distance vectors in $\mathcal{D}(n)$ corresponding to pairs of disjoint
flags and the set of elevated Motzkin paths $\mathcal{E}_{n}$.

######  Corollary 4.7.

The number of distance vectors in $\mathcal{D}(n)$ corresponding to pairs
disjoint flags is the $n$-th number $E_{n}$ defined in (1).

###  4.2 Flag distance equals area

Let us show that the map $\Psi$ takes flag distance to area. In other words,
if $v=(\delta_{1},\dots,\delta_{n-1})\in\mathcal{D}(d,n)$, that is,
$d=\delta_{1}+\cdots+\delta_{n-1}$, then $A(\Psi(v))=d$. To do this, we work
first with elevated Motzkin paths, which means that our corresponding distance
vectors have no null component, by Proposition 4.6. Let us describe a
decomposition of any such a distance vector that may result very convenient
for our purposes.

######  Proposition 4.8.

Consider $v=(\delta_{1},\dots,\delta_{n-1})\in\mathcal{D}(n)$ with
$\delta_{i}\neq 0$ for every $i\in\\{1,\dots,n-1\\}$. Then, there is
$r\geqslant 1$ a positive integer and vectors
$v^{k}=(v_{1}^{k},\dots,v_{n-1}^{k})\in{\mathbb{F}}_{2}^{n-1}$ for
$k\in\\{1,\dots,r\\}$ such that

$\delta_{i}=\sum_{k=1}^{r}v_{i}^{k}.$ (14)

###### Proof.

Take $v=(\delta_{1},\dots,\delta_{n-1})\in\mathcal{D}(n)$ with $\delta_{i}\neq
0$ for $i\in\\{1,\dots,n-1\\}$. Note that, in this case,
$\delta_{1}=\delta_{n-1}=1$. Take $r=\max\\{\delta_{1},\dots,\delta_{n-1}\\}$
and, for any $k\in\\{1,\dots,r\\}$ define a vector
$v_{k}=(v_{1}^{k},\dots,v_{n-1}^{k})$ such that $v_{i}^{k}=0$ if
$k>\delta_{i}$ and $v_{i}^{k}=1$ otherwise. With this choice the desired
equality (14) holds.

∎

######  Remark 4.9.

Note that, if we denote $\rho_{k}=\sum_{i=1}^{n-1}v_{i}^{k}$, from the
previous decomposition, we have that

$d=\sum_{i=1}^{n-1}\delta_{i}=\sum_{i=1}^{n-1}\sum_{k=1}^{r}v_{i}^{k}=\sum_{k=1}^{r}\sum_{i=1}^{n-1}v_{i}^{k}=\sum_{k=1}^{r}\rho_{k}.$
(15)

######  Example 4.10.

Take the distance vector $v=(1,2,3,2,1,2,2,1)\in\mathcal{D}(9)$. Thus, $r=3$,
$v_{1}=(1,1,1,1,1,1,1,1),v_{2}=(0,1,1,1,0,1,1,0),v_{3}=(0,0,1,0,0,0,0,0)$. In
fact, we can put

$\begin{array}[]{cccccccccl}0&0&1&0&0&0&0&0&\rightarrow&\rho_{3}=1\\\
0&1&1&1&0&1&1&0&\rightarrow&\rho_{2}=3+2\\\
1&1&1&1&1&1&1&1&\rightarrow&\rho_{1}=9\\\
\downarrow&\downarrow&\downarrow&\downarrow&\downarrow&\downarrow&\downarrow&\downarrow&&\\\
1&2&3&2&1&2&2&1&&\textbf{14}\\\
\rotatebox{90.0}{$\,=$}&\rotatebox{90.0}{$\,=$}&\rotatebox{90.0}{$\,=$}&\rotatebox{90.0}{$\,=$}&\rotatebox{90.0}{$\,=$}&\rotatebox{90.0}{$\,=$}&\rotatebox{90.0}{$\,=$}&\rotatebox{90.0}{$\,=$}&\\\
\delta_{1}&\delta_{2}&\delta_{3}&\delta_{4}&\delta_{5}&\delta_{6}&\delta_{7}&\delta_{8}&\end{array}$

and observe how the flag distance, $d=14$ in this case, can be decomposed
“vertically” and “horizontally”.

Following the ideas in [9], let us see that the area under a Motzkin path
$p\in\mathcal{M}_{p}$ can be decomposed into horizontal strips determined by
the up and down steps.

######  Proposition 4.11.

Let $p\in\mathcal{E}_{n}$ be an elevated Motzkin path. Then

$A(p)=\sum_{p_{j}=D}j-\sum_{p_{i}=U}i.$ (16)

###### Proof.

Given $p=p_{1}p_{2}\dots p_{n}\in\mathcal{M}_{n}$, as it was pointed out in
Remark 2.3, the letters $U$ and $D$ in $p$ form a balanced parenthesization,
so they can be naturally paired up. Moreover, every couple of matched steps
$p_{i}=U$ and $p_{j}=D$ determines a horizontal strip of area $j-i$ below the
Motzkin path $p$. The sum of areas of all the corresponding horizontal strips
gives us expression (16) for $A(p)$.

∎

######  Example 4.12.

Let us take $p\in\mathcal{M}_{9}$ with $p=UUUDDUHDD$. In this case, we have
the paired steps $(p_{1},p_{9})$, $(p_{2},p_{5})$, $(p_{6},p_{8})$ and
$(p_{3},p_{4})$.

Figure 2: The Motzkin path $p=UUUDDUHDD$ in $\mathcal{M}_{9}$.

Then we have that

$A(p)=(9-1)+(5-2)+(8-6)+(4-3)=8+3+2+1=14.$

Observe that our path $p$ satisfies $p=\Psi(v)$ where $v$ is the vector
considered in Example 4.10. Moreover, the areas corresponding to horizontal
strips at height $1$, $2$ or $3$, as showed in the picture above, correspond,
respectively, to the sum of the non-zero components of $v_{1}$, $v_{2}$ or
$v_{3}$.

######  Remark 4.13.

Note that the null distance vector in $\mathcal{D}(n)$ goes by $\Psi$ to the
“flat” Motzkin path. Besides, a null component in a distance vector $v$ does
not contribute to the computation of the corresponding value of the flag
distance and gives a return on $\Psi(v)$. On the other hand, a Motzkin path
$p$ with a finite number of returns can be decomposed into a finite number of
elevated Motzkin paths whose sum of areas gives $A(p)$. In Figure 3 we can see
a Motzking path $p\in\mathcal{M}_{9}$ with a return in $(4,0)$. This path
corresponds to the distance vector $v=(1,2,1,0,1,2,2,1)\in\mathcal{D}(10,9)$.
Then $p$ can be decomposed into two elevated Motzkin paths
$p^{\prime}=UUDD\in\mathcal{M}_{4}$ and
$p^{\prime\prime}=UUHDD\in\mathcal{M}_{5}$ such that
$A(p)=A(p^{\prime})+A(p^{\prime\prime})=10$.

Figure 3: The Motzkin path $p=UUDDUUHDD$ in $\mathcal{M}_{9}$.

Proposition 4.8 along with Proposition 4.11 and Remark 4.13, give
straightforwardly the following result.

######  Theorem 4.14.

Consider the map $\Psi:\mathcal{D}(n)\rightarrow\mathcal{M}_{n}$ defined in
Theorem 4.2. Given a distance vector
$v=(\delta_{1}\dots,\delta_{n-1})\in\mathcal{D}(n)$, we have that
$A(\Psi(v))=\delta_{1}+\cdots+\delta_{n-1}$. In other words, the map $\Psi$
takes flag distance to area and the restriction
$\Psi\mid_{\mathcal{D}(d,n)}:\mathcal{D}(d,n)\rightarrow\mathcal{M}_{n}(d)$ is
a bijection for any integer $d\in[0,\lfloor\frac{n^{2}}{4}\rfloor].$

######  Corollary 4.15.

The number of distance vectors in $\mathcal{D}(n)$ corresponding to a fixed
flag distance value $d$ equals the number of Motzkin paths
$p\in\mathcal{M}_{n}$ such that $A(p)=d$. This number is the term $T(n,d)$ of
the sequence $A129181$ in [17].

Observe that, as a consequence of Theorem 4.14, we could directly deduce the
bound given in (9) and, by Theorem 4.1, conclude that it is sharp. It is
enough to see that $\lfloor\frac{n^{2}}{4}\rfloor$ is the largest possible
area under a Motzkin path with $n$ steps. This area is attained by the path
$p=p_{1}p_{2}\dots p_{n}$ with $p_{1}=\dots=p_{k}=U$ and
$p_{k+1}=\dots=p_{n}=D$, if $n$ is even ($n=2k,k\geqslant 1)$, or with
$p_{1}=\cdots=p_{k}=U$, $p_{k+1}=H$ and $p_{k+2}=\dots=p_{n}=D$, if $n$ is odd
($n=2k+1,k\geqslant 1)$.

######  Remark 4.16.

An analogous result to Theorem 4.14 was proved also in [3]. In that paper, the
authors define distance paths in a distance support and show that the area
under a distance path corresponds to its associated value of the flag distance
by counting lattice points in the path, or below it, and applying Pick’s
Theorem.

###  4.3 The number of possible distance vectors of a flag code

As a consequence of Theorem 4.14, we can easily compute the number of possible
distance vectors that can be potentially associated to a full flag code with
prescribed minimum distance.

######  Definition 4.17.

Given a full flag code $\mathcal{C}\subseteq\mathcal{F}_{q}(n)$, its _set of
distance vectors_ is defined as

$\mathcal{D}(\mathcal{C})=\\{\textbf{d}(\mathcal{F},\mathcal{F}^{\prime})\ |\
\mathcal{F},\mathcal{F}^{\prime}\in\mathcal{C},\
d_{f}(\mathcal{F},\mathcal{F}^{\prime})=d_{f}(\mathcal{C})\\}.$

######  Example 4.18.

Let $\\{e_{1},e_{2},e_{3},e_{4}\\}$ be the standard basis of
${\mathbb{F}}_{q}^{4}$ as ${\mathbb{F}}_{q}$-vector space and consider the
full flag code $\mathcal{C}$ on ${\mathbb{F}}_{q}^{4}$ given by

$\begin{array}[]{ccccc}\mathcal{F}^{1}&=&(\left\langle
e_{1}\right\rangle,&\left\langle e_{1},e_{2}\right\rangle,&\left\langle
e_{1},e_{2},e_{4}\right\rangle),\\\ \mathcal{F}^{2}&=&(\left\langle
e_{1}\right\rangle,&\left\langle e_{1},e_{3}\right\rangle,&\left\langle
e_{1},e_{2},e_{3}\right\rangle),\\\ \mathcal{F}^{3}&=&(\left\langle
e_{2}\right\rangle,&\left\langle e_{2},e_{3}\right\rangle,&\left\langle
e_{1},e_{2},e_{3}\right\rangle).\end{array}$

Notice that

$\begin{array}[]{ccccccccccc}d_{f}(\mathcal{F}^{1},\mathcal{F}^{2})&=&0&+&1&+&1&=&2,\\\
d_{f}(\mathcal{F}^{1},\mathcal{F}^{3})&=&1&+&1&+&1&=&3,\\\
d_{f}(\mathcal{F}^{2},\mathcal{F}^{3})&=&1&+&1&+&0&=&2.\end{array}$

Hence, we have $d_{f}(\mathcal{C})=2$ and
$\mathcal{D}(\mathcal{C})=\\{(0,1,1),(1,1,0)\\}\subsetneq\mathcal{D}(2,4).$ On
the other hand, there are more distance vectors in $\mathcal{D}(2,4)$. It
suffices to apply Theorem 4.1 and see that $(1,0,1)$ is an element in
$\mathcal{D}(2,4).$

Directly from Corollary 4.15 we can state the following results concerning
full flag codes.

######  Corollary 4.19.

Given a full flag code $\mathcal{C}$ in ${\mathbb{F}}_{q}^{n},$ the number of
distance vectors in $\mathcal{D}(d_{f}(\mathcal{C}),n)$ equals the number of
Motzkin paths $p\in\mathcal{M}_{n}$ such that $A(p)=d_{f}(\mathcal{C})$, i.e.,
the value $T(n,d_{f}(\mathcal{C}))$.

######  Remark 4.20.

Notice that the previous result counts the number of possible distance vectors
associated to the minimum distance of a flag code. Nevertheless, this number
might not coincide with the exact number of distance vectors of the code. For
instance, if we take $\mathcal{F}^{1}$ and $\mathcal{C}$ as in Example 4.18,
it holds $d_{f}(\mathcal{C})=2$ and $|\mathcal{D}(\mathcal{C})|=2.$ Moreover,
if we consider $\mathcal{C}^{\prime}=\\{\mathcal{F}^{1},\mathcal{F}^{4}\\},$
with

$\mathcal{F}^{4}=(\left\langle e_{2}\right\rangle,\left\langle
e_{1},e_{2}\right\rangle,\left\langle e_{1},e_{2},e_{3}\right\rangle),$

then we also have $d_{f}(\mathcal{C}^{\prime})=2$ but
$|\mathcal{D}(\mathcal{C}^{\prime})|=1$. Even more, the sets
$\mathcal{D}(\mathcal{C})$ and $\mathcal{D}(\mathcal{C}^{\prime})$ do not
share any distance vector and form a partition of $\mathcal{D}(2,4)$, which
contains $T(4,2)=3$ elements.

On the other hand, in the special case of a flag code on
${\mathbb{F}}_{q}^{n}$ with minimum distance $D^{n}$, we can give the exact
number of its distance vectors (observe that $T(n,D^{n})=1$), as stated in the
next result.

######  Corollary 4.21.

Let $\mathcal{C}$ be a full flag code in ${\mathbb{F}}_{q}^{n}$ such that
$d_{f}(\mathcal{C})=D^{n}$. Then $\mathcal{C}$ has a unique distance vector.

We finish this section by computing the number of possible distance vectors
that a disjoint full flag code can have.

######  Proposition 4.22.

Let $\mathcal{C}$ be a disjoint full flag code in ${\mathbb{F}}_{q}^{n}$. Then
$d_{f}(\mathcal{C})\geqslant n-1$ and the number of possible distance vectors
for $\mathcal{C}$ is $T(n-2,d_{f}(\mathcal{C})-n+1)$.

###### Proof.

First of all, notice that, if $\mathcal{C}$ is disjoint, then its minimum
distance is attained by distance vectors $(\delta_{1},\dots,\delta_{n-1})$
with no zero components, i.e., $\delta_{i}\geqslant 1$, for every $1\leqslant
i\leqslant n-1$. Hence, such vectors can be decomposed into

$(\delta_{1},\dots,\delta_{n-1})=(1,\dots,1)+(\gamma_{0},\gamma_{1},\dots,\gamma_{n-3},\gamma_{n-2})$

with $\gamma_{i}=\delta_{i+1}-1$, for every $0\leqslant i\leqslant n-2$.
Notice that $\gamma_{0}=\gamma_{n-2}=0$ and, for every $1\leqslant i\leqslant
n-2$, it holds

$\gamma_{i}-\gamma_{i-1}=\delta_{i+1}-\delta_{i}\in\\{-1,0,1\\}.$

As a consequence, and by means of Theorem 4.1,
$(\delta_{1},\dots,\delta_{n-1})$ can be naturally identified with the
distance vector $(\gamma_{1},\dots,\gamma_{n-3})\in\mathcal{D}(n-2)$,
associated to the distance value

$\sum_{i=1}^{n-3}\gamma_{i}=\sum_{i=1}^{n-3}(\delta_{i+1}-1)=\sum_{i=0}^{n-2}(\delta_{i+1}-1)=d_{f}(\mathcal{C})-n+1.$

Hence, the number of distance vectors in $\mathcal{D}(d_{f}(\mathcal{C}),n)$
with no zero components, that is, the number of potential distance vectors for
$\mathcal{C}$, coincides with the number $T(n-2,d_{f}(\mathcal{C})-n+1)$. ∎

In the next table we can see the number of possible distance vectors
associated to a disjoint flag code $\mathcal{C}$ on ${\mathbb{F}}_{q}^{n}$
with prescribed minimum distance $d$ for small values of $n$.

$n$ $d$ | 0 | 1 | 2 | $3$ | 4 | $5$ | 6 | $7$ | $8$ | 9 | $10$ | $11$ | 12 | $13$ | $14$ | $15$ | 16
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
2 | - | $1$ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
3 | - | - | $1$ |  |  |  |  |  |  |  |  |  |  |  |  |  |
4 | - | - | - | $1$ | $1$ |  |  |  |  |  |  |  |  |  |  |  |
5 | - | - | - | - | $1$ | $2$ | $1$ |  |  |  |  |  |  |  |  |  |
6 | - | - | - | - | - | $1$ | $3$ | $3$ | $1$ | $1$ |  |  |  |  |  |  |
7 | - | - | - | - | - | - | $1$ | $4$ | $6$ | $4$ | $3$ | $2$ | $1$ |  |  |  |
8 | - | - | - | - | - | - | - | $1$ | $5$ | $10$ | $10$ | $8$ | $7$ | $5$ | $3$ | $1$ | $1$
Table 2: Numbers $T(n-2,d-n+1)$ for small values of $n$.

###  4.4 Other cases, other sequences

As it was done in Subsection 4.1 with the case of disjoint flag codes, it can
be very useful to interpret the properties of a given family of flags in terms
of a concrete family of Motzkin paths in order to localize a relevant sequence
of integers to count the number of associated distance vectors. To this end we
contemplate a last family of flags.

######  Proposition 4.23.

Let $\mathcal{H}_{n}$ be the set of full flags on ${\mathbb{F}}_{q}^{n}$ such
that given $\mathcal{F},\mathcal{F}^{\prime}\in\mathcal{H}_{n}$, they never
share consecutive subspaces. Hence, the number of possible distance vectors
corresponding to couples of flags in $\mathcal{H}_{n}$ is given by the
sequence of Riordan numbers, that is, sequence $A005043$ in [17].

###### Proof.

It is enough to observe that a couple of flags in
$\mathcal{F},\mathcal{F}^{\prime}\in\mathcal{H}_{n}$ never presents
consecutive collapses, that is, their associated distance vector
$\textbf{d}(\mathcal{F},\mathcal{F}^{\prime})$ never has two consecutive null
components. Thus, the Motzkin path
$\Psi(\textbf{d}(\mathcal{F},\mathcal{F}^{\prime}))$ does not have horizontal
steps in the $x$-axis and, as consequence, it is a Riordan path. ∎

##  5 Conclusions and open questions

In this paper we have addressed the problem of counting the number of distance
vectors associated with the full flag variety $\mathcal{F}_{q}(n)$. Moreover,
we have provided the number of possible distance vectors for a full flag code
with prescribed minimum distance either in the general case or in the disjoint
one. The key to compute these cardinalities is to associate biunivocally a
Motzkin word of length $n$ with a distance vector in $\mathcal{D}(n)$.

The problem of calculating the possible number of distance vectors when we
consider flags of general type $t=(t_{1},\dots,t_{r})$ is still open. We
believe that, to deal with this question, it could be useful the use of
Motzkin paths of higher rank where other kind of steps are allowed (see [13]).

On the other hand, taking into account the definition of the distance in the
context of multishot codes ([15, 16]), not necessarily flag codes, we think
that our work can be a starting point in the study of the possible
distributions of the total distance by using lattice paths.

##  6 Acknowledgements

We are very grateful to Paulo Almeida and Alessandro Neri for suggesting that
we explore the unexpected relationship between Dyck-Motzkin paths and the
distance paths we have introduced in our work [3].

## References

  * [1] R. Ahlswede, N. Cai, R. Li and R. W. Yeung, _Network Information Flow_ , IEEE Transactions on Information Theory, Vol. 46 (2000), 1204-1216.
  * [2] M. Aigner, _Motzkin Numbers_ , European Journal of Combinatorics, Vol. 19 (1998), 663-675.
  * [3] C. Alonso-González and M.A. Navarro-Pérez, _A Combinatorial Approach to Flag Codes_ , https://arxiv.org/pdf/2111.15388 (preprint).
  * [4] C. Alonso-González, M.A. Navarro-Pérez and X. Soler-Escrivà, _Flag Codes: Distance Vectors and Cardinality Bounds_ , https://arxiv.org/abs/2111.00910 (preprint).
  * [5] C. Alonso-González, M.A. Navarro-Pérez and X. Soler-Escrivà, _Flag Codes from Planar Spreads in Network Coding_ , Finite Fields and Their Applications, Vol. 68 (2020), 101745.
  * [6] C. Alonso-González, M. A. Navarro-Pérez and X. Soler-Escrivà, _Optimum Distance Flag Codes from Spreads via Perfect Matchings in Graphs_ , Journal of Algebraic Combinatorics, Vol. 54 (2021), 1279–1297.
  * [7] R. Donaghey and L. W. Shapiro, _Motzkin Numbers_ , Journal of Combinatorial Theory, Series A, Vol. 23 (1977), 291-301.
  * [8] M. Dukes, _The Sandpile Model on the Complete Split Graph, Motzkin Words, and Tiered Parking Functions_ , Journal of Combinatorial Theory, Series A, Vol. 180 (2021), 105418.
  * [9] M. Guay-Paquet and K. Petersen, _The Generating Function for Total Displacement_ , The Electronic Journal of Combinatorics, Vol. 21(3) (2014), P3.37.
  * [10] R. Koetter and F. Kschischang, _Coding for Errors and Erasures in Random Network Coding_ , IEEE Transactions on Information Theory, Vol. 54 (2008), 3579-3591.
  * [11] S. Kurz, _Bounds for Flag Codes_ , Designs, Codes and Cryptography, Vol. 89 (2021), 2759–2785.
  * [12] D. Liebhold, G. Nebe and A. Vázquez-Castro, _Network Coding with Flags_ , Designs, Codes and Cryptography, Vol. 86 (2) (2018), 269-284.
  * [13] T. Mansour, _Motzkin Numbers of Higher Rank: Generating Function and Explicit Expression_ , Journal of Integer Sequences, Vol. 10 (2007), Art.7.7.4.
  * [14] T. Motzkin, _Relations between Hypersurface Cross Ratios, and a Combinatorial Formula for Partitions of a Polygon, for Permanent Preponderance, and for Non-Associative Products_ , Bulletin of the American Mathematical Society, Vol. 54 (1948), 352-360.
  * [15] R. W. Nóbrega and B. F. Uchôa-Filho, _Multishot Codes for Network Coding: Bounds and a Multilevel Construction_ , in: 2009 IEEE International Symposium on Information Theory, Proceedings (ISIT), Seoul, South Korea, 2009, pp. 428–432.
  * [16] R. W. Nóbrega and B. F. Uchôa-Filho, _Multishot Codes for Network Coding Using Rank-Metric Codes_ , in: 2010 Third IEEE International Workshop on Wireless Network Coding, Boston, USA, 2010, pp. 1–6.
  * [17] N. J. A. Sloane, _The On-Line Encyclopedia of Integer Sequences_ , https://oeis.org/.
  * [18] N. J. A. Sloane, _Ennumerative Combinatorics_ , Vol. 2, Cambridge University Press, 1999.
  * [19] A.-L. Trautmann and J. Rosenthal, _Constructions of Constant Dimension Codes_ , in: M. Greferath et al. (Eds.), Network Coding and Subspace Designs, E-Springer International Publishing AG, 2018, pp. 25-42.