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

Полиномы Кравчука или полиномы Кравчука (также написанные с использованием нескольких других транслитераций украинской фамилии Кравчу́к ) — это дискретные ортогональные полиномы , связанные с биномиальным распределением , введенным Михаилом Кравчуком ( 1929 ).Первые несколько полиномов (для q = 2):

{\mathcal {K}}_{0}(x;n)=1,

{\mathcal {K}}_{1}(x;n)=-2x+n,

{\mathcal {K}}_{2}(x;n)=2x^{2}-2nx+{\binom {n}{2}},

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

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

Определение

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

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

Характеристики

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

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

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

Отношения симметрии

Для целых чисел $i,k\geq 0$ , у нас это есть

{\begin{aligned}(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{aligned}}

Отношения ортогональности

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

\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}.

Генерирующая функция

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

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

Трехсрочный рецидив

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

{\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), “Об одном обобщении полиномов Эрмита”. , Comptes Rendus Mathématique (на французском языке), 189 : 620–622, JFM 55.0799.01
Коорнвиндер, Том Х.; Вонг, Родерик СК; Кукук, Рулоф; Свартау, Рене Ф. (2010), «Класс Хана: Определения» , в Олвере, Фрэнке В.Дж .; Лозье, Дэниел М.; Буасверт, Рональд Ф.; Кларк, Чарльз В. (ред.), Справочник NIST по математическим функциям , издательство Кембриджского университета, ISBN 978-0-521-19225-5 , МР 2723248 .
Никифоров А.Ф.; Суслов, СК; Уваров В.Б. (1991), Классические ортогональные полиномы дискретной переменной , Ряды Спрингера в вычислительной физике, Берлин: 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 .
МакВильямс, Ф.Дж.; Слоан, NJA (1977), Теория кодов, исправляющих ошибки , Северная Голландия, ISBN 0-444-85193-3

Внешние ссылки