Полиномы Кравчука

Полиномы Кравчука или полиномы Кравчука (также пишутся с использованием нескольких других транслитераций украинской фамилии Кравчу́к ) — это дискретные ортогональные полиномы , связанные с биномиальным распределением , введенным Михаилом Кравчуком  (1929). Первые несколько полиномов (для q = 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+{\binom {n}{2}},}$

${\displaystyle {\mathcal {K}}_{3}(x;n)=- {\frac {4}{3}}x^{3}+2nx^{2}-(n^{2}- n+{\frac {2}{3}})x+{\binom {n}{3}}.}$

Полиномы Кравчука являются частным случаем полиномов Мейкснера первого рода.

Для любой степени простого числа q и положительного целого числа n определите полином Кравчука

${\displaystyle {\mathcal {K}}_{k}(x;n,q)={\mathcal {K}}_{k}(x)=\sum _{j=0}^{k}( -1)^{j}(q-1)^{kj}{\binom {x}{j}}{\binom {nx}{kj}},\quad k=0,1,\ldots ,n. }$

Полином Кравчука имеет следующие альтернативные выражения:

${\displaystyle {\mathcal {K}}_{k}(x;n,q)=\sum _{j=0}^{k}(-q)^{j}(q-1)^{kj }{\binom {nj}{kj}}{\binom {x}{j}}.}$

${\displaystyle {\mathcal {K}}_{k}(x;n,q)=\sum _{j=0}^{k}(-1)^{j}q^{kj}{\binom {n-k+j}{j}}{\binom {nx}{kj}}.}$

Для целых чисел имеем, что ${\displaystyle i,k\geq 0}$

${\displaystyle {\begin{align}(q-1)^{i}{n \choose i}{\mathcal {K}}_{k}(i;n,q)=(q-1)^{k}{n \choose k}{\mathcal {K}}_{i}(k;n,q).\end{align}}}$

Для неотрицательных целых чисел r , s ,

${\displaystyle \sum _{i=0}^{n}{\binom {n}{i}}(q-1)^{i}{\mathcal {K}}_{r}(i;n,q){\mathcal {K}}_{s}(i;n,q)=q^{n}(q-1)^{r}{\binom {n}{r}}\delta _{r,s}.}$

Производящий ряд полиномов Кравчука приведен ниже. Здесь — формальная переменная.${\displaystyle z}$

${\displaystyle {\begin{aligned}(1+(q-1)z)^{nx}(1-z)^{x}&=\sum _{k=0}^{\infty }{\mathcal {K}}_{k}(x;n,q){z^{k}}.\end{aligned}}}$

Полиномы Кравчука удовлетворяют трехчленному рекуррентному соотношению

${\displaystyle {\begin{aligned}x{\mathcal {K}}_{k}(x;n,q)=-q(n-k){\mathcal {K}}_{k+1}(x;n,q)+(q(n-k)+k(1-q)){\mathcal {K}}_{k}(x;n,q)-k(1-q){\mathcal {K}}_{k-1}(x;n,q).\end{aligned}}}$

• Матрица Кравчука
• Многочлены Эрмита

• Кравчук, М. (1929), «Sur une обобщение полиномов д'Эрмита», Comptes Rendus Mathématique (на французском языке), 189 : 620–622, JFM  55.0799.01
• Коорнвиндер, Том Х.; Вонг, Родерик СК; Кукук, Рулоф; Свартау, Рене Ф. (2010), «Класс Хана: Определения», в Олвере, Фрэнке В.Дж .; Лозье, Дэниел М.; Буасверт, Рональд Ф.; Кларк, Чарльз В. (ред.), Справочник NIST по математическим функциям , издательство Кембриджского университета, ISBN 978-0-521-19225-5, г-н  2723248.
• Никифоров, А.Ф.; Суслов, С.К.; Уваров, В.Б. (1991), Классические ортогональные многочлены дискретной переменной , Springer Series in Computational Physics, Berlin: Springer-Verlag, ISBN 3-540-51123-7, МР  1149380.
• Левенштейн, Владимир И. (1995), «Многочлены Кравчука и универсальные границы для кодов и конструкций в пространствах Хэмминга», IEEE Transactions on Information Theory , 41 (5): 1303–1321, doi :10.1109/18.412678, MR  1366326.
• MacWilliams, FJ; Sloane, NJA (1977), Теория кодов, исправляющих ошибки , North-Holland, ISBN 0-444-85193-3

На Викискладе есть медиафайлы по теме «полиномы Кравчука» .

• Домашняя страница полиномов Кравчука
• «Многочлен Кравчука» на MathWorld