This isn't the best title, but it's easier to explain visually. I want to know the number of rows a transposed collated binary tree matrix (for lack of a better term) has. Normally a tree has its root on the first row, in this case, its root is at the rightmost column and the leaves at the leftmost column. I've shifted each tree position to leave no space towards the top rows.
For example, a tree of height 4 (known value that can be used in the formula) would look like this:
0|1|2|3
0 *|*|*|*
1 *|*|*
2 *|*
3 *|*
4 *
5 *
6 *
7 *
Examples of the how the tree is connected:
(0,3)->{(0,2), (1,2)}
(3,1)->{(6,0),(7,0)}
(1,1)->{(2,0),(3,0)}
And the mapping would be as follows:
0->4
1->3
2->2
3->2
4->1
5->1
6->1
7->1
I've tried a bunch of formulas and even looked at oeis for the sequence to no avail.
I'll assume this encoding is about perfect binary trees, i.e. where all internal nodes have exactly 2 children, and where the leaves of the tree are all on the same level/depth.
If you look at the number of missing asterisks at the right, compared to the first row, then you get this sequence:
0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 5... and so on.
2 appears twice as many times as 1, and 3 twice as many times as 2, ...etc.
The formula here is ⌈log2𝑖⌉, where 𝑖 is the one-based row number.
To get the number of asterisks instead of the missing ones, you need the input 𝑛 (in your example 𝑛=4). As your row numbering starts with zero instead of one, the formula becomes:
asterisks(𝑖) = 𝑛 − ⌈log2(𝑖+1)⌉