МЕТОД УПОРЯДОЧЕНИЯ СОЧЕТАНИЙ ОБЪЕКТОВ В ЗАДАЧАХ СТРУКТУРНОЙ ДИНАМИКИ ТЕХНИЧЕСКИХ СИСТЕМ
8 В. Т. Доможиров
УДК 519.1
В. Т. ДОМОЖИРОВ
МЕТОД УПОРЯДОЧЕНИЯ СОЧЕТАНИЙ ОБЪЕКТОВ В ЗАДАЧАХ СТРУКТУРНОЙ ДИНАМИКИ ТЕХНИЧЕСКИХ СИСТЕМ
Рассматривается проблема упорядочения основных объектов комбинаторного анализа. Приводится метод упорядочения сочетаний.
Ключевые слова: сочетание, порядковый номер сочетания, позиция элемента сочетания.
Введение. Изучение структурной динамики технических и организационных систем во
взаимосвязи с изменениями их свойств базируется на упорядочении структур системы. Упо-
рядочение осуществляется по различным признакам применительно к контексту решаемых
задач. Вместе с тем упорядочение структуры системы реализуется на основе знаний об ее
элементах и связях между ними вне зависимости от прикладного назначения системы. Такое
упорядочение может быть осуществлено с применением метода упорядочения сочетаний,
рассматривающего структуры в качестве объекта комбинаторики. Среди проблем комбина-
торного анализа подобные задачи не обозначены [1—6]. Проблема упорядочения множества
перестановок, размещений, сочетаний и иных комбинаторных конструкций является акту-
альной не только для исследований структур технических систем, но и для изучения много-
параметрических зависимостей и множественных отношений других объектов дискретной
природы.
Упорядочение сочетаний на основе определения их порядкового номера. Рассмот-
рим сочетания из m элементов по k. Общее число сочетаний без повторений определяется из-
вестной формулой [1]
Cmk =
m! k!(m −
k
)!
.
(1)
Поставим задачу упорядочения сочетаний, число которых определяется соотношением
(1). При этом в качестве результата упорядочения сочетаний будем рассматривать их после-
довательность, построенную в виде возрастания порядковых номеров сочетаний.
Рассмотрим некоторое множество из m элементов, представляющих собой позиции для
размещения на них k объектов, обращая внимание при этом только на то, какие из позиций в
рассматриваемом сочетании заняты объектами, и имея в виду, что на одной позиции может
находиться не более одного из k объектов и все объекты размещены.
Присвоим позициям порядковые номера. Упорядочим позиции в соответствии с после-
довательностью их порядковых номеров. Обозначим сочетание последовательностью номе-
ров позиций объектов. Тогда в качестве элементов, образующих сочетание, выступают номе-
ра позиций, занятых объектами, а обозначение, например, сочетания из трех объектов после-
довательностью (3, 6, 12) соответствует тому, что один объект находится на третьей позиции,
один — на шестой, и еще один объект — на двенадцатой позиции. Таким образом, все соче-
тания различаются хотя бы одним из номеров позиций объектов, и если удастся определить
номера сочетаний по номерам позиций образующих их объектов, то поставленная задача бу-
дет решена.
Формально поставленная задача заключается в построении отображения множества
k-элементных подмножеств на множество натуральных чисел.
Примем, что каждое из m чисел соответствует некоторой позиции, которую может за-
нять один из k объектов.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 7
Метод упорядочения сочетаний объектов в задачах структурной динамики технических систем 9
Введем следующие обозначения: I={i |i = 1:k} — множество индексов, I ⊂ N, N — множе-
ство натуральных чисел; B = { bi } — множество позиций, B ⊂ N; bi = (1,m), i =(1,k), m = |B| — число позиций, которые могут быть заняты элементами сочетания, k — число элементов со-
четания; st = ( b1, b2,…, bi, …, bk ) — последовательность k элементов сочетания. Примем, что bi < bj ∀ i, j ∈ I: i < j, bi , bj ∈ B.
Справедливо следующее утверждение.
Утверждение 1. ∀ I = { i } |I |= k B = { bi } |B|= m, k ≤ m, таких что bi < bj , если i < j, где bi, bj ∈ B, i, j∈I, существует отображение
ψ: St→NSt, где NSt∈N, st∈St ⊂ β(B), β(B) — булеан множества B, St — множество подмножеств мощности k множества B, и это отображение задается формулой
k
∑NSt = 1 + Cbii −1 . i=1
Доказательство. Рассмотрим комбинаторное равенство [1, 4]
(2)
Cmk = Cmk −1 + Cmk−−11 .
(3)
Рекурсивно применяя это равенство к последнему слагаемому в правой части, получаем
представление равенства (3) в виде суммы k + 1 слагаемых:
Cmk = Cmk −1 + Cmk −−12 +…+ Cm0 −k −1 .
(4)
Обозначим bk = m, bk-–1 = m–1, …, b1 = m–k+1, b0 = m–k. Перепишем равенство (4) в новых обозначениях:
Cbkk = Cbkk −1 + Cbkk−−11−1 +…+ Cb00 −1 .
(5)
С учетом того, что для любых m > 0, k > 0: m ≥ k, Cbkk = n, где n ∈ N, и того, что Cb00−1 =1, равенство (5) записывается в виде
k
∑NSt = 1 + Cbii −1 . i=1
Приведем без доказательства основные из следствий утверждения 1.
(6)
1. В силу произвольности значений m и k (по условиям утверждения 1) порядковый но-
мер может быть определен для всякого сочетания с произвольным числом элементов, удовле-
творяющим условиям утверждения.
2. Номера k-элементных сочетаний, полученные при меньших значениях m, не изменя-
ются с увеличением общего числа элементов m, на которых рассматриваются k-элементные
сочетания.
3. Если ∀ k: bk= k, то NSt = 1. 4. Равенство (2) определяет правила построения сочетаний в последовательности их поряд-
ковых номеров. Основные правила построения последовательности k-элементных сочетаний:
— в исходном состоянии элементы сочетания размещены на позициях c номерами 1, 2, ..., k;
— для любого сочетания номерá позиций его элементов различны и упорядочены в по-
рядке возрастания;
— очередное сочетание получается из текущего увеличением на единицу номера пози-
ции одного из элементов;
— номер позиции данного элемента сочетания увеличивается на единицу с образовани-
ем очередного сочетания, если на множестве позиций с номерами, не превосходящими номе-
ра позиции данного элемента, не существует пары соседних элементов, номера позиций ко-
торых отличаются больше, чем на единицу; при этом увеличение номера позиции элемента
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 7
10 В. Т. Доможиров
на единицу сопровождается возвращением всех элементов с меньшими номерами позиций в
исходное состояние.
Изложенные правила позволяют строить бесконечную последовательность k-эле-
ментных сочетаний, номера которых удовлетворяют равенству (2).
Определение позиций элементов сочетания по его порядковому номеру. Рассмот-
рим обратную задачу: по порядковому номеру NSt сочетания найти позиции bi, занимаемые каждым i-м элементом из k элементов сочетания.
Решение обратной задачи основывается на следующем утверждении.
Утверждение 2.
Для любых натуральных чисел NSt, bk , m, k, таких что NSt >1, k >0, bk ≥ k, m ≥ k, справедливо равенство
bk = [ k k !(NSt −1) + r(bk, k)],
(7)
где r(bk ,k) > 0 при k >1, r(bk ,k ) = 0 при k=1, [ ] — символ округления. Доказательство. Чтобы подчеркнуть тот факт, что значение bk определено по значе-
нию NSt для k-элементного сочетания, обозначим NSt = NSt (bk, k). Предположим, что имеет место равенство
В силу равенства (2)
k
∑NSt (bk, k)= 1 + Cbii −1 . i=1
(8)
поэтому справедливо неравенство
k
∑ Cbii −1 ≤ Cbkk ,
i=1
(9)
NSt (bk , k ) – 1 ≤ Cbkk , которое запишем в следующем виде:
(10)
NSt (bk , k ) – 1 ≤
bk ! . k !(bk −k)!
(11)
Преобразуя неравенство (11):
(NSt (bk, k )) – 1)k! ≤ (bk – r(bk, k))k,
где r(bk, k) может быть определено из соотношения
(bk – r(bk , k ))k =
bk ! , (bk −k)!
(12)
получаем условие для определения искомого значения bk:
bk ≥ k k !(NSt (bk , k)−1) + r(bk, k ),
(13)
где bk — позиция, занимаемая старшим членом рассматриваемого сочетания. Так как по условиям bk — натуральное число, его значение получаем, округляя значение
правой части неравенства (13):
bk = [ k k !(NSt −1) + r(m, k)].
(14)
Применим доказанное утверждение для решения сформулированной обратной задачи.
Значение bk — номера позиции k-го элемента сочетания — найдено при доказательстве утверждения. Найдем номер позиции (k–1)-го элемента сочетания. Для этого полученное зна-
чение bk подставляем в равенство (8), используя соотношение (3):
NSt (bk, k ) – 1 = Cbkk −1 + Cbkk−−11 .
(15)
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 7
Метод упорядочения сочетаний объектов в задачах структурной динамики технических систем 11
Обозначим
NSt (bk–1, (k–1)) = NSt (bk, k ) – Cbkk −1 и запишем равенство (15) в следующем виде:
(16)
NSt (bk–1, (k–1)) – 1 = Cbkk−−11−1 + Cbkk−−22 −1 +…+ Cb11−1 .
(17)
Используя соотношения (8)—(14), находим значение номера позиции bk–1. Для нахожде-
ния номеров позиций остальных элементов сочетания повторяем процедуру, определяемую
соотношениями (8)—(17). Следует заметить, что в силу существенной дискретности последо-
вательности величин Cmk при решении обратной задачи достаточно использовать прибли-
женное значение величины r(m,k), которое в практических случаях может быть принято рав-
ным k/2.
Совокупность правил построения сочетаний в последовательности их порядковых но-
меров и процедур нахождения номеров позиций элементов сочетания по его номеру состав-
ляет метод упорядочения сочетаний.
Таким образом, изложенный в настоящей статье метод упорядочения сочетаний опреде-
ляет способ построения бесконечной последовательности k-элементных сочетаний, а также
устанавливает однозначную зависимость между порядковым номером k-элементного сочета-
ния в этой последовательности сочетаний и набором позиций образующих его элементов.
Рассмотренный метод находит применение в исследованиях структурно-функцио-
нальной динамики сложных систем, в задачах живучести (выживаемости) сложных систем,
при разработке реляционных баз данных для реализации отношений „многие-ко-многим“ без
введения дополнительных отношений в структуру базы данных, а также в других приложени-
ях, реализующих многозначные отношения.
СПИСОК ЛИТЕРАТУРЫ
1. Виленкин Н. Я., Виленкин А. Н., Виленкин П. А. Комбинаторика. М.: ФИМА, МЦНМО, 2006. 400 с.
2. Липский В. Комбинаторика для программистов. М.: Мир, 1988. 213 с.
3. Баннаи Э., Ито Т. Алгебраическая комбинаторика. Схемы отношений. М.: Мир, 1987. 375 с.
4. Комбинаторный анализ. Задачи и упражнения: Учеб. пособие / Под ред. К. А. Рыбникова. М.: Наука, 1982. 368 с.
5. Цвиркун А. Д. Основы синтеза структуры сложных систем. М.: Наука, 1982. 200 с.
6. Харари Ф., Палмер Э. Перечисление графов. М.: Мир, 1977. 324 с.
Сведения об авторе Виктор Трофимович Доможиров — д-р воен. наук; Научно-производственная фирма „Центральное конст-
рукторское бюро арматуростроения“, Санкт-Петербург; зам. директора по научной работе; E-mail: domojirov@ckba.ru
Рекомендована СПИИРАН
Поступила в редакцию 28.04.09 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 7
УДК 519.1
В. Т. ДОМОЖИРОВ
МЕТОД УПОРЯДОЧЕНИЯ СОЧЕТАНИЙ ОБЪЕКТОВ В ЗАДАЧАХ СТРУКТУРНОЙ ДИНАМИКИ ТЕХНИЧЕСКИХ СИСТЕМ
Рассматривается проблема упорядочения основных объектов комбинаторного анализа. Приводится метод упорядочения сочетаний.
Ключевые слова: сочетание, порядковый номер сочетания, позиция элемента сочетания.
Введение. Изучение структурной динамики технических и организационных систем во
взаимосвязи с изменениями их свойств базируется на упорядочении структур системы. Упо-
рядочение осуществляется по различным признакам применительно к контексту решаемых
задач. Вместе с тем упорядочение структуры системы реализуется на основе знаний об ее
элементах и связях между ними вне зависимости от прикладного назначения системы. Такое
упорядочение может быть осуществлено с применением метода упорядочения сочетаний,
рассматривающего структуры в качестве объекта комбинаторики. Среди проблем комбина-
торного анализа подобные задачи не обозначены [1—6]. Проблема упорядочения множества
перестановок, размещений, сочетаний и иных комбинаторных конструкций является акту-
альной не только для исследований структур технических систем, но и для изучения много-
параметрических зависимостей и множественных отношений других объектов дискретной
природы.
Упорядочение сочетаний на основе определения их порядкового номера. Рассмот-
рим сочетания из m элементов по k. Общее число сочетаний без повторений определяется из-
вестной формулой [1]
Cmk =
m! k!(m −
k
)!
.
(1)
Поставим задачу упорядочения сочетаний, число которых определяется соотношением
(1). При этом в качестве результата упорядочения сочетаний будем рассматривать их после-
довательность, построенную в виде возрастания порядковых номеров сочетаний.
Рассмотрим некоторое множество из m элементов, представляющих собой позиции для
размещения на них k объектов, обращая внимание при этом только на то, какие из позиций в
рассматриваемом сочетании заняты объектами, и имея в виду, что на одной позиции может
находиться не более одного из k объектов и все объекты размещены.
Присвоим позициям порядковые номера. Упорядочим позиции в соответствии с после-
довательностью их порядковых номеров. Обозначим сочетание последовательностью номе-
ров позиций объектов. Тогда в качестве элементов, образующих сочетание, выступают номе-
ра позиций, занятых объектами, а обозначение, например, сочетания из трех объектов после-
довательностью (3, 6, 12) соответствует тому, что один объект находится на третьей позиции,
один — на шестой, и еще один объект — на двенадцатой позиции. Таким образом, все соче-
тания различаются хотя бы одним из номеров позиций объектов, и если удастся определить
номера сочетаний по номерам позиций образующих их объектов, то поставленная задача бу-
дет решена.
Формально поставленная задача заключается в построении отображения множества
k-элементных подмножеств на множество натуральных чисел.
Примем, что каждое из m чисел соответствует некоторой позиции, которую может за-
нять один из k объектов.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 7
Метод упорядочения сочетаний объектов в задачах структурной динамики технических систем 9
Введем следующие обозначения: I={i |i = 1:k} — множество индексов, I ⊂ N, N — множе-
ство натуральных чисел; B = { bi } — множество позиций, B ⊂ N; bi = (1,m), i =(1,k), m = |B| — число позиций, которые могут быть заняты элементами сочетания, k — число элементов со-
четания; st = ( b1, b2,…, bi, …, bk ) — последовательность k элементов сочетания. Примем, что bi < bj ∀ i, j ∈ I: i < j, bi , bj ∈ B.
Справедливо следующее утверждение.
Утверждение 1. ∀ I = { i } |I |= k B = { bi } |B|= m, k ≤ m, таких что bi < bj , если i < j, где bi, bj ∈ B, i, j∈I, существует отображение
ψ: St→NSt, где NSt∈N, st∈St ⊂ β(B), β(B) — булеан множества B, St — множество подмножеств мощности k множества B, и это отображение задается формулой
k
∑NSt = 1 + Cbii −1 . i=1
Доказательство. Рассмотрим комбинаторное равенство [1, 4]
(2)
Cmk = Cmk −1 + Cmk−−11 .
(3)
Рекурсивно применяя это равенство к последнему слагаемому в правой части, получаем
представление равенства (3) в виде суммы k + 1 слагаемых:
Cmk = Cmk −1 + Cmk −−12 +…+ Cm0 −k −1 .
(4)
Обозначим bk = m, bk-–1 = m–1, …, b1 = m–k+1, b0 = m–k. Перепишем равенство (4) в новых обозначениях:
Cbkk = Cbkk −1 + Cbkk−−11−1 +…+ Cb00 −1 .
(5)
С учетом того, что для любых m > 0, k > 0: m ≥ k, Cbkk = n, где n ∈ N, и того, что Cb00−1 =1, равенство (5) записывается в виде
k
∑NSt = 1 + Cbii −1 . i=1
Приведем без доказательства основные из следствий утверждения 1.
(6)
1. В силу произвольности значений m и k (по условиям утверждения 1) порядковый но-
мер может быть определен для всякого сочетания с произвольным числом элементов, удовле-
творяющим условиям утверждения.
2. Номера k-элементных сочетаний, полученные при меньших значениях m, не изменя-
ются с увеличением общего числа элементов m, на которых рассматриваются k-элементные
сочетания.
3. Если ∀ k: bk= k, то NSt = 1. 4. Равенство (2) определяет правила построения сочетаний в последовательности их поряд-
ковых номеров. Основные правила построения последовательности k-элементных сочетаний:
— в исходном состоянии элементы сочетания размещены на позициях c номерами 1, 2, ..., k;
— для любого сочетания номерá позиций его элементов различны и упорядочены в по-
рядке возрастания;
— очередное сочетание получается из текущего увеличением на единицу номера пози-
ции одного из элементов;
— номер позиции данного элемента сочетания увеличивается на единицу с образовани-
ем очередного сочетания, если на множестве позиций с номерами, не превосходящими номе-
ра позиции данного элемента, не существует пары соседних элементов, номера позиций ко-
торых отличаются больше, чем на единицу; при этом увеличение номера позиции элемента
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 7
10 В. Т. Доможиров
на единицу сопровождается возвращением всех элементов с меньшими номерами позиций в
исходное состояние.
Изложенные правила позволяют строить бесконечную последовательность k-эле-
ментных сочетаний, номера которых удовлетворяют равенству (2).
Определение позиций элементов сочетания по его порядковому номеру. Рассмот-
рим обратную задачу: по порядковому номеру NSt сочетания найти позиции bi, занимаемые каждым i-м элементом из k элементов сочетания.
Решение обратной задачи основывается на следующем утверждении.
Утверждение 2.
Для любых натуральных чисел NSt, bk , m, k, таких что NSt >1, k >0, bk ≥ k, m ≥ k, справедливо равенство
bk = [ k k !(NSt −1) + r(bk, k)],
(7)
где r(bk ,k) > 0 при k >1, r(bk ,k ) = 0 при k=1, [ ] — символ округления. Доказательство. Чтобы подчеркнуть тот факт, что значение bk определено по значе-
нию NSt для k-элементного сочетания, обозначим NSt = NSt (bk, k). Предположим, что имеет место равенство
В силу равенства (2)
k
∑NSt (bk, k)= 1 + Cbii −1 . i=1
(8)
поэтому справедливо неравенство
k
∑ Cbii −1 ≤ Cbkk ,
i=1
(9)
NSt (bk , k ) – 1 ≤ Cbkk , которое запишем в следующем виде:
(10)
NSt (bk , k ) – 1 ≤
bk ! . k !(bk −k)!
(11)
Преобразуя неравенство (11):
(NSt (bk, k )) – 1)k! ≤ (bk – r(bk, k))k,
где r(bk, k) может быть определено из соотношения
(bk – r(bk , k ))k =
bk ! , (bk −k)!
(12)
получаем условие для определения искомого значения bk:
bk ≥ k k !(NSt (bk , k)−1) + r(bk, k ),
(13)
где bk — позиция, занимаемая старшим членом рассматриваемого сочетания. Так как по условиям bk — натуральное число, его значение получаем, округляя значение
правой части неравенства (13):
bk = [ k k !(NSt −1) + r(m, k)].
(14)
Применим доказанное утверждение для решения сформулированной обратной задачи.
Значение bk — номера позиции k-го элемента сочетания — найдено при доказательстве утверждения. Найдем номер позиции (k–1)-го элемента сочетания. Для этого полученное зна-
чение bk подставляем в равенство (8), используя соотношение (3):
NSt (bk, k ) – 1 = Cbkk −1 + Cbkk−−11 .
(15)
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 7
Метод упорядочения сочетаний объектов в задачах структурной динамики технических систем 11
Обозначим
NSt (bk–1, (k–1)) = NSt (bk, k ) – Cbkk −1 и запишем равенство (15) в следующем виде:
(16)
NSt (bk–1, (k–1)) – 1 = Cbkk−−11−1 + Cbkk−−22 −1 +…+ Cb11−1 .
(17)
Используя соотношения (8)—(14), находим значение номера позиции bk–1. Для нахожде-
ния номеров позиций остальных элементов сочетания повторяем процедуру, определяемую
соотношениями (8)—(17). Следует заметить, что в силу существенной дискретности последо-
вательности величин Cmk при решении обратной задачи достаточно использовать прибли-
женное значение величины r(m,k), которое в практических случаях может быть принято рав-
ным k/2.
Совокупность правил построения сочетаний в последовательности их порядковых но-
меров и процедур нахождения номеров позиций элементов сочетания по его номеру состав-
ляет метод упорядочения сочетаний.
Таким образом, изложенный в настоящей статье метод упорядочения сочетаний опреде-
ляет способ построения бесконечной последовательности k-элементных сочетаний, а также
устанавливает однозначную зависимость между порядковым номером k-элементного сочета-
ния в этой последовательности сочетаний и набором позиций образующих его элементов.
Рассмотренный метод находит применение в исследованиях структурно-функцио-
нальной динамики сложных систем, в задачах живучести (выживаемости) сложных систем,
при разработке реляционных баз данных для реализации отношений „многие-ко-многим“ без
введения дополнительных отношений в структуру базы данных, а также в других приложени-
ях, реализующих многозначные отношения.
СПИСОК ЛИТЕРАТУРЫ
1. Виленкин Н. Я., Виленкин А. Н., Виленкин П. А. Комбинаторика. М.: ФИМА, МЦНМО, 2006. 400 с.
2. Липский В. Комбинаторика для программистов. М.: Мир, 1988. 213 с.
3. Баннаи Э., Ито Т. Алгебраическая комбинаторика. Схемы отношений. М.: Мир, 1987. 375 с.
4. Комбинаторный анализ. Задачи и упражнения: Учеб. пособие / Под ред. К. А. Рыбникова. М.: Наука, 1982. 368 с.
5. Цвиркун А. Д. Основы синтеза структуры сложных систем. М.: Наука, 1982. 200 с.
6. Харари Ф., Палмер Э. Перечисление графов. М.: Мир, 1977. 324 с.
Сведения об авторе Виктор Трофимович Доможиров — д-р воен. наук; Научно-производственная фирма „Центральное конст-
рукторское бюро арматуростроения“, Санкт-Петербург; зам. директора по научной работе; E-mail: domojirov@ckba.ru
Рекомендована СПИИРАН
Поступила в редакцию 28.04.09 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 7