Permanent of Nakayama algebras

Mare's answer reduces the problem to showing that the permanant of the $n \times n$ matrix $$\begin{bmatrix} 1 & 1 & 1 & \cdots & 1 \\ 1 & 2 & 2 & \cdots & 2 \\ 1 & 1 & 2 & \cdots & 2 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & 1 & 1 & \cdots & 2 \\ \end{bmatrix}$$ is the number of weak orders on $[n]:=\{ 1,2, \ldots, n \}$. This answer will prove that.

First of all, permanent is unchanged by reordering the rows, so I will modify the matrix to $$\begin{bmatrix} 1 & 2 & 2 & \cdots & 2 \\ 1 & 1 & 2 & \cdots & 2 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & 1 & 1 & \cdots & 2 \\ 1 & 1 & 1 & \cdots & 1 \\ \end{bmatrix}.$$ By the definition of the permanent, the permanent is $$\sum_{\sigma \in S_n} 2^{\# \{ j \ :\ \sigma(j) > j \}}.$$

We can give a similar formula for the number of weak orders. Given a weak order $\succeq$ on $[n]$, define a total order on the same set by break all ties in according to the standard order on $[n]$. For example, $13 \succeq 5 \succeq 24$ turns into $3 > 1 > 5 > 4 > 2$. Total orders on $[n]$ correspond to permutations in $S_n$; given a permutation $\sigma$, the number of weak orders which give rise to it is $2^{\# \{ k : \sigma(k) > \sigma(k+1) \}}$. For example, to choose a weak order giving rise to the total order $3 > 1 > 5 > 4 > 2$, we just have to decide whether or not to group $(3,1)$, $(5,4)$ and $(4,2)$ together, and these choices are independent. So A000670 is $$\sum_{\sigma \in S_n} 2^{\# \{ k \ :\ \sigma(k) > \sigma(k+1) \}}.$$

For a permutation $\sigma \in S_n$, the exponent $\# \{ k : \sigma(k) > k \}$ is called the number of exceedances of $\sigma$, and $\# \{ k \ :\ \sigma(k) > \sigma(k+1) \}$ is called the number of descents of $\sigma$. So the conjecture follows from the following stronger result:

Theorem The number of permutations of $n$ elements with $r$ descents is the same as the number of permutations of $n$ elements with $r$ exceedances.

This was originally proved by MacMahon in 1915 and has been reproved many times since. The number of permutations of $n$ elements with $r$ descents is called the Eulerian number, denoted $\left\langle \begin{smallmatrix} n\\r \end{smallmatrix} \right\rangle$ and a statistic $f : S_n \to \mathbb{Z}$ which takes the value $r$ a total of $\left\langle \begin{smallmatrix} n\\r \end{smallmatrix} \right\rangle$ times on $S_n$ is called "Eulerian".

A quick proof can be found as Proposition 3.14 in these notes. (No originality claimed for this source; just the first one I found without a lot of extraneous material.)


I found a proof I guess: First note that a Nakayama algebra with a circle as a quiver and $n \geq 2$ simple modules has Kupisch series of the form $[c_0,c_1,...,c_{n-1}]$ with $c_{n-1}=c_0+1 \geq 3$ and $c_i-1 \leq c_{i+1}$ else. Now in case one has $c_0 \geq n+1$ then the simple modules $S_0$ should have infinite projective dimension and thus the algebra has infinite global dimension. But the algebra with Kupisch series $[n,2n-1,2n-2,...,n+1]$ has finite global dimension. (this should also prove a slight generalisation of a result of gustafson in http://ac.els-cdn.com/0021869385900699/1-s2.0-0021869385900699-main.pdf?_tid=cdb3970c-8c15-11e7-be52-00000aab0f27&acdnat=1503941273_ffdc739fc29a56625414330e0bcbe36f, namely a Nakayama algebra of finite global dimension with $n$ simple modules has Loewy length at most $2n-1$ and each such algebra is a quotient algebra of the one with kupisch series $[n,2n-1,2n-2,...,n+1]$, which is also the unique such algebra with largest Loewy length $2n-1$).

Now what is left to do is calculate the permanent of the algebra with Kupisch series $[n,2n-1,2n-2,...,n+1]$.

The Cartan matrix in this cases is the matrix with rows $[1,1,....,1], [1,2,2,....,2,2], [1,1,2,2,...,2,2]....,[1,1,1,....,1,2]$.

What is left to do is to show that the permanent of this matrix is given by $\sum\limits_{k=0}^{\infty}{\frac{k^n}{2^{k+1}}}$, see https://oeis.org/A000670.

I try my luck on proving that now, but feel free to post a proof if you have a quick argument (I have no experience with calculating permanents)!

The sequence is $\frac{1}{2}$ of the sequence https://oeis.org/A000629 , which also has to do with circles (necklaces). Is there a good reason why?