dm3 (Лекция), страница 2

Ïîäìíîæåñòâà îïðåäåëåííîãîâèäà íàçûâàþòñÿ. Ïîäñ÷åò êîëè÷åñòâà êîìáèíàòîðíûõ êîíôèãóðàöèé () ñîñòàâëÿåò ñóòü ïåðå÷èñëèòåëüíûõ çàäà÷ êîìáèíàòîðíîãî àíàëèçà. Òàêèå çàäà÷è ïðèõîäèòñÿ ðåøàòü êàê ÷àñòèáîëåå ñëîæíûõ çàäà÷ äèñêðåòíîé ìàòåìàòèêè.êîìáèíàòîðíûìè êîíôèãóðàöèÿìèêîìáèíàòîðíûõ ÷èñåë3.1Ïðîñòåéøèå ïðàâèëà êîìáèíàòîðíûõ âû÷èñëåíèéÏðè ïîäñ÷åòå êîìáèíàòîðíûõ êîíôèãóðàöèé ïðèìåíÿþòñÿ äâà î÷åíü ïðîñòûõ ïðàâèëà.Ïðàâèëî ïðîèçâåäåíèÿ.O1N1Åñëè îáúåêò ìîæíî âûáðàòü ðàçëè÷íûìè ñïîñîáàìè, à îáúåêò O2 âûáèðàåòñÿ ðîâíî N2 ñïîñîáàìè, òî ïàðó îáúåêòîâ{O1 , O2 } ìîæíî âûáðàòü ðîâíî N1 · N2 ðàçëè÷íûìè ñïîñîáàìè.

1Ïðàâèëî ñóììû. Åñëè îáúåêò O1 ìîæíî âûáðàòü N1 ðàçëè÷íûìè ñïîñîáàìè, à îáúåêò O2 âûáèðàåòñÿ ðîâíî N2 ñïîñîáàìè, è ïðè ýòîì âûáîð O1 è O2îäíîâðåìåííî íåâîçìîæåí 2, òî âûáîð "O1 èëè O2" ìîæíî îñóùåñòâèòü ðîâíîN1 + N2 ðàçëè÷íûìè ñïîñîáàìè.Ýòè ïðàâèëà ïîçâîëÿþò ëåãêî âû÷èñëèòü êîëè÷åñòâî íåêîòîðûõ ÷àñòî ïðèìåíÿåìûõ êîìáèíàòîðíûõ êîíôèãóðàöèé.Ïðèìåð. Èç ãîðîäà A ðîâíî m1 äîðîã âåäóò â ãîðîä B è n1 äîðîã â ãîðîäC . Ðîâíî m2 äîðoã âåäóò èç B â ãîðîä D, ðîâíî n2 äîðîã èç C â D. Èç A â Dìîæíî ïðîåõàòü òîëüêî ÷åðåç ãîðîä B èëè ãîðîä C .

Ñêîëüêèìè ñïîñîáàìè ìîæíîïîïàñòü èç A â D?Ïðèìåíÿÿ ïðàâèëî ïðîèçâåäåíèÿ, íàõîäèì ÷èñëî m1 m2 ïóòåé èç A â D ÷åðåçB è ÷èñëî n1 n2 ïóòåé èç A â D ÷åðåç C . Äàëåå ïî ïðàâèëó ñóììû ïîëó÷àåì îòâåòm1 m2 + n1 n2 .Òåîðåìà 1.U = {e1 , . . . , en }nn2(U ).Äîêàçàòåëüñòâî. Ïóñòü B ïîäìíîæåñòâî ìíîæåñòâà U . Êàæäîå òàêîå ïîäìíîæåñòâî îäíîçíà÷íî îïðåäåëÿåòñÿ ïðèíàäëåæíîñòüþ èëè íåïðèíàäëåæíîñòüþåìó êàæäîãî èç ýëåìåíòîâ e1 , . . . , en . Èòàê, äëÿ êàæäîãî j = 1, .

