# Combinatorics problem related to Motzkin numbers with prize money I

Here a combinatorics problem. I offer 30 euro for a proof and 100 bounty points for a counterexample: Let $n \geq 2$.

An $n$-Kupisch series is a list of $n$ numbers $c:=[c_1,c_2,...,c_n]$ with $c_n=1$, $c_i \ge 2$ for $i \neq n$ and $c_i-1 \leq c_{i+1}$ for all $i=1,...,n-1$ and setting $c_0:=c_n$. The number of such $n$-Kupisch series is equal to $C_{n-1}$ (Catalan numbers). The CoKupisch series $d$ of $c$ is defined as $d=[d_1,d_2,...,d_n]$ with $d_i:= \min \{k | k \geq c_{i-k} \}$ and $d_1=1$. One can show that the $d_i$ are a permutation of the $c_i$. A number $a \in \{1,...,n \}$ is a descent if $a=1$ or $c_a >c_{a-1}$. Define a corresponding set, indexed by descents: $X_1 := \{1,2,...,c_1-1 \}$, and $X_a := \{ c_{a-1}, c_{a-1}+1 ,..., c_a -1 \}$ for descents $a > 1$.

A $n$-Kupisch series is called $2-$Gorenstein if it satisfies the following condition:

for each descent $a$, and each $b \in X_a$: either $c_{a+b} \geq c_{a+b-1}$ or $d_{a+b-1} = d_{a+b + c_{a+b}-1} - c_{a+b}$ is satisfied.

Conjecture: The number of $n$-Kupisch series that are $2$-Gorenstein for $n \geq 2$ equals 1, 2, 4, 9, 21, 51, 127, 323, 835, 2188, 5798, 15511, 41835, ... which are the Motzin numbers. https://oeis.org/A001006

My computer says it is true for $n=2,3,...,14$. (also for n=1 if [1] is the unique 1-Kupisch series, by a representation-theoretic interpretation)

Here an example which visualises the c and d sequences in a picture of a Dyck path: https://drive.google.com/file/d/0B9hKtvQe-4-bQlpjcURfYnNzUGs/view

