|
| |
|
|
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, 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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
|
|
|
FORMULA
|
|
|
|
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):
|
|
|
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
|
|
|
|
STATUS
|
approved
|
| |
|
|
