# Select k no.s from 1 to N with replacement to have a set with at least one co-prime pair

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)$).

• – Henry Dec 12 '14 at 8:00

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.

• 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? – user123 Dec 12 '14 at 2:38
• Just read a lot about combinatorics and related topics, and practise – Henry Dec 12 '14 at 8:56