Background: This has a representation theoretic background (see http://www.sciencedirect.com/science/article/pii/0022404994900442 )and would give a certain classification result together with a new categorification of the Motzkin numbers. There is a very natural bijection of n-Kupisch series to Dyck paths from (0,0) to (2n-2,0) and probably the 2-Gorenstein algebras among them might give a new combinatorial interpretation of Motzkin paths as subpaths of Dyck paths.

I found in fact many such things and translated them into elementary problems, but I have no talent in complicated combinatorics :(

example for n=5:

All 5-Kupisch series (number is 14): [ [ 2, 2, 2, 2, 1 ], [ 3, 2, 2, 2, 1 ], [ 2, 3, 2, 2, 1 ], [ 3, 3, 2, 2, 1 ], [ 4, 3, 2, 2, 1 ], [ 2, 2, 3, 2, 1 ], [ 3, 2, 3, 2, 1 ], [ 2, 3, 3, 2, 1 ], [ 3, 3, 3, 2, 1 ], [ 4, 3, 3, 2, 1 ], [ 2, 4, 3, 2, 1 ], [ 3, 4, 3, 2, 1 ], [ 4, 4, 3, 2, 1 ], [ 5, 4, 3, 2, 1 ] ]

All 2-Gorenstein 5-Kupisch series (number is 9): [ [ 2, 2, 2, 2, 1 ], [ 3, 2, 2, 2, 1 ], [ 2, 3, 2, 2, 1 ], [ 4, 3, 2, 2, 1 ], [ 2, 2, 3, 2, 1 ], [ 3, 2, 3, 2, 1 ], [ 3, 3, 3, 2, 1 ], [ 2, 4, 3, 2, 1 ], [ 5, 4, 3, 2, 1 ] ]

Representation theoretic conjecture/background:

Conjecture:

The number of 2-Gorenstein algebras that are Nakayama algebras with n simple modules with a linear oriented line as a quiver is equal to the sequence of Motzkin numbers.

Background/explanations:

Here the $c_i$ are the dimension of the indecomposable projective modules which determine the algebra uniquely (assuming that the algebras are connected quiver algebras over a field). The $d_i$ are the dimension of the indecomposable injective modules at point $i$. 2-Gorenstein means that the dual of the regular module $D(A)$ has a projective presentation $P_1 \rightarrow P_0 \rightarrow D(A) \rightarrow 0$ with $P_1$ having injective dimension bound by 1. ($P_0$ is always projective-injective for Nakayama algebras)

Here a link for the program I used to test things (copy all programs, and the finaltest program does the job then. 1 means the Kupisch series is 2-Gorenstein and 0 means it is not): https://docs.google.com/document/d/1U9mriuvCEE9FeXY1TfY_yJ1mi05TCdHRfppwCSwi1S8/pub

edit: Since we have 2 people with proofs now, I award 30 Euro each to them in case their proof is correct (I still have to check) and then no more money for new proofs.

I award additionally 200 bounty points to the nicest proof (which might be one of the two first posted proofs or another not yet posted proof), which can be decided by the community in terms of upvotes near the end when the bounty expires (16.08.)

edit 2: Now at 16.08. I give the bounty points to Anton, since it is the most complete answer and the details of findstats answer are not posted yet. I will give 30 Euro to each after checking findstats proof (when it is posted and correct).

edit 3: Since findstat updated the answer and now has a full proof of an extension of the conjecture just a little time after I awarded the first bounty, I also will give a bounty to them and accept their answer (second bounty had to be 400 or higher and can be awarded after 24 hours).

• I still do not understand the definition of co-Kupisch: for $c=[3,2,1]$, we want $d_2$ to be the smallest $k$ which is at least $c_{2-k}$. For $k=0$, we have $0 \not\geq c_2$, and for $k=1$ we have $1\not\geq c_1$. – Martin Rubey Aug 8 '17 at 20:50
• @MartinRubey Thanks for testing. I think the problem is resolved when looking at the $c_i$ mod $n$ so they are defined for every $i \in \mathbb{Z}$. Then $2 \geq c_{2-2}=c_0=c_n=1$ and thus $d_2=2$ always as it should be by using quiver interpretation. – Mare Aug 8 '17 at 20:58
• So, essentially, the Kupisch and the co-Kupisch sequence are the sequences of heights of the down and up steps, respectively, after prepending an up-step and appending a down-step to your Dyck path. – Martin Rubey Aug 8 '17 at 23:31
• My next problem is the 2-Gorenstein condition. For example, if $c=[3,2,2,2,1]$, I get $d=[1,2,3,2,2]$, only descent $a=1$, $X_1=\{1,2\}$. Now for $a=1$ and $b=1$ I have neither $c_2 \geq c_1$ nor $d_2 = d_{2+c_2-1} -c_2$. – Martin Rubey Aug 9 '17 at 0:23
• @MartinRubey cant thank you enough. Im very sorry, it is $d_{a+b-1} = d_{a+b + c_{a+b}-1} - c_{a+b}$ instead of $d_{a+b} = d_{a+b + c_{a+b}-1} - c_{a+b}$. Was a little late when I posted the question... Now in this example one has $c_2=2<c_1=3$ but $d_2=2$ and $d_{2+c_2-1}=d_3=3=d_1+c_2=1+2$. For $a=1$ and $b=2$ one has $c_3 =2 \geq 2=c_2$. – Mare Aug 9 '17 at 8:05

## UPDATE

The promised writeup, proving both conjectures, is now finished. It will be available on the arxiv on Friday, in the meantime it is available here.

I have the following refined conjecture, which hopefully can be transformed into a proof without too much trouble:

let's call a pair $(a, b)$ where $a$ is a descent and $b\in X_a$ which does not satisfy the condition

$c_{a+b} \geq c_{a+b-1}$ or $d_{a+b-1} = d_{a+b + c_{a+b}-1} - c_{a+b}$

a $2$-Gorenstein failure.

Then it appears that the number of $2$-Gorenstein failures is the composition of http://findstat.org/Mp00129 (The Billey-Jockusch-Stanley bijection to 321-avoiding permutations) and http://findstat.org/St000732 (The number of double deficiencies of a permutation).

In the above mentioned statistic there is a reference to a paper by Sergi Elizalde, "Continued fractions for permutation statistics", which contains a bijection between $321$-avoiding permutations without double excedances and Motzkin paths.

Thus it remains to show that $2$-Gorenstein failures indeed correspond to double deficiencies.

## Outline of proof

Throughout the proof, a Dyck path starts at the origin, has north and east steps and never goes below the diagonal $y=x$. We think of the Dyck path as running in an array of columns labelled $1$ to $n$ from left to right, and rows labelled $1$ to $n$ from bottom to top.

Let us first recall the bijection due to Billey, Jockusch and Stanley, sending a Dyck path $D$ to a $321$-avoiding permutation $\pi$. To obtain the (horizontally flipped) permutation matrix of $\pi$ corresponding to $D$, put a cross into each valley (an east step followed by a north step) and fill the remaining slots with an increasing sequence of crosses.

Our claim is an immediate consequence of the following three statements.

Lemma 1. $c_{x+1} = c_x - 1$ if and only if $x$ is a weak deficiency of $\pi$, that is $\pi(x)\leq x$. Equivalently, there is a double east step spanning columns $x$ and $x+1$.

Lemma 2. $c_{x+1} = c_x - 1$ and $c_{x+1} + d_x = d_{x+c_{x+1}}$ if and only if $x$ is a fixed point of $\pi$.

Lemma 3. Let $x$ be a strict deficiency of $\pi$. Then $\pi^{-1}(x)$ is also a strict deficiency if and only if $x+1=a+b$ where $a$ is a descent and $b\in X_a$.

We intend to provide a detailed and illustrated version of this argument within the next few days.

## Sage code used to discover the conjecture

def kupisch(D):
"""
sage: [kupisch(D) for D in DyckWords(3)]
[[2, 2, 2, 1], [2, 3, 2, 1], [3, 2, 2, 1], [3, 3, 2, 1], [4, 3, 2, 1]]
"""
H = D.heights()
return [1+H[i] for i, s in enumerate(D) if s == 0]+[1]

def cokupisch(D):
"""
sage: [cokupisch(D) for D in DyckWords(3)]
[[1, 2, 2, 2], [1, 2, 2, 3], [1, 2, 3, 2], [1, 2, 3, 3], [1, 2, 3, 4]]
"""
H = D.heights()
return [1]+[1+H[i+1] for i, s in enumerate(D) if s == 1]

def descents(D):
"""
sage: [(D, kupisch(D), descents(D)) for D in DyckWords(3)]
[([1, 0, 1, 0, 1, 0], [2, 2, 2, 1], [1]),
([1, 0, 1, 1, 0, 0], [2, 3, 2, 1], [1, 2]),
([1, 1, 0, 0, 1, 0], [3, 2, 2, 1], [1]),
([1, 1, 0, 1, 0, 0], [3, 3, 2, 1], [1]),
([1, 1, 1, 0, 0, 0], [4, 3, 2, 1], [1])]
"""
c = kupisch(D)
return [1] + [a+1 for a in range(1, len(c)) if c[a] > c[a-1]]

def gorenstein_failures(D):
D = DyckWord(D)
c = kupisch(D)
d = cokupisch(D)
D = descents(D)
f = 0
for a in D:
if a == 1:
X = range(1, c[0])
else:
X = range(c[a-1-1], c[a-1])
for b in X:
if c[a+b-1] >= c[a+b-1-1] or d[a+b-1-1] == d[a+b+c[a+b-1]-1-1] - c[a+b-1]:
continue
else:
f += 1
return f

findstat("Dyck Paths", gorenstein_failures)
0: (St000732: The number of double deficiencies of a permutation., [Mp00129: to 321-avoiding permutation (Billey-Jokusch-Stanley)], 200)
1: (St000366: The number of double descents of a permutation., [Mp00129: to 321-avoiding permutation (Billey-Jokusch-Stanley), Mp00087: inverse first fundamental transformation], 200)
2: (St000731: The number of double exceedences of a permutation., [Mp00129: to 321-avoiding permutation (Billey-Jokusch-Stanley), Mp00066: inverse], 200)
• This looks spectacular. How good tested is your conjecture? – Mare Aug 9 '17 at 20:20
• I can read in your second link the definition of a double deficiency but not of a double excedance : is it the same with reversed inequalities, i. e a "negative" double deficiency ? – Sylvain JULIEN Aug 9 '17 at 20:21
• I think it would be useful to add the code here as it is rather straightforward to see how this works. Should I add it? – Christian Stump Aug 9 '17 at 20:33
• It appears that Sergi Elizalde's cycle diagram makes at least the relation between $c_{a+b}\geq c_{a+b-1}$ and double deficiencies clear. I haven't translated the other condition yet, though. – Martin Rubey Aug 9 '17 at 22:56
• @MartinRubey the condition $c_{a+b} \geq c_{a+b-1}$ alone also has an interesting interpretation. If I made no mistake it counts the algebras having the double centralizer protperty with respect to a minimal faithful projective-injective module. My conjecture is that the corresponding sequence is oeis.org/A005043 . – Mare Aug 9 '17 at 23:24

Here is a sketch of the proof. For me Dyck paths of length $n$ are paths from $(0,0)$ to $(n,n)$ consisting of North and East steps staying weakly above the diagonal. North means $(0,1)$, East means $(1,0)$. A path is called primitive if it is non-empty and touches the diagonal only at the endpoints.

A number of the form $a+b-1$ for a descent $a$ and $b\in N_a$ will be called double rise. A number $i$ such that $c_{i+1}<c_i$ will be called double fall. If a number $i$ is both double rise and double fall, we call it a match. Your condition can be reformulated as follows:

For any match $i$ the part of the Dyck path from $(i-d_i, i)$ to $(i, i+c_i)$ is a sequence of North steps followed by a sequence of East steps.

For any primitive $2$-Gorenstein Dyck path $p$ we pick the smallest match $i$ if it exists and construct two paths $p_1$, $p_2$ as follows. $p_1$ is the path from $(0,0)$ to $(i,i)$ obtained by following $p$ and then as soon as we reach double rise position we make a 'cut', that is, we simply perform $d_i$ East steps. Then we begin the path $p_2$ at $(i,i)$ by $c_i$ North steps so that we reach the double fall position and then continue along the path $p$.

Lemma 1. The construction above provides a bijection between the set of primitive $2$-Gorenstein Dyck paths $p$ of length $n$ with at least one match and the set of pairs of primitive Dyck paths $p_1, p_2$ whose lengths add up to $n$ and such that $p_1$ has no matches and $p_2$ is $2$-Gorenstein.

Iterating this as many times as we need to get rid of all matches we obtain

Corollary 1. There is a bijection between the set of primitive $2$-Gorenstein Dyck paths of lengths $n$ and the set of tuples of primitive Dyck paths without matches whose lengths add to $n$.

Alternatively, we have a bijection between primitive $2$-Gorenstein Dyck paths and arbitrary Dyck paths without matches.

Now we look at the definition of Motzkin numbers, denote them by $M_n$. We use the definition which says that $M_n$ is the number of paths from $(0,0)$ to $(n,0)$ consisting of steps $U=(1,1)$, $D=(1,-1)$, $F=(1,0)$ staying weakly above the horizontal axis. We are going to construct a bijection between paths without matches and Motzkin numbers.

Having a Dyck path without matches let us build a Motzkin path as follows. Let $DR$ be the set of double rises. Let $DF$ be the set of double falls. It is well-known that $|DR|=|DF|$. For a Dyck path without matches these sets do not intersect. Notice that the pair $DR, DF$ uniquely determines the Dyck path. From a pair of non-intersecting sets $DR, DF\subset\{1,\ldots,n-1\}$ of the same size we construct a path from $(0,0)$ to $(n-1,0)$ as follows: We go through $i=1,\ldots,n-1$. When $i\in DR$ we put $U$. When $i\in DF$ we put $D$. Otherwise put $F$. Let us call the resulting path the $UDF$-path corresponding to $DR, DF$. The proof is completed by the following

Lemma 2. A pair of non-intersecting subsets $DR, DF\subset \{1,\ldots,n-1\}$ of same size comes from a Dyck path if and only if the corresponding $UDF$-path is a Motzkin path.

Proof. Consider an arbitrary path from $(0,0)$ to $(n,n)$ consisting of some North and East steps such that the first step is North. Let us view the path as a union of interchanging vertical and horizontal segments (now of lengths $\geq 1$). We label the horizontal and the vertical segments by numbers from $1$ to $k$. I.e. first we have a vertical segment with label $1$, then a horizontal segment with label $1$, then a vertical segment with label $2$ and so on. For each $i$ let $h_i$ be the label of the horizontal segment which intersects the line $x=i-\frac12$. Let $v_i$ be the label of the vertical segment which intersects the line $y=i-\frac12$. Let $d_i=h_i-v_i$. Check that the points $(i-1,d_i)$ are precisely the points through which the $UDF$ path goes. Check that the path is a Dyck path precisely when $d_i\geq 0$ for all $i$.

For example, take Dyck path NNENEE. We have one double rise $i=1$, one double fall $i=2$. We have $d_1=0$, $d_2=1$, $d_3=0$. This corresponds to Motzkin path UD. On the other hand NENENE produces $d_1=d_2=d_3=0$ and Motzkin path FF.

• I would like to point out that this is (a special case of) exactly the same bijection provided in FindStat's answer. For the casual reader, it is helpful to note that here an initial north step is prepended and a trailing east step appended to the original path, so that NNENEE is $2$-Gorenstein. Moreover, $d_k$ is the usual area sequence (and $c_k$ the column version), instead of adding $1$ to every entry. – Martin Rubey Aug 17 '17 at 19:31
• Thanks for the suggestions. Yeah, I see that it's the same bijection. Now I see how to extend it to a bijection from all Dyck paths to red-blue Motzkin paths. Simply mark positions of double rises and double falls. Then go from left to right. If you see double rise put U. If double fall put D. Both put red F, none put blue F. I think it's much easier if you skip the 321 permutations altogether. – Anton Mellit Aug 17 '17 at 20:07
• Well, what you describe is exactly Billey-Jockusch-Stanley and Foata-Zeilberger, except that you describe a special case of the latter and you do not mention the underlying permutation, which makes it clear why they work. The general case of both maps is described by a single picture, or six lines of text for Billey-Jockusch-Stanley and six lines of text for Foata-Zeilberger. – Martin Rubey Aug 17 '17 at 21:01
• (I should add: Sergi's paper which is cited in FindStats answer is of course a description of the Foata-Zeilberger map, which makes the properties obvious which we need. So proving the three lemmas in FindStats answer is essentially equivalent to your proof.) – Martin Rubey Aug 17 '17 at 21:19
• What's the general case of Foata-Zeilberger map? – Anton Mellit Aug 17 '17 at 21:57