Counting all permutations of a string (Cracking the Coding Interview, Chapter VI - Example 12)

In Gayle Laakman's book "Cracking the Coding Interview", chapter VI (Big O), example 12, the problem states that given the following Java code for computing a string's permutations, it is required to compute the code's complexity

public static void permutation(String str) {
    permutation(str, "");
}

public static void permutation(String str, String prefix) {
    if (str.length() == 0) {
        System.out.println(prefix);
    } else {
        for (int i = 0; i < str.length(); i++) {
            String rem = str.substring(0, i) + str.substring(i + 1);
            permutation(rem, prefix + str.charAt(i));
        }
    }
}

The book assumes that since there will be n! permutations, if we consider each of the permutations to be a leaf in the call tree, where each of the leaves is attached to a path of length n, then there will be no more that n*n! nodes in the tree (i.e.: the number of calls is no more than n*n!).

But shouldn't the number of nodes be:

since the number of calls is equivalent to the number of nodes (take a look at the figure in the video Permutations Of String | Code Tutorial by Quinston Pimenta).

If we follow this method, the number of nodes will be 1 (for the first level/root of the tree) + 3 (for the second level) + 3*2 (for the third level) + 3*2*1 (for the fourth/bottom level)

i.e.: the number of nodes = 3!/3! + 3!/2! + 3!/1! + 3!/0! = 16

However, according to the aforementioned method, the number of nodes will be 3*3! = 18

Shouldn't we count shared nodes in the tree as one node, since they express one function call?