Формула для числа сочетаний с повторениями при ограничениях и её применение | ПДМ. 2013. № 2(20).

Формула для числа сочетаний с повторениями при ограничениях и её применение

Получены различные обобщения понятия числа сочетаний с повторениями. Найдены формулы для вычисления введённых комбинаторных чисел и рассмотрены различные задачи, которые решаются с их применением.

A formula for the number of combinations with constrained repetitions and its application.pdf Введение Всё разнообразие комбинаторных формул может быть фактически выведено из нескольких основных утверждений, касающихся конечных множеств [1, 2]. Тем не менее во многих отношениях полезно вводить различные комбинаторные числа, характеризующие те или иные количественные соотношения на множествах произвольной природы. Классические понятия числа сочетаний, размещений и перестановок в случае возможности дублирования элементов в выборках обобщаются в различных направлениях. Так, в частности, возникают сочетания, размещения и перестановки с повторениями [1]. Существует множество комбинаторных задач, которые можно эффективно решать, не обращаясь всякий раз к основным принципам комбинаторики, например к правилу произведения, а используя различные обобщения основных комбинаторных чисел. Непосредственное прикладное применение комбинаторных чисел связано с подсчётом количества подмультимножеств заданного мультимножества [3], обладающих определёнными свойствами. При этом данная задача может рассматриваться и как универсальный способ построения и классификации комбинаторных чисел в зависимости от задаваемых свойств подмультимножеств. Первичная спецификация мультимножества приводит к задаче подсчета m-эле-ментных подмультимножеств заданного мультимножества с фиксированными весами его элементов. Например, в [4] получена формула для решения данной задачи. В [5] на основе данной формулы получено выражение, более удобное для проведения вычислений. В этой же работе получена формула для числа упорядоченных подмультимно-жеств. Другой подход для определения количества m-элементных подмультимножеств заданного мультимножества через их вторичные спецификации рассматривается в [6]. В данной работе получено несколько новых возможных способов обобщения понятия числа сочетаний с повторениями и рассмотрены некоторые комбинаторные задачи, решаемые с их помощью. В частности, полученные результаты имеют непосредственное применение к задаче о подсчёте количества подмультимножеств заданного мультимножества. 1. Определение числа сочетаний с повторениями при ограничениях Формулировка достаточно общей комбинаторной задачи, приводящей к сочетаниям с повторениями, может быть следующей: имеется большое число предметов, например бесконечное, n различных типов. Необходимо определить, сколько из них можно составить различных m-элементных наборов, не принимая во внимание порядок элементов. В качестве точной формализации понятия k-элементного набора можно рассматривать n-компонентный вектор (x1, ж2,... , xn), где означает количество элементов k-го типа, k = 1,..., n, в соответствующем m-элементном наборе. Следовательно, исходная задача эквивалентна задаче определения количества неотрицательных решений линейного диофантова уравнения Ж1 + Ж2 + ... + жга = m, (1) где Xfc ^ 0, k = 1,... , n. Для числа сочетаний с повторениями в литературе используются различные обозначения, например Cra или fm; будем придерживаться последнего обозначения. Решение задачи (1) дается следующей формулой [1]: fm _ en—1 fn Cn— 1+m^ где Cm — число сочетаний без повторений из n элементов по m элементов. Если в исходной задаче количество элементов каждого типа не является бесконечным, а ограничено некоторым числом, для каждого типа своим, то приходим к понятию числа сочетаний с повторениями при ограничениях. Иными словами, рассмотрим следующую комбинаторную задачу. Имеется n ящиков с конфетами. Разрешается взять ровно m конфет из этих ящиков, причём из k-го ящика разрешается взять не более mfc конфет. Необходимо найти, сколькими способами это можно сделать. Формулировка данной задачи в терминах диофантовых уравнений следующая: необходимо найти количество неотрицательных решений линейного диофантова уравнения (1) при наличии ограничений 0 ^ ^ mk, k = 1,..., n. (2) Обозначим данное число символом fm [m1,m2,... , mn] и будем его называть числом сочетаний с повторениями из n типов элементов по m элементов при (простых) ограничениях, определяемых неравенствами (2). Замечание 1. Несложно проверить, что решение задачи (1), (2), т.е. формула для fm [m1, m2,..., mn], имеет смысл лишь при mk ^ 0 для k = 1,..., n и m1 + m2 + + ... + mn ^ m. Задача (1), (2) также может быть сформулирована как задача подсчёта m-эле-ментных подмультимножеств заданного мультимножества с весами элементов m1, m2, ..., mn. Применяя метод производящих функций, далее мы получим новую формулу для решения задачи (1), (2) и некоторых её обобщений. Отметим, что конфеты в ящиках могут быть упакованы не насыпью, а находиться в коробках или блоках по rj штук, j = 1,...,N. Таким образом, имеется N типов коробок, где в коробке j-го типа находится rj конфет. Замечание 2. В отношении последней задачи возможны два варианта. В первом случае разрешается из каждого ящика брать не более одной коробки конфет. Решение задачи в этом случае будем называть числом сочетаний с повторениями при блочных m1, m2,..., mn Во втором случае ограm n Г1,Г2, . . . ничений на количество коробок нет. Необходимо лишь, чтобы суммарное количество ограничениях и обозначать символом f конфет, взятых из k-го ящика, не превышало m^, k = 1,...,n. Решение второй задачи будем называть числом сочетаний второго типа с повторениями при блочных mbm2,...,mra ограничениях и обозначать символом Fr' m n Г1,Г2,. . . , mn m1 , m2 Интерпретация формулы f m n в терминах числа решений диофан- Г1,Г2, . . . това уравнения (1) приводит к следующим ограничениям для допустимых решений: 0 ^ xfc ^ mfc, xfc Е {г1, Г2,..., rw} , k = 1,..., n, , N, —произвольные целые неотрицательные числа, удовлетворяющие rj} ^ min {mk}. Введём в рассмотрение следующие множества целых чисел (k = 1,... , n): N I (mfc; Г1, Г2,..., rw) = 0) >, j = 1,..., n. где Kj = 1 + ma^^ — + sgn j----, : v ь = 1,..., m (aij Поступая по аналогии, как и ранее, положим в (9) t^ = exp }, k = 1,... ,m. Далее, интегрируя полученное выражение на кубе [—n,n]m по переменным ^, учитывая ортогональность системы функций < exp < — i Е 5fc ^fc f : 5fc Е Z+, k = 1,... , m L L fc=1 ) в пространстве L2 [—n,n]m, приходим к следующему результату: 1 п п f m n Kj f m ^ N (A, b) = / ... / exp —i E bfc^ П E exp ^ ik E aij^ ... d

