Panagrinėkime mėginių skaičiaus iš tam tikros aibės skaičiavimo problemą bendra forma. Tegul būna koks nors rinkinys N, susidedantis iš n elementai. Bet koks poaibis, susidedantis iš m elementai gali būti svarstomi neatsižvelgiant į jų eiliškumą, arba į jį atsižvelgiama, t.y. keičiant užsakymą pereiti į kitą m– mėginių ėmimas.
Suformuluokime šiuos apibrėžimus:
Vietos be pasikartojimo
Įdėjimas be pasikartojimon elementai pagalm Nkuriuose yramįvairių elementų.
Iš apibrėžimo matyti, kad šie du išdėstymai skiriasi vienas nuo kito tiek savo elementais, tiek tvarka, net jei elementai yra vienodi.
3 teorema. Vietų skaičius be pasikartojimo yra lygus produktui m veiksniai, iš kurių didžiausias yra skaičius n . Užsirašyti:
Permutacijos be pasikartojimo
Permutacijos išn elementai vadinami skirtingomis aibės eilėmisN.
Iš šio apibrėžimo matyti, kad dvi permutacijos skiriasi tik elementų tvarka ir gali būti laikomos ypatingu išdėstymo atveju.
4 teorema. Skirtingų permutacijų skaičius be pasikartojimo apskaičiuojamas pagal formulę
Deriniai be pasikartojimų
Derinys be pasikartojimon elementai pagalm vadinamas bet koks nesutvarkytas aibės poaibisNkuriuose yram įvairių elementų.
Iš apibrėžimo matyti, kad šie du deriniai skiriasi tik elementais.
5 teorema. Derinių be pasikartojimų skaičius apskaičiuojamas naudojant vieną iš šių formulių:
1 pavyzdys. Kambaryje yra 5 kėdės. Kiek būdų galite juos ant jų uždėti?
a) 7 žmonės; b) 5 žmonės; c) 3 žmonės?
Sprendimas: a) Pirmiausia turite pasirinkti 5 žmones iš 7, kurie sėdės ant kėdžių. Tai galima padaryti 
būdu. Pasirinkę konkrečius penkis, galite gaminti 
pertvarkymų. Pagal daugybos teoremą reikalingas nusileidimo būdų skaičius yra lygus.
komentaras: Problema gali būti išspręsta naudojant tik gaminio teoremą, argumentuojant taip: sėdėjimui ant 1-os kėdės yra 7 variantai, ant 2-os kėdės - 6 variantai, ant 3-osios -5, ant 4-osios -4 ir ant 5-osios. d -3. Tada 7 žmones galima susodinti ant 5 kėdžių. Abiejų metodų sprendimai yra nuoseklūs, nes
b) sprendimas akivaizdus - 
V) 
- užimtų kėdžių rinkimų skaičius.
- vietų skaičius trims žmonėms ant trijų pasirinktų kėdžių.
Bendras rinkimų skaičius yra .
Patikrinti formules nesunku 
;
;
Visų aibės poaibių skaičius, kurį sudaro n elementai.
Pakartokite vietas
Dedant su pasikartojimu nuon elementai pagalm iškviečiamas kiekvienas sutvarkytas aibės poaibisN, susidedantis išm elementų, kad į šį poaibį būtų galima įtraukti bet kurį elementą nuo 1 ikimkartus arba visai jame nedalyvauti.
Vietų skaičius su pasikartojimu žymimas 
ir apskaičiuojamas naudojant formulę, kuri yra daugybos teoremos pasekmė:
2 pavyzdys. Tegu N = (a, b, c) yra trijų raidžių aibė. Bet kurį raidžių rinkinį, įtrauktą į šį rinkinį, pavadinkime žodžiu. Raskime 2 ilgio žodžių skaičių, kurį galima sudaryti iš šių raidžių: 
.
komentaras: Akivaizdu, kad vietos su pasikartojimu taip pat gali būti svarstomos kada 
.
3 pavyzdys. Norint sukurti visus galimus 3 ilgio žodžius, reikia naudoti raides (a, b). Kiek būdų tai galima padaryti?
Atsakymas:
Pažymėtina, kad kombinatorika yra savarankiška aukštosios matematikos šaka (o ne Terver dalis) ir apie šią discipliną buvo parašyti svarūs vadovėliai, kurių turinys kartais nėra lengvesnis už abstrakčiąją algebrą. Tačiau mums užteks nedidelės teorinių žinių dalies, todėl šiame straipsnyje pabandysiu prieinama forma išanalizuoti temos pagrindus su tipiškomis kombinatorinėmis problemomis. Ir daugelis iš jūsų man padės ;-)
Ką mes ketiname daryti? Siaurąja prasme kombinatorika yra įvairių kombinacijų, kurias galima sudaryti iš tam tikros aibės, skaičiavimas diskretus objektų. Daiktai suprantami kaip bet kokie izoliuoti objektai ar gyvos būtybės – žmonės, gyvūnai, grybai, augalai, vabzdžiai ir kt. Tuo pačiu kombinatorikai visiškai nerūpi, kad rinkinį sudaro manų kruopų košės lėkštė, lituoklis ir pelkinė varlė. Iš esmės svarbu, kad šiuos objektus būtų galima išvardinti – jų yra trys (diskretiškumas) ir svarbiausia, kad nė vienas iš jų nėra identiškas.
Daug sprendėme, dabar apie derinius. Labiausiai paplitę derinių tipai yra objektų permutacijos, jų parinkimas iš aibės (derinys) ir paskirstymas (dėstymas). Pažiūrėkime, kaip tai vyksta dabar:
Permutacijos, deriniai ir vietos be pasikartojimo
Nebijokite neaiškių terminų, juolab, kad kai kurie iš jų tikrai nėra labai geri. Pradėkime nuo pavadinimo uodegos – ką reiškia “ jokių pakartojimų"? Tai reiškia, kad šiame skyriuje mes apsvarstysime rinkinius, kuriuos sudaro įvairių objektų. Pavyzdžiui, ... ne, košės su lituokliu ir varlyte nesiūlysiu, geriau ką nors skanesnio =) Įsivaizduokite, kad ant stalo priešais jus materializavosi obuolys, kriaušė ir bananas ( jei juos turite, situacija gali būti imituojama tikrovėje). Vaisius išdėstome iš kairės į dešinę tokia tvarka:
obuolys / kriaušė / bananas
Klausimas vienas: Kiek būdų juos galima pertvarkyti?
Vienas derinys jau buvo parašytas aukščiau, o su kitais nėra jokių problemų:
obuolys / bananas / kriaušė
kriaušė / obuolys / bananas
kriaušė / bananas / obuolys
bananas / obuolys / kriaušė
bananas / kriaušė / obuolys
Iš viso: 6 deriniai arba 6 permutacijas.
Gerai, nebuvo sunku išvardyti visus galimus atvejus, bet kas, jei objektų yra daugiau? Turint tik keturis skirtingus vaisius, derinių skaičius gerokai padidės!
Atidarykite informacinę medžiagą (patogu atsispausdinti vadovą) o punkte Nr.2 raskite permutacijų skaičiaus formulę.
Jokio vargo – 3 objektus galima pertvarkyti skirtingais būdais.
Antras klausimas: Keliais būdais galite pasirinkti a) vieną vaisių, b) du vaisius, c) tris vaisius, d) bent vieną vaisių?
Kodėl rinktis? Taigi apetitą padidinome ankstesniame punkte – tam, kad pavalgytume! =)
a) Vienas vaisius gali būti pasirinktas, žinoma, trimis būdais – paimkite arba obuolį, kriaušę arba bananą. Formalus skaičiavimas atliekamas pagal kombinacijų skaičiaus formulė:
Įrašas šiuo atveju turėtų būti suprantamas taip: „kiek būdų galite pasirinkti 1 vaisių iš trijų?
b) Išvardinkime visus galimus dviejų vaisių derinius:
obuolys ir kriaušės;
obuolys ir bananas;
kriaušė ir bananas.
Derinių skaičių galima lengvai patikrinti naudojant tą pačią formulę:
Įrašas suprantamas panašiai: „kiek būdų galite pasirinkti 2 vaisius iš trijų?
c) Ir galiausiai, yra tik vienas būdas pasirinkti tris vaisius:
Beje, derinių skaičiaus formulė lieka reikšminga tuščiam pavyzdžiui:
Tokiu būdu galite pasirinkti ne vieną vaisių – iš tikrųjų nieko neimkite ir viskas.
d) Kiek būdų galite imtis mažiausiai vienas vaisius? Sąlyga „bent vienas“ reiškia, kad mus tenkina 1 vaisius (bet kuris) arba 2 vaisiai arba visi 3 vaisiai:
naudodamiesi šiais metodais galite pasirinkti bent vieną vaisių.
Skaitytojai, kurie atidžiai išstudijavo įvadinę pamoką tikimybių teorija, mes jau kažką atspėjome. Bet daugiau apie pliuso ženklo reikšmę vėliau.
Kad atsakyčiau į kitą klausimą, man reikia dviejų savanorių... ...Kadangi niekas nenori, tai pakviesiu į lentą =)
Trečias klausimas: Kiek būdų galite paskirstyti po vieną vaisių Dašai ir Natašai?
Norėdami paskirstyti du vaisius, pirmiausia turite juos pasirinkti. Pagal ankstesnio klausimo pastraipą „būti“, tai galima padaryti įvairiais būdais, aš juos perrašysiu:
obuolys ir kriaušės;
obuolys ir bananas;
kriaušė ir bananas.
Tačiau dabar derinių bus dvigubai daugiau. Apsvarstykite, pavyzdžiui, pirmąją vaisių porą:
Dašą galite gydyti obuoliu, o Natašą - kriauše;
arba atvirkščiai – Daša gaus kriaušę, o Nataša – obuolį.
Ir tokia permutacija galima kiekvienai vaisių porai.
Apsvarstykite tą pačią studentų grupę, kuri ėjo į šokį. Kiek būdų berniuką ir mergaitę galima suporuoti?
Tam tikrais būdais galite pasirinkti 1 jaunuolį;
būdai, kaip galite pasirinkti 1 merginą.
Taigi vienas jaunuolis Ir Galite pasirinkti vieną merginą: 
būdai.
Kai iš kiekvieno rinkinio pasirenkamas 1 objektas, galioja toks kombinacijų skaičiavimo principas: “ kas objektas iš vieno rinkinio gali sudaryti porą su kiekvienu kito rinkinio objektas“.
Tai yra, Olegas gali pakviesti bet kurią iš 13 merginų šokti, Jevgenijus taip pat gali pakviesti bet kurią iš trylikos, o likę jaunuoliai turi panašų pasirinkimą. Iš viso: galimos poros.
Pažymėtina, kad šiame pavyzdyje poros susidarymo „istorija“ neturi reikšmės; Tačiau jei atsižvelgsime į iniciatyvą, derinių skaičius turi būti padvigubintas, nes kiekviena iš 13 merginų taip pat gali pakviesti bet kurį berniuką šokti. Viskas priklauso nuo konkrečios užduoties sąlygų!
Panašus principas galioja ir sudėtingesniems deriniams, pavyzdžiui: kiek būdų galima pasirinkti du jaunuolius? Ir dvi merginos dalyvauti KVN seriale?
sąjunga IR aiškiai rodo, kad derinius reikia padauginti:
Galimos menininkų grupės.
Kitaip tariant, kiekviena gali pasirodyti berniukų pora (45 unikalios poros). bet koks merginų pora (78 unikalios poros). O jei svarstysime vaidmenų pasiskirstymą tarp dalyvių, derinių bus dar daugiau. ...labai noriu, bet vis tiek susilaikysiu nuo tęsinio, kad neįskiepytų jums pasibjaurėjimo studentiškam gyvenimui =).
Derinių dauginimo taisyklė taikoma ir didesniam daugiklių skaičiui:
8 problema
Kiek yra triženklių skaičių, kurie dalijasi iš 5?
Sprendimas: aiškumo dėlei pažymėkime šį skaičių trimis žvaigždutėmis: ***
IN šimtų vieta Galite parašyti bet kurį skaičių (1, 2, 3, 4, 5, 6, 7, 8 arba 9). Nulis netinka, nes šiuo atveju skaičius nustoja būti triženklis.
Bet į dešimčių vieta("viduryje") galite pasirinkti bet kurį iš 10 skaitmenų: .
Pagal sąlygą skaičius turi dalytis iš 5. Skaičius dalijasi iš 5, jeigu baigiasi skaičiumi 5 arba 0. Taigi tenkinami 2 skaitmenys mažiausiai reikšmingame skaitmenyje.
Iš viso yra: triženkliai skaičiai, kurie dalijasi iš 5.
Šiuo atveju kūrinys iššifruojamas taip: „9 būdai, kuriais galite pasirinkti skaičių šimtų vieta Ir 10 būdų, kaip pasirinkti skaičių dešimčių vieta Ir 2 būdai vienetų skaitmuo»
Arba dar paprasčiau: “ kiekviena nuo 9 skaitmenų iki šimtų vieta derina su kiekvienu iš 10 skaitmenų dešimčių vieta ir su kiekvienu nuo dviejų skaitmenų iki vienetų skaitmuo».
Atsakymas: 180
Ir dabar…
Taip, aš beveik pamiršau apie žadėtą komentarą prie problemos Nr.5, kuriame Borui, Dimai ir Volodiai gali būti išdalinta po vieną kortą skirtingais būdais. Dauginimas čia turi tą pačią reikšmę: būdai, kaip išimti 3 kortas iš kaladės IR kiekviename pavyzdį pertvarkyti jas būdais.
O dabar problema, kurią reikia išspręsti patiems... dabar sugalvosiu ką nors įdomesnio... tegul apie tą pačią rusišką blackjack versiją:
9 problema
Kiek laiminčių 2 kortų kombinacijų yra žaidžiant „tašką“?
Tiems, kurie nežino: laimėjimo derinys yra 10 + ACE (11 taškų) = 21 taškas ir, pažiūrėkime į laimintį dviejų tūzų derinį.
(kortelių tvarka bet kurioje poroje neturi reikšmės)
Trumpas sprendimas ir atsakymas pamokos pabaigoje.
Beje, nelaikykite pavyzdžio primityviu. Blackjack yra beveik vienintelis žaidimas, kuriam yra matematiškai pagrįstas algoritmas, leidžiantis įveikti kazino. Besidomintys gali nesunkiai rasti daug informacijos apie optimalią strategiją ir taktiką. Tiesa, tokie meistrai gana greitai patenka į visų įstaigų juodąjį sąrašą =)
Atėjo laikas sutvirtinti medžiagą, kuri apima keletą tvirtų užduočių:
10 problema
Vasya namuose turi 4 kates.
a) kiek būdų kates galima sodinti kambario kampuose?
b) kiek būdų galite leisti kates pasivaikščioti?
c) kiek būdų Vasja gali paimti dvi kates (vieną iš kairės, kitą iš dešinės)?
Nuspręskime: pirma, vėl turėtumėte atkreipti dėmesį į tai, kad problema išspręsta skirtinga daiktai (net jei katės yra identiškos dvynės). Tai labai svarbi sąlyga!
a) Kačių tyla. Atsižvelgiant į šį vykdymą visos katės iš karto
+ jų vieta yra svarbi, todėl čia yra permutacijų:
naudodamiesi šiais metodais galite pastatyti kates kambario kampuose.
Kartoju, kad permutuojant svarbu tik skirtingų objektų skaičius ir jų santykinė padėtis. Priklausomai nuo Vasjos nuotaikos, ji gali pasodinti gyvūnus puslankiu ant sofos, eilėje ant palangės ir pan. – visais atvejais bus 24 permutacijos, norintieji patogumo gali įsivaizduoti, kad katės yra įvairiaspalvės (pavyzdžiui, baltos, juodos, raudonos ir tabby) ir išvardinti visus galimus derinius.
b) Kiek būdų galite leisti kates pasivaikščioti?
Spėjama, kad katės eina pasivaikščioti tik pro duris, o klausimas reiškia abejingumą gyvūnų skaičiui – pasivaikščioti gali 1, 2, 3 ar visos 4 katės.
Skaičiuojame visus galimus derinius:
Kai kuriais būdais galite leisti vieną katę (bet kurią iš keturių) pasivaikščioti; 
būdai, kuriais galite leisti dvi kates pasivaikščioti (variantus išvardykite patys);
būdais galite išleisti tris kates pasivaikščioti (viena iš keturių sėdi namuose);
Tokiu būdu galite paleisti visas kates.
Tikriausiai atspėjote, kad gautas vertes reikia susumuoti:
būdai, kaip galite leisti katėms pasivaikščioti.
Entuziastams siūlau sudėtingą problemos variantą – kai bet kuri katė iš bet kurio mėginio gali atsitiktinai išeiti į lauką tiek pro duris, tiek pro langą 10 aukšte. Pastebimai padaugės derinių!
c) Kiek būdų Vasja gali pasiimti dvi kates?
Situacija apima ne tik 2 gyvūnų pasirinkimą, bet ir jų įdėjimą į kiekvieną ranką:
Šiais būdais galite pasiimti 2 kates.
Antras sprendimas: naudodami metodus galite pasirinkti dvi kates Ir sodinimo būdai kas pora po ranka: 
Atsakymas: a) 24, b) 15, c) 12
Na, kad nuvalytų sąžinę, kažkas konkretesnio apie derinių dauginimą... Leiskite Vasjai turėti 5 papildomas kates =) Kiek būdų galite leisti 2 kates pasivaikščioti? Ir 1 katė?
Tai yra, su kiekviena galima paleisti porą kačių kas katė.
Kitas mygtukų akordeonas nepriklausomam sprendimui:
11 problema
Trys keleiviai įlipo į 12 aukštų pastato liftą. Visi, nepriklausomai nuo kitų, vienoda tikimybe gali išeiti iš bet kurio (pradedant nuo 2 aukšto). Kiek būdų:
1) keleiviai gali išlipti tame pačiame aukšte (išėjimo tvarka nesvarbu);
2) viename aukšte gali išlipti du žmonės, kitame – trečias;
3) žmonės gali išeiti iš skirtingų aukštų;
4) ar keleiviai gali išlipti iš lifto?
Ir čia dažnai vėl klausia, patikslinu: jei tame pačiame aukšte išeina 2 ar 3 žmonės, tai išėjimo tvarka nesvarbu. GALVOKITE, naudokite formules ir taisykles derinių sudėjimui/dauginimui. Iškilus sunkumams, keleiviams pravartu nurodyti vardus ir spėlioti, kokiais deriniais jie gali išlipti iš lifto. Nereikia nusiminti, jei kažkas nepavyksta, pavyzdžiui, punktas Nr.2 yra gana klastingas.
Visas sprendimas su išsamiais komentarais pamokos pabaigoje.
Paskutinė pastraipa skirta deriniams, kurie taip pat pasitaiko gana dažnai - mano subjektyviu vertinimu, maždaug 20-30% kombinacinių problemų:
Permutacijos, deriniai ir vietos su pasikartojimais
Išvardyti derinių tipai nurodyti pamatinės medžiagos 5 punkte Pagrindinės kombinatorikos formulės tačiau kai kurie iš jų gali būti nelabai aiškūs per pirmąjį svarstymą. Tokiu atveju pirmiausia patartina susipažinti su praktiniais pavyzdžiais ir tik tada suprasti bendrą formuluotę. Eiti:
Permutacijos su pasikartojimais
Permutacijose su pasikartojimais, kaip ir „įprastose“ permutacijose, visus objektus vienu metu, tačiau yra vienas dalykas: šioje rinkinyje kartojasi vienas ar keli elementai (objektai). Atitikti kitą standartą:
12 problema
Kiek skirtingų raidžių kombinacijų galima gauti perdėliojus korteles su tokiomis raidėmis: K, O, L, O, K, O, L, b, Ch, I, K?
Sprendimas: tuo atveju, jei visos raidės būtų skirtingos, reikėtų taikyti trivialią formulę, tačiau visiškai aišku, kad siūlomam kortelių rinkiniui kai kurios manipuliacijos veiks „neaktyviai“, pavyzdžiui, jei sukeisite bet kurias dvi korteles su raidėmis „K“ bet kuriame žodyje gausite tą patį žodį. Be to, fiziškai kortelės gali būti labai skirtingos: viena gali būti apvali su atspausdinta raide „K“, kita – kvadratinė su nupiešta raide „K“. Bet pagal užduoties prasmę net ir tokios kortelės laikomi vienodais, nes sąlyga klausia apie raidžių derinius.
Viskas labai paprasta - tik 11 kortelių, įskaitant laišką:
K – kartojama 3 kartus;
O – kartojama 3 kartus;
L – kartojama 2 kartus;
b – kartojama 1 kartą;
H – kartojama 1 kartą;
Ir - kartojo 1 kartą.
Patikrinkite: 3 + 3 + 2 + 1 + 1 + 1 = 11, tai ir reikėjo patikrinti.
Pagal formulę permutacijų su pasikartojimais skaičius:
galima gauti įvairių raidžių derinių. Daugiau nei pusė milijono!
Norėdami greitai apskaičiuoti didelę faktorinę reikšmę, patogu naudoti standartinę „Excel“ funkciją: įveskite į bet kurį langelį =FAKTAS(11) ir paspauskite Įeikite.
Praktiškai visiškai priimtina nerašyti bendrosios formulės ir, be to, praleisti vienetinius faktorius: 
Tačiau išankstinės pastabos dėl pasikartojančių laiškų būtinos!
Atsakymas: 554400
Kitas tipiškas permutacijų su pasikartojimu pavyzdys yra šachmatų figūrėlių išdėstymo užduotyje, kurią galima rasti sandėlyje paruoštus sprendimus atitinkamame pdf faile. O savarankiškam sprendimui sugalvojau ne tokią formulę:
13 problema
Aleksejus sportuoja, 4 dienas per savaitę - lengvąją atletiką, 2 dienas - jėgos pratimus ir 1 dieną ilsisi. Kiek būdų jis gali susikurti savaitės tvarkaraštį?
Formulė čia neveikia, nes atsižvelgiama į atsitiktinius apsikeitimus (pavyzdžiui, trečiadienio jėgos pratimų pakeitimas ketvirtadienio jėgos pratimais). Ir dar kartą – iš tikrųjų tos pačios 2 jėgos treniruotės gali labai skirtis viena nuo kitos, tačiau užduoties kontekste (grafiko požiūriu) jos laikomos tais pačiais elementais.
Dviejų eilučių sprendimas ir atsakymas pamokos pabaigoje.
Deriniai su pakartojimais
Būdingas šio tipo derinių bruožas yra tai, kad pavyzdys yra sudarytas iš kelių grupių, kurių kiekviena susideda iš identiškų objektų.
Šiandien visi sunkiai dirbo, todėl laikas atsigaivinti:
14 problema
Studentų valgykloje prekiaujama dešrelėmis tešloje, sūrio pyragais ir spurgomis. Keliais būdais galite nusipirkti penkis pyragus?
Sprendimas: iš karto atkreipkite dėmesį į tipinį derinių su pasikartojimais kriterijų – pagal būklę siūloma rinktis ne objektų rinkinį, o Skirtingos rūšys objektai; daroma prielaida, kad parduodami mažiausiai penki dešrainiai, 5 sūrio pyragaičiai ir 5 spurgos. Pyragai kiekvienoje grupėje, žinoma, skirtingi – nes absoliučiai identiškas spurgas galima imituoti tik kompiuteriu =) Tačiau fizinės pyragų savybės nėra reikšmingos problemos tikslui, o dešrainiai / sūrio pyragaičiai / spurgos jų grupėse laikomos vienodais.
Kas gali būti pavyzdyje? Visų pirma reikia pastebėti, kad pavyzdyje tikrai bus identiškų pyragėlių (kadangi renkamės 5 vnt., o galima rinktis iš 3 rūšių). Čia rasite variantų kiekvienam skoniui: 5 dešrainiai, 5 sūrio pyragaičiai, 5 spurgos, 3 dešrainiai + 2 sūrio pyragaičiai, 1 dešrainiai + 2 sūrio pyragaičiai + 2 spurgos ir kt.
Kaip ir „įprastų“ derinių atveju, pyragų atrankos ir išdėstymo atrankoje tvarka neturi reikšmės - jūs tiesiog išsirinkote 5 gabalus ir viskas.
Mes naudojame formulę 
derinių su pakartojimais skaičius: 
Naudodami šį metodą galite įsigyti 5 pyragus.
Gero apetito!
Atsakymas: 21
Kokią išvadą galima padaryti iš daugelio kombinatorinių problemų?
Kartais sunkiausia yra suprasti situaciją.
Panašus nepriklausomo sprendimo pavyzdys:
15 problema
Piniginėje yra gana daug 1, 2, 5 ir 10 rublių monetų. Keliais būdais iš piniginės galima išimti tris monetas?
Savikontrolės tikslais atsakykite į keletą paprastų klausimų:
1) Ar visos pavyzdyje esančios monetos gali skirtis?
2) Įvardykite „pigiausią“ ir „brangiausią“ monetų derinį.
Sprendimas ir atsakymai pamokos pabaigoje.
Iš savo asmeninės patirties galiu pasakyti, kad deriniai su pakartojimais yra rečiausias svečias praktikoje, ko negalima pasakyti apie šių tipų derinius:
Vietos su pasikartojimais
Iš rinkinio, susidedančio iš elementų, atrenkami elementai, o elementų tvarka kiekviename pasirinkime yra svarbi. Ir viskas būtų gerai, bet gana netikėtas pokštas, kad bet kurį originalaus komplekto objektą galime pasirinkti tiek kartų, kiek norime. Vaizdžiai tariant, „daugybė nesumažės“.
Kada tai įvyksta? Tipiškas pavyzdys yra kombinuotas užraktas su keliais diskais, tačiau dėl technologinės plėtros aktualiau atsižvelgti į jo skaitmeninį palikuonį:
16 problema
Kiek yra keturių skaitmenų PIN kodų?
Sprendimas: iš tikrųjų, norint išspręsti problemą, pakanka žinoti kombinatorikos taisykles: tam tikrais būdais galite pasirinkti pirmąjį PIN kodo skaitmenį Ir būdai – antrasis PIN kodo skaitmuo Ir tiek daug būdų – trečia Ir toks pat skaičius – ketvirtas. Taigi, pagal derinių dauginimo taisyklę, keturženklį PIN kodą galima sudaryti: būdais.
O dabar naudojant formulę. Pagal sąlygą mums siūlomas skaičių rinkinys, iš kurio atrenkami ir išdėstomi numeriai tam tikra tvarka, o imtyje esantys skaičiai gali kartotis (t. y. bet kuris pradinio rinkinio skaitmuo gali būti naudojamas neribotą skaičių kartų). Pagal vietų skaičiaus su pasikartojimais formulę: 
Atsakymas: 10000
Kas čia ateina į galvą... ...jei bankomatas „suvalgo“ kortelę po trečio nesėkmingo bandymo įvesti PIN kodą, tai tikimybė ją pasiimti atsitiktinai yra labai menka.
O kas sakė, kad kombinatorika neturi praktinės prasmės? Pažintinė užduotis visiems svetainės skaitytojams:
17 problema
Pagal valstybinį standartą automobilio valstybinis numeris susideda iš 3 skaičių ir 3 raidžių. Šiuo atveju skaičius su trimis nuliais yra nepriimtinas, o raidės pasirenkamos iš rinkinio A, B, E, K, M, N, O, P, S, T, U, X (naudojamos tik tos kirilicos raidės, kurių rašyba sutampa su lotyniškomis raidėmis).
Kiek skirtingų valstybinių numerių galima sukurti regionui?
Beje, jų nėra tiek daug. Dideliuose regionuose tokio kiekio nepakanka, todėl jiems yra keli užrašo RUS kodai.
Sprendimas ir atsakymas yra pamokos pabaigoje. Nepamirškite pasinaudoti kombinatorikos taisyklėmis ;-) ...norėjau pademonstruoti, kas išskirtinė, bet pasirodė ne išskirtinė =) Pažiūrėjau į Vikipediją - ten yra skaičiavimai, nors be komentarų. Nors edukaciniais tikslais, ko gero, mažai kas tai sprendė.
Mūsų įdomi pamoka baigėsi ir galiausiai noriu pasakyti, kad jūs nešvaistėte savo laiko – dėl to, kad kombinatorikos formulės randa kitą gyvybiškai svarbų praktinį pritaikymą: jos randamos įvairiose problemose tikimybių teorija,
ir į problemos, susijusios su klasikiniu tikimybės nustatymu– ypač dažnai =)
Dėkojame visiems už aktyvų dalyvavimą ir iki greito pasimatymo!
Sprendimai ir atsakymai:
2 užduotis: Sprendimas: suraskite visų galimų 4 kortelių permutacijų skaičių:
Kai kortelė su nuliu dedama į 1 vietą, skaičius tampa triženklis, todėl šios kombinacijos turėtų būti neįtrauktos. Tegul nulis yra 1-oje vietoje, tada likusius 3 skaitmenis apatiniuose skaitmenyse galima pertvarkyti įvairiais būdais.
Pastaba
: nes Kadangi yra tik kelios kortelės, čia lengva išvardyti visas parinktis:
0579
0597
0759
0795
0957
0975
Taigi iš siūlomo rinkinio galime padaryti:
24 – 6 = 18 keturženklių skaičių
Atsakymas
: 18
4 užduotis: Sprendimas: tam tikrais būdais galite pasirinkti 3 korteles iš 36.
Atsakymas
: 7140
6 užduotis: Sprendimas: 
būdai.
Kitas sprendimas
: būdai, kaip galite pasirinkti du žmones iš grupės ir ir
2) „Pigiausiame“ rinkinyje yra 3 rublių monetos, o „brangiausiame“ – 3 dešimties rublių monetos.
17 problema: Sprendimas: 
naudodamiesi šiais metodais galite sukurti skaitmeninį automobilio numerio derinį, o vieną iš jų (000) reikėtų neįtraukti: .
naudodamiesi šiais metodais galite sukurti valstybinio numerio raidžių derinį.
Pagal derinių dauginimo taisyklę, suma gali būti sudaryta:
valstybiniai numeriai
(kiekviena skaitmeninis derinys derinamas su kiekvienu raidžių derinys).
Atsakymas
: 1726272
Kombinatorikoje jie tiria klausimus, kiek tam tikro tipo kombinacijų galima padaryti iš pateiktų objektų (elementų).
Kombinatorikos kaip šakos gimimas siejamas su B. Pascal ir P. Fermat darbais apie azartinių lošimų teoriją. Didelį indėlį į kombinatorinių metodų kūrimą įnešė G.V. Leibnizas, J. Bernoulli ir L. Euleris.
Prancūzų filosofas, rašytojas, matematikas ir fizikas Blaise'as Pascalis (1623–1662) anksti parodė savo išskirtinius matematinius sugebėjimus. Paskalio matematinių interesų spektras buvo labai įvairus. Paskalis įrodė vieną dalyką
iš pagrindinių projekcinės geometrijos teoremų (Paskalio teorema), sukonstravo sumavimo mašiną (Paskalio sumavimo mašiną), davė binominių koeficientų skaičiavimo metodą (Paskalio trikampis), pirmasis tiksliai apibrėžė ir pritaikė matematinės indukcijos metodą įrodinėjimui, padarė reikšmingą žingsnį plėtojant be galo mažą analizę, suvaidino svarbų vaidmenį tikimybių teorijos atsiradime. Hidrostatikoje Paskalis nustatė savo pagrindinį dėsnį (Paskalio dėsnį). Pascalio „Laiškai provincialui“ buvo prancūzų klasikinės prozos šedevras.
Gotfrydas Vilhelmas Leibnicas (1646–1716) – vokiečių filosofas, matematikas, fizikas ir išradėjas, teisininkas, istorikas ir kalbininkas. Matematikoje kartu su I. Newtonu jis sukūrė diferencialinį ir integralinį skaičiavimą. Jis padarė svarbų indėlį į kombinatoriką. Visų pirma jo vardas siejamas su skaičių teorinėmis problemomis.
Gotfrydas Vilhelmas Leibnicas neturėjo įspūdingos išvaizdos, todėl susidarė gana paprastos išvaizdos įspūdį. Vieną dieną Paryžiuje jis nuėjo į knygyną, tikėdamasis nusipirkti pažįstamo filosofo knygą. Lankytojui paklausus apie šią knygą, knygnešys, apžiūrėjęs jį nuo galvos iki kojų, pašaipiai pasakė: „Kam tau to reikia? Ar tikrai mokate skaityti tokias knygas? Mokslininkui nespėjus atsakyti, į parduotuvę įėjo pats knygos autorius su žodžiais: „Sveikinimai ir pagarba Didžiajam Leibnicui! Pardavėjas negalėjo suprasti, kad tai tikrai garsusis Leibnicas, kurio knygos buvo labai paklausios tarp mokslininkų.
Ateityje svarbų vaidmenį atliks šie dalykai
Lemma.Įleiskite elementų rinkinį, o aibėje - elementus. Tada visų skirtingų porų skaičius bus lygus .
Įrodymas. Iš tiesų, su vienu elementu iš rinkinio galime sudaryti tokias skirtingas poras ir iš viso elementų rinkinyje.
Vietos, permutacijos, deriniai
Turėkime trijų elementų rinkinį. Kokiais būdais galime pasirinkti du iš šių elementų? .
Apibrėžimas. Skirtingų elementų aibės išdėstymas pagal elementus yra deriniai, sudaryti iš > elementų pateiktų elementų ir skiriasi arba pačiais elementais, arba elementų tvarka.
Visų elementų rinkinio išdėstymo pagal elementus skaičius žymimas (iš prancūziško žodžio „arrangement“ pradinės raidės, reiškiančios išdėstymą), kur ir .
Teorema. Elementų rinkinio vietų skaičius pagal elementus yra lygus
Įrodymas. Tarkime, kad turime elementų. Tegul galimos vietos. Mes statysime šias vietas nuosekliai. Pirmiausia apibrėžkime pirmąjį paskirties vietos elementą. Iš tam tikro elementų rinkinio jį galima pasirinkti įvairiais būdais. Pasirinkus pirmąjį elementą, dar yra būdų, kaip pasirinkti antrą elementą ir pan. Kadangi kiekvienas toks pasirinkimas suteikia naują vietą, visi šie pasirinkimai gali būti laisvai derinami vienas su kitu. Todėl mes turime:
Pavyzdys. Keliais būdais vėliava gali būti sudaryta iš trijų horizontalių skirtingų spalvų juostų, jei yra penkių spalvų medžiaga?
Sprendimas. Reikalingas trijų juostų vėliavėlių skaičius:
Apibrėžimas. Elementų rinkinio permutacija – tai elementų išdėstymas tam tikra tvarka.
Taigi visos skirtingos trijų elementų rinkinio permutacijos yra
Nurodomas visų elementų permutacijų skaičius (nuo pradinės prancūziško žodžio „permutation“ raidės, reiškiančios „permutacija“, „judėjimas“). Todėl visų skirtingų permutacijų skaičius apskaičiuojamas pagal formulę
Pavyzdys. Keliais būdais galima pastatyti bokštelius ant šachmatų lentos, kad jie nepultų vienas kito?
Sprendimas. Reikalingas trobų skaičius
A-prioras!
Apibrėžimas. Skirtingų elementų deriniai pagal elementus yra deriniai, sudaryti iš nurodytų elementų pagal elementus ir kurie skiriasi bent vienu elementu (kitaip tariant, tam tikros elementų rinkinio elementų poaibiai).
Kaip matote, deriniuose, skirtingai nei paskirties vietose, į elementų tvarką neatsižvelgiama. Nurodomas visų elementų derinių skaičius, kiekvieno elemento skaičius (nuo prancūzų kalbos žodžio „combinasion“, reiškiančio „derinys“ pradinės raidės).
Skaičiai
Visi deriniai iš dviejų rinkinio yra .
Skaičių savybės (\sf C)_n^k
Iš tiesų, kiekvienas nurodyto elementų rinkinio elementų poaibis atitinka vieną ir tik vieną tos pačios aibės elementų poaibį.
Iš tiesų, elementų poaibius galime pasirinkti tokiu būdu: pataisyti vieną elementą; elementų poaibių, turinčių šį elementą, skaičius yra lygus ; elementų poaibių, kuriuose nėra šio elemento, skaičius yra lygus .
Paskalio trikampis
Šiame trikampyje kraštutiniai skaičiai kiekvienoje eilutėje yra lygūs 1, o kiekvienas ne ekstremalus skaičius yra lygus dviejų aukščiau esančios eilutės skaičių sumai. Taigi šis trikampis leidžia apskaičiuoti skaičius.
Teorema.
Įrodymas. Panagrinėkime elementų aibę ir dviem būdais išspręskime šią užduotį: kiek sekų galima sudaryti iš nurodyto elemento
aibės, kurių kiekviename nė vienas elementas nepasirodo du kartus?
1 būdas. Mes pasirenkame pirmąjį sekos narį, tada antrą, trečią ir tt. narys
2 būdas. Pirmiausia pasirinkite elementus iš nurodyto rinkinio, o tada sutvarkykime juos tam tikra tvarka
Padauginkite šios trupmenos skaitiklį ir vardiklį iš:
Pavyzdys. Kiek būdų žaidime „Sportloto“ galite pasirinkti 5 skaičius iš 36?
Reikalingas būdų skaičius
Užduotys.
1.
Automobilio valstybinius numerius sudaro 3 rusiškos abėcėlės raidės (33 raidės) ir 4 skaičiai. Kiek skirtingų valstybinių numerių yra?
2.
Fortepijone yra 88 klavišai. Kiek būdų galite sukurti 6 garsus iš eilės?
3.
Kiek yra šešiaženklių skaičių, kurie dalijasi iš 5?
4.
Keliais būdais į tris kišenes galima įdėti 7 skirtingas monetas?
5.
Kiek penkių skaitmenų skaičių galite sudaryti, kurių dešimtainėje skaitmenyje bent vieną kartą būtų skaitmuo 5?
6.
Keliais būdais prie apvalaus stalo galima susodinti 20 žmonių, laikant būdus vienodais, jei judant ratu juos galima gauti vieną iš kito?
7.
Kiek yra penkiaženklių skaičių, kurie dalijasi iš 5 ir kuriuose nėra identiškų skaitmenų?
8.
Ant languoto popieriaus, kurio langelio kraštinė yra 1 cm, nubrėžiamas 100 cm spindulio apskritimas, kuris nepraeina per langelių viršūnes ir neliečia langelių šonų. Kiek ląstelių gali susikirsti šis ratas?
9.
Keliais būdais galima išdėstyti skaičius iš eilės, kad skaičiai būtų gretimi ir didėjančia tvarka?
10.
Kiek penkiaženklių skaičių galima sudaryti iš skaitmenų, jei kiekvienas skaitmuo gali būti naudojamas tik vieną kartą?
11.
Iš žodžio ROT, perstačius raides, galima gauti tokius žodžius: TOP, ORT, OTR, TRO, RTO. Jie vadinami anagramomis. Kiek anagramų galite padaryti iš žodžio LOGARITMAS?
12.
Paskambinkime skilimas natūralusis skaičius, jo vaizdavimas natūraliųjų skaičių suma. Pavyzdžiui, čia yra visi skaičiaus skaidiniai:
Pertvaros laikomos skirtingomis, jei skiriasi skaičiais arba terminų tvarka.
Kiek skirtingų skaičių skaidinių į terminus yra?
13.
Kiek yra triženklių skaičių su nedidėjančia skaitmenų tvarka?
14.
Kiek yra keturženklių skaičių su nedidėjančia skaitmenų tvarka?
15.
Kiek būdų galima susodinti 17 žmonių iš eilės, kad jie atsidurtų vienas šalia kito?
16.
mergaitės ir berniukai sėdi atsitiktinai į eilę sėdynių. Keliais būdais galima juos susodinti, kad nesėdėtų viena šalia kitos dvi merginos?
17.
mergaitės ir berniukai sėdi atsitiktinai į eilę sėdynių. Kiek būdų jas galima susodinti taip, kad visos merginos sėdėtų viena šalia kitos?
Derinys – tai netvarkingas baigtinės aibės elementų pasirinkimas su fiksuotu skaičiumi ir be elementų pasikartojimų. Skirtingi deriniai turi skirtis bent viename elemente, o elementų tvarka neturi reikšmės. Pavyzdžiui, iš visų lotyniškų raidžių balsių (AEIOU) rinkinio galite sudaryti 10 skirtingų 3 raidžių derinių, sudarydami šiuos netvarkingus trejetus:
AEI, AEO, AEU, AIO, AIU, AOU, EIO, EIU, EOU, IOU.
Įdomu pastebėti, kad iš tų pačių penkių raidžių taip pat galite gauti 10 skirtingų kombinacijų, jei sujungsite jas po 2 raides vienu metu ir sudarysite šias netvarkingas poras:
AE, AI, AO, AU, EI, EO, EU, IO, IU, OU.
Tačiau jei tas pačias balsių lotyniškas raides sujungsite iš 4, gausite tik šiuos 5 skirtingus derinius:
AEIO, AEIU, AIOU, EIOU, AEOU.
Apskritai, norint pažymėti n skirtingų m elementų elementų derinių skaičių, naudojama tokia funkcinė, indekso arba vektorinė (Appel) simbolika:
Nepriklausomai nuo žymėjimo formos, n elementų derinių skaičių iš m elementų galima nustatyti naudojant šias daugybos ir faktorines formules:
Nesunku patikrinti, ar skaičiavimų, naudojant šias formules, rezultatas sutampa su aukščiau aptarto pavyzdžio su balsių deriniais lotyniškomis raidėmis rezultatais. Visų pirma, kai n = 5 ir m = 3, skaičiavimai naudojant šias formules duos tokį rezultatą:
Bendruoju atveju kombinacijų skaičiaus formulės turi kombinatorinę reikšmę ir galioja bet kokioms sveikosioms n ir m reikšmėms, kad n > m > 0. Jei m > n ir m< 0, то число сочетаний равно 0, так как в этом случае основное множество из n элементов вообще не имеет подмножеств мощности m:
Be to, naudinga atsiminti šiuos ribojančius derinių skaičių, kuriuos galima lengvai patikrinti tiesiogiai pakeičiant daugybos ir faktorines formules:
Taip pat reikėtų pažymėti, kad dauginimo formulė galioja net tada, kai n yra tikrasis skaičius, kol m vis dar yra sveikasis skaičius. Tačiau tuomet jį naudojant skaičiavimo rezultatas, išlaikydamas formalų galiojimą, praranda kombinatorinę prasmę.
DERINIŲ TAPATYBĖS
Praktinis dauginamųjų ir faktorinių formulių naudojimas, norint nustatyti savavališkų n ir m reikšmių derinių skaičių, yra mažai produktyvus dėl eksponentinės jų skaitiklio ir vardiklio faktorinių sandaugų augimo. Net esant santykinai mažoms n ir m reikšmėms, šie produktai dažnai viršija sveikųjų skaičių atvaizdavimo galimybes šiuolaikinėse skaičiavimo ir programinės įrangos sistemose. Be to, jų vertės yra žymiai didesnės nei gaunama derinių skaičiaus vertė, kuri gali būti palyginti maža. Pavyzdžiui, n=10 ir m=8 elementų derinių skaičius yra tik 45. Tačiau norėdami rasti šią reikšmę naudodami faktorių formulę, pirmiausia turite apskaičiuoti daug didesnes 10 reikšmes! skaitiklyje ir 8! vardiklyje:
Norėdami pašalinti daug laiko reikalaujančias operacijas apdorojant didelius kiekius, nustatyti kombinacijų skaičių, galite naudoti įvairius pasikartojimo ryšius, kurie tiesiogiai išplaukia iš daugybos ir faktorinių formulių. Visų pirma, iš dauginamosios formulės išplaukia toks pasikartojimo ryšys, leidžiantis priimti jo indeksų santykį už kombinacijų skaičiaus ženklo:
Galiausiai, išlaikant indekso pastovumą, gaunamas toks pasikartojimo ryšys, kuris lengvai gaunamas iš faktorinės kombinacijų skaičiaus formulės:
Po elementariųjų transformacijų trys pasikartojantys santykiai gali būti pavaizduoti tokiomis formomis:
Jei dabar pridėsime pirmųjų 2 formulių kairę ir dešinę puses ir rezultatą sumažinsime n, gautume svarbų pasikartojimo ryšį, kuris vadinamas kombinacijų skaičių sudėjimo tapatumu:
Sudėjimo tapatybė suteikia pagrindinę pasikartojimo taisyklę, leidžiančią efektyviai nustatyti derinių skaičių didelėms n ir m reikšmėms, nes leidžia daugybos operacijas faktorininiuose sandauguose pakeisti paprastesnėmis sudėjimo operacijomis ir mažesniam kombinacijų skaičiui. Visų pirma, naudojant pridėjimo tapatybę, dabar lengva nustatyti n=10 ir m=8 elementų derinių skaičių, kaip buvo aptarta aukščiau, atliekant tokią pasikartojančių transformacijų seką:
Be to, keli naudingi ryšiai baigtinėms sumoms apskaičiuoti gali būti išvesti iš sudėjimo tapatybės, ypač sumavimo pagal indeksą formulės, kurios forma yra tokia:
Šis ryšys gaunamas, jei pridėjimo tapatybėje išplečiame pasikartojimą išilgai termino su didžiausiu viršutiniu indeksu, o jo apatinis indeksas yra didesnis nei 0. Šis skaitinis pavyzdys iliustruoja šį pasikartojančių transformacijų procesą:
Natūraliųjų skaičių laipsnių sumai apskaičiuoti dažnai naudojama apatinio indekso sumavimo formulė. Konkrečiai, darant prielaidą, kad m = 1, naudojant šią formulę lengva rasti natūraliosios eilutės pirmųjų n skaičių sumą:
Kitą naudingą sumavimo formulės versiją galima gauti išplečiant pridėjimo tapatybės pasikartojimą kartu su mažiausiu viršutiniu indeksu. Šis skaitinis pavyzdys iliustruoja šią pasikartojančių transformacijų versiją:
Bendruoju atveju tokių transformacijų rezultate gaunama kombinacijų skaičių suma, kurių abiejų indeksai skiriasi nuo gretimų narių, o indeksų skirtumas išlieka pastovus (nagrinėjamame pavyzdyje taip pat lygus vienam). Taigi gauname tokią abiejų skaičių derinių indeksų sumavimo formulę:
Be aukščiau aptartų pasikartojimo ryšių ir sumavimo formulių, kombinatorinėje analizėje buvo gauta daug kitų naudingų kombinacijų skaičių tapatybių. Svarbiausia iš jų yra simetrijos tapatumas, kuris atrodo taip:
Simetrijos tapatumo pagrįstumą galima patikrinti šiame pavyzdyje, palyginus 5 elementų derinių skaičių su 2 ir (5 2) = 3:
Simetrijos tapatybė turi akivaizdžią kombinatorinę reikšmę, nes, nustatydama parinkčių skaičių m elementų atrinkimui iš n elementų, kartu nustato kombinacijų skaičių iš likusių (nm) nepasirinktų elementų. Nurodyta simetrija iš karto gaunama pakeitus m (nm) kombinacijų skaičiaus faktoriaus formulėje:
Skaičiai ir kombinacijų tapatybės yra plačiai naudojami įvairiose šiuolaikinės skaičiavimo matematikos srityse. Tačiau populiariausios jų programos yra susijusios su Niutono dvejetainiu ir Paskalio trikampiu.
BINOMINĖ TEOREMA
Norint atlikti įvairias matematines transformacijas ir skaičiavimus, svarbu mokėti daugianario pavidalu pavaizduoti bet kokią natūralią algebrinio dvejetainio (binomialo) galią. Esant mažoms galioms, norimą daugianarį galima lengvai gauti tiesiogiai padauginus dvejetainius. Visų pirma, iš elementariosios matematikos kurso gerai žinomos šios dviejų dėmenų sumos kvadrato ir kubo formulės:
Bendruoju atveju savavališkam dvinario laipsniui n reikalingas daugianario atvaizdavimas pateikiamas pagal Niutono dvinario teoremą, kuri skelbia, kad ši lygybė yra teisinga:
Ši lygybė paprastai vadinama Niutono dvejetainiu. Jo dešinėje pusėje esantis daugianaris yra sudarytas iš kairėje pusėje esančio dvinario n narių X ir Y sandaugų, o prieš juos esantys koeficientai vadinami dvinariu ir yra lygūs kombinacijų su indeksais skaičiui, gaunami iš savo galių. Atsižvelgiant į ypatingą Niutono binominės formulės populiarumą kombinatorinėje analizėje, terminai binominis koeficientas ir kombinacijų skaičius paprastai laikomi sinonimais.
Akivaizdu, kad kvadratinės ir kubinės sumos formulės yra specialūs dvinario teoremos atvejai, kai atitinkamai n=2 ir n=3. Norint apdoroti aukštesnius laipsnius (n>3), reikia naudoti Niutono binominę formulę. Jo taikymas ketvirtojo laipsnio binomiui (n=4) parodytas tokiu pavyzdžiu:
Pažymėtina, kad dvinarę formulę dar prieš Niutonas žinojo viduramžių arabų Rytų ir Vakarų Europos matematikai. Todėl visuotinai priimtas jo pavadinimas nėra istoriškai teisingas. Niutono nuopelnas yra tas, kad jis apibendrino šią formulę savavališko realiojo eksponento r atveju, kuris gali turėti bet kokias teigiamas arba neigiamas racionalias ir neracionalias reikšmes. Bendruoju atveju tokia Niutono dvinarė formulė turi begalinę sumą dešinėje ir paprastai rašoma taip:
Pavyzdžiui, esant teigiamai trupmeninei eksponento vertei r=1/2, atsižvelgiant į dvinarių koeficientų reikšmes, gaunamas toks išplėtimas:
Bendruoju atveju Niutono binominė formulė bet kuriam eksponentui yra speciali Maclaurin formulės versija, kuri suteikia savavališkos funkcijos išplėtimą į laipsnių eilutę. Niutonas parodė, kad |z|< 1 этот ряд сходится, и сумма в правой части становится конечной. При любой натуральной степени r = n в правой части также получается конечная сумма из (n+1) первых слагаемых, так как все C(n, k>n) = 0 . Jei dabar nustatysime Z=X/Y ir kairę bei dešinę puses padauginsime iš Yn, gautume aukščiau aptartą Niutono dvinario formulės versiją.
Nepaisant universalumo, dvinario teorema išlaiko kombinatorinę reikšmę tik neneigiamiems sveikiesiems dvinario laipsniams. Šiuo atveju jis gali būti naudojamas norint įrodyti keletą naudingų binominių koeficientų tapatybių. Visų pirma, aukščiau buvo aptartos formulės, skirtos kombinacijų skaičiui sumuoti pagal indeksą ir abu indeksus. Trūkstamą viršutinio indekso sumavimo tapatybę galima lengvai gauti iš Niutono dvinario formulės, į ją įtraukus X = Y = 1 arba Z = 1:
Kita naudinga tapatybė nustato dvinarių koeficientų sumų lygybę su lyginiais ir nelyginiais skaičiais. Jis iš karto gaunamas iš Niutono binominės formulės, jei X = 1 ir Y = 1 arba Z = 1:
Galiausiai iš abiejų nagrinėjamų tapatybių gauname dvinarių koeficientų sumos tapatumą tik su lyginiais arba tik nelyginiais skaičiais:
Remiantis nagrinėjamomis tapatybėmis ir pasikartojančia taisykle pašalinti indeksus iš po kombinacijų skaičiaus ženklo, galima gauti daugybę įdomių ryšių. Pavyzdžiui, jei viršutinio indekso sumavimo formulėje n visur pakeičiame (n1) ir pašaliname kiekvieno dėmens indeksus, gauname tokį ryšį:
Naudojant panašią metodiką dvinarių koeficientų su lyginiais ir nelyginiais skaičiais formulėje, galima įrodyti, pavyzdžiui, tokio ryšio pagrįstumą:
Kita naudinga tapatybė leidžia lengvai apskaičiuoti simetriškai išsidėsčiusių dviejų savavališkų n ir k dvinarių koeficientų sandaugų sumą, naudojant šią Koši formulę:
Šios formulės galiojimas išplaukia iš būtinos koeficientų lygybės bet kuriam kintamojo Z laipsniui m kairėje ir dešinėje šio identiško ryšio pusėse:
Ypatingu atveju, kai n=k=m, atsižvelgiant į simetrijos tapatumą, gaunama populiaresnė dvinarių koeficientų kvadratų sumos formulė:
Daug kitų naudingų binominių koeficientų tapatybių galima rasti plačioje kombinatorinės analizės literatūroje. Tačiau garsiausias jų praktinis pritaikymas yra susijęs su Paskalio trikampiu.
PASKALO TRIKAMPIS
Paskalio aritmetinis trikampis sudaro begalinę skaičių lentelę, sudarytą iš dvinarių koeficientų. Jo eilutės yra išdėstytos dvinario laipsniais iš viršaus į apačią. Kiekvienoje eilutėje dvejetainiai koeficientai yra išdėstyti atitinkamų kombinacijų skaičių viršutinių indeksų didėjimo tvarka iš kairės į dešinę. Paskalio trikampis paprastai rašomas lygiašoniu arba stačiakampiu.
Labiau vaizduojamas ir paplitęs yra lygiašonis formatas, kai dvinariai koeficientai, išdėstyti laipsniškai, sudaro begalinį lygiašonį trikampį. Jo pradinis fragmentas dvinariams iki 4 laipsnio (n=4) yra tokios formos:
Apskritai Paskalio lygiašonis trikampis suteikia patogią geometrinę dvinarių koeficientų nustatymo taisyklę, kuri remiasi sudėjimo tapatybėmis ir skaičių kombinacijų simetrija. Visų pirma, atsižvelgiant į sudėjimo tapatybę, bet kuris binominis koeficientas yra dviejų artimiausios ankstesnės eilutės koeficientų suma. Pagal simetrijos tapatumą Paskalio lygiašonis trikampis yra simetriškas jo pusiausvyros atžvilgiu. Taigi kiekviena jo eilutė yra dvinarių koeficientų skaitinis palindromas. Nurodytos algebrinės ir geometrinės savybės leidžia lengvai išplėsti Paskalio lygiašonį trikampį ir nuosekliai rasti savavališkų laipsnių dvinarių koeficientų reikšmes.
Tačiau norint ištirti įvairias Paskalio trikampio savybes, patogiau naudoti formaliai griežtesnį stačiakampį formatą. Šiame formate jis nurodomas apatine binominių koeficientų trikampe matrica, kur jie sudaro begalinį stačiakampį trikampį. Pradinis Paskalio stačiojo trikampio fragmentas dvinariams iki 9 laipsnio (n=9) turi tokią formą:
Geometriškai tokia stačiakampė lentelė gaunama horizontaliai deformuojant Paskalio lygiašonį trikampį. Dėl to skaičių eilutės, lygiagrečios Paskalio lygiašonio trikampio šoninėms kraštinėms, virsta Paskalio stačiojo trikampio vertikalės ir įstrižainės, o abiejų trikampių horizontalės sutampa. Tuo pačiu metu galioja dvinarių koeficientų sudėjimo ir simetrijos taisyklės, nors Paskalio stačiakampis trikampis praranda vizualinę simetriją, būdingą lygiašoniam atitikmeniui. Norint tai kompensuoti, tampa patogiau formaliai išanalizuoti įvairias dvinarių koeficientų skaitines Paskalio stačiojo trikampio horizontalių, vertikalių ir įstrižainių savybes.
Pradedant Paskalio stačiojo trikampio horizontalių analizę, nesunku pastebėti, kad pagal dvinarių sumavimo pagal viršutinį indeksą formulę bet kurios eilutės, kurios skaičius n, elementų suma yra lygi 2n. Iš to išplaukia, kad elementų, esančių virš bet kurios horizontalios linijos su skaičiumi n, suma yra lygi (2 n 1). Šis rezultatas tampa gana akivaizdus, jei kiekvienos horizontalios linijos elementų sumos reikšmė užrašoma dvejetainėje skaičių sistemoje. Pavyzdžiui, n=4 šis priedas gali būti parašytas taip:
Čia yra keletas įdomesnių horizontalių linijų savybių, kurios taip pat yra susijusios su dviejų galiomis. Pasirodo, jei horizontalusis skaičius yra dviejų laipsnis (n=2 k), tai visi jo vidiniai elementai (išskyrus išorinius) yra lyginiai skaičiai. Priešingai, visi horizontalios linijos skaičiai bus nelyginiai, jei jos skaičius bus vienu mažesnis už dviejų laipsnį (n=2 k 1). Šių savybių pagrįstumą galima patikrinti patikrinus vidinių dvinarių koeficientų paritetą, pavyzdžiui, horizontalėse n=4 ir n=3 arba n=8 ir n=7.
Tegu dabar Paskalio stačiojo trikampio eilutės numeris yra pirminis skaičius p. Tada visi jo vidiniai binominiai koeficientai dalijasi iš p. Šią savybę lengva patikrinti, ar nėra mažų pirminių kontūrų skaičių. Pavyzdžiui, visi penktosios horizontalės vidiniai dvejetainiai koeficientai (5, 10 ir 5) akivaizdžiai dalijasi iš 5. Norėdami įrodyti šį rezultatą bet kuriam pirminiam horizontaliam skaičiui p, turite parašyti jo dvinarių koeficientų dauginimo formulę taip:
Kadangi p yra pirminis skaičius ir todėl nesidalija iš m!, šios formulės skaitiklio likusių veiksnių sandauga turi dalytis iš m, kad būtų garantuota sveikoji dvinario koeficiento reikšmė. Iš to išplaukia, kad santykis laužtiniuose skliaustuose yra natūralusis skaičius N ir norimas rezultatas tampa akivaizdus:
Naudodami šį rezultatą galime nustatyti, kad visų Paskalio trikampio horizontalių tiesių, kurių vidiniai elementai dalijasi iš duoto pirminio skaičiaus p, skaičiai yra p laipsniai, tai yra, turi formą n=p k. Visų pirma, jei p=3, tai pirminis skaičius p dalija ne tik visus vidinius 3 eilutės elementus, kaip nustatyta aukščiau, bet, pavyzdžiui, 9-ąją horizontalę (9, 36, 84 ir 126). Kita vertus, Paskalio trikampyje neįmanoma rasti horizontalios linijos, kurios visi vidiniai elementai dalijasi iš sudėtinio skaičiaus. Priešingu atveju tokios horizontalios linijos skaičius vienu metu turi būti sudėtinio skaičiaus pirminių daliklių laipsnis, iš kurio dalijami visi jos vidiniai elementai, tačiau tai neįmanoma dėl akivaizdžių priežasčių.
Apsvarstyti samprotavimai leidžia suformuluoti tokį bendrąjį Paskalio trikampio horizontalių elementų dalijimosi kriterijų. Paskalio trikampio su skaičiumi n horizontaliosios linijos visų vidinių elementų didžiausias bendras daliklis (GCD) yra lygus pirminiam skaičiui p, jei n = pk arba 1 visais kitais atvejais:
GCD(Cmn) = ( ) bet kuriam 0< m < n .
Baigiant horizontalių analizę, verta apsvarstyti dar vieną įdomią savybę, kurią turi jas sudarančių dvinarių koeficientų eilutės. Jei bet kurios horizontalios linijos su skaičiumi n dvejetainius koeficientus padauginus iš nuoseklių skaičiaus 10 laipsnių, o tada sudėjus visas šias sandaugas, gaunamas 11 n. Formalus šio rezultato pagrindimas yra reikšmių X=10 ir Y=1 (arba Z=1) pakeitimas Niutono binomine formule. Šis skaitinis pavyzdys iliustruoja šios savybės įvykdymą, kai n=5:
Paskalio stačiojo trikampio vertikalių savybių analizė gali prasidėti nuo atskirų juos sudarančių elementų savybių tyrimo. Formaliai kiekvieną vertikalią m sudaro tokia begalinė dvinarių koeficientų seka su pastoviu viršutiniu indeksu (m) ir apatinio indekso prieaugiu:
Akivaizdu, kad kai m=0 gaunama vienetų seka, o kai m=1 susidaro natūraliųjų skaičių eilutė. Kai m = 2, vertikalė sudaryta iš trikampių skaičių. Kiekvienas trikampis skaičius gali būti pavaizduotas plokštumoje lygiakraščio trikampio pavidalu, kuris užpildytas savavališkais objektais (branduoliais), išdėstytais šaškių lentos šablonu. Šiuo atveju kiekvieno trikampio skaičiaus T k reikšmė lemia reprezentuojančių branduolių skaičių, o indeksas parodo, kiek branduolių eilučių reikia jam pavaizduoti. Pavyzdžiui, 4 pradiniai trikampiai skaičiai reiškia šias atitinkamo skaičiaus branduolinių „@“ simbolių konfigūracijas:
Pažymėtina, kad panašiu būdu galima įvesti kvadratinius skaičius S k , kurie gaunami padalijus į kvadratą natūraliuosius skaičius ir apskritai daugiakampius figūrinius skaičius, suformuotus reguliariai užpildant taisyklingus daugiakampius. Visų pirma, 4 pradiniai kvadratiniai skaičiai gali būti pavaizduoti taip:
Grįžtant prie Paskalio trikampio vertikalių analizės, galima pastebėti, kad kita vertikalė ties m=3 užpildyta tetraedriniais (piramidiniais) skaičiais. Kiekvienas toks skaičius P k nurodo branduolių skaičių, kuris gali būti išdėstytas tetraedro pavidalu, o indeksas nustato, kiek horizontalių trikampių šerdies eilių sluoksnių reikia pavaizduoti trimatėje erdvėje. Šiuo atveju visi horizontalūs sluoksniai turi būti pavaizduoti kaip vienas po kito einantys trikampiai skaičiai. Paskalio trikampio vertikalių, skirtų m>3, elementai sudaro hipertetraedalinių skaičių eilutes, kurios neturi vizualinės geometrinės interpretacijos plokštumoje ar trimatėje erdvėje, bet formaliai atitinka daugiamačius trikampių ir tetraedalinių skaičių analogus.
Nors Paskalio trikampio vertikalios skaičių serijos turi svarstomas individualios formos ypatybes, joms taip pat galima apskaičiuoti pradinių elementų reikšmių dalines sumas, naudojant kombinacijų skaičių sumavimo pagal indeksą formulę. . Paskalio trikampyje ši formulė turi tokią geometrinę interpretaciją. Bet kurios vertikalės n viršutinių dvinarių koeficientų verčių suma yra lygi kitos vertikalės, esančios viena eilute žemiau, elemento vertei. Šis rezultatas taip pat atitinka geometrinę trikampių, tetraedrinių ir hipertetraedinių skaičių struktūrą, nes kiekvieno tokio skaičiaus atvaizdavimas susideda iš pagrindinių sluoksnių, vaizduojančių žemesnius eilės numerius. Visų pirma, n-ąjį trikampį skaičių T n galima gauti susumavus visus natūraliuosius skaičius, vaizduojančius jo tiesinius sluoksnius:
Panašiai nesunku rasti tetraedrinį skaičių Pn, apskaičiuojant šią pirmųjų n trikampių skaičių, sudarančių horizontalius pagrindinius sluoksnius, sumą:
Be horizontalių ir vertikalių Paskalio stačiakampiame trikampyje, galima atsekti įstrižas elementų eilutes, kurių savybių tyrimas taip pat yra įdomus. Šiuo atveju dažniausiai skiriamos mažėjančios ir kylančios įstrižainės. Žemyn nukreiptos įstrižainės yra lygiagrečios Paskalio stačiojo trikampio hipotenusei. Jie sudaromi iš dvinarių koeficientų serijų su abiejų indeksų prieaugiu. Dėl simetrijos tapatumo mažėjančios įstrižainės savo elementų reikšmėmis sutampa su atitinkamomis Paskalio trikampio vertikaliomis eilėmis ir todėl pakartoja visas aukščiau aptartas jų savybes. Nurodytą korespondenciją galima atsekti pagal mažėjančios įstrižainės ir vertikalės elementų verčių sutapimą su bet kokiu skaičiumi n, jei neatsižvelgiama į vertikalius nulius:
Didėjančios įstrižainės sudaro skaičių eilutes, geometriškai statmenas Paskalio stačiojo trikampio hipotenusei. Jie užpildomi dvejetainiais koeficientais, mažinant apatinį ir didinant viršutinį indeksą. Visų pirma, 7 viršutinės didėjančios įstrižainės sudaro tokią skaitinę seką, neatsižvelgiant į galinius nulius:
Apskritai įstrižainės didėjantį skaičių n sudaro šie dvinariai koeficientai, kurių kiekvieno indeksų suma yra lygi (n1):
Dėl numerių derinio sudėjimo, kiekvienas įstrižainės elementas yra lygus dviejų elementų, atitinkančių indeksus iš dviejų ankstesnių didėjančių įstrižainių, sumai. Tai leidžia sudaryti kiekvieną paskesnę kylančią įstrižainę poromis sudedant gretimus horizontalius elementus iš dviejų ankstesnių įstrižainių, be galo išplečiant Paskalio trikampį išilgai įstrižainės. Šis Paskalio trikampio fragmentas iliustruoja didėjančios įstrižainės skaičiaus 8 konstravimą išilgai įstrižainių, numeruotų 6 ir 7:
Taikant šį konstravimo metodą, bet kurios didėjančios įstrižainės elementų suma, pradedant nuo 3, bus lygi dviejų ankstesnių didėjančių įstrižainių elementų sumai, o pirmosios 2 įstrižainės susideda tik iš vieno elemento, kurio vertė iš kurių yra 1. Atitinkamų skaičiavimų rezultatai sudaro tokią skaitinę eilutę, pagal kurią galite patikrinti Paskalio stačiojo trikampio kylančių įstrižainių nagrinėjamos savybės galiojimą:
Analizuojant šiuos skaičius matosi, kad pagal panašų dėsnį susidaro gerai žinoma Fibonačio skaičių seka, kur kiekvienas kitas skaičius lygus dviejų ankstesnių sumai, o pirmieji du skaičiai lygūs 1:
Taigi galime padaryti tokią svarbią išvadą: Paskalio trikampio elementų įstrižainės sumos sudaro Fibonačio seką. Ši savybė leidžia mums nustatyti dar vieną įdomų Paskalio trikampio bruožą. Išplečiant Fibonačio formulę rekursyviai, nesunku įrodyti, kad pirmųjų n Fibonačio skaičių suma lygi (F n+2 1).
Todėl dvinarių koeficientų, užpildančių viršutines n įstrižaines, suma taip pat lygi (F n+2 1). Iš to išplaukia, kad Paskalio trikampio pirmųjų n įstrižainių suma yra 1 mažesnė už dvinarių koeficientų, esančių jo įstrižainėje su skaičiumi (n+2), sumą.
Apibendrinant, reikia pažymėti, kad svarstomos Paskalio trikampio horizontalių, vertikalių ir įstrižainių savybės neišsemia didžiulės galimybių įvairovės, jungiančios įvairius matematinius aspektus, kurie iš pirmo žvilgsnio neturi nieko bendro. Tokios neįprastos savybės leidžia Paskalio trikampį laikyti viena tobuliausių skaitinių sistemų, kurios visų galimybių neįmanoma išvardyti ir jas sunku pervertinti.
Žemiau pateikiamas algoritmas, skirtas apskaičiuoti kombinacijų skaičių naudojant Paskalio trikampį:
Privati funkcija SochTT (ByVal n kaip sveikasis skaičius, ByVal k kaip sveikasis skaičius) kaip dvigubas dydis i kaip sveikas skaičius Dim j kaip sveikas skaičius Dim TT () kaip dvigubas ReDim TT (n, k) Kai i = 0 Iki n TT (0, i) = 1 TT (i, i) = 1 kitas Kai i = 2 iki n, j = 1 iki i - 1 TT (i, j) = TT (i - 1, j - 1) + TT (i - 1, j) Kitas Kitas SochTT = TT (n, k) Pabaigos funkcija
Jei jums reikia daug kartų skaičiuoti kombinacijų skaičių, tada gali būti patogiau vieną kartą sukurti Paskalio trikampį ir tada gauti duomenis iš masyvo.
Dim TT () Kaip dvigubas privatus sub CreateTT () ReDim TT (0, 0) BuildTT 0, 0 Baigti antrinę privačią funkciją SochTT (ByVal n kaip sveikasis skaičius, ByVal k kaip sveikasis skaičius) kaip dvigubas, jei n > į kitą pusę (TT) Tada BuildTT Ubound TT j Kaip sveikasis skaičius ReDim Išsaugoti TT (pabaiga, pabaiga) Jei i = pradžia Iki pabaigos TT (0, i) = 1 TT (i, i) = 1 Kitas Jei pabaiga< 2 Then Exit Sub If start < 2 Then start = 2 For i = start To end For j = 1 To i - 1 TT (i, j) = TT (i - 1, j - 1) + TT (i - 1, j) Next Next End Sub
Pirmiausia turite iškviesti CreateTT procedūrą. Tada galite sužinoti derinių skaičių naudodami SochTT funkciją. Kai jums nebereikia trikampio, iškvieskite TerminateTT procedūrą. Aukščiau pateiktame kode, iškviečiant SochTT funkciją, jei trikampis dar nėra užpildytas iki reikiamo lygio, tada jis užpildomas naudojant BuildTT procedūrą. Tada funkcija gauna norimą TT masyvo elementą ir grąžina jį.
Dim X () Kaip sveikasis skaičius Dim skaitiklis () kaip sveikasis skaičius Dim K kaip sveikasis skaičius Dim N kaip sveikasis skaičius Public Sub Soch() Dim i kaip sveikasis skaičius N = CInt(InputBox("Enter N")) K = CInt(InputBox("Enter K ")) K = K + 1 ReDim X(N) For i = 1 To N X(i) = i Kitas txtOut.Text = "" Redim Counter(K) Skaitiklis(0) = 1 SochGenerate 1 End Sub Private Sub SochGenerate( ByVal c Kaip sveikasis skaičius) Dim i kaip sveikasis skaičius Dim j kaip sveikasis skaičius Dim n1 kaip sveikasis skaičius Dim Out() kaip sveikas skaičius Dim X1() kaip sveikas skaičius Jei c = K Tada perreguliuoti (K) X1 = X Kai i = 1 į K - 1 n1 = 0 Kai j = 1 iki N, jei X1(j)<>0 Tada n1 = n1 + 1 Jei n1 = skaitiklis(i) Tada Out(i) = X1(j) X1(j) = 0 Išeiti į pabaigą, jei sekantis txtOut.Text = txtOut.Text & CStr(Out(i)) Kitas txtOut.Text = txtOut.Text & vbCrLf Else Skirtas skaitikliui (c) = skaitikliui (c - 1) iki N - c + 1 SochGenerate c + 1 Next End If End Sub
GAMTINIŲ SKAIČIŲ DERINIŲ SĄRAŠAS
Norint išspręsti daugelį praktinių problemų, būtina išvardyti visus fiksuoto kardinalumo derinius, kuriuos galima gauti iš tam tikros baigtinės aibės elementų, o ne tik nustatyti jų skaičių. Atsižvelgiant į visada egzistuojančią bet kurios baigtinės aibės elementų sveikojo numeravimo galimybę, daugeliu atvejų leistina apsiriboti natūraliųjų skaičių kombinacijų surašymo algoritmų naudojimu. Natūraliausias ir paprasčiausias iš jų yra natūraliųjų skaičių derinių sąrašo algoritmas leksigrafinė tvarka.
Formaliai apibūdinti šį algoritmą patogu daryti prielaidą, kad pagrindinė aibė, kurios visos m elementų kombinacijos turi būti išvardytos, sudaro nuoseklius natūraliuosius skaičius nuo 1 iki n. Tada bet koks m derinys Dėl užsakymo vertė kiekvienoje tokio derinių vektoriaus padėtyje natūraliai apribota vertė iš viršaus ir apačios taip: Leksigrafinis algoritmas nuosekliai generuoja tokius kombinuotus vektorius, pradedant leksigrafiškai mažiausiu vektoriumi, kur visose pozicijose yra šios minimalios galimos elementų reikšmės, lygios jų indeksams: Kiekvienas kitas kombinacijos vektorius formuojamas iš dabartinio, nuskaitant jo elementus iš kairės į dešinę, siekiant rasti labiausiai dešinįjį elementą, kuris dar nepasiekė ribinės vertės: Tokio elemento vertė turėtų būti padidinta 1. Kiekvienam elementui, esančiam dešinėje nuo jo, turi būti priskirta mažiausia įmanoma reikšmė, kuri yra 1 didesnė už kaimyną kairėje. Po šių pakeitimų kitas derinių vektorius turės tokią elementinę sudėtį: Taigi kitas kombinacijos vektorius bus leksigrafiškai didesnis nei ankstesnis, nes jų pradinių (j1) elementų reikšmės yra vienodos, o elemento reikšmė j padėtyje yra 1 didesnė nei ankstesnio. . Nurodytas didėjančios leksigrafinės tvarkos santykis garantuotai bus įvykdytas visose algoritmo iteracijose. Rezultatas yra didėjanti leksigrafinė seka, kurią užbaigia leksigrafiškai didžiausias kombinacijos vektorius, kur visose pozicijose esantys elementai turi šias didžiausias reikšmes: Nagrinėjamas leksigrafinis algoritmas iliustruojamas tokiu pavyzdžiu, kuriame reikia išvardinti didėjančia leksigrafine tvarka visas 15 n=6 pirmųjų natūraliųjų skaičių kombinacijų m=4 skaičiais, tai yra visus galimus pagrindinio generuojančiojo 4 elementų poaibius. rinkinys (1, 2, 3, 4 , 5, 6) iš 6 elementų. Skaičiavimo rezultatai pateikiami šioje lentelėje: Šiame pavyzdyje didžiausios leistinos skaičių reikšmės kombinacijų vektorių padėtyse yra atitinkamai 3, 4, 5 ir 6. Kad būtų lengviau interpretuoti rezultatus, kiekviename kombinacijos vektoryje dešiniausias elementas, kuris turi dar nepasiekė didžiausios vertės, pabraukta. Kombinuotų vektorių skaitiniai indeksai nustato jų skaičius leksigrafine tvarka. Bendruoju atveju bet kurios n elementų kombinacijos leksigrafinis skaičius N gali būti apskaičiuojamas pagal šią formulę, kur dėl kosmetinių priežasčių kombinacijų skaičiams žymėti naudojama Appel simbolika: Konkrečiai, šie skaičiavimai, naudojant šią formulę n=6 elementų, kurių m=4, derinio skaičius (1, 3, 4, 6) leksigrafine tvarka duos rezultatą N=8, kuris atitinka aukščiau aptartą pavyzdį: Bendruoju atveju, naudojant tapatybę abiejų indeksų kombinacijų skaičių sumai, galima parodyti, kad leksigrafiškai mažiausio derinio skaičius (1, ... i, ... m), skaičiuojant naudojant šį formulė visada bus lygi 1: Taip pat akivaizdu, kad leksigrafiškai didžiausio derinio skaičius (m, … nm+i, … n), skaičiuojant pagal šią formulę, bus lygus n elementų kombinacijų skaičiui m: Leksigrafinių kombinacijų skaičių apskaičiavimo formulė gali būti naudojama sprendžiant atvirkštinę problemą, kai derinio vektorių reikia nustatyti pagal jo skaičių leksigrafine tvarka. Norint išspręsti tokią atvirkštinę problemą, ji turi būti parašyta lygties forma, kurioje visos nežinomos norimos kombinacijos vektoriaus elementų reikšmės (C 1, ... C i, ... C m ). Šios lygties sprendimą pateikia toks „godus“ algoritmas, kurio iteracijų metu paeiliui parenkamos norimos kombinacijos vektoriaus elementų reikšmės. Pradinėje iteracijoje pasirenkama mažiausia įmanoma (neviršijant jos apribojimų) C 1 reikšmė, kuriai esant pirmasis dešinėje pusėje esantis terminas turės didžiausią reikšmę, neviršijančią L: Dabar kairiąją L pusę reikia sumažinti pirmuoju derinių skaičiumi dešinėje su pasirinkta C 1 reikšme ir panašiai nustatyti C 2 reikšmę antroje iteracijoje: Panašiai visos vėlesnės iteracijos turėtų būti atliekamos norint pasirinkti visų kitų norimos kombinacijos elementų C i reikšmes iki paskutinio elemento C m: Dėl akivaizdžių priežasčių paskutinio elemento C m reikšmę galima nustatyti remiantis jo derinių skaičiaus lygybe kairiosios L pusės likutinei vertei: Pažymėtina, kad paskutinio derinio elemento C m reikšmę galima rasti dar paprasčiau, neįvardijant galimų jo reikšmių: Nagrinėjamo algoritmo iteracijų įgyvendinimą iliustruoja toks pavyzdys, kur reikia nustatyti derinius su skaičiumi N=8 leksigrafine tvarka, jei n=6 ir m=4: Algoritminis gebėjimas nustatyti derinį pagal tam tikrą skaičių leksigrafine tvarka gali būti naudojamas įvairiomis kryptimis. Visų pirma, surašant derinius leksigrafine tvarka, būtina užtikrinti grįžimą prie bet kurio derinio, kuris buvo gautas anksčiau, pakanka žinoti tik jo numerį. Be to, atsiranda galimybė generuoti derinius bet kokia tvarka, kurią reguliuoja savavališkai duota jų leksigrafinių skaičių seka. Dabar pateikiame kombinacijų generavimo leksikografine tvarka algoritmą: 2, kai i:= nuo 1 iki k daro A[i] := i; 5 pradėti rašyti(A, …, A[k]); 6 jei A[k] = n, tada p:= p 1 kitaip p:= k; 8 i:= k žemyn iki p do A[i] := A[p] + i p + 1 DERINIAI SU KARTOJANTIS ELEMENTAIS Skirtingai nuo klasikinio derinio, kuriame visi elementai yra skirtingi, derinys su pasikartojimais sudaro netvarkingą baigtinės aibės elementų pasirinkimą, kur bet kuris elementas gali pasirodyti neribotai dažnai ir nebūtinai yra vienoje kopijoje. Šiuo atveju elementų pasikartojimų skaičių dažniausiai riboja tik derinio ilgis, o deriniai, kurie skiriasi bent vienu elementu, laikomi skirtingais. Pavyzdžiui, pasirinkę 4 pasirinktinai skirtingus skaičius iš rinkinių 1, 2 ir 3, galite sukurti šių 15 derinių su pasikartojimais: 1111 1112 1113 1122 1123 1133 1222 1223 1233 1333 2222 2223 2233 2333 3333.
Apskritai, derinius su pasikartojimais galima sudaryti pasirinkus n savavališkų tipų elementų. Tačiau juos visada galima susieti su nuosekliais natūraliaisiais skaičiais nuo 1 iki n. Tada bet koks m pasirinktinai skirtingų skaičių derinys šiame diapazone gali būti parašytas vektorine forma, išdėstant juos nemažėjančia tvarka iš kairės į dešinę: Natūralu, kad naudojant šią žymėjimo formą visi gretimi elementai gali būti lygūs dėl neribotų pasikartojimų galimybės. Tačiau kiekvienas kombinacijos vektorius su n elementų pasikartojančiais m gali būti susietas su (n+m−1) elementų deriniu vektoriumi, sudarytu taip: Akivaizdu, kad esant bet kurioms vektoriaus f elementų reikšmėms, garantuojama, kad vektoriaus C elementai bus skirtingi ir griežtai išdėstyti didėjančia jų verčių tvarka nuo diapazono nuo 1 iki (n+m1) : Tai, kad tarp vektorių f ir C elementų yra vienas su vienu atitikimas, leidžia pasiūlyti tokį paprastą metodą, kaip sistemingai išvardyti derinius su n elementų pasikartojimais m. Tereikia, pavyzdžiui, leksigrafine tvarka surašyti visas C (n+m1) m elementų kombinacijas, nuosekliai transformuojant kiekvieno iš jų elementus į atitinkamus derinių elementus su pasikartojimais f, naudojant šią formulę: Dėl to susidaro kombinacijų vektorių seka su elementų pasikartojimais, kurie yra išdėstyti tokia tvarka, kuri susidaro išvardijant atitinkamas kombinacijas be elementų pasikartojimų. Visų pirma, norint gauti pirmiau nurodytą 3 skaitmenų 1, 2 ir 3 derinių seką su 4 skaitmenų pasikartojimais, būtina leksigrafine tvarka išvardyti visus derinius be 6 skaitmenų 1,2,3,4, 5 pasikartojimų. ir 6 yra 4 skaitmenys, konvertuojant juos taip, kaip nurodyta. Toliau pateiktame pavyzdyje parodytas toks derinio (1,3,4,6) su leksikografiniu numeriu 8 konvertavimas: Apsvarstytas vienas su vienu atitikimas tarp derinių su elementų pasikartojimais ir be jų reiškia, kad jų rinkiniai yra vienodai galingi. Todėl bendru atveju kombinacijų skaičius su n elementų pasikartojimais m yra lygus kombinacijų be pasikartojimų (n+m1) elementų skaičiui m. Naudojant tą pačią simboliką, žymint kombinacijų skaičių su pasikartojimais f ir be pasikartojimų C, šią lygybę galima parašyti taip: Nesunku patikrinti, ar aukščiau pateiktame pavyzdyje, kur n=3 ir m=4, pasikartojimų derinių skaičius bus lygus 15, o tai sutampa su jų tiesioginio sąrašo rezultatu: Reikėtų pažymėti, kad, skirtingai nuo klasikinės versijos, derinio parametrų reikšmės su pasikartojimais n ir m nėra tiesiogiai susijusios viena su kita, todėl f(n,m)>0 bet kokiam jų teigiamų reikšmių deriniui. Atitinkamos ribinės sąlygos nustatomos iš lygybės tarp (n+m1) ir (n1) arba (n+m1) ir m verčių: Taip pat turėtų būti visiškai akivaizdu, kad jei m yra lygus 1, tada elementų pasikartojimai negalimi, todėl bet kuriai teigiamai reikšmei n>0 bus teisinga ši lygybė: Be to, derinių skaičiui su pasikartojančiomis bet kokiomis teigiamomis n ir m reikšmėmis galioja toks pasikartojimo ryšys, panašus į kombinacijų skaičiaus pridėjimo tapatybę be elementų pasikartojimų: Tiesą sakant, jis virsta nurodyta papildymo tapatybe, kai formaliai pakeičiamas atitinkamas derinių skaičius be pasikartojimų į jo kairę ir dešinę puses: Nagrinėjamas pasikartojimo ryšys gali būti naudojamas efektyviai nustatyti derinių su pasikartojimais skaičių, kai svarbu pašalinti daug darbo reikalaujančias faktorialinių sandaugų skaičiavimo operacijas ir jas pakeisti paprastesnėmis sudavimo operacijomis. Šiuo atveju, norint apskaičiuoti f(n,m) reikšmę, tereikia taikyti šį pasikartojimo ryšį tol, kol gausite f(1,m) ir f(i,1) formos terminų sumą, kur i įgauna reikšmes intervale nuo n iki 1. Pagal kiekio apibrėžimą tokie terminai yra lygūs atitinkamai 1 ir i. Šis pavyzdys iliustruoja šios transformacijos metodo naudojimą, kai n=3 ir m=4: DVEJETAINIŲ DERINIŲ SĄRAŠAS Diegiant derinius aparatinėje įrangoje arba programuojant asamblėjos kalba, svarbu turėti galimybę apdoroti kombinacijų įrašus dvejetainiu formatu. Šiuo atveju bet koks n elementų derinys m turi būti nurodytas n bitų dvejetainio skaičiaus (B n,...B j,...B 1) forma, kur m vieneto skaitmenų nurodo derinys, o likę (nm) skaitmenys turi nulines reikšmes. Akivaizdu, kad naudojant šią žymėjimo formą skirtingos kombinacijos turi skirtis 1 skaitmenų išdėstymu, o n bitų dvejetainėje aibėje yra tik C(n,m) būdai, kaip išdėstyti m vienetus arba (nm) nulius. Pavyzdžiui, šioje lentelėje išvardyti visi 6 tokie dvejetainiai deriniai, kuriuose pateikiami 4 bitų dvejetainiai skaičiai visoms 4 savavališkos aibės elementų kombinacijoms (E 1 , E 2 , E 3 , E 4 ) po 2: Bendruoju atveju tokių dvejetainių derinių surašymo užduotis yra sisteminga visų n bitų dvejetainių rinkinių su skirtingu m vieno ir (nm) nulio bitų išdėstymu paieška. Paprasčiausia forma tokia paieška įgyvendinama įvairiais gretimų bitų perkėlimo su poslinkiais metodais (transpozityvaus poslinkio algoritmai). Tai iteraciniai algoritmai, kurių pavadinimai atspindi kiekviename žingsnyje atliekamų operacijų pobūdį. Iteracinės transpozityvaus poslinkio algoritmų procedūros sudaro dvejetainių kombinacijų sekas, kurios prasideda dvejetainiais aibėmis, kur visi yra sutelkti žemos eilės skaitmenyse (dešinėje) ir baigiasi, kai visi 1 yra aukščiausios eilės skaitmenyse ( kairėje): Suderinus pradinius ir galutinius derinius, šios sekos skiriasi tarpinių dvejetainių rinkinių sąrašo tvarka. Tačiau visais atvejais kiekvienas paskesnis dvejetainis derinys susidaro iš ankstesnio, atlikus atitinkamas perkėlimo ir perkėlimo operacijas. Tuo pačiu metu įvairūs transpozityvaus poslinkio algoritmai skiriasi tuo, kaip jie pasirenka bitų porą perkėlimui ir bitų grupę perkėlimui. Šis specifiškumas aptariamas toliau perkėlimo algoritmams su poslinkiu į kairę ir į dešinę. Transponavimo algoritme su poslinkiu į kairę kiekviename žingsnyje sekantis dvejetainis derinys gaunamas iš dabartinės, pakeičiant kairiausią skaitmenų porą 01 į 10 (perkėlimas) ir perkeliant pirmaujančių vieneto skaitmenų grupę, jei tokia yra, arti pora 10, gauta po transpozicijos (pamainos). Jei šiuo atveju dabartinėje dvejetainėje kombinacijoje priekiniuose skaitmenyse nėra vienetų, poslinkis nevykdomas, net jei pirmaujantis vienetas gaunamas atlikus perkėlimą šiame žingsnyje. Poslinkis taip pat neatliekamas, kai reikšmingiausiuose bituose prieš porą 10, gautą po perkėlimo, nėra nulių. Nagrinėjamus veiksmus iliustruoja šis dviejų nuoseklių šio algoritmo iteracijų atlikimo pavyzdys, kai vienoje iteracijoje (15) atliekamas tik perkėlimas (T), o kitoje iteracijoje (16) perkėlimas papildomas poslinkiu ( T"+S"): Perkėlimo į dešinę poslinkį algoritme konceptualiai panašūs veiksmai atliekami kiekviename žingsnyje. Tik perkėlimas užtikrina, kad dešiniausi 01 bitai būtų pakeisti 10 (vietoj kairiausių), o tada visi esantys į dešinę nuo jo perkeliami į mažiausiai reikšmingus bitus. Kaip ir anksčiau, pamainos atliekamos tik tuo atveju, jei yra vienetų, kuriuos galima perkelti į dešinę. Nagrinėjamus veiksmus iliustruoja šis dviejų nuoseklių šio algoritmo iteracijų atlikimo pavyzdys, kai vienoje iteracijoje (3) atliekamas tik perkėlimas (T), o kitoje iteracijoje (4) perkėlimas papildomas poslinkiu ( T"+S"): Reikėtų pažymėti, kad abiejų algoritmų iteracijos gali būti parašytos adityvia forma, jei dvejetainės kombinacijos yra interpretuojamos kaip sveikieji skaičiai 2 bazinėje skaičių sistemoje ,…B" j , …B" 1), visada galima gauti iš esamos kombinacijos (B n,…B j,…B 1), atliekant sveikųjų skaičių pridėjimo operacijas naudojant šią adityvinę formulę: Šioje adityvinėje formulėje dviejų f ir t laipsniai atitinkamai žymi esamos dvejetainės kombinacijos žemos eilės nulinių skaitmenų skaičių ir vienetų skaičių eilėje į kairę nuo jų. Pavyzdžiui, 4-ajam dvejetainiam deriniui (001110) iš n=6 skaitmenų f =1 ir t =3. Todėl apskaičiuojant kitą dvejetainį derinį, naudojant adityvinę formulę 5 iteracijoje, bus gautas toks rezultatas, lygiavertis perkėlimo ir perkėlimo operacijoms: Norint atlikti lyginamąją analizuojamų perkėlimo algoritmų su poslinkiais į kairę ir į dešinę analizę, patartina palyginti dvejetainių kombinacijų sekas, kurias jie generuoja savo iteracijose. Šioje lentelėje parodytos dvi tokios dvejetainių 4 elementų iš 2 derinių sekos, kurios gaunamos atitinkamai kairiojo (TSL) ir dešiniojo (TSR) poslinkio algoritmais: Palyginę šias 2 sekas, galite pamatyti, kad jos yra atvirkštinis veidrodis. Tai reiškia, kad bet kurios dvi dvejetainės kombinacijos, esančios jose tuo pačiu atstumu nuo tarpusavyje priešingų jų sekų galų, yra veidrodinis viena kitos vaizdas, tai yra, jie sutampa, kai bet kurio iš jų bitų indeksavimas yra atvirkštinis. Pavyzdžiui, antrasis dvejetainis modelis nuo TSL sekos pradžios (0101) yra veidrodinis dvejetainio modelio (1010) vaizdas, kuris yra antras nuo TSR sekos pabaigos. Apskritai, bet koks dvejetainis derinys su vienos sekos skaičiumi i yra veidrodinis dvejetainės kombinacijos su skaičiumi (ni+1) kitos sekos vaizdas. Šis ryšys tarp šių sekų yra dviejų svarstomų dvejetainių kombinacijų surašymo algoritmų perkėlimo ir poslinkio operacijų simetriškumo pasekmė. Reikėtų pažymėti, kad dvejetainis formatas taip pat gali būti naudojamas įrašant derinius su elementų pasikartojimais. Norėdami tai padaryti, būtina nustatyti „vienas su vienu“ atitikimą tarp derinių su pasikartojimais ir dvejetainių kombinacijų, kurios sudaromos taip. Tebūna savavališkas derinys su pakartojimais, kuris gaunamas pasirenkant m pasirinktinai skirtingus elementus iš n generuojančios aibės elementų. Norėdami nustatyti norimą atitiktį, pirmiausia turite pridėti visus formavimo rinkinio (katės) elementus į derinį, o tada surūšiuoti gautą sujungimą (rūšiuoti), kad visi identiški elementai būtų vienas šalia kito. Rezultatas yra (n+m) elementų seka, kurioje yra n identiškų elementų grupių. Tarp elementų iš viso bus (n+m1) tarpų, tarp kurių bus (n1) tarpai tarp identiškų elementų grupių ir m tarpai tarp elementų grupėse. Kad būtų aiškumo, nurodytose vietose galite įdėti simbolius „|“. ir atitinkamai. Jei dabar sulyginsime 1 su tarpais tarp grupių (|) ir 0 su visomis kitomis erdvėmis (), gausime dvejetainį derinį. Jį sudaro dvejetainė (n+m1) bitų aibė, kur (n1) yra vienetai, o m nulis bitų, kurių vieta vienareikšmiškai atitinka pirminį derinį su elementų pasikartojimais nuo n iki m. Nagrinėjamą transformacijos techniką iliustruoja šis dvejetainio derinio (1001101) konstravimo pavyzdys naudojant derinį su pakartojimais (BBD), kurio elementai parenkami iš pirmųjų penkių lotyniškų raidžių generuojančios rinkinio: Apskritai tokių dvejetainių aibių skaičius lemia, kiek būdų (n1) vienetus (arba m nulius) išdėstyti (n+m1) dvejetainiais skaitmenimis. Ši reikšmė akivaizdžiai lygi derinių nuo (n+m1) iki (n1) arba m, ty C(n+m1,n1) arba C(n+m1,m), skaičiui, kuris yra lygus kombinacijų skaičius su pasikartojimais f( n,m) iš n elementų, po m. Taigi, turint derinių su pasikartojimais ir dvejetainių derinių atitiktį vienas su vienu, derinių su pasikartojimais išvardijimą galima sumažinti iki dvejetainių derinių, pavyzdžiui, naudojant transpozicijos algoritmus su poslinkiu į kairę arba į dešinę. Po to jums tereikia atkurti reikiamus derinius su pakartojimais naudojant gautus dvejetainius derinius. Tai visada galima padaryti naudojant šią atkūrimo techniką. Tegul pagrindinė aibė, iš kurios elementų susidaro kombinacijos su pasikartojimais m nebūtinai skirtingų elementų, yra sutvarkyta savavališkai taip, kad kiekvienas jos elementas turėtų tam tikrą eilės numerį nuo 1 iki n. Taip pat įgyvendinkime dvejetainių (n+m1) dvejetainių skaitmenų kombinacijų, kur (n1) vienetų ir m nulinių skaitmenų, surašymą. Kiekvieną gautą dvejetainį derinį kairėje galima papildyti išgalvotu vieneto skaitmeniu, o visus vieneto skaitmenis galima sunumeruoti iš kairės į dešinę sveikaisiais skaičiais nuo 1 iki n. Tada nulių skaičius eilėje po kiekvieno i-ojo dvejetainio derinio vieneto bus lygus pagrindinės aibės i-ojo elemento atvejų skaičiui atitinkamame derinyje su pasikartojimais. Nagrinėjamą techniką iliustruoja toks pavyzdys, kur naudojant dvejetainį derinį (1001101) atkuriamas derinys su BBD pasikartojimais, kurių elementai parenkami iš generuojančios pirmųjų penkių lotyniškų raidžių, parašytų abėcėlės tvarka, rinkinio. , o antraštė nurodo elementus, kurių šiame derinyje nėra: Atlikdami panašius veiksmus šio pavyzdžio sąlygomis, galite išvardyti visus 35 dvejetainius derinius, sudarančius 7 bitų dvejetainius rinkinius, kur yra 4 vienetai ir 3 nuliai, ir atkurti atitinkamas kombinacijas su 5 elementų pakartojimais iš 3. Kombinatorika yra matematikos šaka, nagrinėjanti klausimus, kiek skirtingų derinių, esant tam tikroms sąlygoms, galima sudaryti iš pateiktų objektų. Atsitiktinių įvykių tikimybei įvertinti labai svarbūs kombinatorikos pagrindai, nes Būtent jie leidžia apskaičiuoti iš esmės galimą skirtingų įvykių raidos scenarijų skaičių. Tegul yra k elementų grupių, o i-oji grupė susideda iš n i elementų. Pažymime po vieną elementą iš kiekvienos grupės. Tada bendras N skaičius būdų, kuriais galima pasirinkti tokį pasirinkimą, nustatomas pagal ryšį N=n 1 *n 2 *n 3 *...*n k . 1 pavyzdys. Paaiškinkime šią taisyklę paprastu pavyzdžiu. Tegul yra dvi elementų grupės, ir pirmoji grupė susideda iš n 1 elementų, o antroji - iš n 2 elementų. Kiek skirtingų elementų porų galima sudaryti iš šių dviejų grupių, kad poroje būtų vienas elementas iš kiekvienos grupės? Tarkime, paėmėme pirmąjį elementą iš pirmosios grupės ir, jo nekeisdami, perėjome visas įmanomas poras, keisdami tik elementus iš antrosios grupės. Šio elemento tokių porų gali būti n 2. Tada paimame antrą elementą iš pirmosios grupės ir taip pat sudarome visas įmanomas poras. Taip pat bus n 2 tokios poros. Kadangi pirmoje grupėje yra tik n 1 elementų, iš viso galimi variantai bus n 1 *n 2 . 2 pavyzdys. Kiek triženklių lyginių skaičių galima sudaryti iš skaitmenų 0, 1, 2, 3, 4, 5, 6, jei skaitmenys gali kartotis? Tuo atveju, kai visos grupės susideda iš vienodo elementų skaičiaus, t.y. n 1 =n 2 =...n k =n galime daryti prielaidą, kad kiekvienas pasirinkimas atliekamas iš tos pačios grupės, o elementas po atrankos grąžinamas į grupę. Tada visų atrankos būdų skaičius lygus n k . Toks atrankos būdas kombinatorikoje vadinamas pavyzdžiai su grąžinimu. 3 pavyzdys. Kiek keturženklių skaičių galima sudaryti iš skaitmenų 1, 5, 6, 7, 8? Apsvarstykite aibę, susidedančią iš n elementų. Kombinatorikoje ši aibė vadinama bendros populiacijos. 1 apibrėžimas. Nakvynė nuo n elementai pagal m kombinatorikoje bet koks užsakytas komplektas iš mįvairūs elementai, atrinkti iš gyventojų n elementai. 4 pavyzdys. Skirtingi trijų elementų (1, 2, 3) išdėstymai po du bus aibės (1, 2), (2, 1), (1, 3), (3, 1), (2, 3), (3) , 2). Vietos gali skirtis viena nuo kitos tiek elementais, tiek jų tvarka. Kombinatorikos vietų skaičius žymimas A n m ir apskaičiuojamas pagal formulę: komentaras: n!=1*2*3*...*n (skaitykite: „en faktorialas“), be to, daroma prielaida, kad 0!=1. 5 pavyzdys. Kiek yra dviženklių skaičių, kurių dešimčių ir vienetų skaitmenys yra skirtingi ir nelyginiai? Apibrėžimas 2. Derinys iš n elementai pagal m kombinatorikoje bet koks neužsakytas komplektas iš mįvairūs elementai, atrinkti iš gyventojų n elementai. 6 pavyzdys. Aibės (1, 2, 3) deriniai yra (1, 2), (1, 3), (2, 3). Derinių skaičius žymimas C n m ir apskaičiuojamas pagal formulę: 7 pavyzdys. Kiek būdų skaitytojas gali pasirinkti dvi knygas iš šešių? Sprendimas: Metodų skaičius lygus šešių knygų iš dviejų kombinacijų skaičiui, t.y. lygu: Apibrėžimas 3. Permutacija iš n elementai vadinami bet kokiais užsakytas komplektasšie elementai. 7a pavyzdys. Visos galimos aibės, susidedančios iš trijų elementų (1, 2, 3), permutacijos yra: (1, 2, 3), (1, 3, 2), (2, 3, 1), (2, 1, 3) , ( 3, 2, 1), (3, 1, 2). Įvairių n elementų permutacijų skaičius žymimas P n ir apskaičiuojamas pagal formulę P n =n!. 8 pavyzdys. Keliais būdais lentynoje vienoje eilėje gali būti išdėstytos septynios skirtingų autorių knygos? Sprendimas:Ši problema susijusi su septynių skirtingų knygų permutacijų skaičiumi. Yra P 7 =7!=1*2*3*4*5*6*7=5040 knygų išdėstymo būdų. Diskusija. Matome, kad galimų kombinacijų skaičius gali būti skaičiuojamas pagal skirtingas taisykles (permutacijas, derinius, vietas) ir rezultatas bus skirtingas, nes Skaičiavimo principas ir pačios formulės skiriasi. Atidžiai pažvelgę į apibrėžimus pastebėsite, kad rezultatas priklauso nuo kelių veiksnių vienu metu. Pirma, iš kiek elementų galime sujungti jų aibes (kiek didelė yra elementų visuma). Antra, rezultatas priklauso nuo mums reikalingų elementų rinkinių dydžio. Galiausiai svarbu žinoti, ar mums svarbi rinkinio elementų tvarka. Paaiškinkime paskutinį veiksnį naudodami šį pavyzdį. 9 pavyzdys. Tėvų susirinkime dalyvauja 20 žmonių. Kiek skirtingų tėvų komiteto sudėties variantų yra, jei jį turi sudaryti 5 žmonės? Viskas bus kitaip, jei kiekvienas komiteto narys iš pradžių bus atsakingas už konkrečią darbo sritį. Tada su ta pačia komiteto sąrašo sudėtimi jame gali būti 5! galimybės permutacijas tas reikalas. Skirtingų (tiek sudėties, tiek atsakomybės srities) variantų skaičius šiuo atveju nustatomas pagal skaičių vietos iš 20 elementų po 5. Savikontrolės užduotys 2. Kiek yra penkiaženklių skaičių, kurie skaitomi vienodai iš kairės į dešinę ir iš dešinės į kairę? 3. Klasėje yra dešimt dalykų ir penkios pamokos per dieną. Kiek būdų galite sudaryti vienos dienos tvarkaraštį? 4. Keliais būdais į konferenciją galima atrinkti 4 delegatus, jei grupėje yra 20 žmonių? 5. Keliais būdais aštuonios skirtingos raidės gali būti dedamos į aštuonis skirtingus vokus, jei į kiekvieną voką dedama tik viena raidė? 6. Komisija, susidedanti iš dviejų matematikų ir šešių ekonomistų, turėtų būti sudaryta iš trijų matematikų ir dešimties ekonomistų. Kiek būdų tai galima padaryti?Pagrindinė kombinatorikos formulė
Sprendimas: n 1 =6 (nes galite paimti bet kurį skaičių iš 1, 2, 3, 4, 5, 6 kaip pirmąjį skaitmenį), n 2 =7 (nes galite paimti bet kurį skaičių nuo 0 kaip antrąjį skaitmenį, 1, 2 , 3, 4, 5, 6), n 3 =4 (nes bet koks skaičius iš 0, 2, 4, 6 gali būti laikomas trečiuoju skaitmeniu).
Taigi, N = n 1 * n 2 * n 3 = 6 * 7 * 4 = 168.
Sprendimas. Kiekvienam keturženklio skaičiaus skaitmeniui yra penkios galimybės, o tai reiškia, kad N=5*5*5*5=5 4=625.n elementų vietų skaičius m
Sprendimas: nes Jei yra penki nelyginiai skaitmenys, būtent 1, 3, 5, 7, 9, tada ši užduotis yra pasirinkti ir sudėti du iš penkių skirtingų skaitmenų į dvi skirtingas pozicijas, t.y. nurodyti skaičiai bus:
n elementų kombinacijų skaičius, po m
n elementų permutacijos
Sprendimas:Šiame pavyzdyje mūsų nedomina vardų tvarka komiteto sąraše. Jei dėl to paaiškėja, kad tie patys žmonės yra jo dalis, tada mums tai yra ta pati galimybė. Todėl skaičiui apskaičiuoti galime naudoti formulę deriniai iš 20 elementų po 5.
1. Kiek triženklių lyginių skaičių galima padaryti iš skaitmenų 0, 1, 2, 3, 4, 5, 6, jei skaitmenys gali kartotis?
