3
$\begingroup$

Let $A=\{i: 1 \leq i \leq n\} \subset \mathbb{N} $ and $B \subset A$, $|B|=k$ ($k < n$). What's the probability that $\gcd(B)>1$?

EDIT: $n$ and $k$ are given. I think this can be solved with inclusion-exclusion principle?

  • 0
    Perhaps it may be useful to know that the probability that a number k < n selected being coprime to $n$ is $\phi(n)/n$.2012-08-05

1 Answers 1

0

Not a complete solution, but a direction:

Let's denote by $A_p$ the event $\forall a\in B,p |a$. We want to know the probability of $\bigcup_{p \space prime}^{} A_p$.

Since we have We have $\lfloor\frac np\rfloor$ numbers that sivisible by $p$, we can get that $p(A_p)=\dfrac{|A_p|}{|\Omega|}=\dfrac{\big\lfloor\frac np\big\rfloor \choose k}{n\choose k}$.

$p(A_p)$ vanishes for $\lfloor\frac np\rfloor \lt k$.

Also, we have $A_p \cap A_q=A_{p \times q}$ for any $p$, $q$ primes.

So we can proceed with inclusion-exclusion principle: $p(n,k)=\sum_{p \space prime}\dfrac{\big\lfloor\frac np\big\rfloor \choose k}{n\choose k}-\sum_{p, q\space primes}\dfrac{\big\lfloor\frac n{p\cdot q}\big\rfloor \choose k}{n\choose k}+...$