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.


$()$ 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.


$(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



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.