Про фрактальну природу комбінаторних множин та знаходження формул комбінаторних чисел
Розглянуто фрактальну структуру комбінаторних множин, яка утворюється в процесі впорядкування комбінаторних конфігурацій. З використанням фрактальних властивостей оговорених множин розроблено підхід до розв’язання перелічувальних задач у комбінаториці. Для знаходження комбінаторних чисел використано...
Збережено в:
| Опубліковано в: : | Кибернетика и системный анализ |
|---|---|
| Дата: | 2020 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2020
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/190347 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Про фрактальну природу комбінаторних множин та знаходження формул комбінаторних чисел / Н.К. Тимофієва // Кибернетика и системный анализ. — 2020. — Т. 56, № 1. — С. 129–137. — Бібліогр.: 11 назв. — укр. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859833064175173632 |
|---|---|
| author | Тимофієва, Н.К. |
| author_facet | Тимофієва, Н.К. |
| citation_txt | Про фрактальну природу комбінаторних множин та знаходження формул комбінаторних чисел / Н.К. Тимофієва // Кибернетика и системный анализ. — 2020. — Т. 56, № 1. — С. 129–137. — Бібліогр.: 11 назв. — укр. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Розглянуто фрактальну структуру комбінаторних множин, яка утворюється в процесі впорядкування комбінаторних конфігурацій. З використанням фрактальних властивостей оговорених множин розроблено підхід до розв’язання перелічувальних задач у комбінаториці. Для знаходження комбінаторних чисел використано арифметичні послідовності.
Рассмотрена фрактальная структура комбинаторных множеств, которая образуется в процессе упорядочения комбинаторных конфигураций. С использованием фрактальных свойств оговоренных множеств разработан подход к решению перечислительных задач в комбинаторике. При нахождении комбинаторных чисел используются арифметические последовательности.
The fractal structure of combinatorial sets, which is formed in ordering of combinatorial configurations, is considered. Using the fractal properties of contracted sets, an approach to solving enumeration problems in combinatorics is developed. Arithmetic sequences are used to find combinatorial numbers.
|
| first_indexed | 2025-12-07T15:33:23Z |
| format | Article |
| fulltext |
ÓÄÊ 519.11.176
Í.Ê. ÒÈÌÎÔ²ªÂÀ
ÏÐÎ ÔÐÀÊÒÀËÜÍÓ ÏÐÈÐÎÄÓ ÊÎÌÁ²ÍÀÒÎÐÍÈÕ ÌÍÎÆÈÍ
ÒÀ ÇÍÀÕÎÄÆÅÍÍß ÔÎÐÌÓË ÊÎÌÁ²ÍÀÒÎÐÍÈÕ ×ÈÑÅË
Àíîòàö³ÿ. Ðîçãëÿíóòî ôðàêòàëüíó ñòðóêòóðó êîìá³íàòîðíèõ ìíîæèí, ÿêà
óòâîðþºòüñÿ â ïðîöåñ³ âïîðÿäêóâàííÿ êîìá³íàòîðíèõ êîíô³ãóðàö³é. Ç âèêî-
ðèñòàííÿì ôðàêòàëüíèõ âëàñòèâîñòåé îãîâîðåíèõ ìíîæèí ðîçðîáëåíî ï³äõ³ä
äî ðîçâ’ÿçàííÿ ïåðåë³÷óâàëüíèõ çàäà÷ ó êîìá³íàòîðèö³. Äëÿ çíàõîäæåííÿ
êîìá³íàòîðíèõ ÷èñåë âèêîðèñòàíî àðèôìåòè÷í³ ïîñë³äîâíîñò³.
Êëþ÷îâ³ ñëîâà: êîìá³íàòîðèêà, ôðàêòàëè, êîìá³íàòîðí³ êîíô³ãóðàö³¿, ðîç-
áèòòÿ íàòóðàëüíîãî ÷èñëà, àðèôìåòè÷íèé òðèêóòíèê, êîìá³íàòîðí³ ÷èñëà.
ÂÑÒÓÏ
ϳä ÷àñ ï³äðàõóíêó ê³ëüêîñò³ êîìá³íàòîðíèõ êîíô³ãóðàö³é ó ¿õí³õ ìíîæèíàõ
âèíèêàþòü êîìá³íàòîðí³ ÷èñëà (÷èñëà Ô³áîíà÷÷³, ê³ëüê³ñòü ïåðåñòàíîâîê
ó ¿õí³é ìíîæèí³ n! , á³íîì³àëüí³ êîåô³ö³ºíòè òîùî). Âèêîðèñòàííÿ ôðàêòàëü-
íèõ âëàñòèâîñòåé êîìá³íàòîðíèõ ìíîæèí äຠçìîãó çíàõîäèòè ôîðìóëè öèõ
÷èñåë. Ó ïðîöåñ³ òàêèõ îá÷èñëåíü âèêîðèñòîâóþòü àðèôìåòè÷í³ ïîñë³äîâíîñò³,
ïðè öüîìó çíà÷åííÿìè ¿õí³õ ñêëàäîâèõ º ìíîãîêóòí³ òà ô³ãóðí³ ÷èñëà.
Äîñë³äæåííþ ôðàêòàë³â ïðèñâÿ÷åíî äóæå áàãàòî íàóêîâèõ ïðàöü, íàïðèêëàä
[1–4]. Çàçâè÷àé äîñë³äæóþòü ãåîìåòðè÷í³ ôîðìè, ôðàêòàëüí³ ÷èñëîâ³ ðÿäè òà
¿õíº âèêîðèñòàííÿ íà ïðàêòèö³, çîêðåìà äëÿ ïðîãíîçóâàííÿ ð³çíèõ ÿâèù. Àëå
àíàë³çó ôðàêòàëüíèõ âëàñòèâîñòåé êîìá³íàòîðíèõ ìíîæèí ó ë³òåðàòóð³ íå
ïðèä³ëåíî äîñòàòíüî¿ óâàãè. Äëÿ ðîçâ’ÿçàííÿ ïåðåë³÷óâàëüíèõ çàäà÷ º áàãàòî
ñïîñîá³â, íàïðèêëàä, ïðèíöèï âêëþ÷åííÿ ³ âèêëþ÷åííÿ, ï³äõîäè ç âèêîðèñòàí-
íÿì ïðîäóêòèâíèõ ôóíêö³é, àëãåáðè ³íöèäåíòíîñò³ òîùî [5–8]. Ïåðåë³÷óâàëüí³
çàäà÷³ ìîæíà ðîçâ’ÿçóâàòè ³ ç âèêîðèñòàííÿì ôðàêòàëüíèõ âëàñòèâîñòåé
êîìá³íàòîðíèõ ìíîæèí, îäíàê öåé ï³äõ³ä â ë³òåðàòóð³ íå ðîçãëÿíóòî.
ÏÎÑÒÀÍÎÂÊÀ ÇÀÄÀײ ÒÀ ÏÐÎÏÎÍÎÂÀÍÈÉ Ï²ÄÕ²Ä
ϳä ÷àñ ãåíåðóâàííÿ êîìá³íàòîðíèõ ìíîæèí çà ñòðîãèìè ïðàâèëàìè ìîæíà
ïîáà÷èòè, ùî âîíè ìàþòü ôðàêòàëüíó ñòðóêòóðó. Ïðîòå, íåçâàæàþ÷è íà âåëè-
÷åçíó ê³ëüê³ñòü ïóáë³êàö³é ùîäî ôðàêòàë³â, öÿ ïðîáëåìà íå º îá’ºêòîì îñîáëè-
âî¿ óâàãè ¿õí³õ àâòîð³â. Îòæå, äëÿ âñòàíîâëåííÿ ôðàêòàëüíî¿ ñòðóêòóðè
êîìá³íàòîðíèõ ìíîæèí íåîáõ³äíî ðîçðîáèòè ñïîñ³á ¿õíüîãî âïîðÿäêóâàííÿ,
ÿêèé áè äàâ çìîãó ïðîñë³äêóâàòè çà óòâîðåííÿì öèõ ñòðóêòóð òà ç âèêîðèñ-
òàííÿì ¿õí³õ âëàñòèâîñòåé ðîçðîáèòè ï³äõ³ä äî ðîçâ’ÿçàííÿ ïåðåë³÷óâàëüíèõ
çàäà÷ ó êîìá³íàòîðèö³.
Äëÿ âñòàíîâëåííÿ ôðàêòàëüíî¿ ñòðóêòóðè êîìá³íàòîðíèõ ìíîæèí ðîçðîáëå-
íî ìåòîä ãåíåðóâàííÿ êîìá³íàòîðíèõ êîíô³ãóðàö³é ç âèêîðèñòàííÿì âëàñòèâîñò³
ïåð³îäè÷íîñò³. Óïîðÿäêóâàííÿ öèì ìåòîäîì çä³éñíåíî çà ñòðîãèìè ïðàâèëàìè.
Âèä³ëåíî ³íòåðâàëè êîìá³íàòîðíèõ ìíîæèí, ÿê³ óòâîðþþòüñÿ çã³äíî ç îäíèìè é
òèìè ñàìèìè ïðîöåäóðàìè. Íèæ÷å ïîêàçàíî, ùî çàâäÿêè òàêîìó âïîðÿäêóâàííþ
óòâîðåí³ ³íòåðâàëè º ñàìîïîä³áíèìè, à âëàñíå êîìá³íàòîðíà ìíîæèíà ìîæå áóòè
ÿê ñê³í÷åííîþ, òàê ³ íåñê³í÷åííîþ, ùî õàðàêòåðíî äëÿ ôðàêòàëüíèõ ñòðóêòóð.
Ôðàêòàëüí³ âëàñòèâîñò³ êîìá³íàòîðíèõ ìíîæèí äàþòü çìîãó çíàõîäèòè
êîìá³íàòîðí³ ÷èñëà.
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 1 129
© Í.Ê. Òèìîô³ºâà, 2020
ÄÅßʲ ÂËÀÑÒÈÂÎÑÒ² ÊÎÌÁ²ÍÀÒÎÐÍÈÕ ÊÎÍÔ²ÃÓÐÀÖ²É
Åëåìåíòàìè êîìá³íàòîðíèõ ìíîæèí º êîìá³íàòîðí³ êîíô³ãóðàö³¿ ïåâíîãî òèïó,
òîìó ðîçãëÿíåìî äåÿê³ ¿õí³ âëàñòèâîñò³. Óòâîðåííÿ òà âïîðÿäêóâàííÿ öèõ
îá’ºêò³â ´ðóíòîâíî îïèñàíî ó [9]. Îãîâîðèìî äåÿê³ ç íèõ.
Îçíà÷åííÿ 1. Êîìá³íàòîðíîþ êîíô³ãóðàö³ºþ íàçâåìî áóäü-ÿêó ñóêóïí³ñòü
åëåìåíò³â, ÿêà óòâîðþºòüñÿ ç óñ³õ àáî ç äåÿêèõ åëåìåíò³â çàäàíî¿ ìíîæèíè
A a an� { , ..., }1 . Ïîçíà÷èìî ¿¿ âïîðÿäêîâàíîþ ìíîæèíîþ w w wk k k� ( , ..., )
1 � . ϳä
ñèìâîëîì w Aj
k � ðîçó쳺ìî ÿê îêðåì³ åëåìåíòè, òàê ³ ï³äìíîæèíè (áëîêè), ïðè
öüîìó � �{ , ..., }1 n — ê³ëüê³ñòü åëåìåíò³â ó wk , W wk q� { }
1
— ìíîæèíà êîìá³íà-
òîðíèõ êîíô³ãóðàö³é. Âåðõí³é ³íäåêñ k (k q�{ , ..., }1 ) ó wk ïîçíà÷ຠïîðÿäêîâèé
íîìåð wk ó W, à q — ê³ëüê³ñòü wk ó W.
Êîìá³íàòîðí³ êîíô³ãóðàö³¿ áóäü-ÿêîãî òèïó ôîðìóþòüñÿ ç åëåìåíò³â çàäàíî¿
ìíîæèíè çà äîïîìîãîþ õàðàêòåðíî¿ äëÿ êîæíîãî ç íèõ îïåðàö³¿. Îäí³ òàê³ îïå-
ðàö³¿ çì³íþþòü ïîðÿäîê ðîçì³ùåííÿ åëåìåíò³â ó öèõ êîíô³ãóðàö³ÿõ, ³íø³ çì³íþ-
þòü ¿õí³é ñêëàä. Ìíîæèíó A a an� { , ..., }1 , ç åëåìåíò³â ÿêî¿ óòâîðþþòüñÿ
êîìá³íàòîðí³ êîíô³ãóðàö³¿, íàçâåìî áàçîâîþ.
гçíîìàí³òí³ òèïè êîìá³íàòîðíèõ êîíô³ãóðàö³é óòâîðþþòüñÿ çà äîïîìîãîþ
òðüîõ ðåêóðåíòíèõ êîìá³íàòîðíèõ îïåðàòîð³â, à ñàìå âèáèðàííÿ, òðàíñïîçèö³¿ òà
àðèôìåòè÷íîãî. Îçíà÷åííÿ îãîâîðåíèõ îïåðàòîð³â ïîäàíî ó [9].
Äâ³ íåòîòîæí³ êîìá³íàòîðí³ êîíô³ãóðàö³¿ w w wk k k
k
� ( , ..., )
1 �
òà w w wi i i
i
� ( , ..., )
1 �
íàçâåìî ³çîìîðôíèìè, ÿêùî � �k i� . ϳäìíîæèíó W Wk�
� íàçâåìî ï³äìíîæèíîþ
³çîìîðôíèõ êîìá³íàòîðíèõ êîíô³ãóðàö³é, ÿêùî ¿¿ åëåìåíòè — ³çîìîðôí³ êîìá³íàòîðí³
êîíô³ãóðàö³¿. Ìíîæèíà ïåðåñòàíîâîê ñêëàäàºòüñÿ ç îäí³º¿ ï³äìíîæèíè W Wk�
� .
Âèá³ðêè (ñïîëó÷åííÿ òà ðîçì³ùåííÿ ç ïîâòîðåííÿìè òà áåç ïîâòîðåíü) óïî-
ðÿäêîâóþòüñÿ ï³äìíîæèíàìè ³çîìîðôíèõ âèá³ðîê. Äëÿ ô³êñîâàíîãî n íà ï³äìíî-
æèí³ ³çîìîðôíèõ âèá³ðîê ð³çíèõ òèï³â ìíîæèíà W Wk�
� º ñê³í÷åííîþ, à äëÿ
äîâ³ëüíîãî n — íåñê³í÷åííîþ.
Êîìá³íàòîðíà ìíîæèíà îäíîãî ³ òîãî ñàìîãî òèïó ìîæå áóòè âïîðÿäêîâàíà
ó ð³çí³ ñïîñîáè. Àíàë³ç öèõ ìíîæèí ïîêàçóº, ùî âîíè çàçâè÷àé óïîðÿäêîâóþòüñÿ
îäíèìè é òèìè ñàìèìè ïðîöåäóðàìè, òîáòî ³ñíóþòü çàêîíîì³ðíîñò³ ¿õíüîãî ãåíå-
ðóâàííÿ. Îäí³ºþ ç íèõ º âëàñòèâ³ñòü ïåð³îäè÷íîñò³, ÿêà âèïëèâຠç ðåêóðåíòíîãî
ñïîñîáó óòâîðåííÿ òà âïîðÿäêóâàííÿ êîìá³íàòîðíèõ êîíô³ãóðàö³é.
Îçíà÷åííÿ 2 [9]. Âëàñòèâ³ñòü ïåð³îäè÷íîñò³ âïîðÿäêóâàííÿ êîìá³íàòîðíèõ
ìíîæèí âèïëèâຠç ðåêóðåíòíîãî ñïîñîáó óòâîðåííÿ êîìá³íàòîðíèõ êîíô³ãóðàö³é
òà ïîëÿãຠâ òîìó, ùî ö³ ìíîæèíè âïîðÿäêîâàí³ ³íòåðâàëàìè, â êîæíîìó ç ÿêèõ
êîìá³íàòîðí³ êîíô³ãóðàö³¿ óòâîðþþòüñÿ çà îäíèìè é òèìè ñàìèìè ïðàâèëàìè.
Óïîðÿäêóºìî ìíîæèíó W êîìá³íàòîðíèìè êîíô³ãóðàö³ÿìè wk , k q�{ , ..., }1 ,
ó òàêèé ñïîñ³á, ùî íàñòóïíà wk�1 óòâîðþºòüñÿ ç ïîïåðåäíüî¿ wk àáî ç áàçîâî¿
ìíîæèíè A çà äîïîìîãîþ õàðàêòåðíî¿ äëÿ çàäàíîãî òèïó ðåêóðåíòíî¿ êîìá³íà-
òîðíî¿ îïåðàö³¿ (òðàíñïîçèö³¿, âèáèðàííÿ àáî àðèôìåòè÷íî¿). Ââàæàòèìåìî, ùî
áàçîâà ìíîæèíà A a an� ( , ..., )1 º âïîðÿäêîâàíîþ. Êîìá³íàòîðíà êîíô³ãóðàö³ÿ
w w w Wk k k� �( , ..., )
1 � òàêîæ º âïîðÿäêîâàíîþ.
Ó ìíîæèí³ êîìá³íàòîðíèõ êîíô³ãóðàö³é âèä³ëèìî íàéìåíøó ï³äìíîæèíó,
êîìá³íàòîðí³ êîíô³ãóðàö³¿ â ÿê³é óòâîðþþòüñÿ çà îäíèì ³ òèì ñàìèì ïðàâèëîì.
Íàçâåìî öþ ï³äìíîæèíó ³íòåðâàëîì íóëüîâîãî ðàíãó. Ïåâíà ê³ëüê³ñòü ³íòåðâàë³â
íóëüîâîãî ðàíãó óòâîðþº ³íòåðâàë ïåðøîãî ðàíãó, îñòàíí³ óòâîðþþòü ³íòåðâàë
130 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 1
äðóãîãî ðàíãó ³ ò. ä. Ç ³íòåðâàë³â ( )� �1 -ãî ðàíãó óòâîðþºòüñÿ ³íòåðâàë �-ãî ðàíãó.
²íøèìè ñëîâàìè, äëÿ ãåíåðóâàííÿ êîìá³íàòîðíèõ êîíô³ãóðàö³é áóäü-ÿêîãî òèïó
íåîáõ³äíî ñôîðìóëþâàòè ïðàâèëà óòâîðåííÿ à) ³íòåðâàë³â íóëüîâîãî ðàíãó, á) îá-
ìåæóâàëüíî¿ êîìá³íàòîðíî¿ êîíô³ãóðàö³¿ (ïåðøî¿ â ³íòåðâàë³ íóëüîâîãî ðàíãó),
â) ³íòåðâàëó �-ãî ðàíãó, ÿêèé ñêëàäàºòüñÿ ç ³íòåðâàë³â ( )� �1 -ãî ðàíãó. Âèêîðèñòàí-
íÿ öèõ ïðàâèë äຠçìîãó îïèñàòè ôðàêòàëüíó ïðèðîäó êîìá³íàòîðíèõ ìíîæèí [9].
ÏÐÎ ÔÐÀÊÒÀËÜÍÓ ÏÐÈÐÎÄÓ ÊÎÌÁ²ÍÀÒÎÐÍÈÕ ÌÍÎÆÈÍ
Ó ë³òåðàòóð³ ôðàêòàëè ðîçãëÿäàþòüñÿ ÿê äåÿê³ ãåîìåòðè÷í³ ô³ãóðè, ÿêèì âëàñ-
òèâà ñàìîïîä³áí³ñòü òà êâàç³ñàìîïîä³áí³ñòü [4]. Âîíè ïîâòîðþþòüñÿ, ìàþòü
ôðàêòàëüíó ðîçì³ðí³ñòü ³ º îäíî÷àñíî ñê³í÷åííèìè òà íåñê³í÷åííèìè.
ßêùî âïîðÿäêóâàòè êîìá³íàòîðí³ ìíîæèíè ç âèêîðèñòàííÿì âëàñòèâîñò³
ïåð³îäè÷íîñò³, òî ìîæíà ïîáà÷èòè, ùî âîíè õàðàêòåðèçóþòüñÿ ñàìîïîä³áí³ñòþ òà
êâàç³ñàìîïîä³áí³ñòþ [10]. Ââàæàºìî, ùî êîìá³íàòîðí³ ìíîæèíè º ñàìîïîä³áíè-
ìè, ÿêùî ¿õí³ åëåìåíòè óòâîðþþòüñÿ çà äîïîìîãîþ îäíîãî é òîãî ñàìîãî ðåêó-
ðåíòíîãî êîìá³íàòîðíîãî îïåðàòîðà, à ¿õíº âïîðÿäêóâàííÿ çä³éñíþºòüñÿ çà îäíè-
ìè é òèìè ñàìèìè ïðàâèëàìè. ²íòåðâàë �-ãî ðàíãó óïîðÿäêîâàíî¿ ìíîæèíè W
ñêëàäàºòüñÿ ç ³íòåðâàë³â ( )� �1 -ãî ðàíãó. Ö³ ³íòåðâàëè ì³ñòÿòü ó ñîá³ ìåíø³, òîáòî
âîíè º ñàìîïîä³áíèìè. Òàê³ âëàñòèâîñò³ º õàðàêòåðíèìè äëÿ ôðàêòàë³â [10].
Ïðèêëàä 1. Äëÿ ô³êñîâàíîãî ÷èñëà n ìíîæèíà W º ñê³í÷åííîþ, à äëÿ
äîâ³ëüíîãî çíà÷åííÿ n âîíà íåñê³í÷åííà, òîáòî W îäíî÷àñíî º ñê³í÷åííîþ òà
íåñê³í÷åííîþ. ϳäìíîæèíà W� ðîçì³ùåíü ç ïîâòîðåííÿìè (àáî ñïîëó÷åíü ç ïî-
âòîðåííÿìè, ðîçáèòòÿ n-åëåìåíòíî¿ ìíîæèíè íà ï³äìíîæèíè ç ïîâòîðåííÿìè)
º ñê³í÷åííîþ, à ìíîæèíà W öèõ ñàìèõ êîìá³íàòîðíèõ êîíô³ãóðàö³é äëÿ òîãî æ
ñàìîãî n — íåñê³í÷åííîþ.
Îñê³ëüêè ³íòåðâàë �-ãî ðàíãó ñêëàäàºòüñÿ ç ³íòåðâàë³â ( )� �1 -ãî ðàíãó,
à ³íòåðâàë 1-ãî ðàíãó — ç ³íòåðâàë³â íóëüîâîãî ðàíãó, íåñêëàäíî, çíàþ÷è ïðàâè-
ëà ¿õíüîãî âïîðÿäêóâííÿ, âèçíà÷àòè ê³ëüê³ñòü êîìá³íàòîðíèõ êîíô³ãóðàö³é
ó ¿õí³é ìíîæèí³. Çà ïåâíèìè ïðàâèëàìè, ÿê³ º ð³çíèìè äëÿ ð³çíèõ òèï³â êîìá³íà-
òîðíèõ êîíô³ãóðàö³é, óòâîðþºìî ñê³í÷åííó ïîñë³äîâí³ñòü, êîæíå çíà÷åííÿ ÿêî¿
çàäຠê³ëüê³ñòü w â ³íòåðâàëàõ �-ãî ðàíãó. Ôîðìóëó êîìá³íàòîðíîãî ÷èñëà äëÿ W
(ê³ëüê³ñòü w ó ìíîæèí³ W) ïîäàìî �-çíà÷íîþ ñóìîþ. Ìíîæèíà W âïîðÿäêî-
âóºòüñÿ W Wk�
� , òîìó çàïèøåìî ¿¿ â òàêîìó âèãëÿä³:
� �( )h
j
H
j
H
1
11 1
1
1
2
2
1
��
��
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
��
��
j
H
j
H nn
�� 1
1
11
11
�
(1)
� ��
�
�
�
�
�
�
�
��
�� ( ) ...
~
~~
h q
j
H
j
H
qq
1
1
2
2
11
�
�
�
�
�
�
�
��
��
j
H
j
H n
q
n
q
�� 1
1
11
~~
,
äå H t
� — ê³ëüê³ñòü ³íòåðâàë³â �-ãî ðàíãó, t �{ , ..., }1 � , � �{ , ..., }2 n , h� —
ê³ëüê³ñòü êîìá³íàòîðíèõ êîíô³ãóðàö³é â ³íòåðâàë³ íóëüîâîãî ðàíãó äëÿ �-¿
ï³äìíîæèíè W Wk�
� , � �{ , ..., ~ }1 q , ~q — ê³ëüê³ñòü ï³äìíîæèí W Wk�
� ,
� �( )h
j
H
j
H
�
��
1
1
2
2
11 ��
��
�
�
�
�
�
�
�
�
�
�
�
�
�
�
��
��
j
H
j
H nn
�
�
�
�
1
1
11
— ê³ëüê³ñòü êîìá³íàòîðíèõ êîíô³ãó-
ðàö³é ó �-é ï³äìíîæèí³ W Wk�
� (àáî ó ìíîæèí³ ïåðåñòàíîâîê). Âèðàç (1) îïè-
ñóº ôðàêòàëüíó ñòðóêòóðó êîìá³íàòîðíî¿ ìíîæèíè, ÿêà º îá’ºìíîþ òà ¿¿ ìîæ-
íà ïîäàòè ãåîìåòðè÷íèì îá’ºêòîì.
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 1 131
Áóäåìî íàçèâàòè êîìá³íàòîðí³ ìíîæèíè ñàìîïîä³áíèìè, ÿêùî ê³ëüê³ñòü
êîìá³íàòîðíèõ êîíô³ãóðàö³é â ³íòåðâàëàõ íóëüîâîãî òà �-ãî ðàíã³â º îäíàêîâîþ,
à êâàç³ñàìîïîä³áíèìè — ÿêùî ê³ëüê³ñòü êîìá³íàòîðíèõ êîíô³ãóðàö³é â ³íòåðâà-
ëàõ íóëüîâîãî òà �-ãî ðàíã³â º ð³çíîþ.
Ñòðóêòóðó êîìá³íàòîðíî¿ ìíîæèíè áóäåìî íàçèâàòè ôðàêòàëüíîþ, ÿêùî
âîíà óòâîðþºòüñÿ çà ðåêóðåíòíèìè ïðàâèëàìè ³ ðåçóëüòàòîì º ìíîæèíè, ÿê³ ìîæ-
íà ïîäàòè ãåîìåòðè÷íèìè ôîðìàìè, íàéá³ëüøà ç ÿêèõ ì³ñòèòü ó ñîá³ ¿õí³ çìåí-
øåí³ êîﳿ. Çàóâàæèìî, ùî òàêèõ îäíàêîâèõ êîï³é ó êîìá³íàòîðí³é ìíîæèí³
ìîæå áóòè áàãàòî.
Àðèôìåòè÷í³ ïîñë³äîâíîñò³. Ðîçãëÿíåìî àðèôìåòè÷í³ ïîñë³äîâíîñò³ [11],
íàïðèêëàä, ïåðø³ n ÷èñåë íàòóðàëüíîãî ðÿäó. Óòâîðåííÿ â íüîìó íàñòóïíèõ ÷è-
ñåë ïðîâîäèòüñÿ äîäàâàííÿì îäèíèö³ äî ïîïåðåäíüîãî. Àíàëîã³÷íî ìîæíà ñêëàñ-
òè ïîñë³äîâíîñò³, ÿê³ ïî÷èíàþòüñÿ ç îäèíèö³, à íàñòóïí³ ¿õí³ åëåìåíòè óòâîðþ-
þòüñÿ äîäàâàííÿì äî ïîïåðåäíüîãî ÷èñëà ïî 2, ïî 3, ïî 4 ³ ò.ä. Îäåðæèìî òàê³
ïîñë³äîâíîñò³:
1 2 3 4 5 6 7, , , , , , , ..., j;
1 3 5 7 9 11 13 2 1, , , , , , , ..., j � ;
1 4 7 10 13 16 19 3 2, , , , , , , ..., j � ; (2)
1 5 9 13 17 21 25 4 3, , , , , , , ..., j � ;
… .
Çíàõîäÿ÷è ñóìó îäíîãî, äâîõ, òðüîõ ³ ò.ä. ÷èñåë ïåðøî¿ (äðóãî¿, òðåòüî¿)
ïîñë³äîâíîñòåé (2), îòðèìàºìî òàê³ ïîñë³äîâíîñò³ ìíîãîêóòíèõ ÷èñåë:
1, 3, 6, 10, 15, 21, 28, ..., j j( ) /� 1 2 — òðèêóòí³ ÷èñëà,
1, 4, 9, 16, 25, 36, 49, ..., j2 — êâàäðàòí³ ÷èñëà,
1, 5, 12, 22, 35, 51, 70, ..., j j( ) /3 1 2� — ï’ÿòèêóòí³ ÷èñëà,
… ,
äå j p�{ , , , ..., }1 2 3 , p — ê³ëüê³ñòü åëåìåíò³â ó çàäàí³é ïîñë³äîâíîñò³.
Ô³ãóðíèìè íàçèâàþòü ÿê ìíîãîêóòí³ ÷èñëà, òàê ³ êîåô³ö³ºíòè ÷ëåí³â ñòåïåí³â
á³íîìà ( )a b n� . Ç éîãî êîåô³ö³ºíò³â ñêëàäàºòüñÿ àðèôìåòè÷íèé òðèêóòíèê (òðè-
êóòíèê Ïàñêàëÿ)
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
Íà êîñèõ ë³í³ÿõ öüîãî òðèêóòíèêà çíàõîäÿòüñÿ êîåô³ö³ºíòè ïåðøèõ (äðóãèõ,
òðåò³õ ³ ò.ä.) ÷ëåí³â ñòåïåí³â ( )a b n� . Ïîäàìî ¿õ ó âèãëÿä³ òàêî¿ òàáëèö³:
1 1 1 1 1 1 1 …
1 2 3 4 5 6 …
1 3 6 10 15 …
1 4 10 20 …
1 5 15
Ïåðøèé ðÿäîê òà ïåðøèé ñòîâïåöü ö³º¿ òàáëèö³ — öå ÷èñëà 1, 1, 1, 1, 1, 1, ...,
Äðóãèé ðÿäîê òà äðóãèé ñòîâïåöü — ÷èñëà íàòóðàëüíîãî ðÿäó: 1, 2, 3, 4, 5, 6, ...
Òðåò³é ðÿäîê òà òðåò³é ñòîâïåöü ì³ñòèòü òðèêóòí³ ÷èñëà 1, 3, 6, 10, 15, 21, ... , j-é
åëåìåíò ÿêîãî º ñóìîþ ïåðøèõ j ÷èñåë íàòóðàëüíîãî ðÿäó. ×åòâåðòèé ðÿäîê òà
÷åòâåðòèé ñòîâïåöü — ÷èñëà 1, 4, 10, 20, 35, 56, ..., j-é åëåìåíò ÿêîãî º ñóìîþ
132 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 1
ïåðøèõ j çíà÷åíü òðèêóòíèõ ÷èñåë. Ö³ ÷èñëà íàçèâàþòü òåòðàåäðè÷íèìè. Ï’ÿòèé ðÿäîê
òà ï’ÿòèé ñòîâïåöü ì³ñòÿòü ÷èñëà, ÿê³ íàçèâàþòü ï’ÿòèêóòíèìè: 1, 5, 15, 35, 70, 126, ... ,
â ÿêèõ j-é åëåìåíò º ñóìîþ ïåðøèõ j çíà÷åíü òåòðàåäðè÷íèõ ÷èñåë, ³ ò.ä. Áóäü-ÿêèé åëå-
ìåíò òàáëèö³, êð³ì ÷èñåë íàòóðàëüíîãî ðÿäó, º ñóìîþ äâîõ ÷èñåë, ùî çíàõîäÿòüñÿ â
òîìó ñàìîìó ðÿäêó âë³âî â³ä øóêàíîãî ÷èñëà ³ â òîìó ñàìîìó ñòîâïö³ íàä íèì.
ßêùî çàïèñàòè ðÿäêè àðèôìåòè÷íîãî òðèêóòíèêà îäèí ï³ä äðóãèì ³ ñêëàñòè
÷èñëà ö³º¿ òàáëèö³ ïî ä³àãîíàë³ (çë³âà íàïðàâî, çíèçó ââåðõ), òî îòðèìàºìî
ïîñë³äîâí³ñòü ÷èñåë Ô³áîíà÷÷³: 1, 1, 1+1=2; 1+2=3; 1+3+1=5; 1+4+3=8; 1+5+6+1=13.
ÏÎÁÓÄÎÂÀ ÀÐÈÔÌÅÒÈ×ÍÈÕ ÏÎÑ˲ÄÎÂÍÎÑÒÅÉ Ï²Ä ×ÀÑ ÃÅÍÅÐÓÂÀÍÍß
ÌÍÎÆÈÍÈ ÊÎÌÁ²ÍÀÒÎÐÍÈÕ ÊÎÍÔ²ÃÓÐÀÖ²É
Îïèñàí³ âèùå ïîñë³äîâíîñò³ ôîðìóþòüñÿ ï³ä ÷àñ çíàõîäæåííÿ ê³ëüêîñò³
êîìá³íàòîðíèõ êîíô³ãóðàö³é w ó ¿õí³é ìíîæèí³ W çà ïðàâèëàìè ¿õíüîãî ãåíå-
ðóâàííÿ ðåêóðåíòíî-ïåð³îäè÷íèì ìåòîäîì [9], çã³äíî ç ÿêèìè óòâîðþþòüñÿ:
à) ³íòåðâàë íóëüîâîãî ðàíãó, á) îáìåæóâàëüíà êîìá³íàòîðíà êîíô³ãóðàö³ÿ (ïåð-
øà â ³íòåðâàë³ íóëüîâîãî ðàíãó), â) ³íòåðâàë �-ãî ðàíãó.
Îñê³ëüêè ³íòåðâàë �-ãî ðàíãó ñêëàäàºòüñÿ ç ³íòåðâàë³â ( )� �1 -ãî ðàíãó, à ³íòåð-
âàë 1-ãî ðàíãó — ç ³íòåðâàë³â íóëüîâîãî ðàíãó, çíàþ÷è ïðàâèëà ¿õíüîãî âïîðÿäêó-
âàííÿ, ìîæíà ëåãêî âèçíà÷èòè ê³ëüê³ñòü êîìá³íàòîðíèõ êîíô³ãóðàö³é ó ¿õí³é ìíî-
æèí³. Çà ïåâíèìè ïðàâèëàìè, ÿê³ º ð³çíèìè äëÿ ð³çíèõ òèï³â êîìá³íàòîðíèõ êîíô³ãó-
ðàö³é, óòâîðèìî àðèôìåòè÷í³ ïîñë³äîâíîñò³, êîæíå çíà÷åííÿ ÿêî¿ çàäຠê³ëüê³ñòü w
â ³íòåðâàëàõ �-ãî ðàíãó. Ôîðìóëó êîìá³íàòîðíîãî ÷èñëà (ê³ëüê³ñòü w ó ìíîæèí³ W)
ïîäàìî �-çíà÷íîþ ñóìîþ (1). ²ç âèðàçó (1) âèäíî, ùî ï³ä ÷àñ âèçíà÷åííÿ ôîðìóëè
êîìá³íàòîðíîãî ÷èñëà çíàõîäÿòüñÿ ñóìè àðèôìåòè÷íèõ ïîñë³äîâíîñòåé.
Äëÿ çíàõîäæåííÿ ôîðìóëè P n� ( ), ÿêà âèçíà÷ຠê³ëüê³ñòü ðîçáèòò³â íàòó-
ðàëüíîãî ÷èñëà ó ï³äìíîæèí³ W W� � , ñôîðìóëþºìî òàêó òåîðåìó.
Òåîðåìà 1. ²ñíóº òðè îñíîâí³ ïîñë³äîâíîñò³
1) ( , , , , , , , , ..., )1 2 4 5 7 8 10 11 J ,
2) ( , , , , , , , , ..., )2 3 5 6 8 9 11 12 1J , (3)
3) ( , , , , , , , , ..., )1 3 4 6 7 9 10 12 2J ,
ð³çíîìàí³òí³ êîìá³íàö³¿ ÿêèõ óòâîðþþòü ³íø³ ïîñë³äîâíîñò³, ñóìà
÷ëåí³â ÿêèõ äîð³âíþº êîìá³íàòîðíîìó ÷èñëó P n� ( ), � � 3 . ×ëåíè J J J, ,1 2
çàëåæàòü â³ä êëàñó ëèøê³â n ïî mod 6 .
Äîâåäåííÿ òåîðåìè 1 íàâåäåíî ó [9]
Òåîðåìà 2. ʳëüê³ñòü ðîçáèòò³â ó ï³äìíîæèí³ W3 îá÷èñëþºòüñÿ çà îäí³ºþ
³ ò³ºþ ñàìîþ ôîðìóëîþ äëÿ òèõ n , äëÿ ÿêèõ n j� ( )mod 6 , j �{ , ..., }0 5 , ³ äîð³âíþº
P n
n
n
n
n
n
� ( )
, ( ) ,
, ( ),
�
�
�
�
�
2
2
2
12
0 6
1
12
1 6
4
�
�
êùî mod
êùî mod
12
2 6
3
12
3 6
4
12
2
2
, ( ) ,
, ( ) ,
,
�
�
�
êùî mod
êùî mod
êùî
n
n
n
n
n
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
4 6
1
12
5 6
2
( ),
, ( ) .
mod
êùî mod
n
n�
(4)
Äîâåäåííÿ. Ôîðìóëè (4) ó [7] âèâåäåíî çà äîïîìîãîþ ðåêóðåíòíîãî âèðàçó
P n P n P n P n k� � �� �( ) ( ) ( ) ( )� � � � � � ��1 1� . Äîâåäåìî òåîðåìó 2 ç âèêîðèñòàí-
íÿì ïîñë³äîâíîñòåé (3).
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 1 133
P n� ( ) äëÿ n j� ( )mod 6 , j �{ , ... , }0 5 , äîð³âíþº ñóì³ ÷ëåí³â îäí³º¿ é ò³º¿ ñàìî¿
ïîñë³äîâí³ñò³ ç N N N) , ), )1 2 [9].
Äëÿ n � 0 6( )mod
P n
n n n n n n
� ( )
( ) ( )
� � � � � � � � � �
�
�
�
�
�
�1 2 4 5 7 8 10 11
2
2
2
8
6
24
2
�
12
.
Äëÿ n �1 6( )mod
P n
n n n n
� ( ) � � � � � � � � � �
�
�
�
�
�
�
�
1 3 4 6 7 9 10 12
1
2
1
8
1
24
1
12
2 2 2
� .
Äëÿ n � 2 6( )mod
P n� ( ) � � � � � � � �2 3 5 6 8 9 11
� � �
�
�
�
�
� �
�
�
12
2
2
2
8
2 4
24
4
12
2
�
n n n n n n( ) ( ) ( )
.
Äëÿ n � 3 6( )mod
P n� ( ) � � �1 2 4 5 7 8 10 11
1
2
1
8
9
24
3
12
2 2 2
� � � � � � �
�
�
�
�
�
�
�
�
n n n n
.
Äëÿ n � 4 6( )mod
P n
n n n n
� ( )
( ) ( )
� � � � � � � � � �
�
�
�
�
� �
�1 3 4 6 7 9 10 12
2
2
2
8
3 1
24
2
�
n2 4
12
�
.
Äëÿ n � 5 6( )mod
P n
n n n n
� ( ) � � � � � � � � � �
�
�
�
�
�
�
�
2 3 5 6 8 9 11 12
1
2
1
8
1
24
1
12
2 2 2
� .
Îòæå, âèðàçè (4), âèâåäåí³ ç âèêîðèñòàííÿì ïîñë³äîâíîñòåé (3), çá³ãàþòüñÿ ç
ôîðìóëàìè, íàâåäåíèìè â [7].
Òåîðåìó 2 äîâåäåíî.
Òåîðåìà 3. ʳëüê³ñòü ðîçáèòò³â P n4 ( ) ï³äìíîæèíè W4 çàëåæèòü â³ä êëàñó
ëèøê³â n çà mod ( )12 òà çàäàºòüñÿ ñóìîþ ÷ëåí³â îäí³º¿ ç äâàíàäöÿòè ïîñë³äîâíîñ-
òåé, óòâîðåíèõ êîìá³íàö³ºþ òðüîõ ïîñë³äîâíîñòåé 1), 2), 3).
Äîâåäåííÿ âèêîíóºòüñÿ òàê ñàìî ÿê ³ äëÿ òåîðåìè 2.
Íàñë³äîê 1. ʳëüê³ñòü ðîçáèòò³â ó ï³äìíîæèí³ W4 îá÷èñëþºòüñÿ çà îäíèì ³
òèì ñàìèì âèðàçîì äëÿ n j� ( )mod 12 , j �{ , ..., }0 11 , ³ äîð³âíþº
P n
n n
n
n n n
4
2
2
3
144
0 12
3 9 5
144
( )
( )
, ( ) ,
( )
,
�
�
�
� � �
�
�
êùî mod
êùî mod àáî mod
êùî mo
n n
n n
n
� �
� �
�
1 12 7 12
3 20
144
2
2
( ) ( ),
( )
, (� d
êùî mod àáî mod
12
3 9 27
144
3 12 9 12
2
) ,
( )
, ( ) ( ),
n n n
n n
� � �
� ��
n n
n
n n n
2
2
3 32
144
4 12
3 9 11
144
( )
, ( ) ,
( )
,
� �
�
� � �
�
�
êùî mod
êùî n n
n n
n
� �
� �
�
5 12 11 12
3 36
144
6
2
( ) ( ),
( )
, (
mod àáî mod
êùî mod� 12
3 16
144
8 12
3 4
144
2
2
),
( )
, ( ) ,
( )
,
n n
n
n n
� �
�
� �
�
�
êùî mod
êùî n �
�
�
�
�
�
�
�
�
�
�
�
�
��
�
�
�
�
�
�
�
�
�
�
�
�
�
10 12( )mod
.
134 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 1
Ðîçãëÿíåìî ìíîæèíó ñïîëó÷åíü áåç ïîâòîðåíü òà ìíîæèíó ðîçáèòò³â n-åëå-
ìåíòíî¿ ìíîæèíè íà ï³äìíîæèíè. Óïîðÿäêóºìî ö³ ìíîæèíè çà çàäàíèìè ïðàâè-
ëàìè ç âèêîðèñòàííÿì ðåêóðåíòíî-ïåð³îäè÷íîãî ìåòîäó [9] ï³äìíîæèíàìè ³çî-
ìîðôíèõ ñïîëó÷åíü W� , ïî÷èíàþ÷è ç � �1 òà çàê³í÷óþ÷è � � n, äå � — ê³ëüê³ñòü
åëåìåíò³â, ÿê³ âèáèðàþòüñÿ ç áàçîâî¿ ìíîæèíè A a an� ( , ..., )1 .
Òåîðåìà 4. Çíà÷åííÿ ïîñë³äîâíîñòåé, ÿê³ çàäàþòü ê³ëüê³ñòü ñïîëó÷åíü áåç
ïîâòîðåíü w ó ¿õí³é ìíîæèí³ W, óïîðÿäêîâàí³é ç âèêîðèñòàííÿì ðåêóðåíòíî-
ïåð³îäè÷íîãî ìåòîäó ãåíåðóâàííÿ êîìá³íàòîðíèõ êîíô³ãóðàö³é, óòâîðþþòü
àðèôìåòè÷íèé òðèêóòíèê òà º ô³ãóðíèìè ÷èñëàìè.
Äîâåäåííÿ. Çàñòîñóºìî ìåòîä ìàòåìàòè÷íî¿ ³íäóêö³¿ äëÿ ï³äìíîæèíè ³çî-
ìîðôíèõ ñïîëó÷åíü. Äëÿ � �1 ï³äìíîæèíà W1 ñêëàäàºòüñÿ ç îäíîãî ³íòåðâàëó
íóëüîâîãî ðàíãó òà ì³ñòèòü óñ³ ìîæëèâ³ äëÿ íüîãî íåòîòîæí³ ñïîëó÷åííÿ
ê³ëüê³ñòþ n.
ϳäìíîæèíà W� äëÿ � � 2 ñêëàäàºòüñÿ ç îäíîãî ³íòåðâàëó ïåðøîãî ðàíãó,
â ÿêèé âõîäÿòü n �1 ³íòåðâàëè íóëüîâîãî ðàíãó. ʳëüê³ñòü w ó íüîìó äîð³âíþº
1 2 3 1
1
2 2 2
� � � � � �
�
�
�
� n
n n n
n
( ) !
( ) ! !
. Àíàëîã³÷íî äëÿ � � 3 ï³äìíîæèíà W3 ,
ïîáóäîâàíà çà òèìè ñàìèìè ïðàâèëàìè, ñêëàäàºòüñÿ ç îäíîãî ³íòåðâàëó äðóãîãî
ðàíãó, â ÿêèé âõîäÿòü ³íòåðâàëè ïåðøîãî ðàíãó, êîæåí ç ÿêèõ ñêëàäàºòüñÿ ç
1 2 3 3, , , ..., n � ³íòåðâàë³â íóëüîâîãî ðàíãó. Òîä³ ê³ëüê³ñòü w ó W3 äîð³âíþº
1 3 6 10
1
2
1 2
6 3 3
2� � � � �
��
�
�
�
� �
�
�
��
j j n n n n
n
n
( ) ( ) ( ) !
( ) ! !
,
j n� �{ , ..., }1 2 . ³äïîâ³äíî, äëÿ � � 4 ï³äìíîæèíà W4 ñêëàäàºòüñÿ ç îäíîãî
³íòåðâàëó òðåòüîãî ðàíãó, â ÿêèé âõîäÿòü n �2 ³íòåðâàëè äðóãîãî ðàíãó, êîæåí
ç ÿêèõ ñêëàäàºòüñÿ ç 1 2 3 3, , , ..., n � ³íòåðâàë³â ïåðøîãî ðàíãó, à îñòàíí³ — ç
1 3 6 10
1
2
3, , , , ...,
( )j j
n
��
�
�
� , j n� �{ , ..., }1 3 , ³íòåðâàë³â íóëüîâîãî ðàíãó. Òîä³
ê³ëüê³ñòü w ó W4 äîð³âíþº 1 4 10 20� � � � ... �
� ��
�
�
�
�
j j j
n
( )( )1 2
6 3
�
� � �
�
�
n n n n n
n
( ) ( )( ) !
( )! !
1 2 3
24 4 4
. Äëÿ n ê³ëüê³ñòü w ó ï³äìíîæèí³ Wn
äîð³âíþº îäèíèö³.
Ç öüîãî âèäíî, ùî îäåðæàí³ ïîñë³äîâíîñò³, ñóìè ÷ëåí³â ÿêèõ çàäàþòü
ê³ëüê³ñòü w ó ï³äìíîæèíàõ W� , óòâîðþþòü àðèôìåòè÷íèé òðèêóòíèê, ùî ³ äîâî-
äèòü òåîðåìó 4.
Ðîçãëÿíåìî ìíîæèíó ðîçáèòò³â n-åëåìåíòíî¿ ìíîæèíè íà ï³äìíîæèíè.
Âïîðÿäêóºìî öþ êîìá³íàòîðíó ìíîæèíó ç âèêîðèñòàííÿì ðåêóðåíòíî-ïåð³îäè÷-
íîãî ìåòîäó äëÿ ï³äìíîæèí W� , äå � — ê³ëüê³ñòü ï³äìíîæèí w wl � , íà ÿê³ ðîç-
áèâàºòüñÿ áàçîâà ìíîæèíà A a an� ( , ..., )1 , � l — ê³ëüê³ñòü åëåìåíò³â ó ï³äìíî-
æèí³ w wl � , l �{ ...,1 �� .
Òåîðåìà 5. Çíà÷åííÿ ïîñë³äîâíîñòåé, ÿê³ çàäàþòü ê³ëüê³ñòü ðîçáèòò³â
n-åëåìåíòíî¿ ìíîæèíè íà ï³äìíîæèíè ó ¿õí³é ï³äìíîæèí³ W� äëÿ � � 2 , óïî-
ðÿäêîâàí³é ç âèêîðèñòàííÿì ðåêóðåíòíî-ïåð³îäè÷íîãî ìåòîäó ãåíåðóâàííÿ
êîìá³íàòîðíèõ êîíô³ãóðàö³é, óòâîðþþòü àðèôìåòè÷íèé òðèêóòíèê òà º ô³ãóð-
íèìè ÷èñëàìè.
Äîâåäåííÿ. Çàñòîñóºìî ìåòîä ìàòåìàòè÷íî¿ ³íäóêö³¿ äëÿ ï³äìíîæèí ³çîìîð-
ôíèõ ðîçáèòò³â W� , � � 2 .
Äëÿ �1 1� �n , �2 1� , ê³ëüê³ñòü ðîçáèòò³â ó ï³äìíîæèí³ W2 äîð³âíþº n.
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 1 135
Äëÿ �1 2� �n , �2 2� , ê³ëüê³ñòü ³íòåðâàë³â �-ãî ðàíãó äîð³âíþº n �1.
ʳëüê³ñòü ³íòåðâàë³â ( )� �1 -ãî ðàíãó â êîæíîìó ç íèõ ïîäàìî ïîñë³äîâí³ñòþ
1 2 3 1, , , ..., n � . Çâ³äñè, ê³ëüê³ñòü w ó W2 äëÿ �1 2� �n , �2 2� äîð³âíþº
1 2 3 1
1
2 2 2
� � � � � �
�
�
�
� n
n n n
n
( ) !
( ) ! !
.
Àíàëîã³÷íî äëÿ çíà÷åíü �1 3� �n , �2 3� , ê³ëüê³ñòü ³íòåðâàë³â �-ãî ðàíãó ñòà-
íîâèòü n �2 , à ê³ëüê³ñòü w ó W2 äîð³âíþº 1 3 6 10
1
2
2� � � �
��
�
�
��
j j
n
( )
n n n n
n
( ) ( ) !
( ) ! !
� �
�
�
1 2
6 3 3
, j n� �{ , ..., }1 2 .
Äëÿ �1 4� �n , �2 4� , ê³ëüê³ñòü w ó W2 äîð³âíþº 1 4 10 20� � � � .. .
� �
� ��
�
�
�
�
j j j
n
( )( )1 2
6 3
n n n n( ) ( )( )� � �
�
1 2 3
24
n
n
!
( )! !� 4 4
.
Çâ³äñè ê³ëüê³ñòü ðîçáèòò³â ó ï³äìíîæèí³ W2 äëÿ � �2 äîð³âíþº
n
n j j
!
( ) ! !�
,
ùî â³äïîâ³äຠâèðàçó
n!
! !� �1 2
. ßêùî �1
2
�
n
, �2
2
�
n
, òî ê³ëüê³ñòü w ó W2
äîð³âíþº
( )!
! !
n
n n
�
��
�
�
�
�
�
�
1
2
2 2
n
n n
!
! ! !
2 2
2
�
�
�
�
�
�
, n j�{ , , ..., }2 4 2 .
Ç öüîãî âèïëèâàº, ùî îäåðæàí³ ïîñë³äîâíîñò³, ñóìè ÷ëåí³â ÿêèõ çàäàþòü
ê³ëüê³ñòü w ó ï³äìíîæèí³ ³çîìîðôíèõ ðîçáèòò³â W2 , óòâîðþþòü àðèôìåòè÷íèé
òðèêóòíèê (òðèêóòíèê Ïàñêàëÿ) òà º ô³ãóðíèìè ÷èñëàìè, ùî ³ äîâîäèòü
òåîðåìó 5.
ÂÈÑÍÎÂÊÈ
Çàâäÿêè çàñòîñóâàííþ ðåêóðåíòíî-ïåð³îäè÷íîãî ìåòîäó, ùî ´ðóíòóºòüñÿ íà
âëàñòèâîñò³ ïåð³îäè÷íîñò³, ìîæíà ó ïðîöåñ³ ãåíåðóâàííÿ êîìá³íàòîðíèõ
êîíô³ãóðàö³é ïðîñë³äêóâàòè äèíàì³êó óòâîðåííÿ ôðàêòàëüíèõ ñòðóêòóð
â êîìá³íàòîðèö³. Öå äຠçìîãó ðîçâ’ÿçóâàòè ïåðåë³÷óâàëüí³ çàäà÷³. ϳä ÷àñ
ï³äðàõóíêó ê³ëüêîñò³ êîìá³íàòîðíèõ êîíô³ãóðàö³é óòâîðþþòüñÿ àðèôìåòè÷í³
ïîñë³äîâíîñò³, ÿê³ º ìíîãîêóòíèìè òà ô³ãóðíèìè ÷èñëàìè. Ñóìè öèõ ïîñë³äîâ-
íîñòåé çàäàþòü ôîðìóëè êîìá³íàòîðíèõ ÷èñåë.
ÑÏÈÑÎÊ Ë²ÒÅÐÀÒÓÐÈ
1. Òóðáèí À.Ô, Ïðàöåâèòûé Í.Â. Ôðàêòàëüíûå ìíîæåñòâà, ôóíêöèè, ðàñïðåäåëåíèÿ. Êèåâ:
Íàóê. äóìêà, 1992. 207 ñ.
2. Ñàâ÷åíêî ².Î. Ôðàêòàëüíèé àíàë³ç ìíîæèí íåïîâíèõ ñóì ÷èñëîâèõ ðÿä³â: àâòîðåô.
äèñ. … êàíä. ôiç.-ìàò. íàóê. Êè¿â, 2016. 20 ñ.
3. Êðîíîâåð Ð.Ì. Ôðàêòàëû è õàîñ â äèíàìè÷åñêèõ ñèñòåìàõ. Îñíîâû òåîðèè. Ìîñêâà: Ïîñòìàð-
êåò, 2000. 352 ñ.
4. Ìàíäåëüáðîò Á. Ôðàêòàëüíàÿ ãåîìåòðèÿ ïðèðîäû. Èæåâñê: ÈÊÈ, 2010. 656 ñ.
5. Ñòåíëè Ð. Ïåðå÷èñëèòåëüíàÿ êîìáèíàòîðèêà. Ìîñêâà: Ìèð, 1990. 440 ñ.
6. Ðûáíèêîâ Ê.À. Ââåäåíèå â êîìáèíàòîðíûé àíàëèç. Ìîñêâà: Èçä-âî Ìîñêîâ. óí-òà, 1985. 308 ñ.
7. Õîëë Ì.Õ. Êîìáèíàòîðèêà. Ìîñêâà: Ìèð, 1970. 424 ñ.
8. Ãóëüäåí ß., Äæåêñîí Ä. Ïåðå÷èñëèòåëüíàÿ êîìáèíàòîðèêà. Ìîñêâà: Íàóêà, 1990. 503 ñ.
136 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 1
9. Òèìîô³ºâà Í.Ê. Òåîðåòèêî-÷èñëîâ³ ìåòîäè ðîçâ’ÿçàííÿ çàäà÷ êîìá³íàòîðíî¿ îïòèì³çàö³¿:
äèñ. … ä-ðà òåõí. íàóê. Êè¿â, 2007. 374 ñ.
10. Òèìîô³ºâà Í.Ê. Ïðî ôðàêòàëüíó ñòðóêòóðó çíàêîâèõ êîìá³íàòîðíèõ ïðîñòîð³â. Ìàòåìàòè÷íå
òà êîìï’þòåðíå ìîäåëþâàííÿ. Ñåð³ÿ: Ô³çèêî-ìàòåìàòè÷í³ íàóêè. 2017. Âèï. 15. Ñ. 236–242.
11. Äåïìàí È.ß. Èñòîðèÿ àðèôìåòèêè. Ìîñêâà: Ãîñóä. ó÷åáíî-ïåäàãîãè÷. èçä-âî Ìèíèñò. ïðî-
ñâåù. ÐÑÔÑÐ, 1959. 423 ñ.
Íàä³éøëà äî ðåäàêö³¿ 15.02.2019
Í.Ê. Òèìîôååâà
Î ÔÐÀÊÒÀËÜÍÎÉ ÏÐÈÐÎÄÅ ÊÎÌÁÈÍÀÒÎÐÍÛÕ ÌÍÎÆÅÑÒÂ
È ÍÀÕÎÆÄÅÍÈÈ ÔÎÐÌÓË ÊÎÌÁÈÍÀÒÎÐÍÛÕ ×ÈÑÅË
Àííîòàöèÿ. Ðàññìîòðåíà ôðàêòàëüíàÿ ñòðóêòóðà êîìáèíàòîðíûõ ìíîæåñòâ,
êîòîðàÿ îáðàçóåòñÿ â ïðîöåññå óïîðÿäî÷åíèÿ êîìáèíàòîðíûõ êîíôèãóðà-
öèé. Ñ èñïîëüçîâàíèåì ôðàêòàëüíûõ ñâîéñòâ îãîâîðåííûõ ìíîæåñòâ ðàç-
ðàáîòàí ïîäõîä ê ðåøåíèþ ïåðå÷èñëèòåëüíûõ çàäà÷ â êîìáèíàòîðèêå. Ïðè
íàõîæäåíèè êîìáèíàòîðíûõ ÷èñåë èñïîëüçóþòñÿ àðèôìåòè÷åñêèå ïîñëåäî-
âàòåëüíîñòè.
Êëþ÷åâûå ñëîâà: êîìáèíàòîðèêà, ôðàêòàëû, êîìáèíàòîðíûå êîíôèãóðàöèè,
ðàçáèåíèå íàòóðàëüíîãî ÷èñëà, àðèôìåòè÷åñêèé òðåóãîëüíèê, êîìáèíàòîðíûå
÷èñëà.
N.K. Timofieva
ON THE FRACTAL NATURE OF COMBINATORIAL SETS AND
FINDING OF FORMULAS FOR COMBINATORIAL NUMBERS
Abstract. The fractal structure of combinatorial sets, which is formed in
ordering of combinatorial configurations, is considered. Using the fractal
properties of contracted sets, an approach to solving enumeration problems in
combinatorics is developed. Arithmetic sequences are used to find combinatorial
numbers.
Keywords: combinatorics, fractals, combinatorial configurations, partitioning of
a natural number, arithmetic triangle, combinatorial numbers.
Òèìîô³ºâà Íàä³ÿ Êîñòÿíòèí³âíà,
äîêòîð òåõí. íàóê, ñòàðøèé íàóêîâèé ñï³âðîá³òíèê, ïðîâ³äíèé íàóêîâèé ñï³âðîá³òíèê ̳æíàðîäíîãî
íàóêîâî-íàâ÷àëüíîãî öåíòðó ³íôîðìàö³éíèõ òåõíîëîã³é òà ñèñòåì ÍÀÍ òà ÌÎÍ Óêðà¿íè, Êè¿â,
e-mail: TymNad@gmail.com.
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 1 137
|
| id | nasplib_isofts_kiev_ua-123456789-190347 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1019-5262 |
| language | Russian |
| last_indexed | 2025-12-07T15:33:23Z |
| publishDate | 2020 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Тимофієва, Н.К. 2023-05-31T14:03:42Z 2023-05-31T14:03:42Z 2020 Про фрактальну природу комбінаторних множин та знаходження формул комбінаторних чисел / Н.К. Тимофієва // Кибернетика и системный анализ. — 2020. — Т. 56, № 1. — С. 129–137. — Бібліогр.: 11 назв. — укр. 1019-5262 https://nasplib.isofts.kiev.ua/handle/123456789/190347 519.11.176 Розглянуто фрактальну структуру комбінаторних множин, яка утворюється в процесі впорядкування комбінаторних конфігурацій. З використанням фрактальних властивостей оговорених множин розроблено підхід до розв’язання перелічувальних задач у комбінаториці. Для знаходження комбінаторних чисел використано арифметичні послідовності. Рассмотрена фрактальная структура комбинаторных множеств, которая образуется в процессе упорядочения комбинаторных конфигураций. С использованием фрактальных свойств оговоренных множеств разработан подход к решению перечислительных задач в комбинаторике. При нахождении комбинаторных чисел используются арифметические последовательности. The fractal structure of combinatorial sets, which is formed in ordering of combinatorial configurations, is considered. Using the fractal properties of contracted sets, an approach to solving enumeration problems in combinatorics is developed. Arithmetic sequences are used to find combinatorial numbers. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Системний аналіз Про фрактальну природу комбінаторних множин та знаходження формул комбінаторних чисел О фрактальной природе комбинаторных множеств и нахождении формул комбинаторных чисел On the fractal nature of combinatorial sets and finding of formulas for combinatorial numbers Article published earlier |
| spellingShingle | Про фрактальну природу комбінаторних множин та знаходження формул комбінаторних чисел Тимофієва, Н.К. Системний аналіз |
| title | Про фрактальну природу комбінаторних множин та знаходження формул комбінаторних чисел |
| title_alt | О фрактальной природе комбинаторных множеств и нахождении формул комбинаторных чисел On the fractal nature of combinatorial sets and finding of formulas for combinatorial numbers |
| title_full | Про фрактальну природу комбінаторних множин та знаходження формул комбінаторних чисел |
| title_fullStr | Про фрактальну природу комбінаторних множин та знаходження формул комбінаторних чисел |
| title_full_unstemmed | Про фрактальну природу комбінаторних множин та знаходження формул комбінаторних чисел |
| title_short | Про фрактальну природу комбінаторних множин та знаходження формул комбінаторних чисел |
| title_sort | про фрактальну природу комбінаторних множин та знаходження формул комбінаторних чисел |
| topic | Системний аналіз |
| topic_facet | Системний аналіз |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/190347 |
| work_keys_str_mv | AT timofíêvank profraktalʹnuprirodukombínatornihmnožintaznahodžennâformulkombínatornihčisel AT timofíêvank ofraktalʹnoiprirodekombinatornyhmnožestvinahoždeniiformulkombinatornyhčisel AT timofíêvank onthefractalnatureofcombinatorialsetsandfindingofformulasforcombinatorialnumbers |