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,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.

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

Links

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

Formula

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

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))];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Dec 27 2017, after Andrew Howroyd *)

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

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

Sequence in context: A149311 A212086 A361359 * A149312 A149313 A149314

Adjacent sequences: A296529 A296530 A296531 * A296533 A296534 A296535

Keyword

nonn

Author

Andrew Howroyd, Dec 14 2017

Status

approved