Number of binomial coefficients among $\binom{n}{k}\;(0\leq k\leq n)$ which are divisible by $p$, where $n = (n_mn_{m - 1}...n_0)_p$ in base $p$

Question

Let $n = (n_mn_{m - 1}...n_0)_p$ in base $p$ . Find the number of binomial coefficients among $$\binom{n}{0},\binom{n}{1},\ldots,\binom{n}{n}$$ that are multiples of $p$ .

What I Tried :- I couldn't think of any good ideas for now but I suppose we can use Lucas's Theorem , but I don't know how to use it here as I am new to Lucas's Theorem . Can anyone help ?

Answer 1

It is enough to find the number of binomial coefficients which are not multiples of $p$. We have to work in the finite field $\mathbb{F}_p$ and the polynomial ring $\mathbb{F}_p[X]$. The number of binomial coefficients $\binom{n}{k}\; (0\leq k\leq n)$, which are not divisible by $p$, is equal to the number of non-zero coeffients in $(1+X)^n$ reduced modulo $p$. We have the following reduction modulo $p$ in the ring $\mathbb{F}_p[X]$

$$(1+X)^{p^j}\equiv(1+X^{p^j})\pmod{p}$$

Then

$$(1+X)^n=\prod_{i=0}^{m}(1+X)^{n_ip^i}\equiv\prod_{i=0}^{m}(1+X^{p^i})^{n_i}\pmod{p}$$

Since $(1+X^{p^i})^{n_i}$ has exactly $(n_i+1)$ non-zero terms modulo $p$, we have that the total number of non-zero terms in $(1+X)^n$ is

$$\prod_{i=0}^{m}(n_i+1)$$

So the number of binomial coefficients which are multiples of $p$ is

$$(n+1)-\prod_{i=0}^{m}(n_i+1)$$

Remark: Following this method one can show that the number of multinomial coefficients in

$$(X_1+X_2+\cdots+X_l)^n$$

which are not divisible by $p$ is exactly

$$\color{red}{\prod_{i=0}^{m}\binom{n_i+l-1}{l-1}}$$