. . , n íàäî âûáðàòüîäíî èç äâóõ óñëîâèé: ej ∈ B èëè ej 6∈ B . Åñòü ðîâíî nj = 2 ñïîñîáà âûáîðà òàêîãî óñëîâèÿ äëÿ êàæäîãî j = 1, . . . , n. Ïðèìåíÿÿ ïðàâèëî ïðîèçâåäåíèÿ, ïîëó÷àåìÊîíå÷íîå ìíîæåñòâîèç ýëåìåíòîâ èìååòïîäìíîæåñòâ âêëþ÷àÿ ïóñòîå è ñàìî ìíîæåñòâîðîâíî1 îòñþäà2 ýòîè íàçâàíèå ïðàâèëà, èìååòñÿ òàêæå àíàëîãèÿ ñ ïðîèçâåäåíèåì ñîáûòèéóñëîâèå î÷åíü âàæíî, åãî èãíîðèðîâàíèå ïðèâîäèò ê ñìûñëîâûì îøèáêàì10÷èñëî 2 × · · · × 2 = 2n ñïîñîáîâ âûáîðà óñëîâèé äëÿ âñåõ j = 1, . . . , n, ò.

å. ÷èñëîðàçëè÷íûõ ïîäìíîæåñòâ ìíîæåñòâà U . Ïðèìåð 1. Ìíîæåñòâî èç 3 ýëåìåíòîâ {E1 , E2 , E3 } èìååò ðîâíî 23 = 8 ïîäìíîæåñòâ:∅, {E1 }, {E2 }, {E3 }, {E1 , E2 }, {E1 , E3 }, {E2 , E3 }, {E1 , E2 , E3 }.Ïîäìíîæåñòâà âçàèìíî îäíîçíà÷íî ñîîòâåòñòâóþò áèíàðíûì âåêòîðàì (x1 , x2 , x3 ),ãäå xj = 1, åñëè Ej ïðèíàäëåæèò ïîäìíîæåñòâó, è xj = 0 â ïðîòèâíîì ñëó÷àå.Ñëåäñòâèå 1.(x1 , . . .

, xn )n2n .Òàêèå âåêòîðû ÷àñòî ïðèìåíÿþò ïðè ïîäñ÷åòå êîìáèíàòîðíûõ êîíôèãóðàöèé.Áèíàðíûå âåêòîðû óíèâåðñàëüíûé ñïîñîá êîäèðîâàíèÿ, ò. å. çàïèñè ëþáîéèíôîðìàöèè â ÿçûêå ñ àëôàâèòîì {0, 1}. Ðàññìîòðèì àíàëîãè÷íûé ñïîñîá çàïèñèâ ÿçûêå ñ ëþáûì êîíå÷íûì àëôàâèòîì. Äàäèì òî÷íûå îïðåäåëåíèÿ è âûâåäåìäîâîëüíî ïðîñòûå, íî âàæíûå ðåçóëüòàòû, øèðîêî ïðèìåíÿåìûå â äèñêðåòíîéìàòåìàòèêå.Êîëè÷åñòâî áèíàðíûõ âåêòîðîâ3.2äëèíû ðàâíîÑëîâà â êîíå÷íîì àëôàâèòåàëôàÑëîâîì äëèíû â àëôàâèòåÊîíå÷íîå ìíîæåñòâî, ñêàæåì, èç k ýëåìåíòîâ, A = {a1 , . . . , ak } íàçûâàåòñÿ, åãî ýëåìåíòû aj , èëè áóêâàìè.nA íàçûâàåòñÿ êîíå÷íàÿ ïîñëåäîâàòåëüíîñòü ñèìâîëîâ àëôàâèòà A:âèòîìñèìâîëàìèaj(1) aj(2) . .

