Math Quiz N. 14 - Counting trees

CONTING TREES

This quiz is about counting trees in certain classes of graphs. Some (maybe all) of these results can be found in the web. Nevertheless it is fun to discover them.

We consider the following classes of graphs:

W(N): the wheel with N spokes, composed of a circle with N vertices and N edges, and a central vertex joined to the N vertices on the circle by N edges
F(N): the fan with N edges, composed of a path of N edges and N+1 vertices, a central vertex, w, and the N+1 edges joining the vertices on the path to w.
L(N): the ladder of length N, composed 2*(N+1) vertices, u₀, ..., u_N, v₀, ..., v_N, and edges e_k=u_kv_k (for k=0,...,N), d_k=u_k-1u_k (for k=1,...,N), and f_k=v_k-1v_k (for k=1,...,N).
X(N): the X-cross of L(N), obtained by adding to L(N) one vertexw, and four edges: u₀w, v_Nw, v₀w, and u_Nw.
Y(N): the Y-cross of L(N), obtained by adding a vertex w and three edges: u₀w, v_Nw, and v₀w.
Z(N), the Z-cross of L(N), optained by adding the edge u₀v_N.
C(N), the C-cross of L(N), obtained by adding the edge u₀v₀.
A(N), the annulus, obtained from L(N) by adding the two edges u₀v₀ u_Nv_N.

                 N    0    1 
   L(N)      ----o    o----o----
         ...     |    |    |    ...
             ----o    o----0----

   X(N)      ----o. , o----o----
         ...     | o  |    |    ...
             ----o' ` o----0----

   Y(N)      ----o. , o----o----
         ...     | o  |    |    ...
             ----o'   o----0----

   Z(N)      ----o  , o----o----
         ...     | /  |    |    ...
             ----o'   o----0----

   C(N)      ----o----o----o----
         ...     |    |    |    ...
             ----o    o----0----

   A(N)      ----o----o----o----
         ...     |    |    |    ...
             ----o----o----0----

Recall that a tree T in a graph G is a connected subgraph with the same vertices as G, and with no cycle. The problem is to count the number of trees in these graphs. I use the graph symbol to denote the number of trees of a graph, as no confusion should arise.

These relations (with a complete proof) can be found in internet:

L(N) = 4 L(N-1) - L(N-2)
F(N) = 3 F(N-1) - F(N-2), which has solution F(N)=Fibinacci(2N)
W(N) = W(N-1) + F(N) + F(N-1), which has solution W(N) = Lucas(2N) - 2

Prove these other relations relating the number of trees of these graphs,

Z(N) = L(N) + Z(N-1) + X(N-2) + Y(N-2)
C(N) = L(N) + C(N-1) + X(N-2) + Y(N-2)
Y(N) = L(N) + Y(N-1) + Z(N) + C(N)
X(N) = Y(N) + 2 X(N-1) + Y(N-1)
A(N) = A(N-1) + C(N-2) + 2 X(N-3) + Y(N-3)

These form a set of recursion relations that can be solved, starting with the initial values

L(0)=1, L(1)=4
Z(0)=2, Z(1)=8
C(0)=1, C(1)=7
Y(0)=5, Y(1)=24
X(0)=11, X(1)=45
A(0)=1, A(1)=12

    L    C    Z    Y     X    A    W    F
1   1    1    2    5     8    1    1    3
2   4    7    8   24    45   12    5    8
3  15   35   36  110   224   74   16   21
4  56  160  161  487  1045  102   45   55
5 209  703  704 2103  4680  251  121  144
6 780 3015 3016 8914 20377  969  320  377

Notice that Z(N)=C(N)+1. This is clear from the recursion relations. Can you show from the graphs which is the extra tree in Z(N) that is not in C(N) ?

Another problem: what about the number of forests?

Marco Corvi - 2011