Многочлены Кравчука

редактировать

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

$K 0 (x; n) = 1 {\ displaystyle {\ mathcal {K}} _ {0} (x; n) = 1}$ ${\ mathcal {K}} _ {0} (x; n) = 1$
$K 1 (Икс; N) = - 2 Икс + N {\ Displaystyle {\ mathcal {K}} _ {1} (x; n) = - 2x + n}$ ${\ mathcal {K}} _ {1} (x; n) = - 2x + n$
$K 2 (x; n) = 2 x 2 - 2 nx + (n 2) {\ displaystyle {\ mathcal {K}} _ {2} (x; n) = 2x ^ {2} -2nx + {n \ choose 2}}$ ${\ mathcal {K}} _ {2} (x; n) = 2x ^ {2} -2nx + {n \ choose 2}$
$K 3 (x ; n) = - 4 3 x 3 + 2 nx 2 - (n 2 - n + 2 3) x + (n 3). {\ displaystyle {\ mathcal {K}} _ {3} (x; n) = - {\ frac {4} {3}} x ^ {3} + 2nx ^ {2} - (n ^ {2} - n + {\ frac {2} {3}}) x + {n \ choose 3}.}$ ${ \ mathcal {K}} _ {3} (x; n) = - {\ frac {4} {3}} x ^ {3} +2 nx ^ {2} - (n ^ {2} -n + {\ frac {2} {3}}) x + {n \ choose 3}.$

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

Содержание

1 Определение
2 Свойства
- 2.1 Отношения симметрии
- 2.2 Отношения ортогональности
- 2.3 Производящая функция
3 См. Также
4 Ссылки
5 Внешние ссылки

Определение

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

K k (x; n, q) = K k (x) = ∑ j = 0 k (- 1) j (q - 1) k - j (xj) (n - xk - j), k = 0, 1,…, 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) = {\ mathcal {K}} _ {k} (x) = \ sum _ {j = 0} ^ {k} (- 1) ^ {j} (q-1) ^ {kj} {\ binom {x} {j}} {\ binom {nx} {kj}}, \ quad К = 0,1, \ ldots, n.}

Свойства

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

K k (x; n, q) = ∑ j = 0 k (- q) j (q - 1) k - j (n - jk - j) (xj). {\ 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} (- q) ^ {j} (q-1) ^ {kj} {\ binom {nj} {kj}} {\ binom {x } {j}}.}

K k (x; n, q) = ∑ j = 0 k (- 1) jqk - j (n - k + jj) (n - xk - 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 {\ mathcal {K}} _ {k} (x; n, q) = \ sum _ {j = 0} ^ {k} (- 1) ^ {j} q ^ {kj} {\ binom {n-k + j} {j}} {\ binom {nx} {kj}}.}

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

(q - 1) i (ni) K k (i; n, q) = (q - 1) k (nk) K i (k; п, д). {\ 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}}}

{\ 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,

∑ i = 0 n (ni) (q - 1) i K r (i; n, q) K s (i; n, q) = qn (q - 1) r (nr). δ r, с. {\ 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 \ 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 {\ displaystyle z}$ $z$ - формальная переменная.

(1 + (q - 1) z) n - x (1 - z) x = ∑ k = 0 ∞ K k (x; n, q) z k. {\ Displaystyle {\ begin {align} (1+ (q-1) z) ^ {nx} (1-z) ^ {x} = \ sum _ {k = 0} ^ {\ infty} {\ mathcal {K}} _ {k} (x; n, q) {z ^ {k}}. \ End {align}}}

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

См. Также

Литература

Кравчук, М. (1929), «Sur une généralisation des polynomes d'Hermite»., Comptes Rendus Mathématique (на французском языке), 189 : 620–622, JFM 55.0799.01
Коорнвиндер, Том Х.; Wong, Roderick S.C.; Коэкоек, Рулоф; Сварттоу, Рене Ф. (2010), «Класс Хан: Определения», в Олвер, Фрэнк У. Дж. ; Lozier, Daniel M.; Бойсверт, Рональд Ф.; Кларк, Чарльз У. (ред.), Справочник по математическим функциям NIST, Cambridge University Press, ISBN 978-0-521-19225-5, MR 2723248
Никифоров, АФ; Суслов, С.К.; Уваров, В.Б. (1991), Классические ортогональные многочлены дискретной переменной, серии Спрингера в вычислительной физике, Берлин: Springer-Verlag, ISBN 3-540-51123-7, MR 1149380.
Левенштейн, Владимир И. (1995), «Многочлены Кравчука и универсальные границы для кодов и схем в пространствах Хэмминга», IEEE Transactions on Information Theory, 41 (5): 1303–1321, doi : 10.1109 / 18.412678, MR 1366326.
MacWilliams, FJ; Sloane, NJA (1977), Теория кодов с исправлением ошибок, Северная Голландия, ISBN 0-444-85193-3

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

Викискладе есть медиафайлы, связанные с полиномами Кравчука.