Number of proper divisors $d_1 < \cdots < d_j$ of $n$ such that $\gcd(d_1, \ldots, d_j) = d$

Question

Let $n$ be a positive integer and let $D^*(n)$ be the set of proper divisors of $n$, i.e., positive divisors of $n$ excluding $n$. For every $j \geq 1$, define the function $f_j : D^*(n) \to \mathbb{N}_0$ by $$ f_j(d) = \#\left\{ d_1 < \cdots < d_j \in D^*(n) \ : \ \gcd(d_1, \ldots, d_j) = d\right\}. $$
Can we give a good formula for $f_j(d)$, perhaps a recursive one? This smells like recursion to me from the gcd but I'm not quite sure how to get there. Also the calculation of $f_j(d)$ can be converted into a similar one for $f_j(1)$ when $n$ is substituted with $n/d$. Perhaps the Mobius function and inversion formula could then come into play. Comments are welcome. Thanks!

Answer 1

It seems the answer is $$ \sum_{b \mid n/d} \mu(n/bd){\tau^*(b) \choose j}, $$ where $\tau^*(b)$ is the number of proper divisors of $b$.

Indeed, first it will be useful to make a change of notation. For $n,j \in \mathbb{N}$ arbitrary and $d$ a positive divisor of $n$, we let $$ f_d^{(j)}(n) = \#\left\{ d_1 < \cdots < d_j \in D^*(n) \ : \ \gcd(d_1, \ldots, d_j) = d \right\}. $$ Note that $f_d^{(j)}(n) = f_1^{(j)}(n/d)$ and so $$ {\tau^*(n) \choose j} = \sum_{d \mid n} f^{(j)}_d(n) = \sum_{d \mid n} f^{(j)}_1(n/d) = \sum_{d \mid n}f^{(j)}_1(d). $$ By the Moebius inversion formula, $$ f^{(j)}_1(n) = \sum_{b \mid n}\mu(n/b) {\tau^*(b) \choose j}. $$ Thus $$ f^{(j)}_d(n) = f^{(j)}_1(n/d) = \sum_{b \mid n/d}\mu(n/bd) {\tau^*(b) \choose j}. $$

Answer 2

Note that $$\sum_{d\mid n}f_j(d)={|D^*(n)|\choose j} $$ so that by Möbius inversion $$ f_j(d)=\sum_{k\mid d}\mu(k/d){|D^*(k)|\choose j} $$