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

%I #16 Jun 12 2018 19:37:33

%S 1,1,1,3,7,28,108,507,2431,12441,65169,351156,1926372,10746856,

%T 60762760,347664603,2009690895,11723160835,68937782355,408323575275,

%U 2434289046255,14598013278960,88011196469040,533216762488020,3245004785069892,19829769013792908

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

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

%C The number of nodes will be n + 1.

%H Andrew Howroyd, <a href="/A296533/b296533.txt">Table of n, a(n) for n = 0..200</a>

%H M. Noy, <a href="https://dx.doi.org/10.1016/S0012-365X(97)00121-0">Enumeration of noncrossing trees on a circle</a>, Discrete Math., 180, 301-313, 1998.

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

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

%e Case n=3:

%e o---o o---o o---o

%e | | \ \

%e o---o o o o---o

%e In total there are 3 distinct noncrossing trees up to rotation and reflection.

%t 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));

%t Table[a[n], {n, 0, 25}] (* _Jean-François Alcover_, Dec 27 2017, after _Andrew Howroyd_ *)

%o (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))}

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

%K nonn

%O 0,4

%A _Andrew Howroyd_, Dec 14 2017