Описание классов комбинаторных конфигураций на основе отображений
The problem of construction of formal descriptions of combinatorial sets based on primary combinatorial sets and proposed mappings is considered. A concept of composition k-image of combinatorial sets is introduced. A class of the composition k-images of combinatorial sets, k-compositions of permuta...
Saved in:
| Date: | 2008 |
|---|---|
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Видавничий дім "Академперіодика" НАН України
2008
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/6089 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Описание классов комбинаторных конфигураций на основе отображений / Ю. Г. Стоян, И.В. Гребенник // Доп. НАН України. — 2008. — № 10. — С. 28-31. — Бібліогр.: 6 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-6089 |
|---|---|
| record_format |
dspace |
| spelling |
Стоян, Ю.Г. Гребенник, И.В. 2010-02-16T16:10:33Z 2010-02-16T16:10:33Z 2008 Описание классов комбинаторных конфигураций на основе отображений / Ю. Г. Стоян, И.В. Гребенник // Доп. НАН України. — 2008. — № 10. — С. 28-31. — Бібліогр.: 6 назв. — рос. 1025-6415 https://nasplib.isofts.kiev.ua/handle/123456789/6089 519.859 The problem of construction of formal descriptions of combinatorial sets based on primary combinatorial sets and proposed mappings is considered. A concept of composition k-image of combinatorial sets is introduced. A class of the composition k-images of combinatorial sets, k-compositions of permutations, is chosen and investigated. Some its properties are researched, and an example is given. ru Видавничий дім "Академперіодика" НАН України Математика Описание классов комбинаторных конфигураций на основе отображений Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Описание классов комбинаторных конфигураций на основе отображений |
| spellingShingle |
Описание классов комбинаторных конфигураций на основе отображений Стоян, Ю.Г. Гребенник, И.В. Математика |
| title_short |
Описание классов комбинаторных конфигураций на основе отображений |
| title_full |
Описание классов комбинаторных конфигураций на основе отображений |
| title_fullStr |
Описание классов комбинаторных конфигураций на основе отображений |
| title_full_unstemmed |
Описание классов комбинаторных конфигураций на основе отображений |
| title_sort |
описание классов комбинаторных конфигураций на основе отображений |
| author |
Стоян, Ю.Г. Гребенник, И.В. |
| author_facet |
Стоян, Ю.Г. Гребенник, И.В. |
| topic |
Математика |
| topic_facet |
Математика |
| publishDate |
2008 |
| language |
Russian |
| publisher |
Видавничий дім "Академперіодика" НАН України |
| format |
Article |
| description |
The problem of construction of formal descriptions of combinatorial sets based on primary combinatorial sets and proposed mappings is considered. A concept of composition k-image of combinatorial sets is introduced. A class of the composition k-images of combinatorial sets, k-compositions of permutations, is chosen and investigated. Some its properties are researched, and an example is given.
|
| issn |
1025-6415 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/6089 |
| citation_txt |
Описание классов комбинаторных конфигураций на основе отображений / Ю. Г. Стоян, И.В. Гребенник // Доп. НАН України. — 2008. — № 10. — С. 28-31. — Бібліогр.: 6 назв. — рос. |
| work_keys_str_mv |
AT stoânûg opisanieklassovkombinatornyhkonfiguraciinaosnoveotobraženii AT grebennikiv opisanieklassovkombinatornyhkonfiguraciinaosnoveotobraženii |
| first_indexed |
2025-11-26T20:57:01Z |
| last_indexed |
2025-11-26T20:57:01Z |
| _version_ |
1850775037644111872 |
| fulltext |
УДК 519.859
© 2008
Член-корреспондент НАН Украины Ю.Г. Стоян, И. В. Гребенник
Описание классов комбинаторных конфигураций
на основе отображений
The problem of construction of formal descriptions of combinatorial sets based on primary
combinatorial sets and proposed mappings is considered. A concept of composition k-image of
combinatorial sets is introduced. A class of the composition k-images of combinatorial sets,
k-compositions of permutations, is chosen and investigated. Some its properties are researched,
and an example is given.
Актуальной проблемой перечислительной комбинаторики является генерация и подсчет ко-
личества комбинаторных конфигураций, имеющих заданные свойства [1]. Специфика мно-
гих прикладных комбинаторных задач требует отражения в математических моделях их
комбинаторной структуры [2], которая часто является сложной и не может быть адекват-
но описана известными комбинаторными множествами [3–5]. Значит, для математического
моделирования и решения указанных задач необходимо введение новых комбинаторных
множеств с требуемыми свойствами. Классические подходы к формализации определения
комбинаторных множеств связаны с конфигурациями К. Бержа [5] и теорией перечисле-
ния Дж. Пойа [5, 6]. Являясь универсальными, классические методы дают эффективные
решения для простых классов комбинаторных множеств. Использование их для сложных
комбинаторных конфигураций дает громоздкие результаты, неприменимые на практике [5].
Постановка задачи. Рассмотрим построение формальных описаний комбинаторных
множеств, имеющих сложную структуру, на основе описаний базовых комбинаторных мно-
жеств, к которым отнесем перестановки, сочетания и размещения [3–5]. Результаты должны
быть не громоздкими и пригодными для использования в математических моделях ком-
бинаторных задач различных классов, а построенные множества — обладать свойством
транзитивности.
Базовые комбинаторные множества. Базовые отображения. Пусть Mi =
= {zi
1, z
i
2, . . . , z
i
ni
}, i ∈ J0
n = {0, 1, . . . , n}, — множества произвольных элементов. Построим
множества Zi, каждое из которых представляет собой множество всех подмножеств мно-
жества Mi, i ∈ J0
n. Возьмем произвольные zi = (zi
β1
, zi
β2
, . . . , zi
βki
) ∈ Zi, βl ∈ Jni
, l ∈ Jki
,
Jk = {1, 2, . . . , k}, i ∈ J0
n. Сформируем комбинаторные множества Yi, порожденные корте-
жами zi, где y = (zi
j1
, zi
j2
, . . . , zi
jmi
) ∈ Yi(z
i), {j1, j2, . . . , jmi
} ⊂ {β1, β2, . . . , βki
}. Построение Yi
представим с помощью отображения ΓYi
: Zi → Y, Y =
⋃
zi∈Zi,i∈J0
n
Yi(z
i).
Множествами Yi ⊂ Yi, i ∈ J0
n, являются базовые комбинаторные множества. Соответст-
вующие отображения ΓYi
, i ∈ J0
n, назовем базовыми отображениями.
Композиционные k-образы комбинаторных множеств. Введем операцию n-ком-
позиции комбинаторных множеств, основанную на операции композиции, описанной в [1].
Пусть комбинаторное множество Y0 порождено элементами z0
1 , z0
2 , . . . , z
0
n, комбинаторные
множества Y1, Y2, . . . , Yn порождены элементами z1, z2, . . . , zn, zi = {zi
1, z
i
2, . . . , z
i
ni
}, i ∈ Jn.
Операция n-замещения для комбинаторных множеств Y0, Y1, Y2, . . . , Yn состоит в заме-
не каждого порождающего элемента z0
1 , z0
2 , . . . , z0
n множества Y0 элементами множеств Y1,
28 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2008, №10
Y2, . . . , Yn соответственно, в результате чего получается элемент некоторого множества Wz.
Каждый элемент z0
i может быть замещен любым элементом множества Yi, i ∈ Jn.
Операцию n-композиции множеств Y0, Y1, Y2, . . . , Yn представим с помощью базовых
отображений. Поскольку y = (z0
t1
, z0
t2
, . . . , z0
tn) ∈ Y0, z0
tj
∈ Yi(z
i), tj ∈ Jn, i ∈ Jn, j ∈ Jn, то
Wz представляется на основе отображений
Wz = ΓW ◦ ΓY (x), (1)
где ΓY : Z0 → Y, ΓW : Y → W, W =
⋃
zi∈Zi,z
0
i
∈Yi(zi)
Wz. Для любого Y0 ⊂ Y справедливо
ΓW (Y0) = Wz ⊂ W, w = (z1
1 , z1
2 , . . . , z1
n1
, z2
1 , z2
2 , . . . , z2
n2
, . . . , zn
1 , zn
2 , . . . , zn
nn
) ∈ Wz.
Выполним операцию n-композиции для порождающих элементов множества Wz, заме-
щая их элементами других базовых комбинаторных множеств. В результате k шагов полу-
чим обобщение множества Wz вида (1).
Пусть zAi = {zAi
1 , z
Ai
2 , . . . , zAi
nAi
} ∈ ZAi
, ZAi
— множество всех подмножеств множества
MAi
= {aAi
1 , aAi
2 , . . . , aAi
mAi
}, ΓAi
: Y
i−1 → Y
i, Y
i =
⋃
zAi∈ZAi
YAi
, YAi
= ΓAi
(zAi),
где
y = (zAi
l1
, z
Ai
l2
, . . . , z
Ai
lAi
) ∈ YAi
, Γi = {ΓAi
}, zAi
αi+1
∈ YAi+1
,
Ai = (α1α2 . . . αi), α1 ∈ Jn, α2 ∈ Jnα1
, . . . , αi+1 ∈ Jnα1...αi
, A0 = {0}, i ∈ Jk,
mi = m0 · mA1
· . . . · mAi−1
, η =
n∑
α1=1
n1∑
α2=1
· · ·
n1...k−2∑
αk−1=1
nα1...αk−1
; Γi ∈ Γi, i ∈ Jk. (2)
Определение. Комбинаторное множество Wz называется композиционным k-образом
комбинаторных множеств Y0, Y1, Y2, . . . , Yn, Y11, Y12, . . . , Y1n1
, . . . , Y1 . . . 1
︸ ︷︷ ︸
k
, . . . , Ynn1...nk−1
,
порожденным множествами zk1, zk2, . . . , zkη, если
Wz = Γk ◦ Γk−1 ◦ . . . ◦ Γ0(z). (3)
Y0 называется множеством нулевого порядка, YAi
— множествами i-го порядка. Отобра-
жения Γi ∈ Γi, i ∈ Jk, строятся на основе операции n-композиции. Wz вида (3) — базовое
комбинаторное множество при k = 0.
Теорема 1. Отображения Γi ∈ Γi, i ∈ Jk, в (3) являются надъективными.
Теорема 2. Card Wz =
∑
{γ1,γ2,...,γr}⊂Jn
αγ1,γ2,...,γr ·
k∏
i=1
∏
Ai=(α1α2...αi)
c(YAi
), где c(YAi
) = Card(YAi
),
Ai удовлетворяет (2), αγ1,γ2,...,γr — количество различных элементов y ∈ Y0, порождаемых
набором z = {z0
1 , z0
2 , . . . , z0
n} ∈ Z0.
Пусть композиционный k-образ комбинаторных множеств
Y0 = Pnm, (4)
Y1 = Pn1m1
, Y2 = Pn2m2
, . . . , Yn = Pnnmn , (5)
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2008, №10 29
Y11 = Pn11m11
, Y12 = Pn12m12
, . . . , Y1n1
= Pn1n1
m1n1
,
Y21 = Pn21m21
, Y22 = Pn22m22
, . . . ,
Y2n2
= Pn2n2
m2n2
, . . . , Ynn1
= Pnn1mn1
,
Ynn2
= Pnn2mn2
, . . . , Ynnn = Pnnnnmnnn
, . . . , (6)
Y1 . . . 1
︸ ︷︷ ︸
k
= Pn1 . . . 1
︸ ︷︷ ︸
k
m1 . . . 1
︸ ︷︷ ︸
k
, . . . , Ynn1...nk−1
= Pnnn1...nk−1
mnn1...nk−1
(7)
порожден множествами
B1 = zk1 = {a1
1, a
1
2, . . . , a
1
n1 . . . 1
︸ ︷︷ ︸
k
}, . . . , Bη = zkη = {aη
1 , a
η
2, . . . , a
η
nnn1...nk−1
}. (8)
Здесь Pnm — множество перестановок с повторениями из n элементов, m из которых раз-
личны, a
j
i ∈ R1, i ∈ JnAk
, Ak, η удовлетворяют (2). Такой композиционный k-образ ком-
бинаторных множеств назовем k-композицией перестановок и обозначим W k
P . Здесь Pnm
вида (4) является множеством нулевого порядка, множества (5)–(7) — множествами пер-
вого, второго, . . . , k-го порядка. W k
P состоит из элементов w = (w1, w2, . . . , wη) ∈ W k
P , где
wi = (aj
s1
, aj
s2
, . . . , aj
snAk
), i, j ∈ Jη , (s1, s2, . . . , snAk
) ∈ LnAk
, Lk — множество перестановок
элементов Jk. В силу теоремы 2
V = Card W k
P = n! ·
k∏
i=1
∏
Ai=(α1α2...αi)
nAi
!. (9)
Из построения множества W k
P следует, что его элементы являются также элементами
PNm0 , порожденного G = {a1
1, a
1
2, . . . , a
1
n1 . . . 1
︸ ︷︷ ︸
k
, . . . , a
η
1 , a
η
2, . . . , a
η
nnn1...nk−1
} = {g1, g2, . . . , gN},
т. е. W k
P ⊂ PNm0 , где
N =
n∑
α1=1
n1∑
α2=1
· · ·
n1...k−1∑
αk=1
nα1...αk
. (10)
Согласно [4] f : W k
P → RN ∀w = (w1, w2, . . . , wN ) ∈ W k
P , x = f(w) = (x1, x2, . . . , xN ) ∈
∈ RN , xi = wi, i ∈ JN . Образ W k
P в RN обозначим EW k
P
. Элементы EW k
P
= f(W k
P ) — это век-
торы x = (x1, x2, . . . , xN ) = (ei1 , ei2 , . . . , eiη ), где (i1, i2, . . . , iη) ∈ Lη, ei = (aj
s1
, aj
s2
, . . . , aj
snAk
),
(s1, s2, . . . , snAk
) ∈ LnAk
, i, j ∈ Jη. Так как W k
P ⊂ PNm0 , то EW k
P
⊂ ENm0 = f(PNm0). Значит,
EW k
P
обладает рядом свойств, справедливых для множества ENm0 [4], а именно:
1) точки EW k
P
принадлежат гиперплоскости
N∑
i=1
xi =
η∑
i=1
∑
ai
j∈Bi
ai
j в пространстве RN . Здесь
Bi — множества вида (8);
2) точки EW k
P
принадлежат (N − 1)-сфере SN−1
N∑
i=1
(xi − τ)2 = r2, где τ =
1
N
η∑
i=1
∑
ai
j∈Bi
ai
j ,
r2 =
η∑
i=1
∑
ai
j∈Bi
(ai
j − τ)2;
30 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2008, №10
3) EW k
P
лежит на семействах параллельных плоскостей
s∑
t=1
xit =
s∑
t=1
gjt , где gj ∈ G, it,
jt ∈ JN , iq 6= ip, jq 6= jp при q 6= p; q, p ∈ Js, s, t ∈ JN ;
4) EW k
P
симметрично относительно плоскостей вида xi − xj = 0, i, j ∈ Jm0
, или i, j ∈
∈ JN \ JN−m0
, i 6= j, m0 = min
l∈Jη
CardBl.
П р и м е р . Рассмотрим композиционный k-образ комбинаторных множеств Y0 = P3; Y1 = P3,
Y2 = P2, Y3 = P4; Y11 = P2, Y12 = P3, Y13 = P2, Y21 = P2, Y22 = P3, Y31 = P2, Y32 = P2, Y33 =
= P2, Y34 = P2, порожденный множествами B1 = {1, 2}, B2 = {3, 4, 5}, B3 = {6, 7}, B4 = {8, 9},
B5 = {10, 11, 12}, B6 = {13, 14}, B7 = {15, 16}, B8 = {17, 18}, B9 = {19, 20}. Это k-композиция
перестановок при k = 2 — множество W 2
P
. Элементами W 2
P
являются (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11,
12, 13, 14, 15, 16, 17, 18, 19, 20), (2, 1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20), (4, 5, 1, 2, 3,
6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20) и т. д. Согласно (9) CardW 2
P = (2!)8 ·(3!)4 ·4! = 7962624.
При отображении W 2
P
в R20 получим EW
2
P
= f(W 2
P
). Точки EW
2
P
принадлежат плоскости
20∑
i=1
xi = 210
и лежат на сфере
20∑
i=1
(xi − 10,5)2 = 25,792. Множество EW 2
P
принадлежит семействам параллельных
плоскостей: x1 = 1, x1 = 2, . . . , x1 = 20, x2 = 1, . . . , x2 = 20; x20 = 20; . . . ; x1 + x2 = 1 + 2,
x1 +x2 = 1+3, . . . ; x19 +x20 = 19+20, . . . ;
20∑
i=1
xi = 210. EW 2
P
симметрично относительно плоскостей
x1 − x2 = 0, x19 − x20 = 0.
Таким образом, введение композиционных k-образов комбинаторных множеств позво-
ляет формально описывать широкие классы комбинаторных множеств на основе базовых
комбинаторных множеств с известными описаниями и построенных отображений. Предло-
женный способ, с одной стороны, обладает достаточной универсальностью за счет использо-
вания в результирующем множестве комбинаторных свойств базовых комбинаторных мно-
жеств. С другой стороны, композиционные k-образы комбинаторных множеств можно весь-
ма просто реализовать конструктивно, что позволяет применять их при математическом
моделировании и решении различных комбинаторных задач.
1. Гульден Я., Джексон Д. Перечислительная комбинаторика. – Москва: Наука, 1990. – 504 с.
2. Сергиенко И.В. Математические модели и методы решения задач дискретной оптимизации. – Киев:
Наук. думка, 1988. – 472 с.
3. Айгнер М. Комбинаторная теория. – Москва: Мир, 1982. – 558 с.
4. Стоян Ю.Г., Ємець О.О. Теорiя i методи евклiдової комбiнаторної оптимiзацiї. – Київ: Iн-т систем.
дослiджень освiти, 1993. – 188 с.
5. Сачков В.Н. Комбинаторные методы дискретной математики. – Москва: Наука, 1977. – 320 с.
6. Пойа Дж. Комбинаторные вычисления для групп, графов и химических соединений // Перечисли-
тельные задачи комбинаторного анализа. – Москва: Мир, 1979. – С. 36–138.
Поступило в редакцию 03.03.2008Харьковский национальный университет
радиоэлектроники
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2008, №10 31
|