The Number of Binomial Coefficients Divisible by a Fixed Power of a Prime

n

100

p

2

3

5

7

11

13

17

19

23

29

31

37

41

43

47

0 2	1 2	2 2	3 2	4 2	5 2	6 2
8	8	20	13	20	24	8

There are

n+1

binomial coefficients



n

k



for every non-negative integer

n

. Choose a prime number

p

, and split the

n+1

binomial coefficients into sets according to the highest power of

p

that divides them. This Demonstration uses a combinatorial formula to compute the sizes of these sets. The first set is made up of the binomial coefficients not divisible by

p

.