OFFSET
1,7
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.
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.
EXAMPLE
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.
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}]
PROG
(PARI) a(n)={my(t=hammingweight(n)-1); (2*t)!/(2^t*t!)} \\ Andrew Howroyd, Jun 15 2021
CROSSREFS
KEYWORD
nonn
AUTHOR
Mareike Fischer, Jun 15 2021
STATUS
approved