Counting Unlabelled Subtrees of a Tree is #P-complete
Counting Unlabelled Subtrees of a Tree is #P-complete
Abstract The problem of counting unlabelled subtrees of a tree (that is, sub-trees that are distinct up to isomorphism) is #P-complete, and hence equivalent in computational difficulty to evaluating the permanent of a 0,1-matrix.