Number of caterpillars

Problem

You are given degree sequence $A$, determine the number of possible caterpillars.

We say that the graphs are different if they are not isomorphic.

Solution

Let us prove first prove the following fact: the degree sequence $A = (a_1,\ldots, a_n)$ can form a tree if and only if the sum of degree sequence is equal to $2\cdot (n - 1)$ and that $\forall i:\, a_i > 0$.

The only if direction is true by the definition of tree. Now for the if direction, let $x$ denote the number of leafs, then $$x + \text{degree sum of non-leafs} = 2 \cdot (n - 1).$$ Chain non-leafs together with $n - x - 1$ edges, which would mean that the number of available edges is $$\text{degree sum of non-leafs} - 2 \cdot (n - 1 - x) = x,$$ which in fact corresponds to the number of leafs, so all of the leafs can be fitted around this chain, forming a caterpillar tree.

Now knowing this, if in the sequence there exists $0$ or the sum of the sequence is not equal to the $2\cdot (n - 1)$, where $n$ is the length of the sequence, then the number of possible caterpillars would be $0$.

So, henceforth, assume that the previous conditions are met. Recall that the caterpillar is a tree in which all the vertices are within distance $1$ of the central path. This means that we simply need to find the number of non-isomorphic central paths, since all nodes that are not in the central path are simply leafs. This is actually equivalent to finding number of sequences $b_1,\ldots, b_m$, where $b_i$’s stand for non-one values from sequence $A$, where no two are semordnilapic. This is equal to number of all sequences plus number of palindromes, all divided by $2$, since division by $2$ removes duplicate semordnilapics and palindrome addition still keeps palindromes.

So let us denote number of $i$’s in $A$ as $c_i$, hence $m = n - c_1$. To find the number of all different sequences $b_1,\ldots, b_m$, then by permutations, the result is $$N = \frac{m!}{\prod_{i=2} c_i!} = \frac{(n - c_1)!}{\prod_{i=2}c_i!}.$$

Now, to find the number of palindromic sequences $b_1,\ldots,b_m$, first of all, if $C$ denotes the number of $c_i$’s ($i > 1$), which are odd,

• then for all $C>1$, there are no palindromic sequences, i.e. $P=0$.
• If $C=1$ and $m$ is even, there are no palindromic sequences, again $P=0$.
• If $C=0$ and $m$ is odd, we again have $P=0$.
• For $C=1$ and $m$ odd or $C=0$ and $m$ even, by permutations, the result is $$P = \frac{\lfloor\tfrac{m}{2}\rfloor!}{\prod_{i=2}\lfloor\tfrac{c_i}{2}\rfloor!}= \frac{\lfloor\tfrac{n-c_1}{2}\rfloor!}{\prod_{i=2}\lfloor\tfrac{c_i}{2}\rfloor!}$$

Thus, the answer is $\frac{N+P}{2}$.

Here is the implementation for Python:

import math

def nr_of_caterpillars(A):
    V = len(A)
    if sum(A) != 2 * (V - 1):
        print("This cannot be a tree.")
        return 0

    freq = [0] * V
    for i in range(V):
        freq[A[i]] += 1
    
    if freq[0] > 0:
        print("This cannot be a tree.")
        return 0

    seq = V - freq[1]
    odds = len(list(filter(lambda x: x % 2 == 1, freq[2:]))) 
    c = math.factorial(seq)
    d = 0
    if odds == 1 and seq % 2 == 1 or odds == 0 and seq % 2 == 0:
        d = math.factorial(math.floor(seq / 2))
    for i in range(2,V):
        c = c / math.factorial(freq[i])
        d = d / math.factorial(math.floor(freq[i] / 2))

    return (int)((c + d) / 2)