. aj(n) ,aj(1) , aj(2) , . . . , aj(n) ∈ A.Ìíîæåñòâî âñåõ ñëîâ äëèíû n â àëôàâèòå A îáîçíà÷àåòñÿ êàê An .×èñëî ýëåìåíòîâ ïðîèçâîëüíîãî êîíå÷íîãî ìíîæåñòâà M îáîçíà÷àåòñÿ êàê |M |è íàçûâàåòñÿM . Î÷åâèäíî, |∅| = 0. Íàòóðàëüíûå ÷èñëà è 0 ýòî âñå ìîùíîñòè êîíå÷íûõ ìíîæåñòâ. Èìåííî òàêèì îáðàçîì óäðåâíèõ ëþäåé ñôîðìèðîâàëîñü àáñòðàêòíîå ïîíÿòèå íàòóðàëüíîãî ÷èñëà, èìåííîòàê ó÷àò ÷èñëàì ìàëåíüêèõ äåòåé.Ïî ïðàâèëó ïðîèçâåäåíèÿ ëåãêî âûâîäèòñÿ îáîáùåíèå ñëåäñòâèÿ 1.Ñëåäñòâèå 2.nkkn.Ýòî æå ìîæíî çàïèñàòü òàê: åñëè |A| = k , òî |An | = k n (÷àñòíûé ñëó÷àé ïðàâèëàïðîèçâåäåíèÿ).Ïðè çàïèñè ñëîâ ôèêñèðîâàííîãî àëôàâèòà óäîáíî ðàñïîëàãàòü ñëîâà â íåêîòîðîì ïîðÿäêå, ïîçâîëÿþùåì ëåãêî èõ ïðîñìàòðèâàòü è ïðîâåðÿòü, âñå ëè íóæíûåñëîâà ïðèñóòñòñòâóþò, íåò ëè ïîâòîðåíèé.

Îáùåïðèíÿòûì ÿâëÿåòñÿ. Ýòèì ñïîñîáîì ïåðå÷èñëÿþòñÿ ñëîâà â ñëîâàðÿõ, ñïðàâî÷íèêàõ,ýíöèêëîïåäèÿõ, ñïèñêàõ èìåí è íàçâàíèé è ò. ï. Ñëîâà cíà÷àëà óïîðÿäî÷èâàþòñÿ ïî ïåðâîé áóêâå, çàòåì ñëîâà ñ îäèíàêîâîé ïåðâîé áóêâîé óïîðÿäî÷èâàþòñÿ ïîìîùíîñòüþ êîíå÷íîãî ìíîæåñòâàÊîëè÷åñòâî ñëîâ äëèíû â àëôàâèòå èç áóêâ ðàâíîëåêñèêîãðà-ôè÷åñêèé ïîðÿäîê11âòîðîé è òàê äàëåå.

Åñëè ecòü ñëîâà ðàçíîé äëèíû, òî ïîðÿäîê ñëîâ ñ îäèíàêîâûìèïåðâûìè áóêâàìè òàêîâ, ÷òî ñíà÷àëà âûïèñûâàþòñÿ êîðîòêèå ñëîâà, ó êîòîðûõíåò ñëåäóþùåé áóêâû, çàòåì óæå îñòàëüíûå ñëîâà (ñ òåìè æå ïåðâûìè áóêâàìè)óïîðÿäî÷èâàþòñÿ ïî ñëåäóþùåé áóêâå.Ïðèìåð 3.

Âûïèøåì â ëåêñèêîãðàôè÷åñêîì ïîðÿäêå âñå 32 = 9 ñëîâ äëèíû 2â àëôàâèòå {a, b, c} ìîùíîñòè 3:aa, ab, ac, ba, bb, bc, ca, cb, cc.Ïðèìåð 4.Âûïèøåì â ëåêñèêîãðàôè÷åñêîì ïîðÿäêå ñëîâà ðàçíîé äëèíû âàëôàâèòå {a, b, c} èç ìíîæåñòâà {bcaa, b, cca, cbac, acb, bcab, abcc, bcca, bbc, cc} :abcc, acb, b, bbc, bcaa, bcab, bcca, cbac, cc, cca.ñîðòèðîâêîéÏðîöåññ óïîðÿäî÷èâàíèÿ ðàçëè÷íûõ ñïèñêîâ íàçûâàåòñÿ èõ. Ñîðòèðîâêà ÷àñòî ïðèìåíÿåòñÿ â ðàçëè÷íûõ çàäà÷àõ îáðàáîòêè èíôîðìàöèè.

