设 $p$ 为素数，$n$ 为正整数，且 $n=n_0+n_1p+n_2p^2+\cdots+n_tp^t$，其中 $n_i\in\mathbb N^*$，$0\leqslant n_i\leqslant p-1$，$i=0,1,2,\cdots,t$．令 $S_n$ 表示满足下列条件的有序三元数组 $(a,b,c)$ 的集合：
① $a,b,c$ 均为非负整数；
② $a+b+c=n$；
③ $\dfrac{n!}{a!b!c!}$ 不能被 $p$ 整除．
问集合 $S_n$ 中共有多少个有序三元数组 $(a,b,c)$？
① $a,b,c$ 均为非负整数；
② $a+b+c=n$；
③ $\dfrac{n!}{a!b!c!}$ 不能被 $p$ 整除．
问集合 $S_n$ 中共有多少个有序三元数组 $(a,b,c)$？
【难度】
【出处】
2012年全国高中数学联赛江苏省复赛（加试）
【标注】
【答案】
$\mathrm{C}_{n_0+2}^{2}\cdot\mathrm{C}_{n_1+2}^{2}\cdots\mathrm{C}_{n_t+2}^{2}$
【解析】
先证明两个引理．
引理一 对每个 $0\leqslant i\leqslant t$，有$$n_0+n_1+\cdots+n_i\leqslant e_0+e_1+\cdots+e_i.$$引理二 若 $n_0+n_1+\cdots+n_t=e_0+e_1+\cdots+e_t$，则 $n_i=e_i,0\leqslant i\leqslant t$．
引理的证明：对 $n$ 用数学归纳法来证明引理一和引理二．
归纳基础 当 $n=1$ 时，$n_0=1=e_0$，引理一和引理二成立；
递推证明 假设对 $n\leqslant k$，引理一和引理二成立，考虑 $n=k+1$ 的情况．
不妨设$$\begin{split}k+1&=n_0+n_1p+\cdots+n_tp^t\\&=e_0+e_1p+\cdots+e_tp^t,\end{split}$$其中 $0\leqslant n_i\leqslant p-1,e_i\geqslant0,0\leqslant i\leqslant t$，那么$$n_0\equiv e_0\pmod p.$$情形一 若 $n_0\ne0$，则 $1\leqslant n_0\leqslant p-1$ 且 $e_0\geqslant1$，因此$$\begin{split}k&=(n_0-1)+n_1p+\cdots+n_tp^t\\&=(e_0-1)+e_1p+\cdots+e_tp^t,\end{split}$$利用归纳假设，有$$(n_0-1)+n_1+\cdots+n_i\leqslant (n_0-1)+e_1+\cdots+e_i,$$即$$n_0+n_1+\cdots+n_i\leqslant e_0+e_1+\cdots+e_i,0\leqslant i\leqslant t,$$从而引理一成立．
如果 $n_0+n_1+\cdots+n_t=e_0+e_1+\cdots+e_t$，那么$$(n_0-1)+n_1+\cdots+n_t\leqslant(e_0-1)+e_1+\cdots+e_t,$$利用归纳假设，有$$n_0-1=e_0-1,n_1=e_1,\cdots,n_t=e_t,$$从而 $n_i=e_i,0\leqslant i\leqslant t$．
引理二成立．
情形二 若 $n_0=0$，则 $p\mid e_0$．
不妨设 $e_0=p\cdot e_0'$，那么$$\dfrac{k+1}{p}=n_1+n_2p+\cdots+n_tp_{t-1}=(e_0'+e_1)+e_2p+\cdots+e_tp^{t-1}\qquad\cdots\cdots\text{ ① }$$利用归纳假设，有$$n_1+n_2+\cdots+n_i\leqslant(e_0'+e_1)+e_2+\cdots+e_i,$$因此$$\begin{split}n_0+n_1+\cdots+n_i&\leqslant e_0'+e_1+\cdots+e_i\\&<e_0+e_1+\cdots+e_i,0\leqslant i\leqslant t,\end{split}$$引理一成立．
如果 $n_0+n_1+\cdots+n_t=e_0+e_+\cdots+e_t$，那么$$n_1+n_2+\cdots+n_t=p\cdot e_0'+e_1+\cdots+e_t\qquad\cdots\cdots\text{ ② }$$利用归纳假设，对 $\text{ ① }$，利用引理一，有$$n_1+n_2+\cdots+n_t=e_0'+e_1+\cdots+e_t,$$再利用 $\text{ ② }$，有 $p\cdot e_0'\leqslant e_0'$，则 $e_0'=0$，从而 $n_0=e_0=0$．
因此，由 $\text{ ① }$，有$$n_1+n_2p+\cdots+n_tp^{t-1}=e_1+e_2+\cdots+e_tp^{t-1}=\dfrac{k+1}{p}\leqslant k,$$且有$$n_1+n_2+\cdots+n_t=e_1+e_2+\cdots+e_t.$$利用归纳假设，有$$n_i=e_i,1\leqslant i\leqslant t,$$从引理二成立．
综上所述，引理一、引理二均成立．
接下来证明原命题：
设 $p$ 为素数，$n$ 为正整数，如果 $p^a\mid n$，但 $p^{a+1}\nmid n$，那么记 $V_{p}(n)=a$，于是$$V_p(n!)=\sum\limits_{k=1}^{+\infty}{\left[\dfrac{n}{p^k}\right]},$$若 $n=n_2+n_1p+\cdots+n_tp^t$，$0\leqslant n_i\leqslant p-1,0\leqslant i\leqslant t$，则$$V_p(n!)=\dfrac{n-(n_0+n_1+\cdots+n_t)}{p-1}\qquad\qquad\cdots\cdots\text{ ③ }$$不妨设$$\begin{cases}n=n_0+n_1p+\cdots+n_tp^t,&0\leqslant n_i\leqslant p-1,\\a=a_0+a_1p+\cdots+a_tp^t,&0\leqslant a_i\leqslant p-1,\\b=b_0+b_1p+\cdots+b_tp^t,&0\leqslant b_i\leqslant p-1,\\c=c_0+c_1p+\cdots+c_tp^t,&0\leqslant c_i\leqslant p-1,\end{cases}$$其中 $n=a+b+c$，那么 $p\nmid\dfrac{n!}{a!b!c!}$，当且仅当$$V_p(n!)=C_p(a!)+V_p(b!)+V_p(c!).$$利用 $\text{ ③ }$，可知 $p\nmid\dfrac{n!}{a!b!c!}$ 当且仅当$$\sum\limits_{i=0}^{t}{n_i}=\sum\limits_{i=0}^{t}{(a_i+b_i+c_i)}.$$再利用引理一、引理二，有 $p\nmid\dfrac{n!}{a!b!c!}$ 当且仅当$$n_i=a_i+b_i+c_i , 0\leqslant i\leqslant t.$$因此，满足条件的有序三元数组 $(a,b,c)$ 的个数为$$|S_n|=\mathrm{C}_{n_0+2}^{2}\cdot\mathrm{C}_{n_1+2}^{2}\cdots\mathrm{C}_{n_t+2}^{2}.$$
引理的证明：对 $n$ 用数学归纳法来证明引理一和引理二．
不妨设$$\begin{split}k+1&=n_0+n_1p+\cdots+n_tp^t\\&=e_0+e_1p+\cdots+e_tp^t,\end{split}$$其中 $0\leqslant n_i\leqslant p-1,e_i\geqslant0,0\leqslant i\leqslant t$，那么$$n_0\equiv e_0\pmod p.$$
如果 $n_0+n_1+\cdots+n_t=e_0+e_1+\cdots+e_t$，那么$$(n_0-1)+n_1+\cdots+n_t\leqslant(e_0-1)+e_1+\cdots+e_t,$$利用归纳假设，有$$n_0-1=e_0-1,n_1=e_1,\cdots,n_t=e_t,$$从而 $n_i=e_i,0\leqslant i\leqslant t$．
引理二成立．
不妨设 $e_0=p\cdot e_0'$，那么$$\dfrac{k+1}{p}=n_1+n_2p+\cdots+n_tp_{t-1}=(e_0'+e_1)+e_2p+\cdots+e_tp^{t-1}\qquad\cdots\cdots\text{ ① }$$利用归纳假设，有$$n_1+n_2+\cdots+n_i\leqslant(e_0'+e_1)+e_2+\cdots+e_i,$$因此$$\begin{split}n_0+n_1+\cdots+n_i&\leqslant e_0'+e_1+\cdots+e_i\\&<e_0+e_1+\cdots+e_i,0\leqslant i\leqslant t,\end{split}$$引理一成立．
如果 $n_0+n_1+\cdots+n_t=e_0+e_+\cdots+e_t$，那么$$n_1+n_2+\cdots+n_t=p\cdot e_0'+e_1+\cdots+e_t\qquad\cdots\cdots\text{ ② }$$利用归纳假设，对 $\text{ ① }$，利用引理一，有$$n_1+n_2+\cdots+n_t=e_0'+e_1+\cdots+e_t,$$再利用 $\text{ ② }$，有 $p\cdot e_0'\leqslant e_0'$，则 $e_0'=0$，从而 $n_0=e_0=0$．
因此，由 $\text{ ① }$，有$$n_1+n_2p+\cdots+n_tp^{t-1}=e_1+e_2+\cdots+e_tp^{t-1}=\dfrac{k+1}{p}\leqslant k,$$且有$$n_1+n_2+\cdots+n_t=e_1+e_2+\cdots+e_t.$$利用归纳假设，有$$n_i=e_i,1\leqslant i\leqslant t,$$从引理二成立．
综上所述，引理一、引理二均成立．
接下来证明原命题：
设 $p$ 为素数，$n$ 为正整数，如果 $p^a\mid n$，但 $p^{a+1}\nmid n$，那么记 $V_{p}(n)=a$，于是$$V_p(n!)=\sum\limits_{k=1}^{+\infty}{\left[\dfrac{n}{p^k}\right]},$$若 $n=n_2+n_1p+\cdots+n_tp^t$，$0\leqslant n_i\leqslant p-1,0\leqslant i\leqslant t$，则$$V_p(n!)=\dfrac{n-(n_0+n_1+\cdots+n_t)}{p-1}\qquad\qquad\cdots\cdots\text{ ③ }$$不妨设$$\begin{cases}n=n_0+n_1p+\cdots+n_tp^t,&0\leqslant n_i\leqslant p-1,\\a=a_0+a_1p+\cdots+a_tp^t,&0\leqslant a_i\leqslant p-1,\\b=b_0+b_1p+\cdots+b_tp^t,&0\leqslant b_i\leqslant p-1,\\c=c_0+c_1p+\cdots+c_tp^t,&0\leqslant c_i\leqslant p-1,\end{cases}$$其中 $n=a+b+c$，那么 $p\nmid\dfrac{n!}{a!b!c!}$，当且仅当$$V_p(n!)=C_p(a!)+V_p(b!)+V_p(c!).$$利用 $\text{ ③ }$，可知 $p\nmid\dfrac{n!}{a!b!c!}$ 当且仅当$$\sum\limits_{i=0}^{t}{n_i}=\sum\limits_{i=0}^{t}{(a_i+b_i+c_i)}.$$再利用引理一、引理二，有 $p\nmid\dfrac{n!}{a!b!c!}$ 当且仅当$$n_i=a_i+b_i+c_i , 0\leqslant i\leqslant t.$$因此，满足条件的有序三元数组 $(a,b,c)$ 的个数为$$|S_n|=\mathrm{C}_{n_0+2}^{2}\cdot\mathrm{C}_{n_1+2}^{2}\cdots\mathrm{C}_{n_t+2}^{2}.$$
答案
解析
备注
