login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual Appeal: Please make a donation (tax deductible in USA) to keep the OEIS running. Over 5000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A054726 Number of graphs with n nodes on a circle without crossing edges. 14
1, 1, 2, 8, 48, 352, 2880, 25216, 231168, 2190848, 21292032, 211044352, 2125246464, 21681954816, 223623069696, 2327818174464, 24424842461184, 258054752698368, 2742964283768832, 29312424612462592, 314739971287154688, 3393951437605044224, 36739207546043105280 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

Related to Schröder's second problem.

A001006 gives number of ways of drawing any number of nonintersecting chords between n points on a circle, while this sequence gives number of ways of drawing noncrossing chords between n points on a circle. The difference is that nonintersection chords have no point in common, while noncrossing chords may share an endpoint. - David W. Wilson, Jan 30 2003

For n>0, a(n) = number of lattice paths from (0,0) to (n-1,n-1) that consist of steps (i,j), i,j nonnegative integers not both 0 and that stay strictly below the line y=x except at their endpoints. For example, a(3)=8 counts the paths with following step sequences: {(2, 2)}, {(2, 1), (0, 1)}, {(2, 0), (0, 2)}, {(2, 0), (0, 1), (0, 1)}, {(1, 0), (1, 2)}, {(1, 0), (1, 1), (0, 1)}, {(1, 0), (1, 0), (0, 2)}, {(1, 0), (1, 0), (0, 1), (0, 1)}. If the word "strictly" is replaced by "weakly", the counting sequence becomes A059435. - David Callan, Jun 07 2006

The nodes on the circle are distinguished by their positions but are otherwise unlabeled. - Lee A. Newberg, Aug 09 2011

REFERENCES

Drmota, Michael; de Mier, Anna; Noy, Marc. Extremal statistics on non-crossing configurations. Discrete Math. 327 (2014), 103--117. MR3192420. See Eq. (6). - N. J. A. Sloane, May 18 2014

LINKS

Vincenzo Librandi, Table of n, a(n) for n = 0..200

F. Cazals, Combinatorics of Non-Crossing Configurations, Studies in Automatic Combinatorics, Volume II (1997).

P. Flajolet and M. Noy, Analytic Combinatorics of Noncrossing Configurations, Discr. Math. 204 (1999), 203-229

P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 486

Marco Kuhlmann, Tabulation of Noncrossing Acyclic Digraphs, arXiv preprint, 2015.

Sequences related to chord diagrams

FORMULA

a(n) = 2^n*A001003(n-2) for n>2.

From Lee A. Newberg, Aug 09 2011: (Start)

G.f.: 1 + (3/2)*z - z^2 - (z/2)*sqrt(1 - 12*z + 4*z^2);

a(n) = ((12*n-30)*a(n-1) - (4*n-16)*a(n-2)) / (n-1) for n>1. (End)

a(n) ~ sqrt(99*sqrt(2) - 140)*(6 + 4*sqrt(2))^n/(4*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Oct 11 2012

MAPLE

with(combstruct): br:= {EA = Union(Sequence(EA, card >= 2), Prod(V, Sequence(EA), Sequence(EA))), V=Union(Prod(Z, G)), G=Union(Epsilon, Prod(Z, G), Prod(V, V, Sequence(EA), Sequence(EA), Sequence(Union(Sequence(EA, card>=1), Prod(V, Sequence(EA), Sequence(EA)))))) }; ggSeq := [seq(count([G, br], size=i), i=0..20)];

MATHEMATICA

Join[{a = 1, b = 1}, Table[c = (6*(2*n - 3)*b)/n - (4*(n - 3) a)/n; a = b; b = c, {n, 1, 40}]] (* Vladimir Joseph Stephan Orlovsky, Jul 11 2011 *)

PROG

(PARI) z='z+O('z^66); Vec( 1+3/2*z-z^2-z/2*sqrt(1-12*z+4*z^2) ) \\ Joerg Arndt, Mar 01 2014

CROSSREFS

Cf. A006013, A001003.

Sequences related to chords in a circle: A001006, A054726, A006533, A006561, A006600, A007569, A007678. See also entries for chord diagrams in Index file.

Sequence in context: A171455 A136722 A085615 * A003576 A225042 A095989

Adjacent sequences:  A054723 A054724 A054725 * A054727 A054728 A054729

KEYWORD

nonn

AUTHOR

Philippe Flajolet, Apr 20 2000

EXTENSIONS

Offset changed to 0 by Lee A. Newberg, Aug 03 2011

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified December 9 12:22 EST 2016. Contains 278971 sequences.