binomial coefficient mod n
in [Math]
|
Prev: Mathematical Convention
Next: Project Euler problem 140
From: recoder on 19 Apr 2010 10:24 I observed that C(n-1,k) mod n = (-1)^k for all k between 0 and n-1 where C(n-1,k) is a binomial coefficient C(n-1,k)= (n-1)! / ((k!)(n- k)!) . I tried to verify it for large numbers by using a big number online calculator at http://world.std.com/~reinhold/BigNumCalc.html I tried to calculate C(2046,1023) mod 2047 but it doesnt produce 1. Ä°s my observation wrong or do I need a better calculator?
From: Dave Dodson on 19 Apr 2010 11:00 On Apr 19, 9:24 am, recoder <kurtulmeh...(a)gmail.com> wrote: > I observed that > C(n-1,k) mod n = (-1)^k  for all k between 0 and n-1 > where > C(n-1,k) is a  binomial coefficient  C(n-1,k)= (n-1)! / ((k!)(n- > k)!)  . > > I tried to verify it for large numbers by using a big number online > calculator athttp://world.std.com/~reinhold/BigNumCalc.html > I tried to calculate C(2046,1023) mod 2047 but it doesnt produce 1. > > İs my observation wrong or do I need a better calculator? Wouldn't it be C(n-1,k) = (n-1)! / (k! (n-1-k)!) ? Dave
From: recoder on 19 Apr 2010 11:11 On 19 Nisan, 18:00, Dave Dodson <dave_and_da...(a)Juno.com> wrote: > On Apr 19, 9:24 am, recoder <kurtulmeh...(a)gmail.com> wrote: > > > I observed that > > C(n-1,k) mod n = (-1)^k  for all k between 0 and n-1 > > where > > C(n-1,k) is a  binomial coefficient  C(n-1,k)= (n-1)! / ((k!)(n- > > k)!)  . > > > I tried to verify it for large numbers by using a big number online > > calculator athttp://world.std.com/~reinhold/BigNumCalc.html > > I tried to calculate C(2046,1023) mod 2047 but it doesnt produce 1. > > > İs my observation wrong or do I need a better calculator? > > Wouldn't it be C(n-1,k) = (n-1)! / (k! (n-1-k)!) ? > > Dave My Bad, Sorry for that.
From: Chip Eastham on 19 Apr 2010 11:56 On Apr 19, 10:24 am, recoder <kurtulmeh...(a)gmail.com> wrote: > I observed that > C(n-1,k) mod n = (-1)^k  for all k between 0 and n-1 > where > C(n-1,k) is a  binomial coefficient  C(n-1,k)= (n-1)! / ((k!)(n- > k)!)  . > > I tried to verify it for large numbers by using a big number online > calculator athttp://world.std.com/~reinhold/BigNumCalc.html > I tried to calculate C(2046,1023) mod 2047 but it doesnt produce 1. > > İs my observation wrong or do I need a better calculator? Maybe I'm not understanding the conjecture, but consider n = 6: C(5,0) = 1 okay, (-1)^0 mod 6 C(5,1) = 5 okay, (-1)^1 mod 6 C(5,2) = 10 ??? not (-1)^2 mod 6 regards, chip
From: recoder on 19 Apr 2010 14:18
On 19 Nisan, 18:56, Chip Eastham <hardm...(a)gmail.com> wrote: > On Apr 19, 10:24 am, recoder <kurtulmeh...(a)gmail.com> wrote: > > > I observed that > > C(n-1,k) mod n = (-1)^k  for all k between 0 and n-1 > > where > > C(n-1,k) is a  binomial coefficient  C(n-1,k)= (n-1)! / ((k!)(n- > > k)!)  . > > > I tried to verify it for large numbers by using a big number online > > calculator athttp://world.std.com/~reinhold/BigNumCalc.html > > I tried to calculate C(2046,1023) mod 2047 but it doesnt produce 1. > > > İs my observation wrong or do I need a better calculator? > > Maybe I'm not understanding the conjecture, > but consider n = 6: > > C(5,0) = 1 okay, (-1)^0 mod 6 > C(5,1) = 5 okay, (-1)^1 mod 6 > C(5,2) = 10  ??? not (-1)^2 mod 6 > > regards, chip Sorry, n has o be an odd integer |