Summation on the basis of combinatorial representation of equal powers

Full Text

Комбинаторным представлением какого-либо математического соотношения мы называем такое его представление, которое производится с применением объектов комбинаторики, например, сочетаний и выражений на их основе [1-4]. В комбинаторном представлении математических выражений можно выделить представление сумм одинаковых степеней [5, 6], в том числе сумм взвешенных одинаковых степеней [7, 8]. Явное комбинаторное представление суммы взвешенных одинаковых степеней (СВОС) выглядит следующим образом [8]: p max ι  ν Φoc (p, ν) = ι+q bl l = l=1  ι (-1)  ι=1 q=1 p-ι q Cι q ν  ι Cp-k bp-k , (1) k=0 © 2016 Самарский государственный технический университет. Образец для цитирования Н и к о н о в А. И. Суммирование на основе комбинаторного представления одинаковых степеней // Вестн. Сам. гос. техн. ун-та. Сер. Физ.-мат. науки, 2016. T. 20, № 1. С. 149-157. 149 Н и к о н о в А. И. где p - число одночленов, в данном случае с весовыми коэффициентами вида bl ∈ R, p ∈ N; ν - одинаковая степень натуральных чисел вида l, ν ∈ N; max ι = min(p, ν). Целью настоящей статьи является получение комбинаторных выражений для сумм членов нескольких последовательностей взвешенного типа, которое производится на основе комбинатроного представления СВОС вида (1). Этими последовательностями, рассматриваемыми в первой части данной статьи, являются геометрическая прогрессия (ГП), простая арифметико-геометрическая прогрессия (АГП), простая комбинированная прогрессия (КП) [9-11]. Они играют, в частности, заметную роль в описании процессов шифрования с участием сумм со слагаемыми-произведениями свободных и весовых компонентов [11]. Во второй части нашей статьи рассматривается вывод двух комбинаторных тождеств с участием свободных компонентов СВОС. Целочисленные аргументы, рассматриваемые в настоящем исследовании, позволяют обеспечить как приближённую оценку суммируемых членов прогрессий, так и их точную оценку в случае наличия рациональных значений знаменателей данных сумм. Исследование второго из указанных выше комбинаторных тождеств (вторая часть нашей статьи) избавлено от целочисленного характера. В дальнейшем для краткости мы будем иногда именовать каждую из рассматриваемых прогрессий взвешенной. Сумма членов любой из данных прогрессий относится к многочленам одной переменной, но имеет и специфическое вышеприведённое название, основанное на названии соответствующей последовательности [11]. Сумма взвешенной геометрической прогрессии с целочисленным знаменателем ρ - числом одночленов в данном случае с весовыми коэффициентами вида bνl = bν выглядит следующим образом: max ν bν ρν , Φгп (ρ, max ν) = bν ∈ R. ν=min ν Для определённости примем min ν = 1; max ν = p ∈ N. ˜ Введём в рассмотрение матрицу взвешенных членов, см. рис. 1. Её строка состоит из взвешенных членов последовательности (bν lν , l = 1, . . . , p) . Суммы членов взвешенной геометрической прогрессии для знаменателей p, p - 1 и степенного показателя ν = p - k, ˜ k = 0, 1, . . . , p - 1 ˜ будут соответствовать набору элементов СВОС произвольной строки рассматриваемой матрицы, а также набору указанных элементов, простирающихся лишь до двойной линии, проведённой в этой матрице. Аналитически данное рассуждение может быть выражено таким образом: p-1 ˜ p ˜ ν Φгп (p, p) = ˜ bν p , ν=1 150 bν (p - 1)ν , Φгп (p - 1, p) = ˜ ν=1 (2) Суммирование на основе комбинаторного представления. . . Рис. 1. Матрица взвешенных членов для ГП [Figure 1. A suspended members matrix for geometric progression] причем ∆Φгп (p, p) = Φoc (p, ν) - Φoc (p - 1, ν) = bν pν . ˜ (3) Из формулы (3) находим: p ˜ p ˜ bν pν = Φгп (p, p) = ˜ ν=1 ∆Φгп (p, p). ˜ (4) ν=1 Здесь величины Φoc (p, ν), Φoc (p - 1, ν) - это суммы взвешенных одинаковых степеней с числом элементов соответственно p, p - 1 и одинаковым показателем ν. Подставив в выражение (4) формулу (1) с параметрами p, p - 1, получим следующее: p ˜ Φгп (p, p) = ˜ bν Aν ; ν=1 max ι Aν =   ι q ι (-1)ι+q Cι q ν  Cp .  ι=1 (5) q=1 Совокупность выражений (5) и есть искомая комбинаторная формула суммы взвешенных членов ГП, соответствующая представлению (2). Использовав теперь непосредственную подстановку в формулу (1) значения l = 0, будем иметь ∆Φгп (p, ν = 0) = ∆Φгп (p, 0) ι=0,q=0 0 0 0 = b0 (-1)0 C0 δ0ν Cp = b0 , где b0 - задаваемый весовой коэффициент с нулевым индексом; δ0ν - символ Кронекера, вводимый сюда, поскольку член 00 принято считать не имеющим смысла. 151 Н и к о н о в А. И. Тогда формула суммы взвешенных членов ГП (5) получает модифицированный вид p ˜ Φгп (p, p) = ˜ bν Aνδ ; ν=0 max ι Aνδ =   ι q ι (-1)ι+q Cι (q + δ0ν )ν  Cp .  ι=0 (6) q=0 Этот вид соответствует такому представлению ГП, как p ˜ bν pν , Φгп (p, p) = ˜ ν=0 что, в свою очередь, связано с добавлением в матрицу взвешенных членов на рис. 1 новой нижней строки b0 l0 = b0 , . . . l = 1, . . . , p . Как видим, выражение (6) позволяет расширить область действия формулы (5). Тем не менее, далее в настоящей работе случаи нулевого нижнего предела определяемых ниже сумм рассматриваться не будут, поскольку данные суммы имеют в таких случаях, в отличие от суммы взвешенной ГП, лишь нулевые значения. Простая форма представления суммы членов взвешенной АГП имеет вид p ˜ p ˜ bν νpν = Φагп (p, p) = ˜ ν=1 bν pν ; bν = bν ν. (7) ν=1 Тогда искомая формула комбинаторного представления суммы Φагп , записанной в виде (7), будет выражаться в соответствии с соотношением (4) как p ˜ Φагп (p, p) = ˜ bν Aν . (8) ν=1 Структуры выражений (7) и (2) соответствуют друг другу, и ясно, что матрица взвешенных членов для простой взвешенной АГП будет аналогична матрице для взвешенной ГП с учетом, естественно, равенства (8). Этот учет дает возможность применить к выражению (8) формулу СВОС для единичной одинаковой степени со значениями соответствующего коэффициента 1 ν 1 = 1 и с весовыми коэффициентами в bν Aν = bν Ap-k при α0 (1) = 1: ˜ p-1 ˜ 1 Cp-k Aν , ˜ p - k = ν; ˜ (9) max ι = max ι(p, ν) = min(p, ν). (10) Φагп = k=0 Соотношения (9), (10) дают искомое комбинаторное представление суммы взвешенных членов простой АГП. 152 Суммирование на основе комбинаторного представления. . . Перейдем теперь к исследованию выражения суммы взвешенных членов простой КП: p ˜ bl (dl)dl , Φкп (p, p) = d ∈ N. (11) l=1 Рассмотрим рис. 2, где изображено положение чисел bl (dl)dl - компонентов выражения (11); слева направо идет нарастание значений l: (dl)dl = ddl ldl , l = 1, . . . , νd = max l, νd = 1, . . . , max νd = p. Рис. 2. Матрица взвешенных членов для простой КП [Figure 2. A suspended members matrix for easy combination progression] Комбинаторная формула суммы взвешенных членов простой КП выводится аналогично формуле суммы взвешенных членов ГП (5) со следующими особенностями: а) ν = dνd ; б) p = p = max νd ; ˜ в) в выводимом выражении присутствует множитель dν . Тогда имеем p bνd ddνd Aνd , Φкп (p, p) = bνd = bmax l ; νd =1 max ι Aνd =   ι q ι (-1)ι+q Cι q ν  Cνd ;  ι=1 (12) q=1 max ι = min(νd , νd ) = νd . Слагаемые из (12) располагаются в строке матрицы на рис. 2 в её первой колонке и правее двойной линии. Переходя к преобразованию (12), видим, что мы можем воспользоваться здесь еще раз, как и при преобразовании формулы (11), выражением (5):     p Φкп (p , νd ) = max ι1 bνd  νd =1 p = dd , ι1 ι q (-1)ι1 +q Cι1 q νd  Cp1  Aνd ,  ι1 =1 q=1 (13) max ι1 = min (p , νd ) . 153 Н и к о н о в А. И. Формула (13) и есть искомое комбинаторное выражение суммы взвешенных членов простой КП. При d = 1 и, соответственно, при p = 1, ν = νd имеет место важный частный случай выражения (13):     p max ι1 bνd  Φкп (p , νd ) = Φкп (1, νd ) = ι1 ι1 =1 νd =1 ι q (-1)ι1 +q Cι1 q νd  Cp1  Aνd ,  q=1 max ι1 = min (p , νd ) = 1. (14) То есть исходя из соотношения (14), получаем p Φкп (1, νd ) = bνd Aνd . νd =1 В заключительной части нашей работы выведем сперва комбинаторное тождество, соответствующее матрице рис. 1. Согласно выражению, аналогичному (3), при bν = 1 имеем ∆Φoc (p, ν) = pν , (15) но в то же время max ι ι ι α0 (ν)Cp , ∆Φoc (p, ν) = max ι = min(p, ν), (16) ι=1 ι где α0 (ν) - свободный компонент СВОС, причем с учетом формулы (1) ι ι α0 (ν) = q (-1)ι+q Cι q ν . q=1 Если принять p ν, то, учитывая (15), (16), получим следующее тождество для свободного компонента СВОС: max ι-1 p α0 (ν) = pν - ι ι α0 (ν)Cp . (17) ι=1 p Используемое для подсчета свободных компонентов вида α0 (ν) тождество (17) позволяет достаточно экономно тратить вычислительные ресурсы на выполнение этого подсчета. При p ν число подсчитываемых свободных компонентов не выходит (поскольку здесь max ι = ν) за рамки числа ν, так что и в данном случае выражение (17) все равно остается справедливым. Наконец, выявим соотношение, связывающее разности последовательных сумм одинаковых степеней и членов ГП: ∆Φoc (rl, l) = Φoc (rl, l) - Φoc (r(l - 1), l) = (rl)l = rl ll ; ∆Φгп (rl, l) = Φгп (rl, l) - Φгп (rl, l - 1) = (rl)l ; 154 Суммирование на основе комбинаторного представления. . . l ∈ N, r ∈ R+ \ [0,1). Мы смогли взять здесь величины ∆Φoc , ∆Φгп , поскольку они именно являются одинаковыми разностями (rl)l последовательных сумм одинаковых степеней и членов ГП, см. рис. 1. Величина ∆Φoc формируется путем использования выражения (1), учета количества одночленов l вида ll и единого множителя rl этих одночленов. В основе формирования величины ∆Φгп лежит использование выражения (5) и учет числа (rl), находящегося в основании степени (rl)l , причем количество этих степеней также равно l. В соответствии с формулой (17) имеем max ι ∆Φoc (rl, l) = (rl ) ι α0 (l)Clι ; ι=1 max ι ι ι α0 (l)Crl ; ∆Φгп (rl, l) = ι=1 max ι в данном случае составляет min(rl, l) = l; ∆Φoc (rl, l) = ∆Φгп (rl, l) = (rl)l . (18) Применяя соотношение (18), получаем max ι max ι r l ι α0 (l)Clι ι ι α0 (l)Crl . = ι=1 (19) ι=1 ι Рассмотрение структуры Crl , содержащей целые числа вида ι, позволяет утверждать, что все используемые в найденном выражении (19) формулы являются конечными. Более того, сомнений в истинности тождества (19) для r - целого положительного начинающегося с единицы числа, естественно, не возникает; таких натуральных чисел r - бесконечное количество. Но тогда, согласно принципу полиномиальной аргументации [12], данное выражение сохраняет свою истинность и для любого вещественного r, лежащего в указанных выше границах.

About the authors

Alexander I Nikonov

Samara State Technical University

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

References

Supplementary files