Одна комбинаторная задача в классе двоичных векторов заданного веса
У класі двійкових векторів фіксованої ваги введено поняття l-сходинки, яке є структурною характеристикою вектора. Виведено формули для обчислення потужностей множин векторів цього класу з певними структурними властивостями, що пов’язані з поняттям l-сходинки....
Gespeichert in:
| Datum: | 2012 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2012
|
| Schriftenreihe: | Кибернетика и системный анализ |
| Schlagworte: | |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/84161 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Одна комбинаторная задача в классе двоичных векторов заданного веса / А.А. Левитская // Кибернетика и системный анализ. — 2012. — Т. 48, № 6. — С. 72-75. — Бібліогр.: 2 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-84161 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-841612015-07-04T03:01:34Z Одна комбинаторная задача в классе двоичных векторов заданного веса Левитская, А.А. Системный анализ У класі двійкових векторів фіксованої ваги введено поняття l-сходинки, яке є структурною характеристикою вектора. Виведено формули для обчислення потужностей множин векторів цього класу з певними структурними властивостями, що пов’язані з поняттям l-сходинки. The notion of l-step is introduced in the class of binary vectors of fixed weight, which is a structural characteristic of a vector. Formulas for calculating the powers of sets of vectors of this class with certain structural properties related to the notion of l-step are derived. 2012 Article Одна комбинаторная задача в классе двоичных векторов заданного веса / А.А. Левитская // Кибернетика и системный анализ. — 2012. — Т. 48, № 6. — С. 72-75. — Бібліогр.: 2 назв. — рос. 0023-1274 http://dspace.nbuv.gov.ua/handle/123456789/84161 519.21 ru Кибернетика и системный анализ Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Системный анализ Системный анализ |
| spellingShingle |
Системный анализ Системный анализ Левитская, А.А. Одна комбинаторная задача в классе двоичных векторов заданного веса Кибернетика и системный анализ |
| description |
У класі двійкових векторів фіксованої ваги введено поняття l-сходинки, яке є структурною характеристикою вектора. Виведено формули для обчислення потужностей множин векторів цього класу з певними структурними властивостями, що пов’язані з поняттям l-сходинки. |
| format |
Article |
| author |
Левитская, А.А. |
| author_facet |
Левитская, А.А. |
| author_sort |
Левитская, А.А. |
| title |
Одна комбинаторная задача в классе двоичных векторов заданного веса |
| title_short |
Одна комбинаторная задача в классе двоичных векторов заданного веса |
| title_full |
Одна комбинаторная задача в классе двоичных векторов заданного веса |
| title_fullStr |
Одна комбинаторная задача в классе двоичных векторов заданного веса |
| title_full_unstemmed |
Одна комбинаторная задача в классе двоичных векторов заданного веса |
| title_sort |
одна комбинаторная задача в классе двоичных векторов заданного веса |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2012 |
| topic_facet |
Системный анализ |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/84161 |
| citation_txt |
Одна комбинаторная задача в классе двоичных векторов заданного веса / А.А. Левитская // Кибернетика и системный анализ. — 2012. — Т. 48, № 6. — С. 72-75. — Бібліогр.: 2 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT levitskaâaa odnakombinatornaâzadačavklassedvoičnyhvektorovzadannogovesa |
| first_indexed |
2025-07-06T11:06:52Z |
| last_indexed |
2025-07-06T11:06:52Z |
| _version_ |
1836895451083702272 |
| fulltext |
ÓÄÊ 519.21
À.À. ËÅÂÈÒÑÊÀß
ÎÄÍÀ ÊÎÌÁÈÍÀÒÎÐÍÀß ÇÀÄÀ×À  ÊËÀÑÑÅ ÄÂÎÈ×ÍÛÕ
ÂÅÊÒÎÐÎÂ ÇÀÄÀÍÍÎÃÎ ÂÅÑÀ
Êëþ÷åâûå ñëîâà: äâîè÷íûé âåêòîð âåñà ( )n m� 0 , l-ñòóïåíü, ÷èñëî
l-ñòóïåíåé.
Ïåðå÷èñëèòåëüíûå çàäà÷è êîìáèíàòîðíîãî àíàëèçà, îáóñëîâëåííûå ïîòðåáíî-
ñòÿìè ñîâðåìåííîé ïðàêòèêè, âûçûâàþò îñîáûé èíòåðåñ êàê ó ïðèêëàäíèêîâ,
òàê è ó ìàòåìàòèêîâ-òåîðåòèêîâ. Èõ ôîðìóëèðîâêè ïîðîé î÷åíü ïðîñòû (äîñ-
òàòî÷íî âñïîìíèòü ðÿä èçâåñòíûõ çàäà÷ èç êðèïòîãðàôèè), îäíàêî íà ðåøåíèÿ
íåêîòîðûõ èç íèõ èíîãäà óõîäÿò ãîäû è äàæå äåñÿòèëåòèÿ.
Èñïîëüçîâàíèå ñîâðåìåííîé âû÷èñëèòåëüíîé òåõíèêè â èññëåäîâàíèè òàêèõ
ïðîáëåì ïîçâîëÿåò ñåãîäíÿ íå òîëüêî óñïåøíî ðåøàòü ìíîãèå àêòóàëüíûå
òåõíè÷åñêèå âîïðîñû, íî è ïðèâîäèò ê ïîÿâëåíèþ íîâûõ êîìáèíàòîðíûõ
ìåòîäîâ äèñêðåòíîé ìàòåìàòèêè. Ðåøåíèþ îäíîé ïåðå÷èñëèòåëüíîé çàäà÷è è
ïîñâÿùåíà äàííàÿ ðàáîòà.
Ïîñòàíîâêà çàäà÷è. Ïóñòü M( , )n m0 — ìíîæåñòâî n-ìåðíûõ äâîè÷íûõ
âåêòîðîâ, ñîñòîÿùèõ èç m m n0 01( )� � íóëåé è n m� 0 åäèíèö, ò.å. ëþáîé âåêòîð
x M� ( , )n m0 èìååò âåñ | |x � �n m0 .
Îïðåäåëåíèå. Áóäåì ãîâîðèòü, ÷òî êîîðäèíàòû xi , xi l�
, ãäå l � 1; i, i l n� � ,
âåêòîðà x M� ( , )n m0 îáðàçóþò l-ñòóïåíü â x, åñëè x xi i l� � �
� �
� 1 1 , xi l�
� 0.
Îáîçíà÷èì �( , ; , )n m l0 x ÷èñëî l-ñòóïåíåé â âåêòîðå x M� ( , )n m0 .
Çàäà÷à ñîñòîèò â îïðåäåëåíèè ÷èñëà âåêòîðîâ x M� ( , )n m0 , äëÿ êîòîðûõ
�( , ; , )n m l k0 x � , ãäå k — íåîòðèöàòåëüíîå öåëîå ÷èñëî, ò.å. â îïðåäåëåíèè
ìîùíîñòè ìíîæåñòâà A x M x( , ; , ) ( , ) : ( , ; , )n m l k n m n m l k0 0 0= { }
def
� �� .
Î÷åâèäíî, åñëè k
n m
l
m
�
�
�
�
�
min ,
0
0 èëè l n m � 0 , òîãäà
| ( , ; , )|A n m l k0 0� ,
ãäå | |A — ìîùíîñòü ìíîæåñòâà A.
Çàìåòèì, ÷òî ïîíÿòèå l-ñòóïåíè âñòðå÷àåòñÿ â ðàáîòàõ Â.È. Ìàñîëà, íàïðè-
ìåð â [1], ãäå îíî îïðåäåëåíî ñëåäóþùèì îáðàçîì: êîîðäèíàòû xi è xi l�
âåêòîðà
x M� ( , )n m0 , 1 1� � �l n , îáðàçóþò l-ñòóïåíü, åñëè x xi i l
�
. Ñëåäîâàòåëüíî,
ïîíÿòèÿ l-ñòóïåíè, èñïîëüçóåìûå â íàñòîÿùåé ñòàòüå è â [1], ñóùåñòâåííî
îòëè÷àþòñÿ.
Îñíîâíûå ðåçóëüòàòû. Ëþáîé âåêòîð x M� ( , )n m0 ïðåäñòàâèì êàê íåêóþ
( , )n m0 -öåïî÷êó, ñîñòîÿùóþ èç m0 ïðîíóìåðîâàííûõ ñëåâà íàïðàâî (îò 1 äî m0)
íóëåé, ïåðåä êàæäûì èç êîòîðûõ è ïîñëå ïîñëåäíåãî íóëÿ ñ íîìåðîì m0 ðàñïî-
ëîæåí ÿùèê.  ñâîþ î÷åðåäü, ÿùèêè òàêæå ïðîíóìåðîâàíû ñëåâà íàïðàâî (îò 1
äî m0 1� ). (Óñëîâèìñÿ äàëåå îáîçíà÷àòü ÿùèêè äâóìÿ âåðòèêàëüíûìè ÷åðòî÷êà-
ìè.) Â ÿùèêè ñîîòâåòñòâåííî äàííîìó âåêòîðó ðàçìåùàþò n m� 0 åäèíèö. Íàïðè-
ìåð, (14,7)-öåïî÷êà âèäà | | | | | | | | | | | | | | | |2030 010 0 0 01 ñîîòâåòñòâóåò òàêîìó äâîè÷íîìó
âåêòîðó: 11011100100001.
72 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 6
� À.À. Ëåâèòñêàÿ, 2012
 ñèëó ââåäåííîãî âûøå îïðåäåëåíèÿ l-ñòóïåíè è â ñâÿçè ñ ïðåäëîæåííîé
