Makala haya yataangazia sehemu maalum ya hisabati inayoitwa combinatorics. Mifumo, sheria, mifano ya utatuzi wa matatizo - yote haya unaweza kupata hapa kwa kusoma makala hadi mwisho.
Kwa hivyo, sehemu hii ni nini? Combinatorics inahusika na suala la kuhesabu vitu vyovyote. Lakini katika kesi hii, vitu sio plums, pears au apples, lakini kitu kingine. Combinatorics hutusaidia kupata uwezekano wa tukio. Kwa mfano, wakati wa kucheza kadi, kuna uwezekano gani kwamba mpinzani ana kadi ya tarumbeta? Au mfano kama huo - kuna uwezekano gani kwamba utapata nyeupe kabisa kutoka kwa begi la mipira ishirini? Ni kwa aina hii ya kazi ambapo tunahitaji kujua angalau misingi ya sehemu hii ya hisabati.
Mipangilio ya uunganishaji
Kwa kuzingatia suala la dhana za kimsingi na fomula za viunganishi, hatuwezi ila kuzingatia usanidi wa upatanishi. Wao hutumiwa sio tu kwa ajili ya uundaji, bali pia kwa kutatua matatizo mbalimbali ya combinatorial. Mifano ya miundo kama hii ni:
- uwekaji;
- ruhusa;
- mchanganyiko;
- muundo wa nambari;
- pasua nambari.
Tutazungumza kuhusu tatu za kwanza kwa undani zaidi baadaye, lakini tutazingatia utunzi na mgawanyiko katika sehemu hii. Wanapozungumza juu ya muundo wa nambari fulani (sema, a), wanamaanisha uwakilishi wa nambari a kama jumla iliyoamriwa ya nambari zingine chanya. Na mgawanyiko ni jumla ambayo haijapangwa.
Sehemu
Kabla hatujaenda moja kwa moja kwa fomula za viunganishi na uzingatiaji wa shida, inafaa kuzingatia ukweli kwamba viunganishi, kama sehemu zingine za hesabu, vina vifungu vyake. Hizi ni pamoja na:
- hesabu;
- muundo;
- uliokithiri;
- nadharia ya Ramsey;
- uwezekano;
- kiolojia;
- isiyo na kikomo.
Katika kesi ya kwanza, tunazungumza kuhusu michanganyiko ya hesabu, matatizo yanazingatia kuhesabu au kuhesabu usanidi tofauti ambao huundwa na vipengele vya seti. Kama sheria, vikwazo vingine vinawekwa kwenye seti hizi (kutofautisha, kutofautisha, uwezekano wa kurudia, na kadhalika). Na idadi ya usanidi huu imehesabiwa kwa kutumia kanuni ya kuongeza au kuzidisha, ambayo tutazungumzia baadaye kidogo. Combinatorics za miundo ni pamoja na nadharia za grafu na matroids. Mfano wa tatizo la uchanganyaji uliokithiri ni upi kipimo kikubwa zaidi cha grafu ambacho kinakidhi sifa zifuatazo… Katika aya ya nne, tulitaja nadharia ya Ramsey, ambayo inachunguza uwepo wa miundo ya kawaida katika usanidi wa nasibu. Uwezekano mkubwa zaidicombinatorics ina uwezo wa kujibu swali - kuna uwezekano gani kwamba seti fulani ina mali fulani. Kama unavyoweza kukisia, michanganyiko ya kitolojia hutumia njia katika topolojia. Na hatimaye, hatua ya saba - michanganyiko isiyokamilika inachunguza utumiaji wa mbinu za uchanganyaji kwa seti zisizo na kikomo.
Sheria ya nyongeza
Kati ya fomula za viunganishi, mtu anaweza kupata rahisi sana, ambazo tumezifahamu kwa muda mrefu. Mfano ni kanuni ya jumla. Tuseme tumepewa vitendo viwili (C na E), ikiwa ni vya kipekee, kitendo C kinaweza kufanywa kwa njia kadhaa (kwa mfano, a), na hatua E inaweza kufanywa kwa njia za b, kisha yoyote kati yao (C). au E) inaweza kufanywa kwa njia a + b.
Kwa nadharia, hii ni ngumu kuelewa, tutajaribu kuwasilisha hoja nzima kwa mfano rahisi. Wacha tuchukue wastani wa idadi ya wanafunzi katika darasa moja - tuseme ni ishirini na tano. Miongoni mwao ni wasichana kumi na tano na wavulana kumi. Mhudumu mmoja anapewa darasa kila siku. Je, kuna njia ngapi za kumgawia mhudumu wa darasa leo? Suluhisho la shida ni rahisi sana, tutaamua sheria ya kuongeza. Nakala ya kazi haisemi kwamba wavulana tu au wasichana pekee wanaweza kuwa kazini. Kwa hiyo, inaweza kuwa yoyote ya wasichana kumi na tano au yoyote ya wavulana kumi. Kutumia sheria ya jumla, tunapata mfano rahisi ambao mwanafunzi wa shule ya msingi anaweza kukabiliana nao kwa urahisi: 15 + 10. Baada ya kuhesabu, tunapata jibu: ishirini na tano. Hiyo ni, kuna njia ishirini na tano tupanga darasa la wajibu kwa leo.
Sheria ya kuzidisha
Sheria ya kuzidisha pia ni ya kanuni za msingi za viunganishi. Wacha tuanze na nadharia. Tuseme tunahitaji kufanya vitendo kadhaa (a): hatua ya kwanza inafanywa kwa njia 1, ya pili - kwa njia 2, ya tatu - kwa njia 3, na kadhalika mpaka hatua ya mwisho inafanywa kwa njia za sa. Kisha vitendo hivi vyote (ambavyo tuna jumla) vinaweza kufanywa kwa njia za N. Jinsi ya kuhesabu N haijulikani? Fomula itatusaidia kwa hili: N \u003d c1c2c3…ca.
Tena, hakuna kitu kilicho wazi katika nadharia, wacha tuendelee kwenye mfano rahisi wa kutumia kanuni ya kuzidisha. Hebu tuchukue darasa moja la watu ishirini na tano, ambapo wasichana kumi na tano na wavulana kumi wanasoma. Wakati huu tu tunahitaji kuchagua watumishi wawili. Wanaweza kuwa wavulana au wasichana tu, au mvulana aliye na msichana. Tunageukia suluhisho la msingi la shida. Tunachagua mhudumu wa kwanza, kama tulivyoamua katika aya ya mwisho, tunapata chaguzi ishirini na tano zinazowezekana. Mtu wa pili kwenye zamu anaweza kuwa mtu yeyote kati ya waliobaki. Tulikuwa na wanafunzi ishirini na watano, tulichagua mmoja, ambayo ina maana kwamba yeyote kati ya watu ishirini na wanne waliobaki anaweza kuwa wa pili kwenye zamu. Hatimaye, tunatumia kanuni ya kuzidisha na kupata kwamba wahudumu wawili wanaweza kuchaguliwa kwa njia mia sita. Tulipata nambari hii kwa kuzidisha ishirini na tano na ishirini na nne.
Badilisha
Sasa tutazingatia fomula moja zaidi ya viunganishi. Katika sehemu hii ya kifungu, sisiWacha tuzungumze juu ya vibali. Fikiria tatizo mara moja na mfano. Wacha tuchukue mipira ya billiard, tunayo nambari ya n-th yao. Tunahitaji kuhesabu: kuna chaguo ngapi ili kuzipanga kwa safu, yaani, kuweka seti iliyopangwa.
Hebu tuanze, ikiwa hatuna mipira, basi pia tuna chaguo sifuri za uwekaji. Na ikiwa tuna mpira mmoja, basi mpangilio pia ni sawa (kihisabati, hii inaweza kuandikwa kama ifuatavyo: Р1=1). Mipira miwili inaweza kupangwa kwa njia mbili tofauti: 1, 2 na 2, 1. Kwa hiyo, Р2=2. Mipira mitatu inaweza kupangwa kwa njia sita (Р3=6): 1, 2, 3; 1, 3, 2; 2, 1, 3; 2, 3, 1; 3, 2, 1; 3, 1, 2. Na ikiwa hakuna mipira mitatu kama hiyo, lakini kumi au kumi na tano? Kuorodhesha chaguzi zote zinazowezekana ni ndefu sana, basi combinatorics huja kwa msaada wetu. Fomula ya vibali itatusaidia kupata jibu la swali letu. Pn=nP(n-1). Ikiwa tunajaribu kurahisisha formula, tunapata: Pn=n (n - 1) … 21. Na hii ni bidhaa ya namba za kwanza za asili. Nambari kama hiyo inaitwa factorial, na inaonyeshwa kama n!
Hebu tuzingatie tatizo. Kiongozi kila asubuhi hujenga kikosi chake kwa mstari (watu ishirini). Kuna marafiki watatu bora kwenye kikosi - Kostya, Sasha na Lesha. Kuna uwezekano gani kwamba watakuwa karibu na kila mmoja? Ili kupata jibu la swali, unahitaji kugawanya uwezekano wa matokeo "nzuri" kwa jumla ya matokeo. Jumla ya vibali ni 20!=2.5 bilioni. Jinsi ya kuhesabu idadi ya matokeo "nzuri"? Tuseme kwamba Kostya, Sasha na Lesha ni superman mmoja. Kisha sisiTuna masomo kumi na nane tu. Idadi ya vibali katika kesi hii ni 18=6.5 quadrillion. Pamoja na haya yote, Kostya, Sasha na Lesha wanaweza kuhama kiholela kati yao katika tatu zao zisizoweza kugawanywa, na hii ni 3 zaidi!=6 chaguzi. Kwa hivyo tunayo makundi 18 "nzuri" kwa jumla!3! Tunapaswa tu kupata uwezekano unaotaka: (18!3!) / 20! Ambayo ni takriban 0.016. Ikibadilishwa hadi asilimia, itageuka kuwa 1.6% pekee.
Malazi
Sasa tutazingatia fomula nyingine muhimu na muhimu ya viunganishi. Malazi ni toleo letu linalofuata, ambalo tunapendekeza ufikirie katika sehemu hii ya kifungu. Tutaenda kuwa ngumu zaidi. Wacha tufikirie kuwa tunataka kuzingatia vibali vinavyowezekana, sio tu kutoka kwa seti nzima (n), lakini kutoka kwa ndogo (m). Hiyo ni, tunazingatia vibali vya vitu vya n kwa m.
Miundo ya kimsingi ya viunganishi haipaswi kukaririwa tu, bali kueleweka. Hata licha ya ukweli kwamba wao huwa ngumu zaidi, kwa kuwa hatuna parameter moja, lakini mbili. Tuseme kwamba m \u003d 1, kisha A \u003d 1, m \u003d 2, kisha A \u003d n(n - 1). Ikiwa tumerahisisha zaidi formula na kubadili nukuu kwa kutumia factorials, tunapata formula mafupi kabisa: \u003d n! / (n - m)!
Mchanganyiko
Tumezingatia takriban fomula zote za kimsingi za viunganishi kwa mifano. Sasa hebu tuendelee kwenye hatua ya mwisho ya kuzingatia kozi ya msingi ya combinatorics - kupata kujua mchanganyiko. Sasa tutachagua vitu vya m kutoka kwa n tuliyo nayo, wakati tutachagua yote kwa njia zote zinazowezekana. Je, hii ni tofauti gani na malazi? Sisi sikuzingatia utaratibu. Seti hii ambayo haijapangwa itakuwa mchanganyiko.
Tambulisha nukuu mara moja: C. Tunachukua nafasi za m mipira kati ya n. Tunaacha kuzingatia kuagiza na kupata mchanganyiko unaorudiwa. Ili kupata idadi ya mchanganyiko, tunahitaji kugawanya idadi ya uwekaji na m! (m factorial). Hiyo ni, C \u003d A / m! Kwa hivyo, kuna njia chache za kuchagua kutoka kwa n mipira, takriban sawa na ngapi kuchagua karibu kila kitu. Kuna usemi wa kimantiki kwa hili: kuchagua kidogo ni sawa na kutupa karibu kila kitu. Pia ni muhimu kutaja katika hatua hii kwamba idadi ya juu zaidi ya michanganyiko inaweza kupatikana unapojaribu kuchagua nusu ya vipengee.
Jinsi ya kuchagua fomula ya kutatua tatizo?
Tumechunguza kwa kina kanuni za msingi za viambatanisho: uwekaji, vibali na mchanganyiko. Sasa kazi yetu ni kuwezesha uchaguzi wa formula muhimu ya kutatua tatizo katika combinatorics. Unaweza kutumia mpango ufuatao rahisi:
- Jiulize: je mpangilio wa vipengele unazingatiwa katika maandishi ya tatizo?
- Kama jibu ni hapana, basi tumia fomula mseto (C=n! / (m!(n - m)!)).
- Kama jibu ni hapana, basi unahitaji kujibu swali moja zaidi: je vipengele vyote vimejumuishwa kwenye mseto?
- Kama jibu ni ndiyo, basi tumia fomula ya vibali (P=n!).
- Kama jibu ni hapana, basi tumia fomula ya mgao (A=n! / (n - m)!).
Mfano
Tumezingatia vipengele vya mchanganyiko, fomula na masuala mengine. Sasa hebu tuendeleeukizingatia tatizo halisi. Fikiria kuwa una kiwi, chungwa na ndizi mbele yako.
Swali la kwanza: ni kwa njia ngapi zinaweza kupangwa upya? Ili kufanya hivyo, tunatumia formula ya vibali: P=3!=njia 6.
Swali la pili: kwa njia ngapi tunda moja linaweza kuchaguliwa? Hii ni dhahiri, tuna chaguzi tatu tu - chagua kiwi, machungwa au ndizi, lakini tunatumia mchanganyiko wa mchanganyiko: C \u003d 3! / (2!1!)=3.
Swali la tatu: ni kwa njia ngapi matunda mawili yanaweza kuchaguliwa? Je, tuna chaguzi gani? Kiwi na machungwa; kiwi na ndizi; machungwa na ndizi. Hiyo ni, chaguzi tatu, lakini hii ni rahisi kuangalia kwa kutumia mchanganyiko wa formula: C \u003d 3! / (1!2!)=3
Swali la nne: ni kwa njia ngapi matunda matatu yanaweza kuchaguliwa? Kama unaweza kuona, kuna njia moja tu ya kuchagua matunda matatu: kuchukua kiwi, machungwa na ndizi. C=3! / (0!3!)=1.
Swali la tano: ni njia ngapi unaweza kuchagua angalau tunda moja? Hali hii ina maana kwamba tunaweza kuchukua matunda moja, mawili au yote matatu. Kwa hiyo, tunaongeza C1 + C2 + C3=3 + 3 + 1=7. Hiyo ni, tuna njia saba za kuchukua angalau kipande kimoja cha matunda kutoka kwa meza.
