2016 UNCO Math Contest II Problems/Problem 8

Problem

Tree


Each circle in this tree diagram is to be assigned a value, chosen from a set $S$, in such a way that along every pathway down the tree, the assigned values never increase. That is, $A \ge B, B \ge C, C \ge D, D \ge E$, and $A, B, C, D, E \in S$. (It is permissible for a value in $S$ to appear more than once.)

(a) How many ways can the tree be so numbered, using only values chosen from the set $S = \{1, . . . , 6\}$?

(b) Generalize to the case in which $S = \{1, . . . , n\}$. Find a formula for the number of ways the tree can be numbered.

For maximal credit, express your answer in closed form as an explicit algebraic expression in $n$.

Solution

a)$994$ b) $\frac{1}{120}n(n + 1)(n + 2)(8n^22 + 11n + 1)$

See also

2016 UNCO Math Contest II (ProblemsAnswer KeyResources)
Preceded by
Problem 7
Followed by
Problem 9
1 2 3 4 5 6 7 8 9 10
All UNCO Math Contest Problems and Solutions