Ключевые слова

сочетания с повторениями при ограничениях, диофантовы уравнения, формальный полином, производящие функции, мультимножества, combinations with constrained repetitions, Diophantine equations, formal polynomial, generating functions, multisets

Авторы

ФИООрганизацияДополнительноE-mail
Гоцуленко Владимир ВладимировичИнститут технической теплофизики Национальной академии наук Украины (г. Киев)старший научный сотрудник, кандидат технических наук, старший научный сотрудник отдела теплофизических основ энергосберегающих теплотехнологийgosul@ukr.net
Всего: 1

Ссылки

Виленкин Н. Я. Комбинаторика. М.: Наука, 1969. 323 с.
Новиков Ф. А. Дискретная математика для программистов. СПб.: Питер, 2009. 384 с.
Петровский А. Б. Пространства множеств и мультимножеств. М.: УРСС, 2003. 248 с.
MacMahon P. A. Combinatory analysis. Cambridge: The University Press, 1915. 296 p.
Juric Z. and Siljak H. A new formula for the number of combinations and permutations of multisets // Appl. Math. Sci. 2011. V. 5. No. 18. P. 875-881.
Заторский Р. А. Подсчет m-подмультимножеств через их вторичные спецификации // Комбинаторный анализ. Вып. 7. М.: МГУ, 1986. С. 136-145.
Полиа Г., Сеге Г. Задачи и теоремы из анализа. М.: Наука, 1978. 391 с.
 Формула для числа сочетаний с повторениями при ограничениях и её применение | ПДМ. 2013. № 2(20).

Формула для числа сочетаний с повторениями при ограничениях и её применение | ПДМ. 2013. № 2(20).

Полнотекстовая версия