A344852 Number of rooted binary trees with n leaves with minimal Symmetry Nodes Index (SNI) or, equivalently, with the maximal number of symmetry nodes.

1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 3, 1, 3, 3, 15, 1, 1, 1, 3, 1, 3, 3, 15, 1, 3, 3, 15, 3, 15, 15, 105, 1, 1, 1, 3, 1, 3, 3, 15, 1, 3, 3, 15, 3, 15, 15, 105, 1, 3, 3, 15, 3, 15, 15, 105, 3, 15, 15, 105, 15, 105, 105, 945, 1, 1, 1, 3, 1, 3, 3, 15, 1, 3, 3, 15, 3, 15, 15, 105, 1, 3, 3, 15, 3, 15, 15, 105, 3, 15, 15, 105, 15, 105, 105, 945, 1

Offset: 1

Author

Mareike Fischer, Jun 15 2021

Keywords

• nonn

Comments

In a rooted binary tree, each internal node has precisely two children. An internal node is called a symmetry node if the subtrees of its two children are isomorphic. The Symmetry Nodes Index SNI, however, counts the internal nodes which are not symmetry nodes. The minimal SNI of a rooted binary tree with n leaves is wt(n)-1, where wt(n) = A000120(n) denotes the binary weight of n, i.e., it refers to the number of 1's in the binary expansion of n.

a(n) is also the number of trees with n leaves and minimal Rogers's J tree balance index, which is the number of internal nodes which are not balanced, i.e., the number of nodes whose left and right subtrees do not have the same number of leaves.

Examples

			a(7)=2, because both trees (((x,x),(x,x)),((x,x),x)) and (((x,x),(x,x),x),(x,x)) have four inner nodes which are symmetry nodes and only two inner nodes which are non-symmetry nodes. So the SNI of both trees equals 2, which is minimal for n=7.
a(8)=1, because only the tree (((x,x),(x,x)),((x,x),(x,x))) is minimal: its SNI equals 0.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..16383
• S. J. Kersting and M. Fischer, Measuring tree balance using symmetry nodes - a new balance index and its extremal properties, arXiv:2105.00719 [q-bio.PE], 2021.

Crossrefs

Cf. A000120, A001147.

Programs

Maple

a:= n-> doublefactorial(2*add(i, i=convert(n, base, 2))-3):
seq(a(n), n=1..100); # Georg Fischer, Jun 15 2021

Mathematica

a[n_] := (2*DigitCount[n, 2, 1] - 3)!!; Table[a[n], {n, 1, 100}]

PARI

a(n)={my(t=hammingweight(n)-1); (2*t)!/(2^t*t!)} \\ Andrew Howroyd, Jun 15 2021

Formula

a(n) = (2*wt(n) - 3)!! = A001147(2*A000120(n) - 3).