A236408 Number of increasing planar st-graphs with n edges.

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

Table of n, a(n) for n=1..26.

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

Sequence in context: A151043 A151044 A247195 * A217617 A320181 A238113

Adjacent sequences: A236405 A236406 A236407 * A236409 A236410 A236411

Keyword

nonn,more

Author

N. J. A. Sloane, Feb 03 2014

Extensions

Name clarified by Michael Wallner, Aug 17 2020

Status

approved