cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

User: Laura Monroe

Laura Monroe's wiki page.

Laura Monroe has authored 1 sequences.

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.

Original entry on oeis.org

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
Offset: 1

Views

Author

Laura Monroe, Jun 25 2020

Keywords

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

Examples

			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   * * *
   / \               / \
  *   *             *   *
From _Andrew Howroyd_, Apr 12 2023: (Start)
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)

Links

Crossrefs

Cf. A000012, A000992, A002620, A011371, A096351, A268289.

Programs

  • 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
end # Peter Luschny, Jun 26 2020
  • 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

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.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.