The number of edges this graph

Question

Let $G$ be a graph with $V(G)=\{d_i;d_i|n,d_i\not=1,n\}$ and $E(G)=\{d_id_j;d_i|d_j ~or~d_j|d_i\}.$ Here $n$ is the natural number.I know that if $n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$,$p_i$ is the prime number for $1\leq i \leq k$, then $|V(G)|=(\alpha_1+1)(\alpha_2+1)\cdots (\alpha_k+1)-2$. I want to know in general $|E(G)|?$ For example for $n=12$, $V(G)=\{2,3,4,6\}$ and $E(G)=\{(2,4),(2,6),(3,6)\}$, so $|E(G)|=3$, and for $n=30$, $V(G)=\{2,3,5,6,10,15\}$ and $E(G)=\{(2,6),(2,10),(3,6),(3,15),(5,10),(5,15)\}$ so $|E(G)|=6$. thanks in advance.

Answer 1

I use instead $V'(G) = \{d_i; d_i|n\}$, and $E'(G) = \{ d_i d_j: d_i | d_j\}$, allowing a loop on each vertex corresponding to $d_i| d_i$; since this is homework I leave the necessary adjustments to you (i.e. counting how many edges are joined to $1$ and $n$, how many other loops there are, and subtracting these off).

So, let us determine $E'(G)$. By considering prime factorization, edit: where $n = \prod p_i^{n_i}$, $V'(G)$ is in bijection with $i$ tuples $(a_i)$, where $a_i \in \mathbb{N}, 0 \leqslant a_i \leqslant n_i$, and we draw an oriented edge $(a_i) \rightarrow (b_i)$ if $a_i \leqslant b_i$ for all $i$, corresponding to divisibility.

For $\lvert E'(G) \rvert$, we may count as follows: if $c_i$ denotes the number of pairs $(a,b)$ such that $0 \leqslant a_i \leqslant b_i \leqslant n_i$, then the number of edges is simply $\prod_i c_i$. By conditioning on whether $b = c_i$ or not, we get the recursion $c_i = c_{i-1} + (i+1)$, yielding $c_i = \frac{(n_i+1)(n_i+2)}{2}$.