<s>[INST] Fibonacci sequence, number of trees, probability How can I prove that the numbers of orderings described below are Fibonacci numbers?
We are given $p_1, \dots , p_n > 0$ such that each $p_i= \frac{1}{2^k}$ for $i \in \{1, \dots , n\}, \ \ k \in \mathbb{N}$  and $$p_1 + \dots +p_n = 1$$ and the sequence $(p_1, ..., p_n)$ must be non rising.
I've computed the numbers of such orderings for small $n$.
And for $n=1$ we have only one possibility: $(1)$ For $n=2$ we have $$\left(\frac{1}{2} , \frac{1}{2}\right)$$ so also one possibility. For $n=3$ we have one: $$\left( \frac{1}{2}, \frac{1}{4}, \frac{1}{4}\right)$$ for $ n=4$ I've found $2$: $$\left( \frac{1}{2}, \frac{1}{4}, \frac{1}{8}, \frac{1}{8}\right) \ \ \left( \frac{1}{4}, \frac{1}{4}, \frac{1}{4}, \frac{1}{4}\right)$$ for $n=5$ we have 3: $$\left( \frac{1}{2}, \frac{1}{4}, \frac{1}{8}, \frac{1}{16}, \frac{1}{16}\right) \ \ \left( \frac{1}{2}, \frac{1}{8}, \frac{1}{8}, \frac{1}{8}, \frac{1}{8}\right) \ \ \left( \frac{1}{4}, \frac{1}{4}, \frac{1}{4}, \frac{1}{8}, \frac{1}{8}\right)$$ for $n=6$ I have $5$:
$$\left(\frac{1}{2},\frac{1}{4}, \frac{1}{8}, \frac{1}{16}, \frac{1}{32}, \frac{1}{32} \right) \ \ \left(\frac{1}{2},\frac{1}{4}, \frac{1}{16}, \frac{1}{16}, \frac{1}{16}, \frac{1}{16} \right) \ \  \ \\ \left(\frac{1}{2},\frac{1}{8}, \frac{1}{8}, \frac{1}{8}, \frac{1}{16}, \frac{1}{16} \right) \ \ \left(\frac{1}{4},\frac{1}{4}, \frac{1}{4}, \frac{1}{8}, \frac{1}{16}, \frac{1}{16} \right), \left(\frac{1}{4},\frac{1}{4}, \frac{1}{8}, \frac{1}{8}, \frac{1}{8}, \frac{1}{8} \right)   $$ and so on. But I don't know how to justify it mathematically, that means - how to find an occurence relation for different $n$s .
 [/INST] It is not the Fibonacci sequence, as it starts $1, 1, 1, 2, 3, 5, 9, 16, \ldots $ so has too many examples when $n \ge 7$.  For $7$ parts, the examples are:


*

*$ \frac1{2}  + \frac1{4}  + \frac1{8}  + \frac1{16}  + \frac1{32}  + \frac1{64}  + \frac1{64} $ 

*$ \frac1{2}  + \frac1{4}  + \frac1{8}  + \frac1{32}  + \frac1{32}  + \frac1{32}  + \frac1{32} $ 

*$ \frac1{2}  + \frac1{4}  + \frac1{16}  + \frac1{16}  + \frac1{16}  + \frac1{32}  + \frac1{32} $ 

*$ \frac1{2}  + \frac1{8}  + \frac1{8}  + \frac1{8}  + \frac1{16}  + \frac1{32}  + \frac1{32} $ 

*$ \frac1{2}  + \frac1{8}  + \frac1{8}  + \frac1{16}  + \frac1{16}  + \frac1{16}  + \frac1{16} $ 

*$ \frac1{4}  + \frac1{4}  + \frac1{4}  + \frac1{8}  + \frac1{16}  + \frac1{32}  + \frac1{32} $ 

*$ \frac1{4}  + \frac1{4}  + \frac1{4}  + \frac1{16}  + \frac1{16}  + \frac1{16}  + \frac1{16} $ 

*$ \frac1{4}  + \frac1{4}  + \frac1{8}  + \frac1{8}  + \frac1{8}  + \frac1{16}  + \frac1{16} $ 

*$ \frac1{4}  + \frac1{8}  + \frac1{8}  + \frac1{8}  + \frac1{8}  + \frac1{8}  + \frac1{8} $ 


The sequence is described by OEIS $A002572$ with several references.
Empirically it seems that number of examples with $n$ parts is slightly more than about $$0.141853\ldots \times 1.794147\ldots^n$$ 
</s>