7
\$\begingroup\$

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: Visualization of the first example 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):

Visualization for symmetry group of first example


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:

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

enter image description here


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 , so shortest code wins.
\$\endgroup\$
  • \$\begingroup\$ When you say two trees are isomorphic, you mean as rooted trees, right? \$\endgroup\$ – xnor Jun 7 '17 at 23:47
  • \$\begingroup\$ @xnor Yes. The isomorphic definition refers to rooted trees. \$\endgroup\$ – fireflame241 Jun 7 '17 at 23:48
3
\$\begingroup\$

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 cs, the number of children at the root.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.