èíòåðïðåòàöèåé äâîè÷íûõ âåêòîðîâ x M� ( , )n m0 î÷åâèäíû ñëåäóþùèå óòâåð-
æäåíèÿ.
Óòâåðæäåíèå 1. Äëÿ ôèêñèðîâàííîãî âåêòîðà x M� ( , )n m0 ðàâåíñòâî
�( , ; , )n m l0 0x � , ãäå 1 0� � �l n m , èìååò ìåñòî òîãäà è òîëüêî òîãäà, êîãäà â
ñîîòâåòñòâóþùåé âåêòîðó x ( , )n m0 -öåïî÷êå â êàæäîì èç ïåðâûõ m0 ÿùèêîâ
ñîäåðæèòñÿ íå áîëåå ( )l �1 åäèíèö.
Óòâåðæäåíèå 2. Äëÿ ôèêñèðîâàííîãî âåêòîðà x M� ( , )n m0 ðàâåíñòâî
�( , ; , )n m l k0 x � , ãäå 1
0
0� �
�
�
�
�
�
k
n m
l
mmin , , èìååò ìåñòî òîãäà è òîëüêî òîãäà,
êîãäà ñðåäè ïåðâûõ m0 ÿùèêîâ åñòü ðîâíî k ÿùèêîâ, â êàæäîì èç êîòîðûõ ñîäåð-
æèòñÿ íå ìåíåå l åäèíèö, à â îñòàëüíûõ ñ íîìåðàìè, íå ïðåâûøàþùèìè m0 , — íå
áîëåå ( )l �1 åäèíèö.
Âû÷èñëèì ìîùíîñòü ìíîæåñòâà A( , ; , )n m l k0 â çàâèñèìîñòè îò çíà÷åíèé l,
1 0� � �l n m , è k, 0
0
0� �
�
�
�
�
�
k
n m
l
mmin , .
Òåîðåìà 1. Åñëè m l n m0 01( )� � � èëè, ÷òî òî æå ñàìîå, l
n
m
�
0
, òîãäà
| ( , ; , )|À n m l l
m
0 0 0
� . (1)
Äîêàçàòåëüñòâî. Ñîãëàñíî óòâåðæäåíèþ 1 â ñîîòâåòñòâóþùåé ( , )n m0 -öåïî÷êå
âåêòîðà x, äëÿ êîòîðîãî �( , ; , )n m l0 0x � , â êàæäîì èç ïåðâûõ m0 ÿùèêîâ ìîæåò
íàõîäèòüñÿ îò 0 äî ( )l �1 åäèíèö; ÷èñëî åäèíèö â ÿùèêå ñ íîìåðîì ( )m0 1� îäíî-
çíà÷íî îïðåäåëÿåòñÿ âåëè÷èíîé ( )n m s� �0 , ãäå s — ñóììàðíîå êîëè÷åñòâî åäè-
íèö â ïåðâûõ m0 ÿùèêàõ. Ïîñêîëüêó ìàêñèìàëüíî âîçìîæíûì çíà÷åíèåì âåëè-
÷èíû s ÿâëÿåòñÿ ÷èñëî m l0 1( )� , êîòîðîå â ñèëó óñëîâèÿ òåîðåìû 1 íå ïðåâûøàåò
( )n m� 0 , ìîùíîñòü ìíîæåñòâà A( , ; , )n m l0 0 ðàâíà ÷èñëó m0-ìåðíûõ âåêòîðîâ,
êàæäàÿ êîîðäèíàòà êîòîðûõ ïðèíèìàåò çíà÷åíèÿ 0 1 1, , ,� l � . ×èñëî òàêèõ
âåêòîðîâ ðàâíî l
m0 , ÷òî è òðåáîâàëîñü äîêàçàòü.
Òåîðåìà 2. Ïðè m l0 1( )� > n m� 0 , ÷òî ðàâíîñèëüíî l
n
m
0
, èìååò ìåñòî
ñëåäóþùåå ðåêóððåíòíîå ñîîòíîøåíèå:
| ( , ; , )| | ( , ;A An m l C n lt m t l
m
t
t
n m
l
0
0
1
00
0
0
� � � �
�
�
�
�
�
�
�
�
�
�
1 0, )|, (2)
ãäå [ ]a — öåëàÿ ÷àñòü ÷èñëà a.
Äîêàçàòåëüñòâî. Èç óñëîâèÿ òåîðåìû 2 ñëåäóåò, ÷òî m
n m
l
0
0
1
�
�
. Ïîýòîìó
ìíîæåñòâî A( , ; , )n m l
0
0 , ñòîÿùåå â ëåâîé ÷àñòè ðàâåíñòâà (2), îïðåäåëÿåòñÿ òåìè
âåêòîðàìè x M� ( , )n m0 , â ñîîòâåòñòâóþùèõ ( , )n m0 -öåïî÷êàõ êîòîðûõ, âî-ïåð-
âûõ, ÷èñëî t ÿùèêîâ ñ íîìåðàìè, íå ïðåâûøàþùèìè m 0 è ñîäåðæàùèìè ïî
( )l �1 åäèíèö â êàæäîì, íå ìîæåò áûòü áîëüøå
n m
l
�
�
0
1
, è, âî-âòîðûõ, â ëþáîì
äðóãîì ÿùèêå èç ïåðâûõ m0 , íå âõîäÿùèõ â ïðèâåäåííûé âûøå íàáîð èç t ÿùè-
êîâ, ñîäåðæèòñÿ íå áîëåå ( )l �2 åäèíèö. Ïîñêîëüêó ÷èñëî ñïîñîáîâ âûáîðà t ÿùè-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 6 73
êîâ ñ ( )l �1 åäèíèöàìè â êàæäîì èç ïåðâûõ m0 ÿùèêîâ ðàâíî C
m
t
0
, à ÷èñëî ðàç-
ëè÷íûõ ðàçìåùåíèé îñòàâøèõñÿ ( ( ) )n m l t� � �0 1 åäèíèö ïî îñòàëüíûì
( )m t0 1� � ÿùèêàì, â êîòîðûõ êàæäûé ÿùèê ñ íîìåðîì, îòëè÷íûì îò ( )m
0
1� , ñî-
äåðæèò íå áîëåå ( )l �2 åäèíèö, ðàâíî | ( , ){ }x Ì� � �n lt m t0 : �( , ,n lt m t� �0
l n lt m t l� � � � � �1 0 1 00; ) | | , , ,x A} ( )|
def
, ôîðìóëà (2) íå âûçûâàåò ñîìíåíèÿ.
Òåîðåìà 2 äîêàçàíà.
Äàëåå íåïîñðåäñòâåííî èç òåîðåì 1, 2 ïîëó÷àåì òàêîé ðåçóëüòàò.
Òåîðåìà 3. Ñïðàâåäëèâû ñëåäóþùèå ðàâåíñòâà:
1) | ( , ; , )|A n m0 1 0 1� ,
2) | ( , ; , )|
, / ,
,
A n m
m n
C m n
m
m
t
t
n m
0
0
0
0
2 0
2 20
0
0
�
�
�
�
�
åñëè
åñëè / .2
�
�
�
�
Äîêàçàòåëüñòâî. Ëåãêî âèäåòü, ÷òî äëÿ l �1 óñëîâèå òåîðåìû 1 âûïîëíåíî.
Ïîýòîìó â ñèëó (2) ñïðàâåäëèâî ðàâåíñòâî 1 òåîðåìû 3, à â ñèëó (1) è (2) èìååò
ìåñòî ðàâåíñòâî 2 òåîðåìû 3, ÷òî è òðåáîâàëîñü äîêàçàòü.
Òåîðåìà 4. Äëÿ ëþáûõ l, 1 0� � �l n m , è k, 1 0
0
� �
�
�
�
�
�
k m
n m
l
min , ,
ñïðàâåäëèâû ñëåäóþùèå ðàâåíñòâà:
| ( , ; , )| | ( ( ) ,A An m l k C C n k l s
m
k
s k
s
s
n m kl
0 1
0
0
0
1� � � �
� �
�
� �
�
m k l0 0� ; , )| , (3)
åñëè 1 0
0
� �
�
�
�
�
�
�
�
�
�
k m
n m
l
min , ;
| ( , ; , )|
( )/
A n m l k C
m
n m l
0
0
0
�
�
, åñëè k m
n m
l
n m
l
�
�
�
�
�
�
�
�
min ,0
0 0
; (4)
| ( , ; , )|A n m l k C
n m l
m
0
0
0
�
�
, åñëè k m
n m
l
m�
�
�
�
�
�
�min ,0
0
0 . (5)
Äîêàçàòåëüñòâî. Ñîãëàñíî óòâåðæäåíèþ 2 ìíîæåñòâî A( , ; , )n m l k0 ñîñòîèò
èç äâîè÷íûõ âåêòîðîâ âåñà ( )n m� 0 , â ñîîòâåòñòâóþùèõ ( , )n m0 -öåïî÷êàõ êîòî-
ðûõ íàéäåòñÿ ðîâíî k ÿùèêîâ ñ íîìåðàìè, íå ïðåâûøàþùèìè m0 , â êàæäîì èç
êîòîðûõ íàõîäèòñÿ íå ìåíåå l åäèíèö, à â êàæäîì èç îñòàâøèõñÿ ÿùèêîâ ñ íîìå-
ðàìè, îòëè÷íûìè îò ( )m0 1� , — íå áîëåå ( )l �1 åäèíèö. Ñ ó÷åòîì ýòîãî ìîùíîñòü
ìíîæåñòâà A( , ; , )n m l k0 îïðåäåëÿåòñÿ ñëåäóþùèì îáðàçîì.
Ïóñòü 1 0
0
� �
�
�
�
�
�
k m
n m
l
min , . Äîêàæåì ðàâåíñòâî (3).
Ôèêñèðóåì k ÿùèêîâ èç ïåðâûõ m0 ÿùèêîâ. Ýòî ìîæíî ñäåëàòü C
m
k
0
ñïîñî-
áàìè. Çàòåì â êàæäûé èç íèõ ïîìåùàåì l åäèíèö. Ïðèíèìàÿ âî âíèìàíèå, ÷òî ÷èñ-
ëî åäèíèö â êàæäîì èç ôèêñèðîâàííûõ k ÿùèêîâ äîëæíî áûòü íå ìåíüøå l, áåðåì s,
0 0� � � �s n m lk, åäèíèö è ïðîèçâîëüíî ðàñïðåäåëÿåì èõ ïî ôèêñèðîâàííûì k ÿùè-
êàì äîïîëíèòåëüíî ê óæå èìåþùèìñÿ òàì åäèíèöàì. Ïîñëåäíåå ìîæíî ñäåëàòü
C
s k
s
� �1
ñïîñîáàìè [2, ñ. 58]. Â êàæäîì èç îñòàâøèõñÿ ÿùèêîâ ñ íîìåðàìè, îòëè÷-
74 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 6
íûìè îò ( )m0 1� , ÷èñëî åäèíèö íå äîëæíî ïðåâûøàòü ( )l �1 ; ýòî ìîæíî îáåñïå-
÷èòü | ( , ; , )|A n m lk s m k l� � � �0 0 0 ñïîñîáàìè. Ïðèâåäåííûå ðàññóæäåíèÿ äîêàçû-
âàþò ôîðìóëó (3).
Äîêàæåì ñîîòíîøåíèå (4). Î÷åâèäíî, ìíîæåñòâî A n m l
n m
l
, ; ,0
0�
�
�
�
�
�
�
�
�
ñîñòîèò èç âåêòîðîâ x, ñîîòâåòñòâóþùèå ( , )n m0 -öåïî÷êè êîòîðûõ èìåþò âèä:
â êàæäîì èç ôèêñèðîâàííûõ k
n m
l
�
� 0
ÿùèêîâ èç ïåðâûõ m0 ÿùèêîâ ñîäåðæèò-
ñÿ ïî l åäèíèö, ò.å. âñå ( )n m� 0 åäèíèö íàõîäÿòñÿ â ôèêñèðîâàííûõ k
n m
l
�
� 0
ÿùèêàõ, à îñòàëüíûå ( )m k0 1� � ÿùèêîâ ïóñòû. Ïîýòîìó ìîùíîñòü
ðàññìàòðèâàåìîãî ìíîæåñòâà ðàâíà ÷èñëó ðàçëè÷íûõ ñïîñîáîâ âûáîðà èç ïåðâûõ
m0 ÿùèêîâ k
n m
l
�
� 0
ÿùèêîâ, ÷òî è òðåáîâàëîñü äîêàçàòü.
È, íàêîíåö, ôîðìóëà (5) ñëåäóåò èç òàêèõ ðàññóæäåíèé.
Ìíîæåñòâî A( , ; , )n m l m0 0
ñîñòîèò èç âåêòîðîâ x, ñîîòâåòñòâóþùèå
( , )n m0 -öåïî÷êè êîòîðûõ ìîæíî ïîñòðîèòü ñëåäóþùèì îáðàçîì: â êàæäûé èç
ïåðâûõ m0 ÿùèêîâ ïîìåùàåì ïî l åäèíèö. Ïîñêîëüêó â ñèëó óñëîâèÿ (5)
lm n m0 0� � , îñòàâøèåñÿ ( )n m lm� �0 0 åäèíèö ïðîèçâîëüíî ðàçìåùàåì ïî
( )m0 1� ÿùèêàì. Ïîñëåäíåå íà îñíîâàíèè [2, ñ. 58] ìîæíî ñäåëàòü C
n m l
m
� 0
0
ñïîñîáàìè.
Òåîðåìà 4 äîêàçàíà.
Çàìåòèì, ÷òî íåïîñðåäñòâåííî èç îïðåäåëåíèÿ ìíîæåñòâ À ( , ; , )n m l0 0 ,
1 0� � �l n m , ñëåäóåò, ÷òî A A( , ; , ) ( , ; , )n m l n m l0 01 0 0� � . Îòñþäà î÷åâèäíî, ÷òî
B A A( , ; ) ( , ; , ) \ ( , ; , )n m l n m l n m l
0 0 01 0 1 0� � � — ýòî ìíîæåñòâî âåêòîðîâ
x M� ( , )n m0 , â êàæäîì èç êîòîðûõ ìàêñèìàëüíàÿ äëèíà ñòóïåíè ðàâíà ( )l �1 .
Ìîùíîñòü òàêîãî ìíîæåñòâà îïðåäåëÿåòñÿ ôîðìëîé
| ( , ; )| | ( , ; , )| | ( , ; , )|B A An m l n m l n m l0 0 01 0 1 0� � � � . (6)
Èòàê, ôîðìóëû (1)–(6) ïîçâîëÿþò âû÷èñëÿòü ìîùíîñòè ñîîòâåòñòâóþùèõ
ïîäìíîæåñòâ ìíîæåñòâà M( , )n m0 . Èñïîëüçîâàíèå ôîðìóë (2), (3), (6) ïðè
áîëüøèõ çíà÷åíèÿõ n òðåáóåò ïðèâëå÷åíèÿ âû÷èñëèòåëüíîé òåõíèêè.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Ì à ñ î ë  . È . Àñèìïòîòè÷åñêîå ïîâåäåíèå íåêîòîðûõ ñòàòèñòèê (0,1)-âåêòîðà // Òåîðèÿ
âåðîÿòíîñòåé è ìàò. ñòàòèñòèêà. — 1990. — Âûï. 43. — Ñ. 83–90.
2. Ô å ë ë å ð Â . Ââåäåíèå â òåîðèþ âåðîÿòíîñòåé è åå ïðèìåíåíèÿ. Ò.1. — M.: Ìèð, 1984. — 528 ñ.
Ïîñòóïèëà 17.02.2012
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 6 75
<<
/ASCII85EncodePages false
/AllowTransparency false
/AutoPositionEPSFiles true
/AutoRotatePages /None
/Binding /Left
/CalGrayProfile (Gray Gamma 2.2)
/CalRGBProfile (sRGB IEC61966-2.1)
/CalCMYKProfile (U.S. Web Coated \050SWOP\051 v2)
/sRGBProfile (sRGB IEC61966-2.1)
/CannotEmbedFontPolicy /Error
/CompatibilityLevel 1.3
/CompressObjects /Off
/CompressPages true
/ConvertImagesToIndexed true
/PassThroughJPEGImages false
/CreateJDFFile false
/CreateJobTicket false
/DefaultRenderingIntent /Default
/DetectBlends true
/DetectCurves 0.0000
/ColorConversionStrategy /LeaveColorUnchanged
/DoThumbnails false
/EmbedAllFonts true
/EmbedOpenType false
/ParseICCProfilesInComments true
/EmbedJobOptions true
/DSCReportingLevel 0
/EmitDSCWarnings false
/EndPage -1
/ImageMemory 1048576
/LockDistillerParams true
/MaxSubsetPct 100
/Optimize true
/OPM 1
/ParseDSCComments true
/ParseDSCCommentsForDocInfo true
/PreserveCopyPage true
/PreserveDICMYKValues true
/PreserveEPSInfo true
/PreserveFlatness true
/PreserveHalftoneInfo false
/PreserveOPIComments false
/PreserveOverprintSettings true
/StartPage 1
/SubsetFonts false
/TransferFunctionInfo /Apply
/UCRandBGInfo /Remove
/UsePrologue false
/ColorSettingsFile (Color Management Off)
/AlwaysEmbed [ true
]
/NeverEmbed [ true
]
/AntiAliasColorImages false
/CropColorImages true
/ColorImageMinResolution 290
/ColorImageMinResolutionPolicy /Warning
/DownsampleColorImages true
/ColorImageDownsampleType /Bicubic
/ColorImageResolution 600
/ColorImageDepth 8
/ColorImageMinDownsampleDepth 1
/ColorImageDownsampleThreshold 1.01667
/EncodeColorImages true
/ColorImageFilter /FlateEncode
/AutoFilterColorImages false
/ColorImageAutoFilterStrategy /JPEG
/ColorACSImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/ColorImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/JPEG2000ColorACSImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/JPEG2000ColorImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/AntiAliasGrayImages false
/CropGrayImages true
/GrayImageMinResolution 290
/GrayImageMinResolutionPolicy /Warning
/DownsampleGrayImages true
/GrayImageDownsampleType /Bicubic
/GrayImageResolution 600
/GrayImageDepth 8
/GrayImageMinDownsampleDepth 2
/GrayImageDownsampleThreshold 2.03333
/EncodeGrayImages true
/GrayImageFilter /FlateEncode
/AutoFilterGrayImages false
/GrayImageAutoFilterStrategy /JPEG
/GrayACSImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/GrayImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/JPEG2000GrayACSImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/JPEG2000GrayImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/AntiAliasMonoImages false
/CropMonoImages true
/MonoImageMinResolution 800
/MonoImageMinResolutionPolicy /Warning
/DownsampleMonoImages true
/MonoImageDownsampleType /Bicubic
/MonoImageResolution 2400
/MonoImageDepth -1
/MonoImageDownsampleThreshold 1.50000
/EncodeMonoImages true
/MonoImageFilter /CCITTFaxEncode
/MonoImageDict <<
/K -1
>>
/AllowPSXObjects false
/CheckCompliance [
/PDFX3:2003
]
/PDFX1aCheck false
/PDFX3Check false
/PDFXCompliantPDFOnly false
/PDFXNoTrimBoxError false
/PDFXTrimBoxToMediaBoxOffset [
0.00000
0.00000
0.00000
0.00000
]
/PDFXSetBleedBoxToMediaBox false
/PDFXBleedBoxToTrimBoxOffset [
0.00000
0.00000
0.00000
0.00000
]
/PDFXOutputIntentProfile (None)
/PDFXOutputConditionIdentifier ()
/PDFXOutputCondition ()
/PDFXRegistryName ()
/PDFXTrapped /False
/Description <<
/CHS <FEFF4f7f75288fd94e9b8bbe5b9a521b5efa7684002000500044004600206587686353ef901a8fc7684c976262535370673a548c002000700072006f006f00660065007200208fdb884c9ad88d2891cf62535370300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c676562535f00521b5efa768400200050004400460020658768633002>
/CHT <FEFF4f7f752890194e9b8a2d7f6e5efa7acb7684002000410064006f006200650020005000440046002065874ef653ef5728684c9762537088686a5f548c002000700072006f006f00660065007200204e0a73725f979ad854c18cea7684521753706548679c300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c4f86958b555f5df25efa7acb76840020005000440046002065874ef63002>
/DAN <FEFF004200720075006700200069006e0064007300740069006c006c0069006e006700650072006e0065002000740069006c0020006100740020006f007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e007400650072002000740069006c0020006b00760061006c00690074006500740073007500640073006b007200690076006e0069006e006700200065006c006c006500720020006b006f007200720065006b007400750072006c00e60073006e0069006e0067002e0020004400650020006f007000720065007400740065006400650020005000440046002d0064006f006b0075006d0065006e0074006500720020006b0061006e002000e50062006e00650073002000690020004100630072006f00620061007400200065006c006c006500720020004100630072006f006200610074002000520065006100640065007200200035002e00300020006f00670020006e0079006500720065002e>
/ESP <FEFF005500740069006c0069006300650020006500730074006100200063006f006e0066006900670075007200610063006900f3006e0020007000610072006100200063007200650061007200200064006f00630075006d0065006e0074006f0073002000640065002000410064006f0062006500200050004400460020007000610072006100200063006f006e00730065006700750069007200200069006d0070007200650073006900f3006e002000640065002000630061006c006900640061006400200065006e00200069006d0070007200650073006f0072006100730020006400650020006500730063007200690074006f00720069006f00200079002000680065007200720061006d00690065006e00740061007300200064006500200063006f00720072006500630063006900f3006e002e002000530065002000700075006500640065006e00200061006200720069007200200064006f00630075006d0065006e0074006f00730020005000440046002000630072006500610064006f007300200063006f006e0020004100630072006f006200610074002c002000410064006f00620065002000520065006100640065007200200035002e003000200079002000760065007200730069006f006e0065007300200070006f00730074006500720069006f007200650073002e>
/FRA <FEFF005500740069006c006900730065007a00200063006500730020006f007000740069006f006e00730020006100660069006e00200064006500200063007200e900650072002000640065007300200064006f00630075006d0065006e00740073002000410064006f00620065002000500044004600200070006f007500720020006400650073002000e90070007200650075007600650073002000650074002000640065007300200069006d007000720065007300730069006f006e00730020006400650020006800610075007400650020007100750061006c0069007400e90020007300750072002000640065007300200069006d007000720069006d0061006e0074006500730020006400650020006200750072006500610075002e0020004c0065007300200064006f00630075006d0065006e00740073002000500044004600200063007200e900e90073002000700065007500760065006e0074002000ea0074007200650020006f007500760065007200740073002000640061006e00730020004100630072006f006200610074002c002000610069006e00730069002000710075002700410064006f00620065002000520065006100640065007200200035002e0030002000650074002000760065007200730069006f006e007300200075006c007400e90072006900650075007200650073002e>
/ITA <FEFF005500740069006c0069007a007a006100720065002000710075006500730074006500200069006d0070006f007300740061007a0069006f006e00690020007000650072002000630072006500610072006500200064006f00630075006d0065006e00740069002000410064006f006200650020005000440046002000700065007200200075006e00610020007300740061006d007000610020006400690020007100750061006c0069007400e00020007300750020007300740061006d00700061006e0074006900200065002000700072006f006f0066006500720020006400650073006b0074006f0070002e0020004900200064006f00630075006d0065006e007400690020005000440046002000630072006500610074006900200070006f00730073006f006e006f0020006500730073006500720065002000610070006500720074006900200063006f006e0020004100630072006f00620061007400200065002000410064006f00620065002000520065006100640065007200200035002e003000200065002000760065007200730069006f006e006900200073007500630063006500730073006900760065002e>
/JPN <FEFF9ad854c18cea51fa529b7528002000410064006f0062006500200050004400460020658766f8306e4f5c6210306b4f7f75283057307e30593002537052376642306e753b8cea3092670059279650306b4fdd306430533068304c3067304d307e3059300230c730b930af30c830c330d730d730ea30f330bf3067306e53705237307e305f306f30d730eb30fc30d57528306b9069305730663044307e305930023053306e8a2d5b9a30674f5c62103055308c305f0020005000440046002030d530a130a430eb306f3001004100630072006f0062006100740020304a30883073002000410064006f00620065002000520065006100640065007200200035002e003000204ee5964d3067958b304f30533068304c3067304d307e30593002>
/KOR <FEFFc7740020c124c815c7440020c0acc6a9d558c5ec0020b370c2a4d06cd0d10020d504b9b0d1300020bc0f0020ad50c815ae30c5d0c11c0020ace0d488c9c8b85c0020c778c1c4d560002000410064006f0062006500200050004400460020bb38c11cb97c0020c791c131d569b2c8b2e4002e0020c774b807ac8c0020c791c131b41c00200050004400460020bb38c11cb2940020004100630072006f0062006100740020bc0f002000410064006f00620065002000520065006100640065007200200035002e00300020c774c0c1c5d0c11c0020c5f40020c2180020c788c2b5b2c8b2e4002e>
/NLD (Gebruik deze instellingen om Adobe PDF-documenten te maken voor kwaliteitsafdrukken op desktopprinters en proofers. De gemaakte PDF-documenten kunnen worden geopend met Acrobat en Adobe Reader 5.0 en hoger.)
/NOR <FEFF004200720075006b00200064006900730073006500200069006e006e007300740069006c006c0069006e00670065006e0065002000740069006c002000e50020006f0070007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e00740065007200200066006f00720020007500740073006b00720069006600740020006100760020006800f800790020006b00760061006c00690074006500740020007000e500200062006f007200640073006b0072006900760065007200200065006c006c00650072002000700072006f006f006600650072002e0020005000440046002d0064006f006b0075006d0065006e00740065006e00650020006b0061006e002000e50070006e00650073002000690020004100630072006f00620061007400200065006c006c00650072002000410064006f00620065002000520065006100640065007200200035002e003000200065006c006c00650072002000730065006e006500720065002e>
/PTB <FEFF005500740069006c0069007a006500200065007300730061007300200063006f006e00660069006700750072006100e700f50065007300200064006500200066006f0072006d00610020006100200063007200690061007200200064006f00630075006d0065006e0074006f0073002000410064006f0062006500200050004400460020007000610072006100200069006d0070007200650073007300f5006500730020006400650020007100750061006c0069006400610064006500200065006d00200069006d00700072006500730073006f0072006100730020006400650073006b0074006f00700020006500200064006900730070006f00730069007400690076006f0073002000640065002000700072006f00760061002e0020004f007300200064006f00630075006d0065006e0074006f00730020005000440046002000630072006900610064006f007300200070006f00640065006d0020007300650072002000610062006500720074006f007300200063006f006d0020006f0020004100630072006f006200610074002000650020006f002000410064006f00620065002000520065006100640065007200200035002e0030002000650020007600650072007300f50065007300200070006f00730074006500720069006f007200650073002e>
/SUO <FEFF004b00e40079007400e40020006e00e40069007400e4002000610073006500740075006b007300690061002c0020006b0075006e0020006c0075006f0074002000410064006f0062006500200050004400460020002d0064006f006b0075006d0065006e007400740065006a00610020006c0061006100640075006b006100730074006100200074007900f6007000f60079007400e400740075006c006f0073007400750073007400610020006a00610020007600650064006f007300740075007300740061002000760061007200740065006e002e00200020004c0075006f0064007500740020005000440046002d0064006f006b0075006d0065006e00740069007400200076006f0069006400610061006e0020006100760061007400610020004100630072006f0062006100740069006c006c00610020006a0061002000410064006f00620065002000520065006100640065007200200035002e0030003a006c006c00610020006a006100200075007500640065006d006d0069006c006c0061002e>
/SVE <FEFF0041006e007600e4006e00640020006400650020006800e4007200200069006e0073007400e4006c006c006e0069006e006700610072006e00610020006f006d002000640075002000760069006c006c00200073006b006100700061002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e00740020006600f600720020006b00760061006c00690074006500740073007500740073006b0072006900660074006500720020007000e5002000760061006e006c00690067006100200073006b0072006900760061007200650020006f006300680020006600f600720020006b006f007200720065006b007400750072002e002000200053006b006100700061006400650020005000440046002d0064006f006b0075006d0065006e00740020006b0061006e002000f600700070006e00610073002000690020004100630072006f0062006100740020006f00630068002000410064006f00620065002000520065006100640065007200200035002e00300020006f00630068002000730065006e006100720065002e>
/DEU <FEFF004a006f0062006f007000740069006f006e007300200066006f00720020004100630072006f006200610074002000440069007300740069006c006c0065007200200037002e000d00500072006f006400750063006500730020005000440046002000660069006c0065007300200077006800690063006800200061007200650020007500730065006400200066006f0072002000680069006700680020007100750061006c0069007400790020007000720069006e00740069006e0067002e000d0028006300290020003200300031003000200053007000720069006e006700650072002d005600650072006c0061006700200047006d006200480020>
/ENU (Use these settings to create Adobe PDF documents for quality printing on desktop printers and proofers. Created PDF documents can be opened with Acrobat and Adobe Reader 5.0 and later.)
>>
/Namespace [
(Adobe)
(Common)
(1.0)
]
/OtherNamespaces [
<<
/AsReaderSpreads false
/CropImagesToFrames true
/ErrorControl /WarnAndContinue
/FlattenerIgnoreSpreadOverrides false
/IncludeGuidesGrids false
/IncludeNonPrinting false
/IncludeSlug false
/Namespace [
(Adobe)
(InDesign)
(4.0)
]
/OmitPlacedBitmaps false
/OmitPlacedEPS false
/OmitPlacedPDF false
/SimulateOverprint /Legacy
>>
<<
/AddBleedMarks false
/AddColorBars false
/AddCropMarks false
/AddPageInfo false
/AddRegMarks false
/ConvertColors /NoConversion
/DestinationProfileName ()
/DestinationProfileSelector /NA
/Downsample16BitImages true
/FlattenerPreset <<
/PresetSelector /MediumResolution
>>
/FormElements false
/GenerateStructure true
/IncludeBookmarks false
/IncludeHyperlinks false
/IncludeInteractive false
/IncludeLayers false
/IncludeProfiles true
/MultimediaHandling /UseObjectSettings
/Namespace [
(Adobe)
(CreativeSuite)
(2.0)
]
/PDFXOutputIntentProfileSelector /NA
/PreserveEditing true
/UntaggedCMYKHandling /LeaveUntagged
/UntaggedRGBHandling /LeaveUntagged
/UseDocumentBleed false
>>
]
>> setdistillerparams
<<
/HWResolution [2400 2400]
/PageSize [2834.646 2834.646]
>> setpagedevice
|