# Combinatorics, 2-Tree, Sequence

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