Многочлены Кравчука
Общая информация
Формула	${\displaystyle {\mathcal {K))_{n}^{(p)}(x)=(-1)^{n}{\binom {N}{n))p^{n}{}_{2}F_{1}(-n,-x;-N;1/p)}$
Скалярное произведение	${\displaystyle (f,g)=\sum \limits _{x=0}^{N}f(x)g(x)\sigma (x)}$.
Область определения	${\displaystyle x\in {1,2,...N))$
Дополнительные характеристики
Названы в честь	Кравчук, Михаил Филиппович

Многочлены Кравчука (М. Ф. Кравчук, 1929) относятся к классическим ортогональным полиномам дискретной переменной на равномерной сетке, для которых соотношение ортогональности представляет собой не интеграл, а ряд или конечную сумму: ${\displaystyle \sum \limits _{x=0}^{N}k_{n}^{(p)}(x)k_{m}^{(p)}(x)\sigma (x)=d_{n}^{2},\delta _{m,n))$.

Здесь ${\displaystyle \sigma (x)={\binom {N}{x))p^{x}q^{N-x))$ — весовая функция, ${\displaystyle d_{n}={\sqrt ((\binom {N}{n))(pq)^{n))))$ — квадратичная норма, ${\displaystyle 0<p<1,\quad 0<q<1,\quad p+q=1}$. Для ${\displaystyle p=q=1\left/2\right.}$ весовая функция с точностью до постоянного множителя ${\displaystyle 1\left/2^{N}\right.}$ сводится к биномиальному коэффициенту.

Рекуррентное соотношение для этих многочленов имеет вид ${\displaystyle (n+1)k_{n+1}^{(p)}(x)+pq\left(N-n+1\right)k_{n-1}^{(p)}(x)={\bigl [}x+n(p-q)-pN{\bigr ]}k_{n}^{(p)}(x)}$.

Путём несложных преобразований его можно привести к форме

${\displaystyle f_{n+1}{\frac {k_{n+1}^{(p)}(x)}{d_{n+1))}+f_{n}{\frac {k_{n-1}^{(p)}(x)}{d_{n-1))}=\left(rx+\varepsilon n+\Delta \right){\frac {k_{n}^{(p)}(x)}{d_{n))))$,

где

${\displaystyle f_{n}={\sqrt {\frac {n(N+1-n)}{N))},\quad r={\frac {1}{\sqrt {pqN))},\quad \varepsilon =r(p-q),\quad \Delta =-rpN.}$

Многочлены Кравчука могут быть выражены через гипергеометрическую функцию Гаусса:

${\displaystyle k_{n}^{(p)}(x)=(-1)^{n}{\binom {N}{n))p^{n}{}_{2}F_{1}(-n,-x;-N;1/p)}$

В пределе при ${\displaystyle N\to \infty }$ многочлены Кравчука переходят в многочлены Эрмита:

${\displaystyle \lim \limits _{N\to \infty }\left(2/Npq\right)^{n/2}n!;k_{n}^{(p)}\left(Np+{\sqrt {2Npq)),x\right)=H_{n}(x)}$

Первые четыре полинома для простейшего случая ${\displaystyle p=q=1/2}$:

• ${\displaystyle {\mathcal {K))_{0}(x,N)=1}$
• ${\displaystyle {\mathcal {K))_{1}(x,N)=-2x+N}$
• ${\displaystyle {\mathcal {K))_{2}(x,N)=2x^{2}-2Nx+{N \choose 2))$
• ${\displaystyle {\mathcal {K))_{3}(x,N)=-{\frac {4}{3))x^{3}+2Nx^{2}-\left(N^{2}-N+{\frac {2}{3))\right)x+{N \choose 3))$

• Sur une généralisation des polynomes d’Hermite. M. Krawtchouk. C.R.Acad. Sci. 1929. T.189, No.17. P.620 — 622 — статья, в которой впервые введены многочлены Кравчука; по ссылке доступны французский оригинал и переводы на английский и русский языки.
• А. Ф. Никифоров, С. К. Суслов, В. Б. Уваров. Классические ортогональные полиномы дискретной переменной. Москва, «Наука», 1985.
• Krawtchouk Polynomials Home Page — сайт, посвященный многочленам Кравчука, содержит, в частности, обширную библиографию.

• Матрицы Кравчука
• Теорема Мак-Вильямс