login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 (list; graph; refs; listen; history; text; internal format)
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..20.

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.

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

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)

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 21 23:35 EDT 2021. Contains 345367 sequences. (Running on oeis4.)