Combinatorics problem related to Motzkin numbers with prize money I

Question

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).

Answer 1

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 on the arXiv.

FindStat's original answer

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)

Answer 2

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.