There is quite general question.

Let $A=\{1,2,3,...,n\}$ be a set.

Calculate the following: $$W_{k}=\sum_{\substack{a_{1},...,a_{k}\in A\\ a_{i}\neq a_{j} \text{ if }i\neq j\\ \gcd(a_{1},...a_{k})=1}}\hspace{-1.5em}1$$

For example $W_{2}=\sum_{2\le a \le N}\phi(a)$

Where $\phi$ is Euler totient function.

But I have no idea how to carry it on.

I wonder whether inclusion-exclusion principle should be used.

I hope for help.


  • 1
    $\begingroup$ What kind of answer are you looking for? Even the $\sum \phi(n)$ doesn't have a closed form so far as I can tell. $\endgroup$ – saulspatz May 26 at 12:23
  • 1
    $\begingroup$ @saul, but it does have good asymptotics. $\endgroup$ – Gerry Myerson May 26 at 12:58

We have $W_k=W_k(n):=\#A(n,k,1)$, where $$A(n,k,d)=\left\{(a_1,\ldots,a_k)\in\{1,\ldots,n\}^k\ \middle|\ \begin{gathered}i\neq j\implies a_i\neq a_j\\ \gcd(a_1,\ldots,a_k)=d\end{gathered}\right\}.$$ Now clearly $\#A(n,k,d)=W_k(\lfloor n/d\rfloor)$, and $\bigcup_{d=1}^{n}A(n,k,d)$ is the set of all $k$-tuples of distinct numbers from $\{1,\ldots,n\}$. This set has $(n)_k=n(n-1)\cdots(n-k+1)$ elements, which gives $$\sum_{d=1}^{n}W_k(\lfloor n/d\rfloor)=(n)_k\implies W_k(n)=\sum_{d=1}^{n}\mu(d)\big(\lfloor n/d\rfloor\big)_k$$ by Möbius inversion (for computing, it may be preferable to use the first of these equalities, as a recurrence relation for $O(\sqrt{n})$ needed values of $W_k$, rather than the last formula; see the bottom of this answer for details).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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