login
A236408
Number of increasing planar st-graphs with n edges.
0
1, 1, 3, 9, 33, 131, 561, 2535, 11971, 58579, 295297, 1526427, 8061879, 43380351, 237266225, 1316536991, 7399318871, 42065753191, 241628448517, 1400957386207, 8192041067535, 48275893465005, 286523348026527, 1711729590481577, 10288166837542901, 62183463880569941
OFFSET
1,3
COMMENTS
From Michael Wallner, Aug 17 2020: (Start)
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).
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)
REFERENCES
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.
LINKS
Alin Bostan, Jordan Tirrell, Bruce W. Westbury, and Yi Zhang, On sequences associated to the invariant theory of rank two simple Lie algebras, arXiv:1911.10288 [math.CO], 2019.
Alin Bostan, Jordan Tirrell, Bruce W. Westbury, and Yi Zhang, On some combinatorial sequences associated to invariant theory, arXiv:2110.13753 [math.CO], 2021.
FORMULA
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]
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
EXAMPLE
From Michael Wallner, Aug 17 2020: (Start)
All edges are directed to the bottom.
a(3)=3:
1 1 1
| |\ /|
2 | 2 2 |
| |/ \|
3 3 3
|
4
a(4)=9:
1 1 1 1 1 1 1 1 1
| | | |\ /| |\ /| / \ / \
2 2 2 2 | | 2 2 | | 2 2 3 3 2
| |\ /| |/ \| | | | | \ / \ /
3 3 | | 3 3 3 3 | | 3 4 4
| |/ \| | | |/ \|
4 4 4 4 4 4 4
|
5
(End)
MAPLE
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:
seq(a(n), n = 1..26); # Peter Luschny, Nov 05 2023
CROSSREFS
Sequence in context: A151043 A151044 A247195 * A217617 A320181 A238113
KEYWORD
nonn,more
AUTHOR
N. J. A. Sloane, Feb 03 2014
EXTENSIONS
Name clarified by Michael Wallner, Aug 17 2020
STATUS
approved