sigma19
asked on
pairing with out repeattaions
there are 1000 people.
starting from 1 to 1000.
1 can pair with (2 to 1000) so there are 999 combinations.
2 can pair with (1,3 to 1000) so there are 999 combinations.
.. up to 1000.
effectively there are 1000 multiplied by 1000 combinations.
==
If you see that case 1 is paired to 2.
so there is no need for 2 to again paired and counted to 1.
using this logic how many possible combinations are possible?
what is the formula that can be derived?
starting from 1 to 1000.
1 can pair with (2 to 1000) so there are 999 combinations.
2 can pair with (1,3 to 1000) so there are 999 combinations.
.. up to 1000.
effectively there are 1000 multiplied by 1000 combinations.
==
If you see that case 1 is paired to 2.
so there is no need for 2 to again paired and counted to 1.
using this logic how many possible combinations are possible?
what is the formula that can be derived?
1000 choose 2 = (1000!)/((2!)*((1000-2)!)) = 499500
ASKER
can you please explain me the logic
C(1000,2)
=1000!/(2! *(1000-2)!)
=(1000*999)/(1*2)
=1000!/(2! *(1000-2)!)
=(1000*999)/(1*2)
as you said, 1000 ways to choose the first element of the pair, 999 ways to choose the second element of the pair,
but the order does not matter, so divide by the number of ways the pair can be ordered.
but the order does not matter, so divide by the number of ways the pair can be ordered.
ASKER
thanks ozo,
1000! for first combination.
1*2 as the ways paired. you also have *(1000-2)? why is that
1000! for first combination.
1*2 as the ways paired. you also have *(1000-2)? why is that
1000!/(1000-2)! =
1000*999*998*997*996*...
/
998*997*996*...
= 1000*999
1000*999*998*997*996*...
/
998*997*996*...
= 1000*999
Hmmmm Surely not?
Surely the answer is 250,000
The first person can be paired with n-1 people, here thats 1000-1 or 999
The second person can be paired with n-3 or 997
The third person can be paired with n-5 or 995
For all people upto the value of n/2
So its (n-1)+(n-3)+(n-5)...+(n-n/ 2))
=250,000 for a start value of 1000.
Surely the answer is 250,000
The first person can be paired with n-1 people, here thats 1000-1 or 999
The second person can be paired with n-3 or 997
The third person can be paired with n-5 or 995
For all people upto the value of n/2
So its (n-1)+(n-3)+(n-5)...+(n-n/
=250,000 for a start value of 1000.
Or, if you meant the number of ways to choose 500 disjoint pairs of items from 1000 items,
rather than the number of ways to choose a single pair, that would be the double factorial
1*3*5*7*...*999
rather than the number of ways to choose a single pair, that would be the double factorial
1*3*5*7*...*999
As there seems to be some confusion about what is being asked, perhaps you could clarify with a smaller example.
If there were 8 people, would the answer you were looking for be 105, 28, or 16?
If there were 8 people, would the answer you were looking for be 105, 28, or 16?
Everybody has 999 pairings so there are 1000*999 pairs. Now every pair is represented twice so if you count these two as one you get 1000*999/2=499500.
Here is a link for a more general explanation of this: http://mathforum.org/library/drmath/view/61212.html
Here is a link for a more general explanation of this: http://mathforum.org/library/drmath/view/61212.html
ASKER
thanks abbright.
if we want to represent in a algorithm how can we do that?
basically i want know the formula not only to have the total count but also the possible combination.
if we want to represent in a algorithm how can we do that?
basically i want know the formula not only to have the total count but also the possible combination.
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.