$$ g(n)=\begin{cases} 1 & \text{if }n=1 \\[10pt] \sum_{d\mid n,\ d\ne n} g(d) & \text{else} \end{cases} $$
How can I calculate $g(n)$ efficiently?
I was trying to collect all the $g(p)$ terms after complete decomposition of $n$.
After some googling I found that whay I am looking for is perfect partition which is same as number of ordered factorization of $n$. There is a formula called Mac Mohan's formula to compute number of ordered factorization of $n$. Can someone explain how Mac Mohan's formula is derived. Also see the orignal question.
Let $n$ is square free. Then if $n$ has $\nu(n)$ distinct prime factors, $$f\left(\nu(n)\right):=g(n)=\sum_{d|n,\ d\ne n}g(d)=\sum_{k=0}^{\nu(n)-1}\binom{\nu(n)}{k} f(k)$$ where we denote by $f(k)$ the value of $d(n)$ when $\nu(n)=k$ (because clearly $g(n)$ depends upon the number of prime factors only, not on the prime numbers themselves).
So, the function $f(n)$ is defined by $$f(n)=\left\{ \begin{array}{lr} 1 && \mbox{if}\ n=0\\ \sum_{k=0}^{n-1}\binom{n}{k} f(k) && \mbox{if}\ n\geq1 \end{array} \right. $$
I find a striking resemblance of the function $f(n)$ to the Bell number $B(n)$ which is also defined very similarly with a slight (but maybe significant) difference.
To find $g(n)$ for $n$ not square free, we proceed as below.
First, let $n=p^k$ for some prime $p$ and $k\in \mathbb{Z}^+$. Then, $$g(p^k)=\sum_{d|p^k,\ d\ne p^k}g(d)=\sum_{d|p^{k-1},\ d\ne p^{k-1}}g(d)+g(p^{k-1})=2g(p^{k-1})$$ So iteratively, $$g(p^k)=2^kg(1)=2^k$$
Now, let $n=p^kq$ where $p, q$ are distinct prime numbers. Then $$g(p^kq)=2g(p^{k-1}q)+g(p^k)=2g(p^{k-1}q)+2^k$$ Iteratively, $$g(p^kq)=2^kg(q)+k2^k=(k+1)2^k$$
If $n=p^kq^2$ then, similarly we will get the recurrence relation $$g(p^kq^2)=2g(p^{k-1}q^2)+g(p^k)+g(p^kq)$$ Since we know $g(p^kq)$ from the previous computation we can find $g(p^kq^2)$.
Likewise, extending the idea, we get $$g(p^kq^r)=2g(p^{k-1}q^r)+\sum_{i=0}^{r-1}g(p^kq^i)$$
In general, if $n=p_1^{k_1}p_2^{k_2}\cdots\ p_r^{k_r}$, then, to find $g(n)$, i guess we have to solve this multidimensional recursive equation $$f_r(k_1,k_2,\cdots\ ,k_r)=\sum_{0\le a_1\le k_1,\cdots\ ,0\le a_r\le k_r}\frac{(a_1+a_2+\cdots\ a_r)!}{a_1!a_2!\cdots\ a_r!}f_r(a_1,a_2,\cdots\ ,a_r)$$ I don't quite know though how to solve this equation.
Right now, I don't see any easier method.