Summation on the basis of combinatorial representation of equal powers

Abstract


In the paper the conclusion of combinatorial expressions for the sums of members of several sequences is considered. Conclusion is made on the basis of combinatorial representation of the sum of the weighted equal powers. The weighted members of a geometrical progression, the simple arithmeticgeometrical and combined progressions are subject to summation. One of principal places in the given conclusion occupies representation of members of each of the specified progressions in the form of matrix elements. The row of this matrix is formed with use of a gang of equal powers with the set weight factor. Besides, in work formulas of combinatorial identities with participation of free components of the sums of equal powers, and also separate power-member of sequence of equal powers or a geometrical progression are presented. All presented formulas have the general basis-components of the sums 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
244, Molodogvardeyskaya st., Samara, 443100, Russian Federation
(Dr. Tech. Sci.; nikonovai@mail.ru), Professor, Dept. of Electronic Systems and Information Security

References

  1. Coolidge J. L. The story of the Binomial Theorem // Amer. Math. Monthly, 1949. vol. 56, no. 3. pp. 147-157. doi: 10.2307/2305028.
  2. Lin Cong On Bernoulli Numbers and Its Properties, 2004. 7 pp., arXiv: math/0408082 [math.HO]
  3. Benjamin A. T., Plott S. S. A combinatorial approach to Fibonomial coefcients // Fibonacci Quarterly, 2008/2009. vol. 46/47, no. 1. pp. 7-9, URL: http://www.fq.math.ca/Papers1/46_47-1/Benjamin_11-08.pdf (дата обращения: 08.08.2015).
  4. Benjamin A. T., Greg O. P., Quinn J. J. A Stirling Encounter with Harmonic Numbers // Mathematics Magazine, 2002. vol. 75, no. 2. pp. 95-103. doi: 10.2307/3219141.
  5. Edwards A. W. F. Sums of Powers of Integers: A Little of the History // The Mathematical Gazette, 1982. vol. 66, no. 435. pp. 22-28. doi: 10.2307/3617302.
  6. Beery J. Sums of Powers of Positive Integers - Introduction: Convergence (July 2010), 2010. doi: 10.4169/loci003284.
  7. Никонов А. И. Преобразование суммы взвешенных степеней натуральных чисел с одинаковыми показателями // Вестн. Сам. гос. техн. ун-та. Сер. Физ.-мат. науки, 2010. № 1(20). С. 258-262. doi: 10.14498/vsgtu751.
  8. Никонов А. И. Приведение суммы взвешенных одинаковых степеней к явному комбинаторному представлению // Вестн. Сам. гос. техн. ун-та. Сер. Физ.-мат. науки, 2012. № 3(28). С. 163-169. doi: 10.14498/vsgtu1099.
  9. Arithmetic and Geometric Series in Ken Ward’s Mathematics Pages, URL: http://www.trans4mind.com/personal_development/mathematics/series/airthmeticGeometricSeries.htm (дата обращения: 08.08.2015).
  10. Riley K. F., Hobson M. P., Bence S. Y. Mathematical Methods for Physics and Engineering. Cambridge: Cambridge University Press, 2006, xxiv+1232 pp. doi: 10.1017/CBO9781139164979.
  11. Никонов А. И. Повышение эффективности шифрования на основе суммирования произведений // Вестн. Сам. гос. техн. ун-та. Сер. Физ.-мат. науки, 2014. № 2(35). С. 199-207. doi: 10.14498/vsgtu1316.
  12. Graham R. L., Knuth D. E., Patashnik O. Concrete mathematics. A foundation for computer science. Reading, MA: Addison-Wesley Publishing Company, 1994. xiv+657 pp.

Statistics

Views

Abstract - 25

PDF (Russian) - 3

Cited-By


PlumX

Dimensions

Refbacks

  • There are currently no refbacks.

Copyright (c) 2016 Samara State Technical University

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.

This website uses cookies

You consent to our cookies if you continue to use our website.

About Cookies