= Kravchuk polynomials
{c}
{title2=$K_s(t;n,q)=\sum_{j=0}^s(-1)^j(q-1)^{s-j}\binom tj\binom{n-t}{s-j}$}
{wiki}
= Krawtchouk polynomials
{c}
{synonym}
These <polynomials> are orthogonal for a <binomial distribution> weight and encode the coefficient transformation in the <MacWilliams identity>. Their <generating function> follows by expanding the two factors:
$$
\sum_{s=0}^nK_s(t;n,q)z^s=(1-z)^t(1+(q-1)z)^{n-t}.
$$
For binary <linear codes>, $q=2$. Expanding the factors gives $K_s(t;n,2)=\sum_j(-1)^j\binom tj\binom{n-t}{s-j}$, where <binomial coefficients> outside their usual integer range are zero. Orthogonality follows by multiplying <generating functions> and summing over $t$ with weight $\binom nt(q-1)^t$: the result is $q^n(1+(q-1)zw)^n$, whose coefficient of $z^rw^s$ is zero for $r\ne s$ and $q^n(q-1)^r\binom nr$ for $r=s$.
Back to article page
