CMIMC 2022 Team Problem 14

Let a tree on m n+1 vertices be (m, n)-nice if the following conditions hold:

  • m+1 colors are assigned to the nodes of the tree
  • for the first m colors, there will be exactly n nodes of color i(1 \leq i \leq m)
  • the root node of the tree will be the unique node of color m+1.
  • the (m, n)-nice trees must also satisfy the condition that for any two non-root nodes i, j, if the color of i equals the color of j, then the color of the parent of i equals the color of the parent of j.
  • Nodes of the same color are considered indistinguishable (swapping any two of them results in the same tree).

Let N(u, v, l) denote the number of (u, v)-nice trees with l leaves. Note that N(2,2,2)=2, N(2,2,3)= 4, N(2,2,4)=6. Compute the remainder when \sum_{l=123}^{789} N(8,101, l) is divided by 101.

Definition: Any rooted, ordered tree consists of some set of nodes, each of which has a (possibly empty) ordered list of children. Each node is the child of exactly one other node, with the exception of the root, which has no parent. There also cannot be any cycles of nodes which are all linearly children of each other.