Ñëîæíîñòü ñîðòèðîâêè îöåíèâàåòñÿ ìåòîäàìè äèñêðåòíîé ìàòåìàòèêè.Ñèììåòðè÷íûå îòíîñèòåëüíî ñâîåé ñåðåäèíû ñëîâà íàçûâàþòñÿ.Ïðèìåðû ïàëèíäðîìîâ â ðóññêîì ÿçûêå èìÿ Àëëà, ñëîâî "êàçàê". Íàéäåì ÷èñëîïàëèíäðîìîâ äëèíû n â àëôàâèòå ìîùíîñòè k .  ïàëèíäðîìå ÷åòíîé äëèíû nïðîèçâîëüíî ìîæíî çàäàòü òîëüêî ïåðâûå n/2 áóêâ, îñòàëüíûå òå æå ïåðâûån/2 áóêâ, çàïèñàííûå â îáðàòíîì ïîðÿäêå. ×èñëî ïàëèíäðîìîâ ÷åòíîé äëèíû nðàâíî k n/2 .

 ïàëèíäðîìå íå÷åòíîé äëèíû n = 2m + 1 ïðîèçâîëüíî ìîæíî çàäàòüïåðâûå m áóêâ è åùå îäíó öåíòðàëüíóþ. ×èñëî òàêèõ ïàëèíäðîìîâ ðàâíî k m+1 . ìàòåìàòèêå ïðèíÿòî îáîçíà÷åíèå dxe äëÿ íàèìåíüøåãî öåëîãî ÷èñëà N òàêîãî,÷òî N ≥ x, ãäå x ïðîèçâîëüíîå âåùåñòâåííîå ÷èñëî. Òàê, d0.7e = 1, dπe = 4,d(−5)e = −5. Ðåçóëüòàòû íàøèõ íàáëþäåíèé íàä ïàëèíäðîìàìè ìîæíî çàïèñàòüêàêÑëåäñòâèå 3.nkdn/2ek.Ïðèìåð 5. Âûïèøåì â ëåêñèêîãðàôè÷åñêîì ïîðÿäêå âñå ïàëèíäðîìû äëèíûíå áîëåå 3 â àëôàâèòå {a, b, c}.Èìååì k = 3.

×èñëî ïàëèíäðîìîâ äëèíû 1 ðàâíî 3d1/2e = 31 = 3, äëèíû 2 3d2/2e = 31 = 3 , äëèíó 3 èìåþò 3d3/2e = 32 = 9 ïàëèíäðîìîâ. Îñòàëîñü âûïèñàòüâñå 3 + 3 + 9 = 15 ïàëèíäðîìîâ â ëåêñèêîãðàôè÷åñêîì ïîðÿäêå:ïàëèíäðîìàìè×èñëî ïàëèíäðîìîâ äëèíû â àëôàâèòå ìîùíîñòè ðàâíîa, aa, aaa, aba, aca, b, bab, bb, bbb, bcb, c, cac, cbc, cc, ccc.Íåêîòîðûå ìàñòåðà ñëîâà ïðîÿâëÿþò íåìàëî èñêóññòâà â ñîñòàâëåíèè îñìûñëåííûõ ïàëèíäðîìîâ, íàïðèìåð, "Àííà, Âàñ è òèíà ìàíèò, è ñàâàííà". Ýòà ôðàçàñîäåpæèò 24 áóêâû ðóññêîãî àëôàâèòà.

Îáùåå ÷èñëî ïàëèíäðîìîâ òàêîé äëèíû12åñòü 3312 , íî èç íèõ íàäî åùå âûáðàòü ñèíòàêñè÷åñêè ïðàâèëüíî çàïèñûâàåìûå, àèç ïîñëåäíèõ îñìûñëåííûå. Òðåáóåòñÿ âèðòóîçíîå âëàäåíèå ÿçûêîì!Ïðèìåð 6. Àâòîìîáèëüíûå íîìåðà ñîäåðæàò 3 äåñÿòè÷íûå öèôðû è 4 áóêâûèç 12, îáùèõ äëÿ êèðèëëè÷åñêîãî è ëàòèíñêîãî àëôàâèòîâ. Íàéäåì ÷èñëî âñåõâîçìîæíûõ íîìåðîâ. Òðè öèôðû ìîæíî âûáðàòü, ïî ïðàâèëó ïðîîèçâåäåíèÿ, 103ñïîñîáàìè.

