Arrangements and Combinations · Lucas Theorem and the Sierpiński Triangle (Optional)

Lesson 12

Nikolai Chukhin · Alexander S. Kulikov

For \(p=2\), Lucas's theorem becomes especially clean. Since each binary digit is either \(0\) or \(1\), \[\binom{n}{k}\equiv 1\pmod 2\] exactly when every binary \(1\)-digit of \(k\) occurs only in a position where \(n\) also has a \(1\)-digit.

In bit language, this condition is

For example, \(13=(1101)_{2}\). The valid values of \(k\) are obtained by choosing any subset of the three positions where \(13\) has a one. Hence row \(13\) has \(2^{3}=8\) odd entries.