cp's OEIS Frontend

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

%I A344852 #75 Aug 15 2023 18:53:16
%S A344852 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,
%T A344852 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,
%U A344852 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
%N A344852 Number of rooted binary trees with n leaves with minimal Symmetry Nodes Index (SNI) or, equivalently, with the maximal number of symmetry nodes.
%C A344852 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.
%C A344852 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.
%H A344852 Alois P. Heinz, <a href="/A344852/b344852.txt">Table of n, a(n) for n = 1..16383</a>
%H A344852 S. J. Kersting and M. Fischer, <a href="https://arxiv.org/abs/2105.00719">Measuring tree balance using symmetry nodes - a new balance index and its extremal properties</a>, arXiv:2105.00719 [q-bio.PE], 2021.
%F A344852 a(n) = (2*wt(n) - 3)!! = A001147(2*A000120(n) - 3).
%e A344852 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.
%e A344852 a(8)=1, because only the tree (((x,x),(x,x)),((x,x),(x,x))) is minimal: its SNI equals 0.
%p A344852 a:= n-> doublefactorial(2*add(i, i=convert(n, base, 2))-3):
%p A344852 seq(a(n), n=1..100); # _Georg Fischer_, Jun 15 2021
%t A344852 a[n_] := (2*DigitCount[n, 2, 1] - 3)!!; Table[a[n], {n, 1, 100}]
%o A344852 (PARI) a(n)={my(t=hammingweight(n)-1); (2*t)!/(2^t*t!)} \\ _Andrew Howroyd_, Jun 15 2021
%Y A344852 Cf. A000120, A001147.
%K A344852 nonn
%O A344852 1,7
%A A344852 _Mareike Fischer_, Jun 15 2021