Question

Given a list of n numbers. How many pairs can exist such that product of those pairs is never repeated.
For example: If list has {5,7,11,13} then pairs are {(5,5) , (5,7), (5,11), (5,13), (7,7), (7,11), (7,13), (11,11), (11,13), (13,13) } that is total 10 pairs exists.
How will get number of pairs of list of n numbers ?

Answer 1

If you ignore (5,5), (7,7), (11,11) and (13,13)

There are 6 pairs of numbers

Answer 2

There are 4 numbers in {5,7,11,13}

Notice how 4 C 2 = (4!)/(2!*(4-2)!) = 6

This is not a coincidence

Answer 3

Basically there are 6 ways to choose 2 numbers from the set {5,7,11,13} where repeats aren't allowed

Answer 4

but if repeats are allowed, then you add on the 4 repeats to get 6+4 = 10

Answer 5

in general, if you have a set with n items, then there are

n C 2 = (n!)*(2!*(n-2)!) = (n(n-1)(n-2)!)/(2!*(n-2)!) = (1/2)*n(n-2)

ways to pick 2 items where no repeats are allowed

Answer 6

If repeats are allowed (like in this case), then you would add on the n repeats

Answer 7

So, finally, number of pairs = nC2 + n ??

Answer 8

yeah you could write it like that to be simpler

Answer 9

Thanks.

Answer 10

np