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.
Combinatorial Interpretation of a Certain Product of Factorials
-
10You 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
– 2012-07-27 -
1@ThomasAndrews, that formula doesn't get any closer to a combinatorial interpretation. – 2014-03-11
-
4If it did, do you think I might have posted it as an answer? @vonbrand – 2014-03-11
-
0Well, the later formula suggest one approach. If we can find a faithful action of a group of size $\prod_{d |n, d
$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.... – 2014-05-26 -
0Something similar-looking: http://math.stackexchange.com/questions/7531 – 2015-03-29
1 Answers
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)$