Àíàëîãè÷íî 4 áóêâû ìîæíî âûáðàòü 124 = 20 736 ñïîñîáàìè. Âûáèðàÿ è öèôðû è áóêâû, ïîëó÷àåì, ïî ïðàâèëó ïðîèçâåäåíèÿ, 20 736 000 íîìåðîâ.Íåêîòîðûå ëþäè ñ÷èòàþò ïðåñòèæíûìè "çåðêàëüíûå" íîìåðà, â êîòîðûõ ñëîâî,ñîñòàâëåííîå èç öèôð, åñòü ïàëèíäðîì. ×èñëî òàêèõ íîìåðîâ îêàçûâàåòñÿ, â ñîîòâåòñòâèè ñ óæå èçëîæåííûìè ðåçóëüòàòàìè, 122 103 = 144 000.3.3Ðàçìåùåíèÿ, ïåðåñòàíîâêè, ñî÷åòàíèÿÏóñòü ôèêñèðîâàíî n-ýëåìåíòíîå ìíîæåñòâî U = {E1 , .

. . , En }. Åãî íåóïîðÿäî÷åííûå k -ýëåìåíòíûå ïîäìíîæåñòâà{Ej(1) , . . . , Ej(k) }, 1 ≤ j(1) < · · · < j(k) ≤ n, 0 ≤ k ≤ n,ñî÷åòàíèÿìè èç ýëåìåíòîâ ïîíàçûâàþòñÿnk (óïîòðåáëÿþòñÿ ôèãóðíûå ñêîáêè). ×èñëî ñî÷åòàíèé èç n ýëåìåíòîâ ïî k îáîçíà÷àåòñÿ êàê Cnk .Óïîðÿäî÷åííûå k -ýëåìåíòíûå ïîäìíîæåñòâà(Ej(1) , .

. . , Ej(k) ), 1 ≤ j(1) < · · · < j(k) ≤ n, 0 ≤ k ≤ n,ðàçìåùåíèÿìè èç ýëåìåíòîâ ïîíàçûâàþòñÿnk (óïîòðåáëÿþòñÿ êðóãëûå ñêîáêè, êàê ïðè óêàçàíèè ýëåìåíòîâ âåêòîðîâ è ìàòðèö). ×èñëî ðàçìåùåíèé èç nýëåìåíòîâ ïî k îáîçíà÷àåòñÿ êàê Akn . Ðàçìåùåíèå èç k ýëåìåíòîâ k ïî íàçûâàåòñÿýòèõ k.Òåîðåìà 2.0≤k≤nïåðåñòàíîâêîéýëåìåíòîâÅñëè, òîAkn = n(n − 1)(n − 2) · · · (n − k + 1) = ÷àñòíîñòè,n!.(n − k)!3Akk = k!.Äîêàçàòåëüñòâî.Ïóñòü A ðàçìåùåíèå, ñîñòîÿùåå èç k ýëåìåíòîâ ìíîæåñòâà U = {E1 , . .

. , En }. Îíî îäíîçíà÷íî îïðåäåëÿåòñÿ âûáîðîì ñâîèõ ýëåìåíòîâEj(1) , . . . , Ej(k) . Ýëåìåíò Ej(1) ìîæíî âûáðàòü n ñïîñîáàìè (ëþáîé èç n ýëåìåíòîâìíîæåñòâà Ω), Ej(2) (n − 1) ñïîñîáîì (ëþáîé èç ýëåìåíòîâ ìíîæåñòâà U êðîìå3 Åñëèk ïîëîæèòåëüíîå öåëîå, òî k! = 1 × 2 × · · · × k è ïî îïðåäåëåíèþ 0!=113Ej(1) ), Ej(3) (n − 2) ñïîñîáàìè è òàê äàëåå. Ïîñëåäíèé ýëåìåíò Ej(k) ðàçìåùåíèÿ ìîæíî âûáðàòü (n − (k − 1)) ñïîñîáàìè (ëþáîé â U êðîìå Ej(1) , .

. . , Ej(k−1) .Ïðèìåíÿÿ ïðàâèëî ïðîèçâåäåíèÿ, ïîëó÷àåì Akn = n(n − 1)(n − 2) · · · (n − k + 1). Ïðèìåð 7. Âûïèøåì â ëåêñèêîãðàôè÷åñêîì ïîðÿäêå âñå k! ïåðåñòàíîâîê kýëåìåíòîâ äëÿ k = 2, 3, 4. Èìååì 2! = 2, 3! = 6, 4! = 24. Ýòî ÷èñëî ïåðåñòàíîâîê.Óêàæåì ñàìè ïåðåñòàíîâêè â íóæíîì ïîðÿäêå.k=2:12, 21.k=3:123, 132, 213, 231, 312, 321.k=4:1234, 1243, 1324, 1342, 1423, 1432,2134, 2143, 2314, 2341, 2413, 2431,3124, 3142, 3214, 3241, 3412, 3421,4123, 4132, 4213, 4231, 4312, 4321.Ïðèìåð 8.Íà ïðàçäíèê ïðèøëè ñóïðóæåñêàÿ ïàðà ñ äâóìÿ äåòüìè, ñåìüÿñ îäíèì ðåáåíêîì, äâå ïàðû áåç äåòåé è ñâîáîäíûé ìóæ÷èíà. Îíè õîòÿ âñòàòüøåðåíãîé äëÿ ñîâìåñòíîãî ôîòî.

Ñêîëüêèìè ñïîñîáàìè ìîæíî ýòî ñäåëàòü, åñëèâñå ÷ëåíû êàæäîé ñåìüè õîòÿò áûòü ðÿäîì äðóã ñ äðóãîì?Áóäåì ñ÷èòàòü êàæäóþ ñåìüþ (è îäíîãî ìóæ÷èíó) êàê åäèíûé îáúåêò. Èìååì5 îáúåêòîâ, êîòîðûå ìîæíî ïåðåñòàâèòü 5! ñïîñîáàìè. Íî íàäî åùå óïîðÿäî÷èòüâñåõ ïðåäñòàâèòåëåé êàæäîé ñåìüè-îáúåêòà. Ïðèìåíÿÿ ïðàâèëî ïðîèçâåäåíèÿ, íàõîäèì 5!4!3!(2!)2 1! = 69 120 ñïîñîáîâ.ñëîâà w íàçûâàåòñÿ ñëîâî, ïîëó÷åííîå ïåðåñòàíîâêîé âñåõ áóêâñëîâà w.

Ñëîâî "ñëîí" èìååò 4! àíàãðàìì, à ñëîâî "æàáà" íå 4!, à òîëüêî 12 (âëåêñèêîãðàôè÷åñêîì ïîðÿäêå: ààáæ, ààæá, àáàæ, àáæà, àæàá, àæáà, áààæ, áàæà,áæàà, æààá, æàáà, æáàà), ïîñêîëüêó áóêâà "à" ïîâòîðÿåòÿ äâàæäû, ïåðåñòàíîâêèýòèõ áóêâ íå ìåíÿþò ñëîâî. Àíàëîãè÷íî ñëîâî "êàêàäó" èìååò íå 6!, à 6!/(2!)2àíàãðàìì, â ýòîì ñëîâå ïî äâà ðàçà ïîâòîðÿþòñÿ áóêâû "à" è "ê". Íåòðóäíîâûâåñòè îáùóþ ôîðìóëó:nk, k ≤ nÀíàãðàììîéåñëè ñëîâî èìååò äëèíó è ñîäåðæèò, ðàçëè÷íûõ áóêâ, ïîâòîðÿþùèõñÿ k1, . . .

, kn ðàç (ïðè ýòîì k1 + · · · + kn = n), òî÷èñëî àíàãðàìì òàêîãî ñëîâà åñòün!.k1 ! · · · kn !Àíàãðàììû ÷àñòî èñïîëüçóþòñÿ êàê ïñåâäîíèìû (âûìûøëåííûå èìåíà). Íàïðèìåð, Ôðàíñóà Ðàáëå ïîäïèñûâàë ñâîé îñòðîñàòèðè÷åñêèé ðîìàí "Ãàðãàíòþà èÏàíòàãðþýëü"(15331551) ïñåâäîíèìîì Àëüêîôðèáàñ Íàçüå (Alcofribas Nasier ïîëíàÿ àíàãðàììà, âêëþ÷àÿ ïðîáåë, ïîäëèííîãî èìåíè Francois Rabelais). Äðóãîé14ïðèìåð: âåñüìà óñïåøíîãî õóäîæíèêà XX âåêà Ñàëüâàäîðà Äàëè (Salvador Dali)äðóçüÿ íàçûâàëè Avida Dollars ("Ãðåáóùèé Äåíüãè").Òåîðåìà 3.0≤k≤nÅñëèCnk =, òîn(n − 1)(n − 2) · · · (n − k + 1)n!=.k!k!(n − k)!(1)Çàìåòèì, ÷òî Cnk = Akn /Akk è ïðèìåíèì òåîðåìó 2.