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.
James Cranch, Representing and Enumerating Two-Dimensional Pasting Diagrams, 2014.
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
KEYWORD
nonn,more
AUTHOR
N. J. A. Sloane, Feb 03 2014
EXTENSIONS
Name clarified by Michael Wallner, Aug 17 2020
STATUS
approved