See https://en.wikipedia.org/wiki/Nakayama_algebra for the definition of Nakayama algebras and define the permanent of such an algebra to be the permanent of its Cartan matrix. (all algebras are assumed to be connected and finite dimensional) Conjecture: Let $X$ be the set of Nakayama algebras of finite global dimension with $n$ simple modules. Then the maximum of the permanents of algebras in X is given by $\sum\limits_{k=0}^{\infty}{\frac{k^n}{2^{k+1}}}$ and it is uniquely attained. See https://oeis.org/A000670 for the conjectured sequence.

The algebras with a line as a quiver should always have permanent equal to one. Here the algebras with permanent higher than 1 and finite global dimension with 3 simple modules (given by their Kupisch series as first entry and the permanent as second entry):

[ [ [ 2, 2, 3 ] 3 ], [ [ 2, 4, 3 ], 5 ], [ [ 3, 4, 4 ], 11 ], [ [ 3, 5, 4 ], 13 ] ]


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?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.