Algorithm: How to find the number of independent sets in a tree?

I'm thinking that there are two cases for each sub-tree: the root is in the independent set and the root is not in the set. How to write a recursive algorithm for finding the number of independent sets in a tree? The tree is n-ary.

https://en.wikipedia.org/wiki/Independent_set_(graph_theory)

This is my solution so far, but it isn't correct. The variable parentIncluded is equal to true if the parent of the current subtree is already included in the independent set, thus the root of the current subtree can't be added to the independent set. If parentIncluded is equal to false, then the root of the current subtree can be added to the independent set. There are two cases for when parentIncluded is false. The first case: Add the root to the set. Second case: don't add the root.

public static int numberOfIndependentSets(Binary root) {
        if (root == null) {
            return 1;
        }
        return numberOfIndependentSets(root, false) + 1;
    }

    private static int numberOfIndependentSets(Binary current, boolean parentIncluded) {
        if (current.left == null && current.right == null) {
            if (parentIncluded) {
                return 0;
            } else {
                return 1;
            }
        }
        int total = 0;
        if (parentIncluded) {
            int left = numberOfIndependentSets(current.left, false);
            int right = numberOfIndependentSets(current.right, false);
           total += (left + 1) * (right + 1) - 1;
        } else {
            // include current node
            int left = numberOfIndependentSets(current.left, true);
            int right = numberOfIndependentSets(current.right, true);
            total = (left+1) *( right +1);

            // not include current node
            left = numberOfIndependentSets(current.left, false);
            right = numberOfIndependentSets(current.right, false);
            total += (left+1) * (right+1) -1;
        }
        return total;
    }

Your basic idea should work.

You could defined two mutually recursive functions on the set of rooted trees:

f(T) = number of independent sets containing the root
g(T) = number of independent sets not containing the root

You want to compute f(T) + g(T)

For 1-node trees, L, as basis cases we have:

f(L) = 1
g(L) = 1

Say that T_1, T_2, .. T_n are the subtrees of the root. Then the recursive equations are:

f(T) = g(T_1)*g(T_2)* ... *g(T_n)
g(T) = (f(T_1)+g(T_1))*(f(T_2)+g(T_2)) * ... * (f(T_n)+g(T_n))

As a check: you can use this to get the number of independent sets of full binary trees with n levels (equivalently, height n-1). Make the f, g a function of level. A Python implementation:

def f(n):
    if n == 1:
        return 1
    else:
        return (g(n-1))**2

def g(n):
    if n == 1:
        return 1
    else:
        return (f(n-1) + g(n-1))**2

def h(n): return f(n)+g(n)

[h(n) for n in range(1,7)] evaluates to

2, 5, 41, 2306, 8143397, 94592167328105

This is sequence A076725 in the Online Encyclopedia (slightly shifted) which is described as "the number of independent sets on a complete binary tree with 2^(n-1)-1 nodes", so it seems that this approach makes sense.