|
%I #42 Nov 06 2023 04:30:30
%S 1,1,3,9,33,131,561,2535,11971,58579,295297,1526427,8061879,43380351,
%T 237266225,1316536991,7399318871,42065753191,241628448517,
%U 1400957386207,8192041067535,48275893465005,286523348026527,1711729590481577,10288166837542901,62183463880569941
%N Number of increasing planar st-graphs with n edges.
%C From _Michael Wallner_, Aug 17 2020: (Start)
%C A graph with m vertices is called increasing, or topolicically ordered, if each vertex v is assigned a number l(v) from {1,...,m} and if there is a directed path from vertex v to vertex w then l(v) < l(w).
%C Note that a planar st-graph is an actual embedding into the plane, i.e., we distinguish a left-to-right order on the children of each node. In other words, it is a plane graph, a concept also sometimes called isotopy. (End)
%D Ioannis G. Tollis, Giuseppe Di Battista, Peter Eades, and Roberto Tamassia, Graph drawing, Prentice Hall Inc., Upper Saddle River, NJ, 1999. Algorithms for the visualization of graphs. MR2064104 (2005i:68067). See Sect. 4.2.
%H Alin Bostan, Jordan Tirrell, Bruce W. Westbury, and Yi Zhang, <a href="https://arxiv.org/abs/1911.10288">On sequences associated to the invariant theory of rank two simple Lie algebras</a>, arXiv:1911.10288 [math.CO], 2019.
%H Alin Bostan, Jordan Tirrell, Bruce W. Westbury, and Yi Zhang, <a href="https://arxiv.org/abs/2110.13753">On some combinatorial sequences associated to invariant theory</a>, arXiv:2110.13753 [math.CO], 2021.
%H James Cranch, <a href="http://jdc41.user.srcf.net/research/pasting/Pasting.pdf">Representing and Enumerating Two-Dimensional Pasting Diagrams</a>, 2014.
%F Conjecture: (n+2)*(n+3)*a(n) = 2*n*(2*n+1)*a(n-1) + (n-2)*(19*n-9)*a(n-2) + 14*(n-3)*(n-2)*a(n-3). - _Vaclav Kotesovec_, Feb 14 2014 [For a proof of the conjecture see Corollary 4.14 in Bostan et. al. arxiv.org/abs/2110.13753. - _Mark van Hoeij_, Nov 05 2023]
%F O.g.f.: ((8*x^3 + 12*x^2 + 6*x + 1)*hypergeom([1/4, 3/4], [2], 64*x*(1 + 2*x)^3 / (1 + 22*x + 13*x^2)^2) / (x^2*(1 + 22*x + 13*x^2)^(1/2)) - 1/x - 1/x^2)/3 - 1. - _Mark van Hoeij_, Nov 05 2023
%e From _Michael Wallner_, Aug 17 2020: (Start)
%e All edges are directed to the bottom.
%e a(3)=3:
%e 1 1 1
%e | |\ /|
%e 2 | 2 2 |
%e | |/ \|
%e 3 3 3
%e |
%e 4
%e a(4)=9:
%e 1 1 1 1 1 1 1 1 1
%e | | | |\ /| |\ /| / \ / \
%e 2 2 2 2 | | 2 2 | | 2 2 3 3 2
%e | |\ /| |/ \| | | | | \ / \ /
%e 3 3 | | 3 3 3 3 | | 3 4 4
%e | |/ \| | | |/ \|
%e 4 4 4 4 4 4 4
%e |
%e 5
%e (End)
%p a := proc(n) option remember; if n < 4 then [1, 1, 3][n] else (2*n*(2*n+1)*a(n-1) + (n-2)*(19*n-9)*a(n-2) + 14*(n-3)*(n-2)*a(n-3)) / ((n+2)*(n+3)) fi end:
%p seq(a(n), n = 1..26); # _Peter Luschny_, Nov 05 2023
%K nonn,more
%O 1,3
%A _N. J. A. Sloane_, Feb 03 2014
%E Name clarified by _Michael Wallner_, Aug 17 2020
|
