Krawtchouk 多项式定义为：

$$ K_w(k,n)=\sum_{p=0}^{w}(-1)^p{k\choose p}{n-k\choose w-p}$$

一个等价形式是 $$(1-x)^k(1+x)^{n-k}=\sum_{w=0}^{n}K_w(k,n)x^w$$

线性递推公式指的是给定 $n,k$，可以在 $\Theta(n)$ 时间内求出 $K_i(k,n),i\in[0,n]$ 的值。

具体方法

结论是 $(i+1)\times K_{i+1}(k,n)=(n-2k)\times K_{i}(k,n)-(n-i+1)\times K_{i-1}(k,n)$。

证明

分别对 $(1-x)^k(1+x)^{n-k}=\sum_{w=0}^{n}K_w(k,n)x^w$ 两边求导，有：

$$\text{LHS’}=-k(1-x)^{k-1}(1+x)^{n-k}+(n-k)(1-x)^k(1+x)^{n-k-1},\text{RHS’}=\sum_{w=0}^{n}w\times K_w(k,n)x^{w-1}$$

左边求导结果化简一下：$\text{LHS’}=\frac{n-2k-nx}{1-x^2}(1-x)^k(1+x)^{n-k}$。

于是我们得到 $(1-x^2)\sum_{w=1}^{n}w\times K_w(k,n)x^{w-1}=(n-2k-nx)(1-x)^k(1+x)^{n-k}=(n-2k-nx)\sum_{w=0}^{n}K_w(k,n)x^w$。

展开之后有 $\sum_{w=1}^{n}w\times K_w(k,n)x^{w-1}-\sum_{w=1}^{n}w\times K_w(k,n)x^{w+1}=(n-2k)\sum_{w=0}^{n}K_w(k,n)x^w-n\sum_{w=0}^{n}K_w(k,n)x^{w+1}$。

对于展开后的多项式考察 $x$ 次数为 $i$ 的项的左右式系数：

1. 来自 $\sum_{w=1}^{n}w\times K_w(k,n)x^{w-1}$：系数为 $(i+1)\times K_{i+1}(k,n)$。
2. 来自 $\sum_{w=1}^{n}w\times K_w(k,n)x^{w+1}$：系数为 $-(i-1)\times K_{i-1}(k,n)$。
3. 来自 $\sum_{w=0}^{n}K_w(k,n)x^w$：系数为 $(n-2k)\times K_{i}(k,n)$。
4. 来自 $\sum_{w=0}^{n}K_w(k,n)x^{w+1}$：系数为 $-n\times K_{i-1}(k,n)$。

于是得到 $(i+1)\times K_{i+1}(k,n)-(i-1)\times K_{i-1}(k,n)=(n-2k)\times K_{i}(k,n)-n\times K_{i-1}(k,n)$。

$(i+1)\times K_{i+1}(k,n)=(n-2k)\times K_{i}(k,n)-(n-i+1)\times K_{i-1}(k,n)$ 得证。

对于这个三项递推关系，易知 $K_0(k,n)=1,K_1(k,n)=n-2k$，后面的项可以在线性时间内求出。