求证多项式$(x_1+x_2+...+x_N)^{2k}$中全偶项数量≤$a_kN^k$

我来帮你把这个证明的思路理清楚，咱们从问题的核心拆解到具体的统计和上界推导一步步来：

核心问题转换 #

首先，我们把全偶项的条件做个等价转换，让问题更简单：

• 设每个变量$x_i$的指数为$e_i$，全偶项要求每个$e_i$都是偶数，且所有指数之和$\sum_{i=1}^N e_i=2k$。
• 令$e_i=2f_i$（$f_i$是非负整数），代入指数和条件可得：$\sum_{i=1}^N f_i = k$。
• 现在问题就变成了：统计满足这个等式的非负整数组$(f_1,f_2,\dots,f_N)$的个数——这个个数就是原多项式中全偶项的数量。

分类统计指数组合 #

接下来我们按非零$f_i$的个数来分类统计（对应原指数$e_i$中正数的个数）：

• 当恰好有$t$个$f_i$为正（$t$的取值范围是$1≤t≤k$，因为$\sum f_i=k$）：
  1. 先从$N$个变量里选$t$个来分配这些正的$f_i$，选法有$\binom{N}{t}$种；
  2. 对于这$t$个变量，每个$f_i≥1$，令$g_i=f_i-1$（$g_i≥0$），则等式变为$\sum_{i=1}^t g_i = k-t$，这个方程的非负整数解个数是$\binom{(k-t)+t-1}{t-1}=\binom{k-1}{t-1}$。

求和并推导上界 #

把所有$t$对应的组合数加起来，全偶项的总数量就是：
$$\sum_{t=1}^k \binom{N}{t}\binom{k-1}{t-1}$$

现在我们来给这个和找一个只依赖$k$的常数$a_k$，让它不超过$a_kN^k$：

• 首先，$\binom{N}{t}$是从$N$个元素选$t$个的组合数，显然$\binom{N}{t} ≤ \frac{N^t}{t!} ≤ N^t$（因为$t!≥1$）；
• 而$\binom{k-1}{t-1}$是只和$k$有关的常数，根据二项式定理，$\sum_{t=1}^k \binom{k-1}{t-1}=2^{k-1}$；
• 代入后总和可以放缩为：
  $$\sum_{t=1}^k N^t \binom{k-1}{t-1} = N\sum_{t=0}^{k-1} N^t \binom{k-1}{t} = N(1+N)^{k-1}$$
• 进一步放缩：当$N≥1$时，$(1+N)^{k-1} ≤ (2N)^{{k-1}$，所以总和$≤N·(2N)}{k-1}=2^{k-1}Nk$。
• 这里我们取$a_k=2^{k-1}$，它是只依赖$k$的常数，完全满足题目的要求。

当然你也可以用更紧的常数，比如直接用$\sum_{t=1}^k \binom{N}{t}\binom{k-1}{t-1}=\binom{N+k-1}{k}$（这是组合数的卷积公式），而$\binom{N+k-1}{k}$是关于$N$的$k$次多项式，最高次项系数为$\frac{1}{k!}$，所以取$a_k=\frac{1}{k!}$也可以（当$N$足够大时），或者取更大的常数覆盖所有$N≥1$的情况。

举个简单例子验证 #

比如$k=1$时，$(x_1+\dots+x_N)^{2$的全偶项是$x_1}2,x_2^2,\dots,x_N2$，共$N$个，取$a_1=1$，满足$N≤1·N^1$；
$k=2$时，全偶项包括$x_i^{4$（$N$个）和$x_i}2x_j^2$（$\binom{N}{2}$个），总数量是$N+\frac{N(N-1)}{2}=\frac{N(N+1)}{2} ≤ N^2$，取$a_2=1$就完全符合要求。

内容的提问来源于stack exchange，提问作者RothX