show/hide this revision's text 4 added 2 characters in body

I think it just depends on how you want to use it. I will claim that sometimes the empty graph is best considered a tree and even a rooted tree but other times, neither. Even the one vertex tree is a little odd, it is the only tree with a degree zero vertex.

The Catalan numbers count many kinds of trees. In an Ordered Binary Tree each node may have up to two children left and/or right. If we let $C_n$ be the number of such with $n$ nodes then could exclude the empty tree and say

  • $C_1=1$

  • $C_{n+1}=C_n+C_n+\sum_i=1^{n-1}C_iC_{n-i}$ C_{n+1}=C_n+C_n+\sum_{i=1}^{n-1}C_iC_{n-i}$

The first two terms for the case of only one child. But it is nicer to think of the left and right children as being themselves binary trees, both present, but perhaps one or both the empty tree.

  • $C_0=1$

  • $C_{n+1}=\sum_0^nC_iC_{n-i}$.

I think that the second approach is nicer. Particularly for the analogous situation with trinary trees.

A Full Ordered Binary Tree is as above except that a node may have either $0$ or $2$ children (thought of as nodes). There is a natural bijection between OBTs (including the empty tree) having $n$ nodes and FOBTs (not including the empty tree) having $n+1$ leaf nodes. In one direction assign each leaf node two children and in the other remove all the leaf nodes.

So here we interpret $C_n$ as the number of FOBTs with $n+1$ leaf nodes and do not bother to consider the empty tree as a FOBT.

Given a non-associative product, an expression $x_1\cdot x_2 \cdot x_k$ needs parentheses to be evaluated. We can use a FOBT with $k-1$ non-leaf nodes corresponding to the multiplications and $k$ leaves corresponding to the variables. Then $C_0$ counts the one vertex tree from the "product" $x_1.$ Now there seems no reason to count the empty tree. Of course we do like the empty product, but that is not especially relevant.

If we want to have a definition of rooted tree which does not specifically mention "the root" then we can say that a rooted tree is precisely a finite partial order $(S,\prec)$ such that

  1. for all $u \in S$ the set $\{x \mid x \preceq u\}$ is totally ordered by $\prec$
  2. for all $u,v \in S$ there is a common lower bound.

If we can get away with that, then the empty order is an order.

show/hide this revision's text 3 added 218 characters in body

I don't see a whole bunch of think it just depends on how you want to use for it. However if I will claim that sometimes the empty graph is best considered a connected graph tree and every connected graph has even a spanning rooted tree then..but other times, neither.

It all depends what you want Even the one vertex tree is a little odd, it is the only tree with a degree zero vertex.

The Catalan numbers count many kinds of trees. In an Ordered Binary Tree each node may have up to do two children left and/or right. If we let $C_n$ be the number of such with $n$ nodes then could exclude the empty tree and say

  • $C_1=1$

  • $C_{n+1}=C_n+C_n+\sum_i=1^{n-1}C_iC_{n-i}$

    • The first two terms for the case of only one child. But it is nicer to think of the left and right children as being themselves binary trees, both present, but perhaps one or both the empty tree.

  • $C_0=1$

  • $C_{n+1}=\sum_0^nC_iC_{n-i}$.

    • I think that the second approach is nicer. Particularly for the analogous situation with trinary trees.

    A Full Ordered Binary Tree is as above except that a node may have either $0$ or $2$ children (thought of generating functionsas nodes). The first article in There is a Google search says "It will turn out to work better if we natural bijection between OBTs (including the empty tree) having $n$ nodes and FOBTs (not including the empty tree) having $n+1$ leaf nodes. .. In one direction assign each leaf node two children and in the other remove all the leaf nodes.

    So here we interpret $C_n$ as the number of FOBTs with $n+1$ leaf nodes and do not count bother to consider the empty tree as a rooted tree." So that indicates that "who knowsFOBT.

    Given a non-associative product, it could have been better an expression $x_1\cdot x_2 \cdot x_k$ needs parentheses to be evaluated. We can use a FOBT with $k-1$ non-leaf nodes corresponding to the other way but it isn't.multiplications and $k$ leaves corresponding to the variables. Then $C_0$ counts the one vertex tree from the "It also product" $x_1.$ Now there seems no reason to say "it is a count the empty tree. Of course we do like the empty product, but that is not especially relevant.

    If we want to have a definition of rooted one." Then again, the author tree which does not need to take a position since rooted trees are what is needed.

    Would it be so perverse to specifically mention "the root" then we can say that a rooted tree is precisely a finite partial order $(S,\prec)$ such that

    If we can get away with that, then the empty order is an order...

    For the purposes of this question let me stipulate a structure called an Rooted Oriented Trinary Tree (a ROTT.) This is simply a rooted tree such that each node may have a left, and/or middle, and/or right child. So, it might have only a middle and a right child.

    It might be convenient to inductively define

  • The empty graph is a ROTT
  • any ordered tripple $[T_{\ell},T_m,T_r]$ of ROTTs is a ROTT
  • That is all ROTTs

    • Sure you could avoid it, but in that case It will turn out to work better if we "count the empty tree as a rooted tree."

    I can't remember the venerable book I first learned the theory of convex sets from, but I recall that the introduction said something like "to save ink we will not mention the word "nonempty" in the statement of theorems." The point being that we want the intersection of convex sets to be convex and there is an operation which sends $A,B$ to the convex hull of their union and the empty set is the identity for this operation. But we ignore it when it suits usorder.

    show/hide this revision's text 2 added 1271 characters in body; added 34 characters in body

    I guess one can always

    Would it be so perverse to say "non-empty" trees that a rooted tree is precisely a finite partial order $(S,\prec)$ such that

  • for all $u \in S$ the set $\{x \mid x \preceq u\}$ is totally ordered by $\prec$
  • for all $u,v \in S$ there is a common lower bound.

    • If we can get away with that then the empty order is an order...

    For the purposes of this question let me stipulate a structure called an Rooted Oriented Trinary Tree (a ROTT.) This is simply a rooted tree such that each node may have a left, and/or middle, and/or right child. So, it might have only a middle and a right child.

    It might be convenient to inductively define

  • The empty graph is a ROTT
  • any ordered tripple $[T_{\ell},T_m,T_r]$ of ROTTs is a ROTT
  • That is all ROTTs

    • Sure you could avoid it, but in that case It will turn out to work better if neededwe "count the empty tree as a rooted tree."

    I can't remember the venerable book I first learned the theory of convex sets from, but I recall that the introduction said something like "to save ink we will not mention the word "nonempty" in the statement of theorems." The point being that we want the intersection of convex sets to be convex and there is an operation which sends $A,B$ to the convex hull of their union and the empty set is the identity for this operation. But we ignore it when it suits us.
    show/hide this revision's text 1