Re: C(n, k): binomial coefficient calculation

From: Dave Seaman (dseaman_at_no.such.host)
Date: 01/26/05 

Date: Wed, 26 Jan 2005 03:53:52 +0000 (UTC)

On Wed, 26 Jan 2005 02:49:02 GMT, Chris McMahon wrote:
> Dave Seaman wrote:
>> On 25 Jan 2005 14:19:30 GMT, Timothy Little wrote:

>>>Dave Seaman wrote:

>>>>> (n/1) * ((n-1)/2) * ((n-2)/3) * ... * ((n-s+1)/s)

>>>>I meant, if you do the computation in left-to-right order and ignore the
>>>>extra parentheses.

>>>I'm still not following... can you demonstrate for a small number,
>>>e.g. C(7,3) mod 6?

>> You can't do the reductions as you go along, as far as I can see. It's
>> just normal arithmetic, but the partial products are smaller than if you
>> do all the multiplications followed by all the divisions.

>> C(7,3) = 7/1 * 6/2 * 5/3
>> = 42/2 * 5/3
>> = 21 * 5/3
>> = 105/3
>> = 35
>> == 5 (mod 6)

> ok, so if i understand correctly:

I think one of us doesn't.

> C(7,3) mod 6 = ((7*6*5)/(3*2*1)) mod 6 = 5

> can be expressed as:

> ((7/1) mod 6) * ((6/2) mod 6) * ((5/3) mod 6) = 1 * 3 * 5/3 = 5

I don't even know what ((5/3) mod 6) means, since 5/3 is not an integer.

> and does it only apply to the central binomial coefficient, when we know
> there are an equal number of terms in the factorial in the numerator as
> there are in the factorial in the denominator?

I don't follow. For every n and k, C(n,k) can be expressed with an equal
number of terms in the numerator and denominator.

        C(n,k) = n/1 * (n-1)/2 * (n-2)/3 * ... * (n-k+1)/k.

> along those lines, given a number x, is there a way to find values of n
> and k that such that you can know C(n,k) mod x will be easier to calculate?

See Robert Israel's post concerning the Chinese Remainder Theorem. My
suggestion was simply to compute C(n,k) first and then perform the
reduction mod x, in which case the value of x makes very little
difference in the difficulty of the computation. You do gain something
in ease of computation by performing divisions earlier rather than later. 

-- 
Dave Seaman
Judge Yohn's mistakes revealed in Mumia Abu-Jamal ruling.
<http://www.commoncouragepress.com/index.cfm?action=book&bookid=228>