0
$\begingroup$

Given N positive integers, not necessarily distinct, how many ways you can take 4 integers from the N numbers such that their GCD is 1. For example,N=10 and the positive integers are 12,46,100,131,5,6,7,8,9 and 10, the result will be 195.

If the value of N varies how can I find out the number of ways using inclusion-exclusion principle? I'm a novice in learning inclusion-exclusion principle.So I need better explanation

$\endgroup$

migrated from cs.stackexchange.com Nov 17 '14 at 11:38

This question came from our site for students, researchers and practitioners of computer science.

  • $\begingroup$ I guess you're looking for combinations, rather than permutations, since the answer you give in your example isn't divisible by $4!\,$? $\endgroup$ – David Richerby Nov 17 '14 at 10:50
0
$\begingroup$

I can see two approaches. The first does not use inclusion-exclusion. Start by forming each pair of elements. I'll start at the back because it helps to show the point. When you pick $9,10$, they already have GCD of $1$, so you can pick two more in ${8 \choose 2}=28$ ways. When you start with $8,10$ (and can't pick $9$) you have a GCD of $2$, so when you pick $7$ you can use any other one. When you pick $6$ for the third, you still have a GCD of $2$, so have to pick an odd. This will be somewhat faster than $N^4$, but can be that bad in the worst case.

To use inclusion-exclusion, you note that there are ${10 \choose 4}=210$ four element subsets you could choose. To have a GCD of $1$, you can't choose four even ones. As there are six even numbers in the set, that rules out ${6 \choose 4}=15$ of the subsets, leaving $195$. So far, most would not call this using inclusion-exclusion. That would come up if (for example) you had a set of $20$ numbers, $10$ of which are even, $9$ of which are multiples of $3$, and $7$ of which are multiples of $6$. You would start with ${20 \choose 4}=4845$ ways to choose four numbers. You would deduct the ${10 \choose 4}=210$ where they were all even, as the GCD would be at least $2$. You would also deduct the ${9 \choose 4}=126$ where they were all multiples of $3$. Now you have deducted the ones that are multiples of $6$ twice, so you need to add back in the ${7 \choose 4}=35$ ways to choose them all multiples of $6$, getting $4845-210-126+35=4544$

$\endgroup$

Your Answer

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