Is there a planar network whose path give a TNN matrix whose entries are Eulerian numbers?

2012-04-19T04:26:48Z

It is well-known that for each planar graph, the number of paths from each source to each sink will give rise to a totally non-negative matrix. However, did anyone ever come up with a planar network whose paths give a matrix whose entries are Eulerian numbers?

Answer by Gjergji Zaimi for Is there a planar network whose path give a TNN matrix whose entries are Eulerian numbers?

2012-04-19T23:50:17Z

There is a Bratelli diagram which satisfies this. Consider $\mathbb N^2$ as a graph where the edges are given by k parallel directed edges from $(n,k)$ to $(n+1,k)$, and $n-k+1$ parallel directed edges from $(n,k)$ to $(n+1,k+1)$. Here the number of paths from $(1,1)$ (the unique source) to any vertex $(n,k)$ is the Eulerian number $A(n,k)$, the number of permutations in $S_n$ with exactly $k$ ascents. For a picture see fig.1 in "Random permutations and unique fully supported ergodicity for the Euler adic transformation" by Frick and Petersen. This can be proven quickly using the recurrence $$A(n, k) = (k+1) A(n-1, k) + (n-k+1) A(n-1, k-1).$$

Somewhat similarly one can give a directed graph where the number of paths from the source to any vertex in the graph is equal to an Euler number $E(n,k)$, which counts the number of alternating permutations of $S_n$ which start with $k$. For a picture of how this looks like look at fig.5 in "Generating alternating permutations lexicographically" by Bauslaugh and Ruskey.

Is there a planar network whose path give a TNN matrix whose entries are Eulerian numbers? - MathOverflow

Is there a planar network whose path give a TNN matrix whose entries are Eulerian numbers?

Answer by Gjergji Zaimi for Is there a planar network whose path give a TNN matrix whose entries are Eulerian numbers?