Even/Odd Binomial Coefficients

Question

I was wondering if there's a nice general solution for the following problem:

How many numbers in the $n^\text{th}$ row of Pascal's triangle are even? How many are odd?

Answer 1

I think the criterion for ${n \choose k}$ and prime $p$ is

$$\sum_{j=1}^{\infty}\lfloor n/p^j \rfloor \leq \sum_{j=1}^{\infty} \lfloor k/p^j \rfloor + \sum_{j=1}^{\infty} \lfloor (n-k)/p^j \rfloor.$$

Here's my reasoning. We have

$${n \choose k} = \frac{n!}{k!(n-k)!}.$$

Each factorial picks up a factor of $p$ with each integer multiple: $p, 2p, 3p,$ etc. It picks up another factor of $p$ each time it's an integer multiple of $p^2$. And another when it's an integer multiple of $p^3$. And so forth.

So if the number of factors of $p$ in the numerator exceed that of the denominator, then there's at least one factor of $p$ left over, which means that ${n \choose k}$ is divisible by $p$. If it doesn't, then it's not divisible by $p$.

Answer 2

Kummer proved that the power of $p$ dividing ${n\choose k}$ is the number of carries when $k$ is added to $n-k$ in base $p$.

Say $n$ has base $p$ representation $a_m\ldots a_0$ and $k$ has base $p$ representation $b_m\ldots b_0$. Kummer's theorem shows that $p$ does not divide ${n\choose k}$ if and only if $b_i\leq a_i$ for every $i$. This means, for fixed $n$, the number of such $k$ is $$ \prod_{i=0}^m (a_i+1). $$