login
A296533
Number of nonequivalent noncrossing trees with n edges up to rotation and reflection.
4
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
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
KEYWORD
nonn
AUTHOR
Andrew Howroyd, Dec 14 2017
STATUS
approved