|
|
A296532
|
|
Number of nonequivalent noncrossing trees with n edges up to rotation.
|
|
4
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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.
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.
|
|
LINKS
|
|
|
FORMULA
|
|
|
EXAMPLE
|
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.
|
|
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))];
|
|
PROG
|
(PARI) a(n)={(binomial(3*n, n)/(2*n+1) + if(n%2, binomial((3*n-1)/2, (n-1)/2)))/(n+1)}
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|