Is there a planar network whose path give a TNN matrix whose entries are Eulerian numbers? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T17:23:40Z http://mathoverflow.net/feeds/question/94490 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/94490/is-there-a-planar-network-whose-path-give-a-tnn-matrix-whose-entries-are-eulerian Is there a planar network whose path give a TNN matrix whose entries are Eulerian numbers? Percy 2012-04-19T04:26:48Z 2012-04-21T00:21:48Z <p>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? </p> http://mathoverflow.net/questions/94490/is-there-a-planar-network-whose-path-give-a-tnn-matrix-whose-entries-are-eulerian/94581#94581 Answer by Gjergji Zaimi for Is there a planar network whose path give a TNN matrix whose entries are Eulerian numbers? Gjergji Zaimi 2012-04-19T23:50:17Z 2012-04-21T00:21:48Z <p>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 <a href="http://en.wikipedia.org/wiki/Eulerian_number" rel="nofollow">Eulerian number</a> \$A(n,k)\$, the number of permutations in \$S_n\$ with exactly \$k\$ ascents. For a picture see fig.1 in <a href="http://projecteuclid.org/DPubS?service=UI&amp;version=1.0&amp;verb=Display&amp;handle=euclid.aihp/1222261916" rel="nofollow">"Random permutations and unique fully supported ergodicity for the Euler adic transformation"</a> 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).\$\$</p> <p>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 <a href="http://en.wikipedia.org/wiki/Alternating_permutation" rel="nofollow">alternating permutations</a> of \$S_n\$ which start with \$k\$. For a picture of how this looks like look at fig.5 in <a href="http://www.springerlink.com/content/xx43404n2t4388p0/" rel="nofollow">"Generating alternating permutations lexicographically"</a> by Bauslaugh and Ruskey.</p>