Formalization of combinatorial numbers in terms of entire solutions of systems of linear diophan-tine equations.pdf В работе вводятся в рассмотрение комбинаторные числа размещений с повторениями при различных дополнительных ограничениях [1]. Формулировка достаточно общей комбинаторной задачи, приводящей к размещениям с повторениями при рассматриваемых ограничениях, может быть следующей [2]. Предположим, что имеется N различных ящиков, в каждом из которых находится достаточно большое (например, бесконечное) число конфет q различных видов. Конфеты упакованы по коробкам. Известно, что в i-м ящике (i = 1,... , N) конфеты j-го вида (j = 1,... , q) упакованы в коробки вместительностью по rjs (s = 1,... , n^) штук, где n^ -число объёмов коробок i-го ящика, в которых находятся конфеты j-го вида. Путь также имеется R детей, которым необходимо дать конфеты из этих N ящиков. При этом k-му ребёнку (k = 1,... , R) необходимо дать ровно m^fc конфет j-го вида. Необходимо, чтобы суммарное число конфет всех коробок, взятых из i-го ящика для k-го ребёнка, было равно p^fc, где p^ - фиксированные целые неотрицательные числа. Также требуется, чтобы суммарное число всех конфет j-го вида, розданных всем детям из i-го ящика, было равно наперёд заданному целому неотрицательному числу dj. Любое допустимое распределение конфет q видов R детям из N различных ящиков будем называть обобщённым q-размещением из N по R при жёстких ограничениях. Если безразлично, сколько конфет каждого вида необходимо раздать детям из каждого ящика, то допустимое распределение конфет q видов R детям из N различных ящиков будем называть обобщённым q-размещением из N по R при мягких ограничениях. В последнем случае будем предполагать, что для k-го ребёнка (k = 1,..., R) задано число конфет m^, которые необходимо ему дать из всех N ящиков. Также предполагается заранее заданным pi - суммарное число конфет, которое разрешается взять из i-го ящика (i = 1,... , N). Как в первом, так и во втором случаях на выборку конфет из ящиков возможны различные ограничения. Рассмотрим следующие три типа ограничений: A) Конфеты во всех ящиках находятся не в коробках, а россыпью (т.е. rjs = 1 для всех i, j, s) и из каждого ящика разрешается брать любое допустимое число конфет. B) Из каждого ящика разрешается брать не более одной допустимой коробки конфет каждого вида. C) Разрешается брать любое число допустимых коробок конфет каждого вида из любого ящика. Обозначим через Xj число конфет j-го вида, взятых из i-го ящика k-му ребёнку. Тогда при жёстких ограничениях приходим к следующей системе линейных диофан-товых уравнений (i = 1 , . . . , N, j = 1 , . . . , q, k = 1 , . . . , R) : N q R xijfc mjfc ; У ] xijfc pifc ; У ] xijfc dij. (1) i=1 j=1 fc=1 При мягких ограничениях получается система уравнений N q q R EE Xjjfc = mfc; EE Xjjfc = Pi, i =1,...,N, k =1,...,R. (2) i=1j=1 j=1fc=1 В случае «B» областью допустимых значений для (1) и (2) являются множества ж^ е {j : 1 ^ s ^ j U {0}, i = 1,... , N, j = 1,... , q, k = 1,... , R. (3) Введём в рассмотрение множества целых чисел (i = 1,..., N, j = 1,... , q) Ij = ({j = (P {rjJNxj = {r е ^ ({rjs}Nxnj : r ^ P j , P е N. Тогда для задачи «C» множествами допустимых решений для (1) и (2) являются Г nij I Ea^rjs : а5 е N U {0}, s = 1,...,n U=1 q Nxn, ^•fcе (min{mjfc^fc,} , (rL}Nxn) , i = ^...,^ j = 11...,q, k = 1,... , R. (4 м Таким образом, вычисление введённых комбинаторных чисел сводится к определению числа целых неотрицательных решений систем уравнений (1) или (2) без ограничений, а также при ограничениях (3) или (4). Установлено, что число всех целых неотрицательных решений системы уравнений (1) равно коэффициенту при t^j"1t^2 ... t/K в разложении по возрастающим показателям степеней t111^2 ... t/K следующей производящей функции (а = 1,... , K, в = 1,... , M): -1 ,t2,...,t/) = U ( 1 - П ta a=1 r - 1 n2 V в=1 (r) = (r1, r2) , r1 = 1 + ав где M = NqR, K = Nq + qR + NR, r1 (5) r = 1, ,n1n2, , r2 = 1 + n2 n2 ф (в) = (i, j, k), ф (в) = i, ф (в) = j, Фз (в) = k, Ф21 (в) = (j, k) , Ф22 (в) = (i, k) ^23 (в) = (i,j) ,i = 1 + "1 [в -11 _q . R . в - 1 R в - 1 R 1 + q{ -q k=1+R j M / n^1(e),*2(e) к a вr Ф (t 1, t2 ,...,t*)=n 1+ E nt^ в=1 V fc=1 a=1 в Г*2(в) в '*1(в)Л (6) Аналогично, производящей функцией для определения числа целых неотрицательных решений системы уравнений (1) при ограничениях (4) является функция м к ,t2,...,t/) = П в=1 ав T nta a=1 E (7) q N xn, reJ, ,2з(в) Полагая в (5)-(7) K = R + N, M = RN, 1, если 1 ^ а ^ R, (в) = а, = О, если R +1 ^ а ^ R + N, ^ (в) = а - R, 0 в остальных случаях; mj, если 1 ^ а ^ R, а = i, pk, если R +1 ^ а ^ R + N, а - R = к, получим производящие функции для числа целых неотрицательных решений системы (2) без ограничений, а также соответственно при ограничениях (3) и (4).

Скачать электронную версию публикации