|
| |
|
|
A335833
|
|
Triangle read by rows. T(n,k) is the number of full binary trees with n leaves and with k internal nodes whose left and right children have the same number of leaf descendants, where n > 0 and 0 <= k < n.
|
|
2
|
|
|
|
1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 2, 2, 1, 0, 0, 1, 4, 3, 3, 0, 0, 0, 1, 6, 7, 6, 3, 0, 1, 0, 1, 9, 14, 13, 8, 1, 1, 0, 0, 1, 12, 27, 28, 23, 8, 3, 1, 0, 0, 1, 16, 49, 58, 54, 25, 8, 3, 0, 0, 0, 1, 20, 82, 119, 125, 82, 34, 15, 2, 1, 0
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,18
|
|
|
COMMENTS
|
Consider a full binary tree with n unlabeled leaves, such that for every internal node, the number of leaf descendants of the left child is greater than or equal to the number of leaf descendants of the right child. Two such trees are considered isomorphic if one may be obtained from the other by some series of transpositions of left and right children. Label an internal nodes S if its two children have the same number of leaf descendants, and D if its two children have a different number of leaf descendants, and call this an SD-tree. T(n,k) is then the number of distinct trees having n > 0 leaves and 0 <= k < n S-nodes, read by rows (Monroe et al., proposition 38).
Binary operations that are commutative and non-associative map to this type of tree. One example of this kind of operation is floating-point summation on n summands on a machine adhering to IEEE 754 arithmetic standards. Another example is a single-elimination tournament on n teams (A096351), which always has A268289(n-1) S-nodes.
Column 1 gives A000012 (Monroe et al., proposition 11 and remark 42).
Column 2 gives A002620 (Monroe et al., proposition 18).
Row sums give A000992 (Monroe et al., proposition 36 and remark 42).
T(n,n-1) is 1 if n = 2^k and is 0 otherwise. This is true because there are exactly n-1 internal nodes on a binary tree with n leaves, and the only way for all of these to be S-nodes is if the tree is the unique perfect tree with 2^k leaves.
T(n,1) is the first non-0 entry in row n, when n>1. T(n,A011371(n)) is the last non-0 entry in row n. (Monroe et al., propositions 27 and 34)
The number of unique leaf-labeled full binary trees of isomorphic parenthetic form with exactly k >= 1 S-nodes is n!/(2^k) (Monroe et al., corollary 4). There are then T(n,k)*n!/(2^k) not necessarily isomorphic unique leaf-labeled full binary trees having exactly k nodes. For example, serial summation, where the parenthesization is in summand order, as in (...(((a+b)+c)+d)+...), always has exactly 1 S-node, so there are n!/2 possible serial summations (Monroe et al., lemmas 8 and 9, corollary 10, and proposition 11).
The comments above that suggest that this sequence enumerates binary trees up to transpositions of left and right children appear to be incorrect. This sequence rather enumerates those trees as specified in the opening paragraph: for every internal node, the number of leaf descendants of the left child is greater than or equal to the number of leaf descendants of the right child. This is the difference between A000992 which is the row sums of this sequence and A001190. The two diverge for n >= 8. The remark that commutative binary operations map to this type of tree is, therefore, also incorrect. - Andrew Howroyd, Mar 25 2023
|
|
|
LINKS
|
|
|
|
FORMULA
|
T(n,k) = 0, if k >= n. T(n,k) = 1, if n = 1 and k = 0.
T(n,k) = Sum_{j=1..floor((n-1)/2)} Sum_{i=0..k} T(j,i)*T(n-j,k-i), if n is odd and > 1.
T(n,k) = Sum_{j=1..floor((n-1)/2)} Sum_{i=0..k} T(j,i)*T(n-j,k-i) + Sum_{i=0..k-1} T(n/2,i)*T(n/2,k-1-i), if n is even.
|
|
|
EXAMPLE
|
The table for T(n,k) begins:
n\k 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1 1
2 0 1
3 0 1 0
4 0 1 0 1
5 0 1 1 1 0
6 0 1 2 2 1 0
7 0 1 4 3 3 0 0
8 0 1 6 7 6 3 0 1
9 0 1 9 14 13 8 1 1 0
10 0 1 12 27 28 23 8 3 1 0
11 0 1 16 49 58 54 25 8 3 0 0
12 0 1 20 82 119 125 82 34 15 2 1 0
13 0 1 25 132 237 270 213 99 42 8 3 0 0
14 0 1 30 199 449 578 542 322 151 51 11 3 0 0
15 0 1 36 294 821 1190 1255 867 440 173 39 15 0 0 0
16 0 1 42 414 1419 2394 2841 2338 1388 656 215 79 18 7 0 1
...
The complete set of non-isomorphic 4-leaf SD-trees is:
D S
/ \ / \
D * S S
/ \ /| |\
S * * * * *
/ \
* *
T(6,2) = 2 gives the first example of a set of parameters n and k that has more than one non-isomorphic SD-tree. The complete set of non-isomorphic 6-leaf 2-S-node SD-trees is:
D D
/ \ / \
D S D *
/ \ |\ / \
D * * * D S
/ \ / \ |\
S * S * * *
/ \ / \
* * * *
When n = 8 there are two trees, illustrated below, which are isomorphic (up to exchange of left and right children), but are counted separately by this sequence:
S S
/ \ / \
D S S D
/ | | \ / | | \
D * S S S S D *
/ \ /| |\ /| |\ | \
S * * * * * * * * * S *
/ \ / \
* * * *
(End)
|
|
|
PROG
|
(C++)
long long T_memo(int n, int k, int numk)
{
static std::map<int, long long> memo;
int offset = (n*(n-1))>>1;
if ((k>(n-1)) || (k<0)) return 0;
else if ((n==1) && (k==0)) return 1;
else if(memo.count(offset+k)>0) return memo[offset+k];
else
{
long long t=0;
int ndiv2 = n>>1;
for (int i=1; i<ndiv2; i++)
for (int j=0; j<=k; j++)
t += T_memo(i, j, numk)*T_memo(n-i, k-j, numk);
if (n&1)
for (int j=0; j<=k; j++)
t += T_memo(ndiv2, j, numk)*T_memo(ndiv2+1, k-j, numk);
else
for (int j=0; j<=k; j++)
t += T_memo(ndiv2, j, numk)*T_memo(ndiv2, k-j-1, numk);
memo[offset+k] = t;
return t;
}
}
(Julia)
using Memoize
@memoize function T(n, k)
k > n-1 && return 0
(n==1) && (k==0) && return 1
t, h = 0, n>>1
for j in 1:h-1, i in 0:k
t += T(j, i)*T(n-j, k-i)
end
if n&1 > 0
for i in 0:k
t += T(h, i)*T(h+1, k-i)
end
else
for i in 0:k
t += T(h, i)*T(h, k-i-1)
end
end
t
end
for n in 1:16
[T(n, k) for k in 0:n-1] |> println
(PARI)
T(n)={my(v=vector(n)); v[1] = 1; for(n=2, n, v[n] = (polcoef(Ser(v[1..n])^2, n-2) + if(n%2==0, (2*y-1)*v[n/2]^2))/2); vector(#v, n, Vecrev(v[n], n))}
{ my(A=T(12)); for(n=1, #A, print(A[n])) } \\ Andrew Howroyd, Mar 25 2023
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
