A296533 Number of nonequivalent noncrossing trees with n edges up to rotation and reflection.

1, 1, 1, 3, 7, 28, 108, 507, 2431, 12441, 65169, 351156, 1926372, 10746856, 60762760, 347664603, 2009690895, 11723160835, 68937782355, 408323575275, 2434289046255, 14598013278960, 88011196469040, 533216762488020, 3245004785069892, 19829769013792908

Offset

0,4

Comments

The number of all noncrossing trees with n edges is given by A001764.

The number of nodes will be n + 1.

Links

Andrew Howroyd, Table of n, a(n) for n = 0..200

M. Noy, Enumeration of noncrossing trees on a circle, Discrete Math., 180, 301-313, 1998.

Formula

a(2n) = (A296532(2n) + A001764(n))/2, a(2n-1) = (A296532(2n-1) + A006013(n-1))/2.

a(2n) = A005034(2n).

Example

Case n=3:
   o---o   o---o   o---o
   |       | \       \
   o---o   o   o   o---o
In total there are 3 distinct noncrossing trees up to rotation and reflection.

Mathematica

a[n_] := (If[OddQ[n], 3*Binomial[(1/2)*(3*n - 1), (n - 1)/2], Binomial[3*n/2, n/2]] + Binomial[3*n, n]/(2*n + 1))/(2*(n + 1));
Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Dec 27 2017, after Andrew Howroyd *)

Prog

(PARI) a(n)={(binomial(3*n, n)/(2*n+1) + if(n%2, 3*binomial((3*n-1)/2, (n-1)/2),  binomial(3*n/2, n/2)))/(2*(n+1))}

Crossrefs

Cf. A001764, A005034, A006013, A296532 (up to rotation only).

Sequence in context: A197550 A289605 A361360 * A321719 A309619 A143948

Adjacent sequences: A296530 A296531 A296532 * A296534 A296535 A296536

Keyword

nonn

Author

Andrew Howroyd, Dec 14 2017

Status

approved