Sign up ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $\mu$ denote the Moebius function. What is a combinatorial interpretation of the following integer, \begin{align} \prod_{d \mid n} d!^{\,\mu(n/d)}, \end{align} where the product is taken over divisors of $n$? Does it have a simpler representation in terms of known functions? Note: The Online Encyclopedia of Integer Sequences does not have an entry containing the corresponding sequence.

share|cite|improve this question
You can take the log and use Mobius inversion to show that (if $f$ is your function,) then $n! = \prod_{d|n} f(d)$. That lets you compute $f(n)$ recursively as $$\frac{n!}{\prod_{d|n, d<n} f(d)}$$ – Thomas Andrews Jul 27 '12 at 17:40
@ThomasAndrews, that formula doesn't get any closer to a combinatorial interpretation. – vonbrand Mar 11 '14 at 2:19
If it did, do you think I might have posted it as an answer? @vonbrand – Thomas Andrews Mar 11 '14 at 3:18
Well, the later formula suggest one approach. If we can find a faithful action of a group of size $\prod_{d |n, d<n} f(d)$ on $S_{n}$, then that formula will count the orbits of that action. Now, I don't know what that group or action might be, but.... – coolpapa May 26 '14 at 7:48
Something similar-looking: – barto Mar 29 at 19:51

1 Answer 1

This is an idea of approach, and it does not completely answer to the question. Define $$ \mathcal{R}_n(x) = \{r \le x: (r,n) = 1\}$$ and note that, by Inclusion-Exclusion principle $$ | \mathcal{R}_n(x) | = \sum_{d \mid n} \mu(d) \left \lfloor \frac{x}{d} \right \rfloor $$ Let $S_n$ be the sum in the text. Now, for every prime $p \le n$, consider $ V_p(S_n) $.
Recalling Polignac identity on $V_p(k!)$, we have $$ V_p(S_n) = \sum_{d \mid n} \mu(n/d) V_p(d!) = \sum_{d \mid n} \mu(n/d) \sum_{k=1}^{\infty} \left \lfloor \frac{d}{p^k} \right \rfloor = \sum_{k=1}^{\infty} \sum_{d \mid n} \mu(d) \left \lfloor \frac{n}{dp^k} \right \rfloor = \sum_{k=1}^{\infty} |\mathcal{R}_n(n/p^k) | $$ Take $r \in \mathcal{R}_n(n)$: the number of times it is counted in the last infinite sum is the number of positive integer solutions $k$ of $n/p^k \ge r$, i.e. $ \lfloor \log_p n/r \rfloor $. So $$ \sum_{k=1}^{\infty} |\mathcal{R}_n(n/p^k)| = \sum_{r \in \mathcal{R}_n(n)} \lfloor \log_p (n/r) \rfloor $$ Define $q_p(x) := \max \{ p^n \ | \ p^n \le x\}$, and note that $ q_p(x) =p^{ \lfloor \log_p x \rfloor} $. So, in conclusion: $$ S_n = \prod_{p \le n} p^{V_p(S_n)} = \prod_{\substack{p \le n \\ r \in \mathcal{R}_n(n) }} p^{ \lfloor \log_p (n/r) \rfloor } = \prod_{\substack{r,p \le n \\(r,n)=1 }} q_p(n/r) $$

I don't know, actually, if this can be useful; I think that it gives a combinatorial meaning to involved quantities, even if not much to the formula itself.

Hope it helps, Andrea

EDIT: I found an error in an inequality I used; so I can't actually state two bounds (upper and lower) of the same order. I would like to know more about this: Second-order asymptotics for $\pi(n), \theta(n)$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.