Reduction of the sum of the weighted equal powers to explicit combinatorial representation

Full Text

В настоящей работе путём выработки соответствующих доказательств формируется явное комбинаторное представление суммы взвешенных одинаковых степеней (СВОС) натуральных чисел, не использующее проведение операций рекуррентного характера. При этом полагается, что данное комбинаторное представление СВОС содержит основные компоненты, соответственно независимые и зависимые от весовых коэффициентов. Компоненты первого из названных видов будем называть свободными, а компоненты второго вида, как и сами коэффициенты, от которых они зависят, — весовыми. Весовые коэффициенты отображают в СВОС информацию, соответствующую исходному тексту, который требуется передать от источника шифрованных сообщений к их получателю. В доказательствах, обеспечивающих получение комбинаторного представления основных компонентов СВОС, будет использоваться известное комбинаторное выражение СВОС [1, 2] вида max r αr Φp−r 0 ; 0 Φ(p, ν) = (1) r=1 p, ν ∈ N, r = 1, . . . , max r, max r = min(p, ν), 163 Н и к о н о в А. И. где αr , Φp−r 0 — соответственно свободный и весовой компоненты СВОС. Са0 ми же исходные весовые коэффициенты имеют вид bp−k = b0 , p−k k = 0, . . . , p − 1. Здесь полагается, в частности, что сумма взвешенных степеней выражается следующим образом: p(r) br p(r)−τ , p(r) = p − r; Φp−r 0 = τ =0 τ bi p(i)−k , i = r − 1. br p(r)−τ = k=0 Достижение искомого комбинаторного представления СВОС будет производиться ниже сначала применительно к весовому, а затем — к свободному компоненту данной СВОС. Теорема 1. Для чисел вида p, ν, r, bp−k справедливо равенство p−r r Cp−k b0 . p−k Φp−r 0 = (2) k=0 Д о к а з а т е л ь с т в о. В качестве исходного станем рассматривать здесь соотношение, полученное ранее [3]: p−r τ i Ci+τ −k b0 ; p−k Φp−r 0 = τ ∈ {0, . . . , p − r} . (3) τ =0 k=0 Перемену порядка двойного суммирования (3) произведём ниже с учётом заданного формулой (3) неравенства τ k. Перед этим рассмотрим вспомогательный вопрос о нахождении пределов суммирования некоторой целочисленной величины υ(j, l) , когда действует неравенство, связывающее значения её целочисленных индексов j = 1, . . . , max j и l = 0, . . . , max l: l j − 1, или j l + 1. Определим набор парных индексов вида (j, l), ограниченный пределами исходной двойной суммы max j max l υ = υ(j, l), j=1 l j−1 как допустимое множество индексов M ; M = {{j}×{l; l j−1}; j = 1, . . . , max j} = {{j; j l+1}×{l}; l = 0, . . . , max l}. Отсюда видим, что искомые пределы двойного суммирования после перемены его порядка представляют собой границы интервалов: по l — [0, . . . , max l]; по j — [l + 1, . . . , max j]. Тогда исходная двойная сумма приобретает вид max l max j υ 164 = υ(l, j). l=0 j=l+1 Приведение суммы взвешенных одинаковых степеней к явному комбинаторному представлению Используя решение данного вспомогательного вопроса, можно записать: p−r p−r i Ci+τ −k b0 . p−k Φp−r 0 = (4) τ =k k=0 Теперь преобразуем сумму из правой части равенства (4), заключенную в скобки, используя для этого известное комбинаторное правило [4]: p−r i+1 r i Ci+τ −k = C(i+(p−r)−k)+1 = Cp−k . τ =k Следовательно, имеем p−r r Cp−k b0 , p−k Φp−r 0 = k=0 что и завершает доказательство справедливости соотношения (2). Теорема 2. Для чисел p, ν ∈ N, r ∈ {1, . . . , min(p, ν)} свободный компонент СВОС может быть представлен в виде r q (−1)r+q Cr q ν . αr = αr (ν) = 0 0 (5) q=1 Д о к а з а т е л ь с т в о. Доказательство этой теоремы проведём, используя метод математической индукции и вводя в рассмотрение отсылочные (промежуточные) величины вида ν ν . Нам потребуется также использовать известное выражение свободного компонента СВОС [1, 2] max j(i) αr j(r) j(r) Cj(i) αi , j(i) = j(i)=j(r)+1 гдеj(i) ∈ {1, . . . , max j(i)} ⊂ N, j(r) ∈ {0, . . . , max j(r)} ⊂ N ∪ {0}; max j(i) = ν − i, max j(r) = ν − r. База индукции предусматривает здесь обращение к значению ν = 1 и к соответствующей отсылочной величине 11 . В данном случае, используя вышеприведенное выражение для αr , компонент αr можно выразить следующим 0 j(r) образом: max j(0)=1 αr (1) 0 = α1 (1) 0 j(1) Cj(0) α0 j(0) = j(1)=0 . j(0)=1 1 Отсюда при α0 j(0)=1 = 1 имеем α0 (1) = 1. Это соответствует частному случаю ν = 1 ⇒ r = 1, относящемуся к выражению (5), когда 1 αr (ν)|r=1 0 1 (−1)2 C1 11 = 1. = q=1 165 Н и к о н о в А. И. В рамках индукционного шага будем рассматривать последовательность с членами вида ν ν , каждый из которых можно представлять как Φ(p, ν) = Φ(ν, ν) = Φ(ν, ν, β(ν)); β(ν) = (bp−τ = δp−τ p , τ = 0, . . . , ν − 1), где δp−τ p — символ Кронекера. Другими словами, имеем β(ν) = 1, 0ν−1 ; 0ν−1 — конечная последовательность, состоящая из (ν − 1) нулей. Для ν = n − 1 1 полагаем, что исходное допущение вида (5) справедливо при любом ν n − 1. Тогда, используя рекуррентное комбинаторное представление СВОС [1, 2], имеем n−1 αr (n − 1)Φn−1−r 0 = 0 (n − 1)n−1 = Φ(n − 1, n − 1, β(n − 1)) = r=1 n−1 r q r (−1)r+q Cr q n−1 Cn−1 , (6) = r=1 q=1 β(n − 1) = (bp−τ = δp−τ p , τ = 0, . . . , n − 2) = 1,0n−2 , где 0n−2 — последовательность, содержимое которой состоит из (n − 2) нулей. r Множитель Cn−1 из выражения (6) оказывается не чем иным, как числом Φn−1−r 0 , поскольку согласно доказанной выше теореме 1 n−1−r r Cn−1−k bn−1−k . Φn−1−r 0 = k=0 В данном выражении среди всех коэффициентов вида bn−1−k лишь коэффициент bn−1 не равен нулю; он имеет единичное значение. Изменив в выражении (6) порядок двойного суммирования, с учётом неравенства q r получаем: n−1 n−1 q r (−1)r+q Cr Cn−1 q n−1 . Φ(n − 1, n − 1, β(n − 1)) = q=1 r=q Далее используем известное комбинаторное тождество [4], связанное с произведением двух биноминальных коэффициентов: n−1 n−1 q r−q (−1)r+q Cn−1 Cn−1−q q n−1 = Φ(n − 1, n − 1, β(n − 1)) = q=1 r=q n−1 q Cn−1 q n−1 Aq (n − 1); (7) = q=1 n−1 r−q (−1)r+q Cn−1−q . Aq (n − 1) = r=q 166 (8) Приведение суммы взвешенных одинаковых степеней к явному комбинаторному представлению Значениям числа q на основании другого известного тождества могут быть поставлены в соответствие следующие значения, относящиеся к выражению (8): 0 : q < n − 1, Aq (n − 1) = 1 : q = n − 1. Как видим, левая и правая части из (7) имеют одинаковое значение: n−1 Φ(n − 1, n − 1, β(n − 1)) = Cn−1 (n − 1)n−1 = (n − 1)n−1 . Следует помнить, что в правой части (7) данное значение появилось с использованием исходного допущения (5). Рассмотрим приращение величины (7), состоящее из двух частей, обозначаемых как ∆Φ1 , ∆Φ2 . При этом n−1 n−1 n−1 ∆Φ1 = n−1 ∆Φn−1 (r, q); q=1 q r−q q r−q ∆Φn−1 (r, q) = (−1)r+q (Cn Cn−q q n − Cn−1 Cn−1 q n−1 ), q r, q, r ∈ {1, . . . , n − 1} ; n n ∆Φ2 = n−1 q n−q (−1)n+q Cn Cn−q q n . q (−1)n+q Cn q n = q=1 q=1 Таким образом, получив приращение ∆Φs = ∆Φ1 + ∆Φ2 , n−1 n−1 n−1 величина Φ(n − 1, n − 1, β(n − 1)) перешла на уровень n n q Cn q n Aq (n); r−q (−1)r+q Cn−q . Aq (n) = (9) r=q q=1 Нетрудно видеть, что все значения Aq (n), кроме того, которое соответствует q = n и равно единице, являются нулевыми. Это аналогично тому, что наблюдалось выше применительно к величине Aq (n − 1). Тогда уровень (9) оказывается не чем иным, как величиной Φ(n, n, β(n)) = nn , β(n) = 1,0n−1 ; 0n−1 — последовательность, состоящая из (n − 1) нулей. Произведём теперь возвращение порядка двойного суммирования к его исходному виду, то есть возвратимся к порядку двойного суммирования, характерному для выражения (6). При этом, учитывая справедливость тождества q r q r−q Cn Cn−q = Cr Cn и неравенства r q, будем иметь 167 Н и к о н о в А. И. n n q Cn q n Aq (n) Φ(n, n, β(n)) = r q r (−1)r+q Cr q n Cn = = r=1 q=1 q=1 n αr (n)Φn−r 0 . (10) 0 = r=1 r Здесь биномиальный коэффициент Cn интерпретируется как величина n−r r Cn−k bn−k , Φn−r 0 = bn−k = δn−k n , k=0 а значения весовых коэффициентов вида bn−k берутся из последовательности β(n), участвующей в формировании суммы (10). Итак, с использованием допущения (5) о виде величины αr при ν = n − 1 0 найдено соответствующее комбинаторное представление числа (n−1)n−1 . Поn сле добавления к нему величины ∆Φs n−1 было получено число n , комбинаторное представление которого в виде суммы (10) и её алгебраического компонента αr по своей структуре совпадает с соответствующими величинами 0 Φ(n − 1, n − 1, β(n − 1)), αr (n − 1) 0 из выражения (6) при учёте принятия в (10) числом ν значения, на единицу превышающего (n − 1). Другими словами, из истинности выражений (6), (10) следует, что изменение значения ν с (n − 1) на n вызывает соответствующее изменение свободного компонента СВОС от исходного принятого вида r q (−1)r+q Cr q n−1 , αr (n − 1) = 0 q=1 используемого выражением (6), к виду r q (−1)r+q Cr q n , αr (n) = 0 q=1 используемому выражением (10). Указанные действия и представление используемых величин действительны при всех последовательных изменениях натурального n > 1. Таким образом, данную теорему можно считать доказанной. Тогда основу явного комбинаторного представления СВОС составляет, согласно исходному выражению (1), сумма попарных произведений величин, которые определяются из равенств, доказанных в теоремах 1 и 2: max r max r αr Φp−ro 0 Φ(p, ν) = r=1 p−r r r+q (−1) = r=1 q=1 r Cp−k b0 p−k . q Cr q ν k=0 Данное представление обеспечивает вычисление СВОС, не требующее выполнения рекуррентных переходов от предыдущих к последующим состояниям её свободных и весовых компонентов. 168 Приведение суммы взвешенных одинаковых степеней к явному комбинаторному представлению

About the authors

Alexander I Nikonov

Samara State Technical University

Email: nikonovai@mail.ru
(Dr. Sci. (Tech.)), Professor, Dept. of Electronic Systems and Information Security 244, Molodogvardeyskaya st., Samara, 443100, Russia

References

Supplementary files