1,3

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

a(n)=number of lattice paths from (0,0) to (n-2,n-2) 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(4)=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 (callan(AT)stat.wisc.edu), Jun 07 2006

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

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

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)];

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.

a(n) = 2^(n-1)*A001003(n-2).

a(n) = 2^(n-1)*A001003(n-3).

Sequence in context: A007170 A136722 A085615 this_sequence A003576 A095989 A124453

Adjacent sequences: A054723 A054724 A054725 this_sequence A054727 A054728 A054729

nonn

Philippe Flajolet (Philippe.Flajolet(AT)inria.fr), Apr 20 2000