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