Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

for calculating the value of choosing r items from n items where q are of same kind, and we should take %m , i used the following relation

  • (nPr/q!) %m where m is prime

For calculating this

  • i calculated n!

  • n!%m

  • then, i calculated (n-r)! and multiplied it with q!, i.e temp = (n-r)!*q!;

  • Then i mulitplied modular mulitplicative inverse of temp with n! and took mod of result

    but am not getting the correct answer..E.g if n= 3 ; r = 2; q = 2 then the expected result is (3P2/2!)%1000000007 = 3 but am getting 250000004 ..I can't understand my mistake here..Thanks.

share|improve this question

migrated from stackoverflow.com Jun 5 '12 at 21:03

This question came from our site for professional and enthusiast programmers.

1  
Can you edit your question so the algorithm is shown step by step using a bullet list? –  Emil Vikström Jun 4 '12 at 16:39
    
modulo arithmetic doesn't work in division –  nims Jun 4 '12 at 16:40
    
@nims : so i've used multiplicative inverse –  pranay Jun 4 '12 at 16:44
    
@DanAndrews: thanks.. –  pranay Jun 4 '12 at 16:47

1 Answer 1

up vote 4 down vote accepted

The method you've described is correct, so there must be a bug in your implementation. In this case (n=3, r=2, q=2, m=1000000007):

n! = 6
temp = (n-r)!*q! = 2
Multiplicative inverse of 2 (mod m) = 500000004

result = (6*500000004) % 1000000007 = 3, the expected result.
share|improve this answer
    
thanks interjay..indeed there was a mistake in my implementation.. –  pranay Jun 4 '12 at 17:10

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.