Rooting for Trees With the Right Nodes

Question

Background

A rooted tree is an acyclic graph such that there is exactly one path from one node, called the root, to each other node. A node v is called the parent of another node u if and only if the path from the root to u goes through v and there is an edge connecting u and v. If node v is the parent of node u, node u is a child of node v.

Task

Write a program or function that, given a positive integer number of nodes and a set of non-negative integer numbers of children each parent has, outputs the number of possible rooted trees with that number of nodes (including the root) and each vertex having a number of children in the set, not counting those trees isomorphic to trees already found.

Two trees are isomorphic if one can be transformed into another by renaming the nodes, or in other words look the same when the nodes are unlabelled.

Examples

We shall represent trees as a 0-indexed list of children per index where 0 represents the root, for example [[1],[2],[]] represents that the root 0 has 1 as a child, node 1 has node 2 as a child, and node 2 has no children.

Inputs n=3 and set = [0,1,2]. This is equal to binary trees with three nodes. The two possible trees are: [[1],[2],[]] and [[1,2],[],[]]. Because they are identical in structure to the two trees, we count neither [[2],[],[1]] nor [[2,1],[],[]]. There are two trees, so the output is 2 or equivalent.

Here is a visualization: You can see that the second set of two trees are identical in structure to the first set of two and are thus not counted. Both sets are composed of two trees which have one of the following two structures (the root is the node at the top):

---

Inputs n=5 and set=[0,2]. The only possible tree is [[1,2],[3,4],[],[],[]]. Note that, for example, [[1,2],[],[3,4],[],[]] and [[1,3],[],[],[2,4],[]] are not counted again because they are isomorphic to the sole tree which is counted. The output is 1 or equivalent.

Here is another visualization:

Clearly, all of the trees are isomorphic, so only one is counted. Here is what the trees look like unlabeled:

---

Input n=4, set=[0,2]. There are no possible trees because each time children are generated from a node, there are either 0 or 2 more nodes. Clearly, 4 nodes cannot be produced by adding 2 or 0 successively to 1 node, the root. Output: 0 or falsey.

Input/Output

Input and output should be taken in a reasonable format.

Input is a positive integer representing n and a list of non-negative integers representing the set of valid numbers of children.

The output is a non-negative integer corresponding to how many trees can be formed.

Test cases

n ; set ; output
3 ; [0,1,2] ; 2
5 ; [0,2] ; 1
4 ; [0,2] ; 0
3 ; [0,1] ; 1
3 ; [0] ; 0
1 ; [0] ; 1
6 ; [0,2,3] ; 2
7 ; [0,2,3] ; 3

Rules

• The set of numbers of children will always include zero.
• The root node always counts as a node, even if it has no children (see the 1; [0] test case)
• This is code-golf, so shortest code wins.

Answer 1

Haskell, 120 bytes

_#0=1
i#j=div(i#(j-1)*(i+j-1))j
s!n|let(0?1)0=1;(0?_)_=0;(m?n)c=sum[s!m#j*((m-1)?(n-j*m)$c-j)|j<-[0..c]]=sum$(n-1)?n<$>s

Try it online!

How it works

i#j is i multichoose j.

(m?n)c is the number of n-node trees with c children at the root, each of which has a subtree of at most m nodes. It’s computed by summation over j, the number of these subtrees that have exactly m nodes.

s!n is the number of n-node trees. It’s computed by summation over c ∈ s, the number of children at the root.

Answer 2

Pyth, 47 bytes

.N?Nsm*/.P+tyNdd.!d:tN-T*dN-YdhY!|tTYLs:LtbbQyE

Try it online

A port of my Haskell answer, but it’s much faster in Pyth thanks to Pyth’s free automatic memoization. I had to work around a bug in Pyth’s binomial coefficient builtin, though.

Answer 3

Python, 127 bytes

lambda*x:len(g(*x))
g=lambda n,s,d=0:[[]][n-1:d in s]or[[t]+u for c in range(1,n)for t in g(c,s)for u in g(n-c,s,d+1)if[t]+u>u]

Try it online!

The function g enumerates trees, and the main function counts them.

Each tree is recursively generated by splitting the requiring number of nodes n between c nodes in the first branch t, and n-c nodes in the remaining tree u. For a canonical form up to isomorphism, we require the branches to be sorted in decreasing order, so t must be at most the first element of u is u is non-empty. This is enforced as [t]+u>u.

We count the number of children d so far of the current node. When only one node n=1 is left, is must be the current node and there's no more node for children. If the current number of children d is valid, this level can be finished successfully, so we output a singleton of the one-node tree. Otherwise, we've failed and output the empty list.