Why every factor tree has the same number of splits

Text

In a factor tree of a number $n$, every non-prime node splits into two factors, down to the primes (the leaves). Prove that, however the tree is built, the number of “splits” is always the same, equal to $\Omega(n)-1$, where $\Omega(n)$ is the number of prime factors of $n$ counted with multiplicity.

Solution

Count the leaves. The tree starts with a single node (the root $n$). Each split replaces one node with two children: it removes one leaf and adds two, so it increases the number of leaves by exactly $1$. In the end the leaves are the prime factors counted with multiplicity, so there are $\Omega(n)$ of them (a number that, by the fundamental theorem of arithmetic, does not depend on the choices made). If $S$ is the number of splits, starting from $1$ leaf and reaching $\Omega(n)$ leaves gives $1+S=\Omega(n)$, that is $S = \Omega(n)-1.$ This value depends only on $n$, not on the chosen tree. $\blacksquare$