1
$\begingroup$

I've just thought about a combinatoric problem.

Say you have a tree with $n$ nodes at the $n$-th level ($2$-tree). Number elements based on their position left to right, top to bottom. Let $a_{n,i}$ be the value of the node at position $i$ at the $n$-th level.

To attribute value to node $(n,i)$ represent it instead by the $(n-1)$-digit number with $i-1\quad$ $1$'s.

Example:

$()$ is the only node on first level

$(0)$ is the first node on the second level. $(1)$ is the second

$(000)$ first node on 4th level.

$(100)=(010)=(001)$ are all representing the second node on the fourth level.

Now attribute at each node the sum of the values of its representation. Each representation gets assigned a value based on the following rule: If a representation has $k$ $1$'s then its value is $(x_1x_2x_3..x_k)^2$ where the index represents the position of such $1$'s.

Example:

$(100)=(010)=(001)$ has $a_{4,2}=1+4+9=14$

$(110)=(101)=(001)$ has $a_{4,3}=4+9+4*9=49$

I would like to know a formula for $a_{n,i}$!

I believe you can formulate this as a recurrence like

$a_{n,i}=a_{n-1,i-1}+(i-1)^2 a_{n-1,i}$

but im not sure

$\endgroup$

0

Your Answer

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

Browse other questions tagged or ask your own question.