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

 

Logo

Invitation: celebrating 50 years of OEIS, 250000 sequences, and Sloane's 75th, there will be a conference at DIMACS, Rutgers, Oct 9-10 2014.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A054726 Number of graphs with n nodes on a circle without crossing edges. 13
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 Schroeder'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

Sequences related to chord diagrams

FORMULA

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

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. - Lee A. Newberg, Aug 09 2011

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

Content is available under The OEIS End-User License Agreement .

Last modified July 29 19:03 EDT 2014. Contains 245041 sequences.