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.

Can we determine if a binomial coefficient $C(n,p)$ is even or odd, without calculating its value? ($p\lt n$, $p$ and $n$ are positive integers)

share|improve this question
8  
    
Know someone say who is the author of the work contained in the file below? cs.columbia.edu/~cs4205/files/CM4.pdf –  Paulo Argolo Nov 20 '10 at 22:40

4 Answers 4

There is a beautiful result of Kummer that says that if $q$ is a prime, then the largest power of $q$ that divides $\binom{m+n}{n}$, $m$ and $n$ nonnegative, is the number of carries when $m$ and $n$ are added in base $q$.

As a corollary, we get the Theorem of Lucas mentioned by Michael Lugo: we get a carry in the addition if and only if there is a $k$ such that the $k$th digit of $m+n$ in base $q$ is smaller than the $k$th digit in the base $q$ expansion of $n$, so $\binom{m+n}{n}$ is divisible by $q$ if and only if there is a $k$ such that the $k$th digit of the base $q$ expansion of $m+n$ is smaller than the $k$th digit of the base $q$ expansion of $n$.

Thus, to determine if $\binom{n}{p}$ is odd, you just need to know whether there is at least one carry when adding $p$ and $n-p$ in base $2$; you get a carry exactly when the $k$th binary digit of both $n-p$ and $p$ is $1$.

So just write $p$ and $n-p$ in binary, one digit at a time (from least significant to most significant digit), until you get that both are $1$; or write $p$ and $n$ one binary digit at a time, until you get a $1$ in $p$ and a $0$ in $n$. If this happens, $\binom{n}{p}$ is even; otherwise, it is odd.

Andrew Granville's paper Arithmetic properties of binomial coefficients is chock full of interesting stuff about binomial coefficients and their divisibility. The proof of Kummer's Theorem can be found there. There are also other formats available.

share|improve this answer
2  
Nice! In C-style languages, then, it's just: if (p & (n-p)) –  TonyK Nov 20 '10 at 12:31
    
@TonyK: I don't think that's quite right; the bit-wise comparison would only give true if all bits are 1 in both, wouldn't it? You would need to do a disjunction of all the individual bit-comparisons. I recall you can easily extract the last bit, and shuffle to the right, so a simple loop-with-escape will do it. –  Arturo Magidin Nov 20 '10 at 21:53
7  
in C-style languages, 'if (a & b)' evaluates to 'true' whenever a and b have at least one bit in common. –  TonyK Dec 9 '10 at 19:49

Yes.

We only need to know how many powers of two appear in the prime factorization of C(n,p). The number of powers of two that appear in the prime factorization of $n!$ is $\lfloor n/2 \rfloor + \lfloor n/4 \rfloor + \lfloor n/8 \rfloor + \cdots$ -- count all the multiples of two, of four, of eight, and so on. This turns out to be $n$ minus the number of ones in the binary expansion of $n$.

It turns out that this reduces to the following: C(n,p) is odd if and only if every bit of the binary expansion of $p$ is less than or equal to the corresponding bit of the binary expansion of $n$. This is due to Lucas.

share|improve this answer

I already commented with one Wikipedia link above, but I just want to add that if you run the Pascal's triangle recurrence $\bmod 2$ what you get is a sequence of approximations to the Sierpinski triangle. So the result that comes out of Lucas' theorem is an explicit nonrecursive algorithm for plotting the Sierpinski triangle.

I also want to take this opportunity to mention a paper which discusses generalizations of this problem, and which is both quite entertaining to read and perhaps has one of the strangest titles of any math paper: Granville's Zaphod Beeblebrox's Brain and the Fifth-Ninth Row of Pascal's Triangle.

share|improve this answer

Motivated by a duplicated question that has been asked today, I'd like to offer an alternative approach to the problem.

Let $C_n^r$ be the set of subsets of $\{1,\ldots,n\}$ that have cardinal $r$. Define the function $\sigma:C_n^r\to C_n^r$ given by $$k\in\sigma(A)\Leftrightarrow n-k\in A$$ Let $S_n^r$ be the set of the fixed points of $\sigma$ and $T_n^r=C_n^r-S_n^r$. It is clear that $f\circ f=id$. Thus, $|T_n^r|$ is even and $|C_n^r|$ and $|S_n^r|$ have the same parity.

Let's study the parity of $|S_n^r|$. Represent each element of $A\in S_n^r$ with a binary word of length $n$ whose $k$th digit is $1$ if $k\in A$ and $0$ otherwise. So, the elements of $S_n^r$ are the symmetric words. For each of these symmetric words:

  • If $n$ is odd, there is a central digit. If $r$ is odd it must be $1$, otherwise $0$. Any case, the word is determined by the $\lfloor n/2\rfloor$ first digits and $\lfloor r/2\rfloor$ of these digits are $1$'s. Therefore, $$|S_n^r|=\binom{\lfloor n/2\rfloor}{\lfloor r/2\rfloor}$$

  • If $n$ is even, $r$ must be even and there must be $r/2$ of $1$'s each side. Then

$$|S_n^r|=\left\{ \begin{array}{cl} \binom{\lfloor n/2\rfloor}{\lfloor r/2\rfloor}&\text{ if $r$ is even}\\ 0&\text{ otherwise} \end{array} \right.$$

Thus, we have a method that allows to obtain the parity of $\binom nr$ in at most $\log_2 r$ steps.

Example: $$\binom{1000}{376}\equiv\binom{500}{188}\equiv\binom{250}{94}\equiv\binom{125}{47}\equiv\binom{62}{23}\equiv 0\pmod 2$$

share|improve this answer

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.