Given $1$ to $N$ numbers. You have to make array of $k$ no.s using those no.s, where repetition of same no. is also allowed, such that at least one pair in that chosen array is co-prime. Find no. of all such combinations? In how many ways can we achieve this?

You have to chose $k$ no.s from the set $1, 2, 3, 4, 5, \ldots, N$. You will be given that N.

The combinations, say $(1, 2)$ and $(2, 1)$, will be considered as different.

For example, if $N = 2$ and $K = 5$, there are total $31$ possibilities (all $32$ combinations except $(2, 2, 2, 2, 2)$).


I doubt there is a closed form, but there an answer which is relatively simple to express.

Clearly you start with $N^k$ possible arrays but some of these are not coprime. So you then have to correct this by a process of inclusion-exclusion.

Let $S_j$ be the set of square-free numbers less than or equal to $N$ with $j$ distinct prime factors, none of the prime factors repeated as the numbers have to be square-free. For example $S_1$ is the set of prime numbers up to $N$, while $S_2$ starts $\{6, 10, 14, 15,\ldots\}$. Then consider $\left\lfloor\frac{N}{s}\right\rfloor$, the rounded-down quotient of $N$ divided by one of these square-free numbers, designed to count the number of multiples of $s$ less than or equal to $N$.

The solution to your question is then

$$N^k-\sum_{s\in S_1} \left\lfloor\dfrac{N}{s}\right\rfloor^k+\sum_{s\in S_2} \left\lfloor\dfrac{N}{s}\right\rfloor^k-\sum_{s\in S_3} \left\lfloor\dfrac{N}{s}\right\rfloor^k+ \ldots .$$

You could simplify this further, first by noting that $S_0=\{1\}$ and so $\displaystyle N^k= \sum_{s\in S_0} \left\lfloor\tfrac{N}{s}\right\rfloor^k$, and second by using the Möbius function $\mu(n)$ which is $0$ if $n$ is not square-free, $+1$ if $n$ is square-free with an even number of prime factors, and $-1$ is square-free with an odd number of prime factors. The answer then becomes $$\sum_{n =1}^N \mu(n) \left\lfloor\dfrac{N}{n}\right\rfloor^k.$$ In fact you do not even need to restrict the sum to $n \le N$, since removing it would simply add zeros to the answer.

  • $\begingroup$ Thank you! A very good explaination. Can I get to know some resources where I can learn these things from basics? I don't know if this is right place to ask this question, but can you please tell me? $\endgroup$ – user123 Dec 12 '14 at 2:38
  • $\begingroup$ Just read a lot about combinatorics and related topics, and practise $\endgroup$ – Henry Dec 12 '14 at 8:56

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.