\[ C(n,m) \equiv \prod_{i=0}^{k} C(n_i, m_i) \mod p \]

where $n_i$ and $m_i$ are the digits of $n$ and $m$ in base $p$ respectively, with $n_0$ and $m_0$ being the least significant digits.

When $p=2$, $n_i$ and $m_i$ are the bits in the binary expansion of $n$ and $m$ and $C(n_i, m_i)$ is $0$ if and only if $n_i < m_i$. This implies that $C(n,m) \equiv 0 \mod 2$ if and only if $n_i < m_i$ for some $i$.

The truth table for $n_i < m_i$ is:

\[\begin{array}{ c | c || c }

n_i & m_i & n_i < m_i \\ \hline

0 & 0 & 0 \\

0 & 1 & 1 \\

1 & 0 & 0 \\

1 & 1 & 0 \\

\end{array}\]

i.e., it is logically equivalent to $m_i AND ( NOT n_i)$. If we think of $AND$ and $NOT$ as bitwise operations on the binary representation of numbers, then we have shown that:

$C(n,m) \equiv 0 \mod 2$ if and only if $m AND ( NOT n)$ is not zero.

A simple Python function that implements this statement is

def bincoefmod2(n,m):

# computes binomial(n,m) mod 2

return 0 if ~n & m else 1

or equivalently:

def bincoefmod2(n,m):

# computes binomial(n,m) mod 2

return int(not ~n & m)

Incidentally, for bits $n_i$ and $m_i$, $n_i < m_i$ is logically equivalent to $NOT (m_i\Rightarrow n_i)$.

Next we consider C(n,m)C(a,b) mod 2. Clearly this is equivalent (mod 2) to (C(n,m) mod 2)*(C(a,b) mod 2). Thus $C(n,m)C(a,b) \equiv 0 mod 2$ if and only if $m AND ( NOT n)$ is not zero or $b AND ( NOT a)$ is not zero. This in turns implies the following:

\[\begin{array}{l}

C(n,m)C(a,b) \equiv 0 mod 2 \Leftrightarrow \\

(m AND ( NOT n)) OR (b AND ( NOT a)) \ne 0

\end{array}\]

where OR is a bitwise operation. The corresponding Python function is:

def bincoefprodmod2(n,m,a,b):

# computes binomial(n,m)*binomial(a,b) mod 2

return 0 if (~n & m)|(~a & b) else 1

or equivalently:

def bincoefprodmod2(n,m,a,b):

# computes binomial(n,m)*binomial(a,b) mod 2

return int(not (~n & m)|(~a & b))

## No comments:

## Post a Comment