Algebraic tree-based problem

Question

Mathematics!

I have encountered a one problem that is being solved by using an algebraic (I guess?) tree with a following structure:

_ _ _ _ 16 _ _ _ _

_ _ _ 8 _ 8 _ _ _

_ _ 4 _ 4 _ 4 _ _

_ 2 _ 2 _ 2 _ 2 _

1 _ 1 _ 1 _ 1 _ 1

In this example we use a tree with a height h = 5 and as you can notice the bounds of this tree are the powers of 2 from 0 to h-1.

The problem states the following: there is a magic stone at the origin of the number line (x = 0) with a mass of 2^n (n is an arbitrary number). Each second the stone with m > 1 (hereinafter m = mass of the stone) decomposes into 2 stones with a mass of m / 2 each at locations x-1 and x+1 (the stone that has just decomposed disappears). We have to find the number of stones on each coordinate at the bottom line (when a mass of each stone will be equal to 1).

So if we reformat the previous tree we will get the following:

n(m) = a number(n) of rocks with a mass(m) at a particular coordinate

_ _ _ _ 1(16) _ _ _ _

_ _ _ 1(8) _ 1(8) _ _ _

_ _ 1(4) _ 2(4) _ 1(4) _ _

_ 1(2) _ 3(2) _ 3(2) _ 1(2) _

1(1) _ 4(1) _ 6(1) _ 4(1) _ 1(1)

And for n = 4 the answer will be {1, 0, 4, 0, 6, 0, 4, 0, 1} where 0 is an empty coordinate.

How can we find the number of stones on each coordinate at the bottom line? What will be a solution via this tree structure or probably you could suggest other more efficient approaches? And a kind of off-topic question: what is the name of the tree with a such structure as in the first example?

Answer 1

This tree is essentially Pascal's triangle.

To find the number of stones on each coordinate at the bottom line, simply consider the values at the $n$th row of Pascal's triangle.

Note that

The entry in the $n$th row and $t$th column of Pascal's triangle is denoted $n \choose t$.

It follows that for a magic stone of mass $2^n$, the number of stones at the $k$th coordinate of the bottom line is $${n \choose \frac{n+k}{2}} = \frac{n!}{\left(\frac{n+k}{2}\right)!\cdot\left(\frac{n-k}{2}\right)!} \; \text{if} \; \frac{n+k}{2} \in \mathbb{Z}$$ $$\; 0 \; \text{if} \; \frac{n+k}{2} \notin \mathbb{Z}$$

To prove this, we need to map the coordinate $k$ to column $t$ i.e. we need, for example, $-4 \rightarrow0, -2 \rightarrow1, 0 \rightarrow 3, ... 4 \rightarrow 5$

First, consider the inverse mapping $0 \rightarrow -4, 1 \rightarrow-2, ..., 5 \rightarrow 4$. This is a simple arithmetic progression with difference $2$ and the initial value as $-n$ with $n = 4$ in this case. This arithmetic progression can be modelled by the equation $-n + 2t$. We can then solve for $t$ in $k = -n + 2t$ to get $t = \frac{n+k}{2}$. We can now substitute the value for $t$ in the original equation $n \choose t$. We also note that for the coordinates where there are no stones, $\frac{n+k}{2} \notin \mathbb{Z}.$

Answer 2

The triangle of numbers is called Pascals triangle, the numbers in the n th row are the binomial coefficient of$(x+y)^n$ see under binomial coefficient in wiki.