A296532 Number of nonequivalent noncrossing trees with n edges up to rotation.

1, 1, 1, 4, 11, 49, 204, 984, 4807, 24739, 130065, 701584, 3851316, 21489836, 121517768, 695307888, 4019338527, 23446201495, 137875318035, 816646459860, 4868576661795, 29196022525905, 176022384523440, 1066433501134560, 6490009520072676, 39659537885087124

Offset: 0

Author

Andrew Howroyd, Dec 14 2017

Keywords

• nonn

Comments

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

The number of nodes will be n + 1.

Rotational symmetry is only possible with an even number of nodes and with a rotation of 180 degrees (rotation by n/2 nodes). A tree with rotational symmetry will always include exactly one edge that connects diametrically opposite nodes.

The sequence satisfies a(2n) = A000139(2n)/2. - F. Chapoton, Sep 08 2023

Examples

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

Links

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

Crossrefs

Cf. A001764, A006013, A296533 (up to rotation and reflection), A000139.

Programs

Mathematica

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

PARI

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

Formula

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