Mahdolliset yhdistelmät laskin. Yhdistelmät ilman toistoja: Kombinatoriikka MS EXCELissä

Tämä artikkeli keskittyy matematiikan erityishaaraan, nimeltään kombinatoriikka. Kaavat, säännöt, esimerkkejä ongelmanratkaisusta - kaiken tämän löydät täältä lukemalla artikkelin loppuun.

Joten mikä tämä jakso on? Kombinatoriikka käsittelee kysymystä minkä tahansa objektin laskemisesta. Mutta tässä tapauksessa esineet eivät ole luumuja, päärynöitä tai omenoita, vaan jotain muuta. Kombinatoriikka auttaa meitä löytämään tapahtuman todennäköisyyden. Esimerkiksi korttia pelatessa - mikä on todennäköisyys, että vastustajalla on valttikortti? Tai tällainen esimerkki - millä todennäköisyydellä saat täsmälleen valkoisen kahdenkymmenen pallon pussista? Juuri tällaisia ​​tehtäviä varten meidän on tiedettävä ainakin tämän matematiikan osan perusteet.

Kombinatoriset kokoonpanot

Kun tarkastellaan kysymystä kombinatoriikan peruskäsitteistä ja kaavoista, emme voi muuta kuin kiinnittää huomiota kombinatorisiin konfiguraatioihin. Niitä ei käytetä vain muotoilemaan, vaan myös ratkaisemaan erilaisia ​​esimerkkejä tällaisista malleista:

• majoitus;
• permutaatio;
• yhdistelmä;
• numeron koostumus;
• jakamalla numeron.

Puhumme kolmesta ensimmäisestä yksityiskohtaisemmin myöhemmin, mutta kiinnitämme huomiota koostumukseen ja jakamiseen tässä osiossa. Kun he puhuvat tietyn luvun koostumuksesta (esim. a), he tarkoittavat luvun a esittämistä joidenkin positiivisten lukujen järjestetynä summana. Split on järjestämätön summa.

Osat

Ennen kuin siirrymme suoraan kombinatoriikan kaavoihin ja tehtävien tarkasteluun, on syytä kiinnittää huomiota siihen, että kombinatoriikalla, kuten muilla matematiikan aloilla, on omat alajaksonsa. Nämä sisältävät:

• luetteloiva;
• rakenteellinen;
• äärimmäinen;
• Ramseyn teoria;
• todennäköisyys;
• topologinen;
• ääretön.

Ensimmäisessä tapauksessa puhumme numeratiivisesta kombinatoriikasta, ongelmat käsittelevät joukkojen elementtien muodostamien erilaisten konfiguraatioiden luetteloimista tai laskemista. Yleensä näille sarjoille asetetaan joitain rajoituksia (erottavuus, erottamattomuus, toiston mahdollisuus ja niin edelleen). Ja näiden kokoonpanojen lukumäärä lasketaan käyttämällä yhteen- tai kertolaskua, josta puhumme hieman myöhemmin. Rakenteellinen kombinatoriikka sisältää graafien ja matroidien teoriat. Esimerkki äärimmäisestä kombinatorisesta ongelmasta on, mikä on graafin suurin ulottuvuus, joka täyttää seuraavat ominaisuudet... Neljännessä kappaleessa mainittiin Ramseyn teoria, joka tutkii säännöllisten rakenteiden esiintymistä satunnaisissa kokoonpanoissa. Probabilistinen kombinatoriikka pystyy vastaamaan kysymykseen - millä todennäköisyydellä tietyllä joukolla on tietty ominaisuus. Kuten arvata saattaa, topologinen kombinatoriikka soveltaa menetelmiä topologiassa. Ja lopuksi seitsemäs kohta - ääretön kombinatoriikka tutkii kombinatoristen menetelmien soveltamista äärettömiin joukkoihin.

Lisäyssääntö

Kombinatoriikan kaavoista löytyy myös varsin yksinkertaisia, jotka olemme olleet tuttuja jo pitkään. Esimerkki on summasääntö. Oletetaan, että meille annetaan kaksi toimenpidettä (C ja E), jos ne ovat toisensa poissulkevia, toiminto C voidaan tehdä useilla tavoilla (esimerkiksi a) ja toiminto E voidaan tehdä b-tavoilla, niin mikä tahansa niistä (C tai E) voidaan tehdä a + b tavoilla .

Teoriassa tätä on melko vaikea ymmärtää, yritämme välittää koko asian yksinkertaisella esimerkillä. Otetaan yhden luokan oppilaiden keskimääräinen lukumäärä - oletetaan, että se on kaksikymmentäviisi. Heidän joukossaan on viisitoista tyttöä ja kymmenen poikaa. Kurssille määrätään päivittäin yksi hoitaja. Kuinka monella tapaa on olemassa luokanhoitajan nimeäminen nykyään? Ratkaisu ongelmaan on melko yksinkertainen, turvaudumme lisäyssääntöön. Tehtävän tekstissä ei sanota, että vain pojat tai vain tytöt voivat olla päivystyksessä. Siksi se voi olla mikä tahansa viidestätoista tytöstä tai mikä tahansa kymmenestä pojasta. Summa-sääntöä sovellettaessa saamme melko yksinkertaisen esimerkin, josta alakoululainen selviytyy helposti: 15 + 10. Laskettuaan saamme vastauksen: kaksikymmentäviisi. Toisin sanoen on vain 25 tapaa määrittää päivystysluokka tälle päivälle.

kertolasku sääntö

Kertolasääntö kuuluu myös kombinatoriikan peruskaavoihin. Aloitetaan teoriasta. Oletetaan, että meidän on suoritettava useita toimintoja (a): ensimmäinen toiminto suoritetaan yhdellä tavalla, toinen - kahdella tavalla, kolmas - kolmella tavalla ja niin edelleen, kunnes viimeinen a-toiminto suoritetaan samalla tavalla. Sitten kaikki nämä toiminnot (joita meillä on yhteensä) voidaan suorittaa N tavalla. Kuinka laskea tuntematon N? Kaava auttaa meitä tässä: N \u003d c1 * c2 * c3 * ... * ca.

Jälleen, mikään ei ole teoriassa selvää, siirrytään yksinkertaiseen esimerkkiin kertolaskusäännön soveltamisesta. Otetaan sama 25 hengen luokka, jossa opiskelee viisitoista tyttöä ja kymmenen poikaa. Vain tällä kertaa meidän on valittava kaksi hoitajaa. He voivat olla joko vain poikia tai tyttöjä tai poikia tytön kanssa. Siirrymme ongelman perusratkaisuun. Valitsemme ensimmäisen hoitajan, kuten viimeisessä kappaleessa päätimme, saamme kaksikymmentäviisi mahdollista vaihtoehtoa. Toinen päivystävä henkilö voi olla kuka tahansa jäljellä olevista henkilöistä. Meillä oli kaksikymmentäviisi opiskelijaa, valitsimme yhden, mikä tarkoittaa, että kuka tahansa jäljellä olevista 24 henkilöstä voi olla toinen päivystävä. Lopuksi sovellamme kertolasääntöä ja huomaamme, että kaksi hoitajaa voidaan valita kuudellasadalla tavalla. Saimme tämän luvun kertomalla kaksikymmentäviisi ja kaksikymmentäneljä.

permutaatio

Nyt tarkastelemme vielä yhtä kombinatoriikan kaavaa. Tässä artikkelin osassa puhumme permutaatioista. Mieti ongelmaa välittömästi esimerkin avulla. Otetaan biljardipalloja, niitä on n:s määrä. Meidän on laskettava: kuinka monta vaihtoehtoa on järjestää ne peräkkäin, eli tehdä tilattu sarja.

Aloitetaan, jos meillä ei ole palloja, niin meillä on myös nolla sijoitusvaihtoehtoa. Ja jos meillä on yksi pallo, niin järjestely on myös sama (matemaattisesti tämä voidaan kirjoittaa seuraavasti: Р1 = 1). Kaksi palloa voidaan järjestää kahdella eri tavalla: 1.2 ja 2.1. Siksi P2 = 2. Kolme palloa voidaan järjestää kuudella tavalla (P3=6): 1,2,3; 1,3,2; 2,1,3; 2,3,1; 3.2.1; 3,1,2. Ja jos tällaisia ​​palloja ei ole kolme, vaan kymmenen tai viisitoista? Kaikkien mahdollisten vaihtoehtojen luettelo on hyvin pitkä, niin kombinatoriikka tulee avuksemme. Permutaatiokaava auttaa meitä löytämään vastauksen kysymykseemme. Pn = n*P(n-1). Jos yritämme yksinkertaistaa kaavaa, saamme: Pn = n* (n - 1) *…* 2 * 1. Ja tämä on ensimmäisten luonnollisten lukujen tulo. Tällaista lukua kutsutaan faktoriaaliksi, ja se merkitään n:llä!

Mietitäänpä tehtävää. Johtaja rakentaa joka aamu osastonsa jonoon (kaksikymmentä henkilöä). Ryhmässä on kolme parasta ystävää - Kostya, Sasha ja Lesha. Millä todennäköisyydellä ne ovat vierekkäin? Löytääksesi vastauksen kysymykseen, sinun on jaettava "hyvän" tuloksen todennäköisyys tulosten kokonaismäärällä. Permutaatioiden kokonaismäärä on 20! = 2,5 kvintiljoonaa. Kuinka laskea "hyvien" tulosten lukumäärä? Oletetaan, että Kostya, Sasha ja Lesha ovat yksi supermies. Sitten meillä on vain kahdeksantoista aihetta. Permutaatioiden lukumäärä tässä tapauksessa on 18 = 6,5 kvadriljoonaa. Kaiken tämän myötä Kostya, Sasha ja Lesha voivat mielivaltaisesti liikkua keskenään jakamattomassa kolmiossa, ja tämä on vielä 3! = 6 vaihtoehtoa. Meillä on siis yhteensä 18 "hyvää" tähtikuviota! * 3! Meidän on vain löydettävä haluttu todennäköisyys: (18! * 3!) / 20! Mikä on noin 0,016. Prosentteina muutettuna tämä on vain 1,6 prosenttia.

Majoitus

Nyt tarkastelemme toista erittäin tärkeää ja tarpeellista kombinatoriikan kaavaa. Majoitus on seuraava numeromme, jota suosittelemme harkitsemaan artikkelin tässä osassa. Meistä tulee monimutkaisempia. Oletetaan, että haluamme harkita mahdollisia permutaatioita, ei vain koko joukosta (n), vaan pienemmästä (m). Eli tarkastelemme n kohteen permutaatioita m:llä.

Kombinatoriikan peruskaavoja ei pidä vain opetella ulkoa, vaan myös ymmärtää. Huolimatta siitä, että niistä tulee monimutkaisempia, koska meillä ei ole yhtä parametria, vaan kaksi. Oletetaan, että m \u003d 1, sitten A \u003d 1, m \u003d 2, sitten A = n * (n - 1). Jos yksinkertaistamme kaavaa entisestään ja siirrymme merkintään kertoimia käyttämällä, saadaan melko ytimekäs kaava: A \u003d n! / (n - m)!

Yhdistelmä

Olemme tarkastelleet lähes kaikkia kombinatoriikan peruskaavoja esimerkein. Siirrytään nyt kombinatoriikan peruskurssin pohdinnan viimeiseen vaiheeseen - yhdistelmään tutustumiseen. Nyt valitsemme m kohdetta n:stä, joka meillä on, samalla kun valitsemme ne kaikki kaikilla mahdollisilla tavoilla. Miten tämä sitten eroaa majoituksesta? Emme ota järjestystä huomioon. Tämä tilaamaton setti tulee olemaan yhdistelmä.

Otamme heti käyttöön merkinnän: C. Otetaan m pallon sijoittelut n:stä. Lakkaamme kiinnittämästä huomiota järjestykseen ja saamme toistuvia yhdistelmiä. Yhdistelmien lukumäärän saamiseksi meidän on jaettava sijoittelujen määrä m:llä! (m factorial). Eli C \u003d A / m! Näin ollen on olemassa muutamia tapoja valita n pallosta, mikä vastaa suunnilleen sitä, kuinka monta valita melkein kaikki. Tälle on looginen ilmaus: vähän valitseminen on sama kuin melkein kaiken heittäminen pois. Tässä vaiheessa on myös tärkeää mainita, että maksimimäärä yhdistelmiä voidaan saavuttaa, kun yritetään valita puolet kohteista.

Kuinka valita kaava ongelman ratkaisemiseksi?

Olemme tutkineet yksityiskohtaisesti kombinatoriikan peruskaavat: sijoitus, permutaatio ja yhdistelmä. Nyt tehtävämme on helpottaa tarvittavan kaavan valintaa ongelman ratkaisemiseksi kombinatoriikassa. Voit käyttää seuraavaa melko yksinkertaista kaavaa:

1. Kysy itseltäsi kysymys: otetaanko elementtien järjestys huomioon tehtävätekstissä?
2. Jos vastaus on ei, käytä yhdistelmäkaavaa (C \u003d n! / (m! * (n - m))).
3. Jos vastaus on ei, on vastattava vielä yhteen kysymykseen: ovatko kaikki elementit mukana yhdistelmässä?
4. Jos vastaus on kyllä, käytä permutaatiokaavaa (P = n!).
5. Jos vastaus on ei, käytä sijoituskaavaa (A = n! / (n - m)!).

Esimerkki

Olemme pohtineet kombinatoriikan elementtejä, kaavoja ja joitain muita asioita. Siirrytään nyt todelliseen ongelmaan. Kuvittele, että sinulla on edessäsi kiivi, appelsiini ja banaani.

Ensimmäinen kysymys: kuinka monella tavalla ne voidaan järjestää uudelleen? Tätä varten käytämme permutaatiokaavaa: P = 3! = 6 tapaa.

Kysymys 2: Kuinka monella tavalla yksi hedelmä voidaan valita? Tämä on ilmeistä, meillä on vain kolme vaihtoehtoa - valitse kiivi, appelsiini tai banaani, mutta käytämme yhdistelmäkaavaa: C \u003d 3! / (2! * 1!) = 3.

Kysymys 3: Kuinka monella tavalla voidaan valita kaksi hedelmää? Mitä vaihtoehtoja meillä on? Kiivi ja appelsiini; kiivi ja banaani; appelsiini ja banaani. Eli kolme vaihtoehtoa, mutta tämä on helppo tarkistaa yhdistelmäkaavalla: C \u003d 3! / (1! * 2!) = 3

Kysymys 4: Kuinka monella tavalla voidaan valita kolme hedelmää? Kuten näet, on vain yksi tapa valita kolme hedelmää: ota kiivi, appelsiini ja banaani. C=3! / (0! * 3!) = 1.

Kysymys 5: Kuinka monella tavalla voit valita ainakin yhden hedelmän? Tämä ehto tarkoittaa, että voimme ottaa yhden, kaksi tai kaikki kolme hedelmää. Siksi lisäämme C1 + C2 + C3 = 3 + 3 + 1 = 7. Eli meillä on seitsemän tapaa ottaa ainakin yksi hedelmä pöydältä.

On huomattava, että kombinatoriikka on korkeamman matematiikan itsenäinen osa (eikä osa teraria) ja tälle tieteenalalle on kirjoitettu painavia oppikirjoja, joiden sisältö ei toisinaan ole abstraktia algebraa helpompaa. Pieni osuus teoreettisesta tiedosta kuitenkin riittää meille, ja tässä artikkelissa yritän analysoida aiheen perusteita tyypillisillä kombinatorisilla ongelmilla saavutettavassa muodossa. Ja monet teistä auttavat minua ;-)

Mitä aiomme tehdä? Suppeassa merkityksessä kombinatoriikka on erilaisten yhdistelmien laskemista, jotka voidaan tehdä tietystä joukosta diskreetti esineitä. Esineillä tarkoitetaan kaikkia yksittäisiä esineitä tai eläviä olentoja - ihmisiä, eläimiä, sieniä, kasveja, hyönteisiä jne. Samaan aikaan kombinatoriikka ei välitä ollenkaan siitä, että setti koostuu mannasuurimosta, juotosraudasta ja suosammakosta. On erittäin tärkeää, että nämä esineet ovat luettavissa - niitä on kolme. (diskreetti) ja on tärkeää, että mikään niistä ei ole samanlainen.

Kun paljon on selvitetty, nyt yhdistelmistä. Yleisimmät yhdistelmätyypit ovat objektien permutaatiot, niiden valinta joukosta (yhdistelmä) ja jakautuminen (sijoittelu). Katsotaan kuinka tämä tapahtuu juuri nyt:

Permutaatiot, yhdistelmät ja sijoittelut ilman toistoa

Älä pelkää epäselviä termejä, varsinkin kun jotkut niistä eivät todellakaan ole kovin menestyviä. Aloitetaan otsikon hännästä - mitä tekee " ilman toistoa"? Tämä tarkoittaa, että tässä osiossa tarkastellaan joukkoja, jotka koostuvat eri esineitä. Esimerkiksi ... ei, en tarjoa puuroa juotosraudalla ja sammakolla, jotain maukkaampaa on parempi =) Kuvittele, että omena, päärynä ja banaani materialisoituivat edessäsi olevalle pöydälle (jos niitä on) mikä tahansa, tilanne voidaan simuloida ja olla todellinen). Asetamme hedelmät vasemmalta oikealle seuraavassa järjestyksessä:

omena / päärynä / banaani

Kysymys yksi: Kuinka monella tavalla ne voidaan järjestää uudelleen?

Yksi yhdistelmä on jo kirjoitettu yllä ja muiden kanssa ei ole ongelmia:

omena / banaani / päärynä
päärynä / omena / banaani
päärynä / banaani / omena
banaani / omena / päärynä
banaani / päärynä / omena

Kaikki yhteensä: 6 yhdistelmää tai 6 permutaatioita.

No, ei ollut vaikeaa luetella kaikkia mahdollisia tapauksia tänne, mutta entä jos esineitä on enemmän? Jo neljällä eri hedelmällä yhdistelmien määrä kasvaa merkittävästi!

Avaa viitemateriaali (Käsikirja on helppo tulostaa) ja kappaleesta numero 2 etsi kaava permutaatioiden lukumäärälle.

Ei piinaa - 3 esinettä voidaan järjestää uudelleen eri tavoilla.

Kysymys kaksi: Kuinka monella tavalla voit valita a) yhden hedelmän, b) kaksi hedelmää, c) kolme hedelmää, d) vähintään yhden hedelmän?

Miksi valita? Joten he lisäsivät ruokahalua edellisessä kappaleessa - syödäkseen! =)

a) Yksi hedelmä voidaan valita ilmeisesti kolmella tavalla - ota joko omena, päärynä tai banaani. Muodollinen laskenta perustuu yhdistelmien lukumäärän kaava:

Tässä tapauksessa merkintä tulee ymmärtää seuraavasti: "Kuinka monella tavalla voit valita 1 hedelmän kolmesta?"

b) Listaamme kaikki mahdolliset kahden hedelmän yhdistelmät:

omena ja päärynä;
omena ja banaani;
päärynä ja banaani.

Yhdistelmien lukumäärä on helppo tarkistaa samalla kaavalla:

Merkintä ymmärretään samalla tavalla: "Kuinka monella tavalla voit valita 2 hedelmää kolmesta?".

c) Ja lopuksi, kolme hedelmää voidaan valita ainutlaatuisella tavalla:

Muuten, yhdistelmien lukumäärän kaava on järkevä myös tyhjälle näytteelle:
Tällä tavalla et voi valita yhtään hedelmää - itse asiassa, et ota mitään ja se on siinä.

d) Kuinka monella tavalla voit ottaa ainakin yksi hedelmää? "Vähintään yksi" ehto tarkoittaa, että olemme tyytyväisiä yhteen hedelmään (mihin tahansa) tai mihin tahansa kahteen hedelmään tai kaikkiin kolmeen hedelmään:
tapoja, joilla voit valita ainakin yhden hedelmän.

Lukijat, jotka ovat huolellisesti tutkineet johdantotunnin aiheesta todennäköisyysteoria keksi jo jotain. Mutta plusmerkin merkityksestä myöhemmin.

Vastatakseni seuraavaan kysymykseen tarvitsen kaksi vapaaehtoista ... ... No, koska kukaan ei halua, niin soitan hallitukseen =)

Kolmas kysymys: Kuinka monella tavalla yksi hedelmä voidaan jakaa Dashalle ja Natashalle?

Jotta voit jakaa kaksi hedelmää, sinun on ensin valittava ne. Edellisen kysymyksen kappaleen "olla" mukaan tämä voidaan tehdä eri tavoilla, kirjoitan ne uudelleen:

omena ja päärynä;
omena ja banaani;
päärynä ja banaani.

Mutta nyt yhdistelmiä on kaksi kertaa enemmän. Harkitse esimerkiksi ensimmäistä hedelmäparia:
voit hoitaa Dashaa omenalla ja Natashaa päärynällä;
tai päinvastoin - Dasha saa päärynän ja Natasha omenan.

Ja tällainen permutaatio on mahdollista jokaiselle hedelmäparille.

Harkitse samaa opiskelijaryhmää, joka meni tanssimaan. Kuinka monella tavalla poika ja tyttö voidaan yhdistää?

Voit valita 1 nuoren miehen;
tapoja, joilla voit valita 1 tytön.

Siis yksi nuori mies ja yksi tyttö voidaan valita: tavoilla.

Kun jokaisesta joukosta valitaan 1 kohde, seuraava yhdistelmien laskentaperiaate on voimassa: " jokainen yhdestä joukosta oleva esine voi muodostaa parin jokaisen kanssa toisen joukon esine.

Toisin sanoen Oleg voi kutsua minkä tahansa 13 tytöstä tanssimaan, Jevgeni voi kutsua minkä tahansa 13 tytöstä, ja muilla nuorilla on samanlainen valinta. Yhteensä: mahdolliset parit.

On huomattava, että tässä esimerkissä parinmuodostuksen "historialla" ei ole merkitystä; jos oma-aloitteisuus kuitenkin otetaan huomioon, yhdistelmien määrä on tuplattava, koska jokainen 13 tytöstä voi kutsua myös minkä tahansa pojan tanssimaan. Kaikki riippuu tietyn tehtävän olosuhteista!

Samanlainen periaate pätee esimerkiksi monimutkaisempiin yhdistelmiin: kuinka monella tavalla voidaan valita kaksi nuorta miestä ja kaksi tyttöä osallistumaan KVN-skettiin?

liitto Ja vihjaa yksiselitteisesti, että yhdistelmät on kerrottava:

Mahdolliset taiteilijaryhmät.

Toisin sanoen, jokainen poikien pari (45 ainutlaatuista paria) voi kilpailla minkä tahansa pari tyttöä (78 ainutlaatuista paria). Ja jos otamme huomioon roolien jakautumisen osallistujien välillä, yhdistelmiä tulee vielä enemmän. ... Haluan todella, mutta silti pidättäydyn jatkamasta, jotta en juurruttaisi sinuun vastenmielisyyttä opiskelijaelämää kohtaan =).

Kertolasääntö koskee useampia kertoimia:

Tehtävä 8

Kuinka monta kolminumeroista lukua on jaollinen 5:llä?

Ratkaisu: selvyyden vuoksi merkitsemme tätä numeroa kolmella tähdellä: ***

AT satojen paikka voit kirjoittaa minkä tahansa numeron (1, 2, 3, 4, 5, 6, 7, 8 tai 9). Nolla ei ole hyvä, koska tässä tapauksessa numero lakkaa olemasta kolminumeroinen.

Mutta sisään kymmenien paikka("keskellä") voit valita minkä tahansa 10 numerosta: .

Ehdon mukaan luvun on oltava jaollinen 5:llä. Luku on jaollinen viidellä, jos se päättyy 5:een tai 0:aan. Näin ollen vähiten merkitsevässä numerossa tyydytään 2 numeroon.

Yhteensä on: kolminumeroiset luvut, jotka ovat jaollisia viidellä.

Samalla teos puretaan seuraavasti: ”9 tapaa, joilla voit valita numeron satojen paikka ja 10 tapaa valita numero kymmenien paikka ja 2 tietä sisään yksikön numero»

Tai vielä yksinkertaisempaa: jokainen 9 numerosta satojen paikka yhdistetty jokaisen kanssa 10 numerosta kymmenien paikka ja jokaisen kanssa kahdesta numerosta yksiköiden numero».

Vastaus: 180

Ja nyt…

Kyllä, melkein unohdin luvatun kommentin tehtävään nro 5, jossa Borya, Dima ja Volodya voidaan jakaa kullekin yksi kortti eri tavoin. Kertomalla tässä on sama merkitys: voit poimia pakasta 3 korttia Ja jokaisessa näyte järjestää ne uudelleen.

Ja nyt itsenäisen ratkaisun tehtävä ... nyt keksin jotain mielenkiintoisempaa, ... olkoon kyse samasta venäläisestä blackjackin versiosta:

Tehtävä 9

Kuinka monta kahden kortin voittoyhdistelmää on "piste"-pelissä?

Niille, jotka eivät tiedä: voittoyhdistelmä 10 + ACE (11 pistettä) = 21 pistettä, ja harkitaan kahden ässän voittoyhdistelmää.

(korttien järjestyksellä parissa ei ole väliä)

Lyhyt ratkaisu ja vastaus oppitunnin lopussa.

Muuten, esimerkkiä ei tarvitse pitää primitiivisenä. Blackjack on melkein ainoa peli, jolle on olemassa matemaattisesti järkevä algoritmi, jonka avulla voit voittaa kasinon. Halukkaat löytävät helposti paljon tietoa optimaalisesta strategiasta ja taktiikoista. Totta, tällaiset mestarit putoavat nopeasti kaikkien laitosten mustalle listalle =)

On aika koota materiaalia, joka on katettu parilla kiinteällä tehtävällä:

Tehtävä 10

Vasyalla on kotona 4 kissaa.

a) Kuinka monella tavalla kissat voidaan istuttaa huoneen kulmiin?
b) Kuinka monella tavalla kissojen voidaan sallia vaeltaa?
c) kuinka monella tavalla Vasya voi poimia kaksi kissaa (toinen vasemmalta, toinen oikealta)?

Me päätämme: Ensinnäkin on jälleen huomattava, että ongelma koskee eri esineitä (vaikka kissat olisivat identtisiä kaksosia). Tämä on erittäin tärkeä ehto!

a) Kissojen hiljaisuus. Tämä toteutus edellyttää kaikki kissat kerralla
+ niiden sijainti on tärkeä, joten tässä on permutaatioita:
tapoja, joilla voit istuttaa kissat huoneen kulmiin.

Toistan, että permutoitaessa vain eri objektien lukumäärällä ja niiden suhteellisella sijainnilla on merkitystä. Mielialasta riippuen Vasya voi istuttaa eläimet puoliympyrässä sohvalle, riviin ikkunalaudalle jne. - permutaatioita tulee kaikissa tapauksissa 24. Mukavuuden vuoksi halukkaat voivat kuvitella, että kissat ovat monivärisiä (esim. valkoinen, musta, punainen ja raidallinen) ja listata kaikki mahdolliset yhdistelmät.

b) Kuinka monella tavalla kissojen voidaan sallia vaeltaa?

Oletetaan, että kissat lähtevät kävelylle vain ovesta, kun taas kysymys viittaa välinpitämättömyyteen eläinten lukumäärästä - 1, 2, 3 tai kaikki 4 kissaa voivat mennä kävelylle.

Harkitsemme kaikkia mahdollisia yhdistelmiä:

Tapoja, joilla voit päästää yhden kissan kävelylle (mikä tahansa neljästä);
tapoja, joilla voit päästää kaksi kissaa kävelylle (luettelo vaihtoehdot itse);
tapoja, joilla voit päästää kolme kissaa kävelylle (yksi neljästä istuu kotona);
miten voit vapauttaa kaikki kissat.

Luultavasti arvasit, että saadut arvot pitäisi laskea yhteen:
tapoja päästää kissoja kävelylle.

Harrastajille tarjoan monimutkaisen version ongelmasta - kun mikä tahansa kissa mistä tahansa näytteestä voi satunnaisesti mennä ulos sekä 10. kerroksen ovesta että ikkunasta. Yhdistelmiä tulee lisää!

c) Kuinka monella tavalla Vasya voi poimia kaksi kissaa?

Tilanne ei koske vain 2 eläimen valintaa, vaan myös niiden sijoittamista käsiin:
tapoja, joilla voit noutaa 2 kissaa.

Toinen ratkaisu: tavallaan voit valita kaksi kissaa ja tapoja istuttaa joka pari kädessä:

Vastaus: a) 24, b) 15, c) 12

No, omantuntoni tyhjentämiseksi, jotain tarkempaa yhdistelmien kertomisesta... Anna Vasyalle 5 ylimääräistä kissaa =) Kuinka monella tavalla voit päästää 2 kissaa kävelylle ja 1 kissa?

Eli kanssa jokainen pari kissaa voidaan vapauttaa joka kissa.

Toinen nappiharmonika itsenäiseen ratkaisuun:

Tehtävä 11

3 matkustajaa nousi 12-kerroksisen talon hissiin. Jokainen, muista riippumatta, voi poistua mistä tahansa (2. kerroksesta alkaen) samalla todennäköisyydellä. Kuinka monella tavalla:

1) Matkustajat voivat jäädä pois samassa kerroksessa (poistumisjärjestyksellä ei ole väliä);
2) kaksi henkilöä voi nousta toisessa kerroksessa ja kolmas toisessa;
3) ihmiset voivat jäädä pois eri kerroksista;
4) Voivatko matkustajat poistua hissistä?

Ja täällä he usein kysyvät uudelleen, selvensin: jos 2 tai 3 ihmistä menee ulos samassa kerroksessa, poistumisjärjestyksellä ei ole väliä. Ajattele, käytä kaavoja ja sääntöjä yhteen- ja kertolaskuyhdistelmille. Vaikeuksissa matkustajien on hyödyllistä ilmoittaa nimet ja syyt, millä yhdistelmillä he voivat nousta hissistä. Ei tarvitse olla järkyttynyt, jos jokin ei onnistu, esimerkiksi kohta numero 2 on melko salakavala.

Täydellinen ratkaisu yksityiskohtaisilla kommenteilla opetusohjelman lopussa.

Viimeinen kappale on omistettu yhdistelmille, joita esiintyy myös melko usein - subjektiivisen arvioni mukaan noin 20-30 prosentissa kombinatorisista ongelmista:

Permutaatiot, yhdistelmät ja sijoittelut toistoilla

Listatut yhdistelmätyypit on kuvattu vertailumateriaalin kappaleessa 5 Kombinatoriikan peruskaavat Jotkut niistä eivät kuitenkaan välttämättä ole kovin selkeitä ensimmäisessä käsittelyssä. Tässä tapauksessa on suositeltavaa tutustua ensin käytännön esimerkkeihin ja vasta sitten ymmärtää yleinen muotoilu. Mennä:

Permutaatiot toistoilla

Permutaatioissa, joissa on toistoja, kuten "tavallisissa" permutaatioissa, koko esinesarja kerralla, mutta on yksi asia: tässä joukossa yksi tai useampi elementti (objekti) toistetaan. Täytä seuraava standardi:

Tehtävä 12

Kuinka monta eri kirjainyhdistelmää saadaan järjestämällä kortit uudelleen seuraavilla kirjaimilla: K, O, L, O, K, O, L, L, H, I, K?

Ratkaisu: siinä tapauksessa, että kaikki kirjaimet olivat erilaisia, tulisi soveltaa triviaalia kaavaa, mutta on kuitenkin aivan selvää, että ehdotetulle korttisarjalle jotkin manipulaatiot toimivat "tyhjinä", joten esimerkiksi jos vaihdat mitä tahansa kahta kortit kirjaimilla "K missä tahansa sanassa, se on sama sana. Lisäksi fyysisesti kortit voivat olla hyvin erilaisia: yksi voi olla pyöreä, jossa on painettu kirjain “K”, toinen neliö, jossa on piirretty kirjain “K”. Mutta ongelman merkityksen mukaan jopa sellaiset kortit pitää samana, koska ehto kysyy kirjainyhdistelmiä.

Kaikki on erittäin yksinkertaista - yhteensä: 11 korttia, mukaan lukien kirje:

K - toistetaan 3 kertaa;
O - toistetaan 3 kertaa;
L - toistetaan 2 kertaa;
b - toistetaan 1 kerran;
H - toistetaan 1 kerran;
Ja - toistuu 1 kerran.

Tarkista: 3 + 3 + 2 + 1 + 1 + 1 = 11, jonka halusimme tarkistaa.

Kaavan mukaan permutaatioiden määrä toistoilla:
erilaisia ​​kirjainyhdistelmiä voidaan saada. Yli puoli miljoonaa!

Suuren tekijäarvon nopeaan laskemiseen on kätevää käyttää tavallista Excel-toimintoa: pisteytetään missä tahansa solussa =FAKTA(11) ja napsauta Tulla sisään.

Käytännössä on melko hyväksyttävää olla kirjoittamatta yleistä kaavaa ja lisäksi jättää pois yksikkötekijät:

Mutta alustavat kommentit toistuvista kirjeistä ovat tarpeen!

Vastaus: 554400

Toinen tyypillinen esimerkki permutaatioista toistoilla on shakkinappuloiden järjestysongelma, joka löytyy varastosta valmiita ratkaisuja vastaavassa pdf:ssä. Ja itsenäistä ratkaisua varten keksin vähemmän mallitehtävän:

Tehtävä 13

Aleksei harrastaa urheilua ja 4 päivää viikossa - yleisurheilua, 2 päivää - voimaharjoituksia ja 1 lepopäivä. Kuinka monella tavalla hän voi ajoittaa viikoittaiset tunninsa?

Kaava ei toimi tässä, koska se ottaa huomioon päällekkäiset permutaatiot (esim. kun keskiviikon voimaharjoitukset vaihtuvat torstaina voimaharjoitteluun). Ja jälleen - itse asiassa samat 2 voimaharjoittelua voivat olla hyvin erilaisia ​​​​toisistaan, mutta tehtävän yhteydessä (aikataulun kannalta) niitä pidetään samoilla elementeillä.

Kaksirivinen ratkaisu ja vastaus oppitunnin lopussa.

Yhdistelmät toistoilla

Tämän tyyppiselle yhdistelmälle on ominaista, että näyte on otettu useista ryhmistä, joista jokainen koostuu samoista objekteista.

Kaikki työskentelivät tänään kovasti, joten on aika virkistäytyä:

Tehtävä 14

Opiskelijakahvilassa myydään taikina-makkaroita, juustokakkuja ja munkkeja. Kuinka monella tavalla viisi kakkua voi ostaa?

Ratkaisu: kiinnitä välittömästi huomiota tyypilliseen kriteeriin yhdistelmille, joissa on toistoja - tilanteen mukaan, ei esinejoukko sellaisenaan, vaan erilaisia esineitä; oletetaan, että myynnissä on vähintään viisi hot dogia, 5 juustokakkua ja 5 munkkia. Jokaisen ryhmän piirakat ovat tietysti erilaisia ​​- koska täysin identtisiä munkkeja voidaan simuloida vain tietokoneella =) Piirakojen fyysiset ominaisuudet eivät kuitenkaan ole ongelman kannalta oleellisia, ja hot dogit / juustokakut / munkit heidän ryhmissään pidetään samoina.

Mitä näytteessä voi olla? Ensinnäkin on huomattava, että näytteessä on varmasti identtisiä piirakoita (koska valitsemme 5 kappaletta ja 3 tyyppiä tarjotaan valita). Vaihtoehtoja jokaiseen makuun: 5 hot dogia, 5 juustokakkua, 5 munkkia, 3 hot dogia + 2 juustokakkua, 1 hot dog + 2 + juustokakkua + 2 munkkia jne.

Kuten "tavallisissa" yhdistelmissä, piirakoiden valintajärjestyksellä ja sijoittamisella näytteeseen ei ole väliä - he valitsivat vain 5 kappaletta ja siinä se.

Käytämme kaavaa toistojen yhdistelmien määrä:
tapa ostaa 5 piirakkaa.

Nauti ateriastasi!

Vastaus: 21

Mitä johtopäätöksiä voidaan tehdä monista kombinatorisista ongelmista?

Joskus vaikeinta on ymmärtää tilanne.

Samanlainen esimerkki tee-se-itse-ratkaisusta:

Tehtävä 15

Lompakko sisältää melko paljon 1, 2, 5 ja 10 ruplan kolikoita. Kuinka monella tavalla lompakosta voi ottaa kolme kolikkoa?

Vastaa itsehillinnän vuoksi muutamaan yksinkertaiseen kysymykseen:

1) Voivatko kaikki näytteen kolikot olla erilaisia?
2) Nimeä "halvin" ja "kallein" kolikoiden yhdistelmä.

Ratkaisu ja vastaukset oppitunnin lopussa.

Omasta kokemuksestani voin sanoa, että yhdistelmät toistojen kanssa ovat käytännössä harvinaisin vieras, mitä ei voi sanoa seuraavan tyyppisistä yhdistelmistä:

Sijoitukset toistoilla

Elementeistä koostuvasta joukosta valitaan elementit, ja elementtien järjestys kussakin otoksessa on tärkeä. Ja kaikki olisi hyvin, mutta melko odottamaton vitsi on, että voimme valita minkä tahansa esineen alkuperäisestä sarjasta niin monta kertaa kuin haluamme. Kuvaannollisesti sanoen "joukko ei vähene".

Milloin se tapahtuu? Tyypillinen esimerkki on yhdistelmälukko, jossa on useita levyjä, mutta tekniikan kehityksen vuoksi on tärkeämpää tarkastella sen digitaalista jälkeläistä:

Tehtävä 16

Kuinka monta 4-numeroista PIN-koodia on?

Ratkaisu: itse asiassa ongelman ratkaisemiseksi riittää, että tiedät kombinatoriikan säännöt: voit valita pin-koodin ensimmäisen numeron eri tavoilla ja tapoja - PIN-koodin toinen numero ja niin monella tapaa - kolmasosa ja yhtä monta - neljäs. Siten yhdistelmien kertolaskusäännön mukaan nelinumeroinen pin-koodi voidaan muodostaa: tavoilla.

Ja nyt kaavan kanssa. Ehdon mukaan meille tarjotaan joukko numeroita, joista numerot valitaan ja sijoitetaan tietyssä järjestyksessä, kun taas näytteen numerot voidaan toistaa (eli mitä tahansa alkuperäisen joukon numeroa voidaan käyttää mielivaltaisen määrän kertoja). Toistojen sijoittelujen lukumäärän kaavan mukaan:

Vastaus: 10000

Mitä tästä tulee mieleen ... ... jos pankkiautomaatti "syö" kortin kolmannen epäonnistuneen PIN-koodin syöttämisyrityksen jälkeen, mahdollisuudet poimia se satunnaisesti ovat hyvin harhaanjohtavia.

Ja kuka sanoi, ettei kombinatoriikassa ole käytännön järkeä? Kognitiivinen tehtävä kaikille sivuston lukijoille:

Ongelma 17

Valtion standardin mukaan auton rekisterikilpi koostuu 3 numerosta ja 3 kirjaimesta. Tässä tapauksessa numero, jossa on kolme nollaa, ei ole sallittu, ja kirjaimet valitaan joukosta A, B, E, K, M, H, O, R, C, T, U, X (käytetään vain niitä kyrillisiä kirjaimia, joiden oikeinkirjoitus vastaa latinalaisia ​​kirjaimia).

Kuinka monta erilaista rekisterikilpiä voidaan muodostaa alueelle?

Ei muuten niin ja paljon. Suurilla alueilla tämä määrä ei riitä, ja siksi niille on useita koodeja merkinnälle RUS.

Ratkaisu ja vastaus oppitunnin lopussa. Älä unohda käyttää kombinatoriikan sääntöjä ;-) …Halusin kerskua yksinoikeudella, mutta osoittautui, ettei se ole poissulkevaa =) Katselin Wikipediaa - siellä on kuitenkin laskelmia, ilman kommentteja. Vaikka koulutustarkoituksiin, luultavasti harvat ihmiset ratkaisivat sen.

Kiehtova oppituntimme on päättynyt, ja lopuksi haluan sanoa, että et hukannut aikaasi - siitä syystä, että kombinatoriikkakaavat löytävät toisen tärkeän käytännön sovelluksen: ne löytyvät erilaisista tehtävistä todennäköisyysteoria,
ja sisään klassista todennäköisyyden määritelmää koskevia tehtäviä- varsinkin usein

Kiitos kaikille aktiivisesta osallistumisesta ja nähdään pian!

Ratkaisut ja vastaukset:

Tehtävä 2: Ratkaisu: etsi 4 kortin kaikkien mahdollisten permutaatioiden lukumäärä:

Kun kortti, jossa on nolla, on 1. sijalla, numerosta tulee kolminumeroinen, joten nämä yhdistelmät tulee jättää pois. Olkoon nolla 1. paikalla, niin loput 3 vähiten merkitsevistä numeroista voidaan järjestää uudelleen tavalla.

Merkintä : koska kortteja on vähän, kaikki sellaiset vaihtoehdot on helppo luetella tähän:
0579
0597
0759
0795
0957
0975

Siten ehdotetusta sarjasta voit tehdä:
24 - 6 = 18 nelinumeroista numeroa
Vastaus : 18

Tehtävä 4: Ratkaisu: 3 korttia voidaan valita 36 eri tavalla.
Vastaus : 7140

Tehtävä 6: Ratkaisu: tavoilla.
Toinen ratkaisu : tapoja, joilla voit valita kaksi henkilöä ryhmästä ja ja
2) Halvin sarja sisältää 3 ruplaa ja kallein sarja 3 kymmenen ruplan kolikkoa.

Tehtävä 17: Ratkaisu: tapoja, joilla voit tehdä rekisterikilven digitaalisen yhdistelmän, kun taas yksi niistä (000) tulisi sulkea pois:.
tapoja, joilla voit tehdä kirjainyhdistelmän auton numerosta.
Yhdistelmien kertolaskusäännön mukaan kaikki voidaan muodostaa:
auton numerot
(jokainen yhdistetty digitaalinen yhdistelmä jokaisen kanssa kirjainyhdistelmä).
Vastaus : 1726272

Yhdistelmä on äärellisen joukon elementtien järjestämätön valikoima kiinteällä määrällä ja ilman elementtien toistoa. Eri yhdistelmien tulee erota ainakin yhdellä elementillä, eikä elementtien järjestyksellä ole väliä. Esimerkiksi latinalaisten kirjainten (AEIOU) kaikkien vokaalien joukosta voidaan muodostaa 10 erilaista 3 kirjaimen yhdistelmää, jotka muodostavat seuraavat järjestämättömät kolmoset:

AEI, AEO, AEU, AIO, AIU, AOU, EIO, EIU, EOU, IOU.

On mielenkiintoista huomata, että samoista viidestä kirjaimesta saat myös 10 erilaista yhdistelmää, jos yhdistät niistä 2 kirjainta, jolloin muodostuu seuraavat järjestämättömät parit:

AE, AI, AO, AU, EI, EO, EU, IO, IU, OU.

Jos kuitenkin yhdistät samat latinalaiset vokaalit neljällä, saat vain seuraavat 5 eri yhdistelmää:

AEIO, AEIU, AIOU, EIOU, AEOU.

Yleisessä tapauksessa n eri elementin yhdistelmien lukumäärän merkitsemiseksi m elementillä käytetään seuraavaa funktionaalista, indeksi- tai vektorisymboliikkaa (Appel):

Riippumatta merkintämuodosta, n elementin yhdistelmien lukumäärä m elementillä voidaan määrittää seuraavilla kerto- ja tekijäkaavoilla:

On helppo tarkistaa, että näitä kaavoja käyttävien laskelmien tulos vastaa yllä olevan esimerkin tuloksia latinalaisten vokaalien yhdistelmillä. Erityisesti arvoilla n=5 ja m=3 näitä kaavoja käyttävät laskelmat antavat seuraavan tuloksen:

Yleisessä tapauksessa yhdistelmien lukumäärän kaavoilla on kombinatorinen merkitys ja ne ovat voimassa kaikille n:n ja m:n kokonaislukuarvoille siten, että n > m > 0. Jos m > n ja m< 0, то число сочетаний равно 0, так как в этом случае основное множество из n элементов вообще не имеет подмножеств мощности m:

Lisäksi on hyödyllistä muistaa seuraavat yhdistelmärajaluvut, jotka on helppo tarkistaa vaihtamalla suoraan kerto- ja kertolaskavoihin:

On myös huomattava, että kertokaava pysyy voimassa, vaikka n on reaaliluku, niin kauan kuin m on edelleen kokonaisluku. Kuitenkin silloin sen laskennan tulos, säilyttäen muodollisen pätevyyden, menettää kombinatorisen merkityksensä.

YHDISTELMÄIDENTITEETIT

Kerto- ja tekijäkaavojen käytännön käyttö n:n ja m:n mielivaltaisten arvojen yhdistelmien lukumäärän määrittämiseksi ei ole kovin tuottavaa, koska niiden osoittajan ja nimittäjän tekijätulot kasvavat eksponentiaalisesti. Jopa suhteellisen pienillä n:n ja m:n arvoilla nämä tuotteet ylittävät usein mahdollisuudet esittää kokonaislukuja nykyaikaisissa laskenta- ja ohjelmistojärjestelmissä. Samaan aikaan niiden arvot osoittautuvat paljon suuremmiksi kuin tuloksena saatu yhdistelmien lukumäärä, joka voi olla suhteellisen pieni. Esimerkiksi yhdistelmien lukumäärä n = 10 m = 8 elementillä on vain 45. Kuitenkin, jotta tämä arvo voidaan löytää tekijäkaavalla, sinun on ensin laskettava paljon suuremmat arvot 10! osoittajassa ja 8! nimittäjässä:

Voit sulkea pois aikaa vievät suurten arvojen käsittelyoperaatiot ja määrittää yhdistelmien lukumäärän käyttämällä erilaisia ​​toistuvuussuhteita, jotka seuraavat suoraan kerto- ja tekijäkaavoista. Erityisesti seuraava toistuvuussuhde seuraa kerrannaiskaavasta, jonka avulla voimme ottaa sen indeksien suhteen yhdistelmän lukumäärän etumerkin yli:

Lopuksi alaindeksin pitäminen muuttumattomana tuottaa seuraavan toistumisen, joka saadaan helposti yhdistelmien lukumäärän tekijäkaavasta:

Alkuperäisten muunnosten jälkeen kolme tuloksena olevaa toistuvuussuhdetta voidaan esittää seuraavissa muodoissa:

Jos nyt lasketaan yhteen kahden ensimmäisen kaavan vasen ja oikea osa ja vähennetään tulosta n:llä, saadaan tärkeä toistuvuusrelaatio, jota kutsutaan yhdistelmien lukumäärän yhteenlaskemisen identiteetiksi:

Summa-identiteetti tarjoaa perusrekursiivisen säännön yhdistelmien lukumäärän tehokkaaseen määrittämiseen suurille n:n ja m:n arvoille, koska sen avulla kertolaskuoperaatiot voidaan korvata yksinkertaisemmilla summausoperaatioilla ja harvemmilla yhdistelmillä. Erityisesti summausidentiteettiä käyttämällä on nyt helppo määrittää edellä tarkasteltu n=10 m=8 elementin yhdistelmien lukumäärä suorittamalla seuraava toistuvien muunnosten sarja:

Lisäksi summausidentiteetistä voidaan johtaa useita hyödyllisiä suhteita äärellisten summien laskemiseen, erityisesti alaindeksin summauskaavasta, jolla on seuraava muoto:

Tällainen suhde saadaan laajentamalla lisäysidentiteetin toistuvuutta termin yli, jolla on suurin yläindeksi, kunhan sen alaindeksi on suurempi kuin 0. Seuraava numeerinen esimerkki havainnollistaa ilmoitettua rekursiivisten muunnosten prosessia:

Alaindeksin summauskaavaa käytetään usein laskettaessa luonnollisten lukujen potenssien summaa. Erityisesti, jos oletetaan m=1, tätä kaavaa käyttämällä on helppo löytää luonnollisen sarjan n ensimmäisen luvun summa:

Toinen hyödyllinen versio summauskaavasta voidaan saada laajentamalla summausidentiteetin toistumista termille pienimmällä yläindeksillä. Seuraava numeerinen esimerkki havainnollistaa tätä toistuvien muunnosten muunnelmaa:

Yleisessä tapauksessa tällaisten muunnosten tuloksena saadaan yhdistelmien lukumäärien summa, joiden molemmat indeksit eroavat yhdellä naapuritermeistä ja indeksien ero pysyy vakiona (tarkasteltavassa esimerkissä se on myös yhtä suuri kuin yksi). Siten saadaan seuraava summauskaava molemmille yhdistelmälukujen indekseille:

Yllä käsiteltyjen toistuvuusrelaatioiden ja summauskaavojen lisäksi kombinatorisessa analyysissä on saatu monia muita hyödyllisiä identiteettejä yhdistelmänumeroille. Tärkein niistä on symmetria-identiteetti, jolla on seuraava muoto:

Symmetriaidentiteetin pätevyys voidaan nähdä seuraavassa esimerkissä vertaamalla 5 elementin yhdistelmien lukumäärää kahdella ja (5 2) = 3:lla:

Symmetria-identiteetillä on ilmeinen kombinatorinen merkitys, koska samalla kun se määrittää vaihtoehtojen lukumäärän m elementin valitsemiseksi n elementistä, se määrittää samanaikaisesti yhdistelmien lukumäärän jäljellä olevista (nm) valitsemattomista elementeistä. Ilmoitettu symmetria saadaan välittömästi korvaamalla m:llä (nm) yhdistelmien lukumäärän tekijäkaavassa:

Numeroita ja yhdistelmäidentiteettejä käytetään laajasti modernin laskennallisen matematiikan eri alueilla. Kuitenkin niiden suosituin sovellus liittyy Newtonin binomiaaliin ja Pascalin kolmioon.

BINOMILAUSE

Erilaisten matemaattisten muunnosten ja laskutoimitusten suorittamiseksi on tärkeää pystyä esittämään mikä tahansa algebrallisen binomin (binomiaalin) luonnollinen potenssi polynomin muodossa. Pienillä asteilla haluttu polynomi saadaan helposti kertomalla binomit suoraan. Erityisesti seuraavat kaavat kahden termin summan neliölle ja kuutiolle tunnetaan hyvin alkeismatematiikan kurssista:

Yleisessä tapauksessa mielivaltaiselle binomin asteikolle n haluttu esitys polynomin muodossa saadaan Newtonin binomilauseella, joka julistaa, että seuraava yhtälö pätee:

Tätä yhtälöä kutsutaan yleensä Newtonin binomiaaliksi. Sen oikealla puolella oleva polynomi on vasemman puolen binomin n termien X ja Y tulojen summa, ja niiden edessä olevia kertoimia kutsutaan binomiiksi ja ne ovat yhtä suuria kuin saatujen indeksien yhdistelmien lukumäärä voimistaan. Ottaen huomioon Newtonin binomikaavan erityisen suosion kombinatorisessa analyysissä, termejä binomikerroin ja yhdistelmien lukumäärä pidetään yleensä synonyymeinä.

On selvää, että summaneliö- ja kuutiokaavat ovat binomilauseen erikoistapauksia arvoille n=2 ja n=3. Suurempien tehojen (n>3) käsittelemiseksi tulee käyttää Newtonin binomikaavaa. Sen soveltaminen neljännen asteen binomiaaliin (n=4) on havainnollistettu seuraavalla esimerkillä:

On huomattava, että binomikaava tunsivat jo ennen Newtonia keskiaikaisille arabi-idän ja Länsi-Euroopan matemaatikoille. Siksi sen yleinen nimi ei ole historiallisesti oikea. Newtonin ansio on, että hän yleisti tämän kaavan mielivaltaisen reaalieksponentin r tapaukseen, joka voi ottaa mitä tahansa positiivisia tai negatiivisia rationaalisia ja irrationaalisia arvoja. Yleisessä tapauksessa tällaisen Newtonin binomikaalin oikealla puolella on ääretön summa ja se on tapana kirjoittaa seuraavasti:

Esimerkiksi eksponentin positiivisella murto-arvolla r=1/2, kun otetaan huomioon binomikertoimien arvot, saadaan seuraava laajennus:

Yleisessä tapauksessa minkä tahansa eksponentin Newtonin binomikaali on erityinen versio Maclaurinin kaavasta, joka antaa mielivaltaisen funktion laajennuksen potenssisarjassa. Newton osoitti, että |z|< 1 этот ряд сходится, и сумма в правой части становится конечной. При любой натуральной степени r = n в правой части также получается конечная сумма из (n+1) первых слагаемых, так как все C(n, k>n) = 0. Jos nyt laitetaan Z=X/Y ja kerrotaan vasen ja oikea puoli Yn:llä, saadaan muunnelma yllä käsitellystä Newtonin binomikaalista.

Universaalisuudestaan ​​huolimatta binomilause säilyttää kombinatorisen merkityksensä vain binomin ei-negatiivisten kokonaislukujen osalta. Tässä tapauksessa sitä voidaan käyttää useiden hyödyllisten binomikertoimien identiteetin todistamiseen. Yllä tarkasteltiin erityisesti yhdistelmien lukumäärän summauskaavoja alemman indeksin ja molempien indeksien mukaan. Puuttuva yläindeksin summausidentiteetti saadaan helposti Newtonin binomikaavasta asettamalla siihen X = Y = 1 tai Z = 1:

Toinen hyödyllinen identiteetti määrittää binomikertoimien summien yhtäläisyyden parillisten ja parittomien lukujen kanssa. Se saadaan välittömästi Newtonin binomikaavasta, jos X = 1 ja Y = 1 tai Z = 1:

Lopuksi molemmista tarkastelluista identiteeteistä saadaan binomikertoimien summa, joissa on vain parillisia tai vain parittomat luvut:

Tarkastettujen identiteettien ja rekursiivisen säännön perusteella, jolla indeksit poistetaan yhdistelmien lukumäärän merkin alta, voidaan saada useita mielenkiintoisia suhteita. Jos esimerkiksi yläindeksin summauskaavassa korvaamme n:n (n1):llä kaikkialla ja poistamme indeksit kustakin termistä, saadaan seuraava relaatio:

Käyttämällä samanlaista tekniikkaa parillisten ja parittomien lukujen binomikertoimien summan kaavassa voidaan todistaa esimerkiksi seuraavan suhteen pätevyys:

Toinen hyödyllinen identiteetti tekee helpoksi laskea kahden mielivaltaisen asteen n ja k binomin symmetrisesti sijaitsevien binomikertoimien tulojen summa käyttämällä seuraavaa Cauchyn kaavaa:

Tämän kaavan pätevyys seuraa muuttujan Z mille tahansa asteen m kertoimien välttämättömästä yhtäläisyydestä seuraavan identiteettisuhteen vasemmalla ja oikealla puolella:

Erityisessä tapauksessa, kun n=k=m, saadaan symmetria-identiteetti huomioon ottaen suositumpi kaava binomiaalisten kertoimien neliöiden summalle:

Monia muita hyödyllisiä identiteettejä binomiaalisille kertoimille löytyy laajasta kombinatorisen analyysin kirjallisuudesta. Niiden tunnetuin käytännön sovellus liittyy kuitenkin Pascalin kolmioon.

PASCALIN KOLMIO

Pascalin aritmeettinen kolmio muodostaa äärettömän numeerisen taulukon, joka koostuu binomiaalisista kertoimista. Sen rivit on järjestetty binomiaalisten potenssien mukaan ylhäältä alas. Jokaisella rivillä binomikertoimet on järjestetty nousevaan järjestykseen vastaavien yhdistelmien lukumäärän yläindeksien mukaan vasemmalta oikealle. Pascalin kolmio kirjoitetaan yleensä joko tasakylkiseksi tai suorakaiteen muotoiseksi.

Visuaalisempi ja yleisempi on tasakylkinen muoto, jossa binomiaaliset kertoimet shakkitaulun kuvioon järjestyneinä muodostavat äärettömän tasakylkisen kolmion. Sen alkuperäinen fragmentti binomiaaleille 4. asteeseen asti (n=4) on seuraava:

Yleisesti ottaen Pascalin tasakylkinen kolmio tarjoaa kätevän geometrisen säännön binomikertoimien määrittämiseen, joka perustuu yhteenlaskettuihin identiteeteihin ja yhdistelmälukujen symmetriaan. Erityisesti summausidentiteetin mukaan mikä tahansa binomikerroin on sitä lähinnä olevan edellisen rivin kahden kertoimen summa. Symmetriaidentiteetin mukaan Pascalin tasakylkinen kolmio on symmetrinen puolittajaansa nähden. Siten jokainen sen rivi on binomiaalisten kertoimien numeerinen palindromi. Näiden algebrallisten ja geometristen ominaisuuksien avulla on helppo laajentaa Pascalin tasakylkistä kolmiota ja löytää johdonmukaisesti mielivaltaisten asteiden binomikertoimien arvot.

Pascalin kolmion eri ominaisuuksien tutkimiseen on kuitenkin kätevämpää käyttää muodollisesti tiukempaa suorakaiteen muotoa. Tässä muodossa se annetaan binomiaalisten kertoimien alemman kolmion matriisina, jossa ne muodostavat äärettömän suorakulmaisen kolmion. Pascalin suorakulmaisen kolmion alkufragmentti binomiaaleille 9. asteeseen asti (n=9) on seuraavanlainen:

Geometrisesti tällainen suorakaiteen muotoinen pöytä saadaan muuttamalla Pascalin tasakylkistä kolmiota vaakasuunnassa. Seurauksena on, että Pascalin tasakylkisen kolmion sivujen suuntaiset numerosarjat muuttuvat Pascalin suorakulmaisen kolmion pystysuoraksi ja lävistäjäksi, ja molempien kolmioiden vaakasuorat ovat samat. Samanaikaisesti binomikertoimien yhteenlasku- ja symmetriasäännöt pysyvät voimassa, vaikka Pascalin suorakulmainen kolmio menettää tasakylkiselle vastineelle ominaisen visuaalisen symmetrian. Tämän kompensoimiseksi on kätevämpää analysoida muodollisesti Pascalin suorakulmaisen kolmion vaaka-, pysty- ja diagonaalien binomikertoimien erilaisia ​​numeerisia ominaisuuksia.

Aloittamalla Pascalin suorakulmaisen kolmion ääriviivojen analyysin on helppo nähdä, että minkä tahansa rivin, jonka numero on n, alkioiden summa on yhtä suuri kuin 2 n binomialin yläindeksin summauskaavan mukaisesti. Tästä seuraa, että minkä tahansa vaakatason, jonka numero on n, elementtien summa on yhtä suuri kuin (2 n 1). Tämä tulos tulee varsin ilmeiseksi, jos kunkin vaakatason elementtien summan arvo kirjoitetaan binäärilukujärjestelmään. Esimerkiksi arvolle n=4 tällainen lisäys voidaan kirjoittaa seuraavasti:

Tässä on pari muuta mielenkiintoista ääriviivojen ominaisuutta, jotka liittyvät myös kahden potenssiin. Osoittautuu, että jos vaakaluku on kahden potenssi (n=2 k), niin kaikki sen sisäiset alkiot (paitsi ääriyksiköt) ovat parillisia lukuja. Päinvastoin, kaikki vaakaluvut ovat parittomia, jos niiden luku on yksi pienempi kuin kahden potenssi (n=2 k 1). Näiden ominaisuuksien pätevyys voidaan varmistaa tarkistamalla sisäisten binomikertoimien pariteetti esimerkiksi vaakasuuntaisissa n=4 ja n=3 tai n=8 ja n=7.

Olkoon nyt Pascalin suorakulmaisen kolmion rivinumero alkuluku p. Silloin kaikki sen sisäiset binomikertoimet ovat jaollisia p:llä. Tämä ominaisuus on helppo tarkistaa yksinkertaisten vaakasuuntaisten lukumäärien pienistä arvoista. Esimerkiksi kaikki viidennen vaakatason sisäiset binomikertoimet (5, 10 ja 5) ovat ilmeisesti jaollisia 5:llä. Todistaaksemme tämän tuloksen pätevyyden mille tahansa vaakasuuntaisen p:n alkuluvulle, meidän on kirjoitettava sen binomiaalin kertolasku. kertoimet seuraavasti:

Koska p on alkuluku eikä siksi jaollinen m:llä!, tämän kaavan osoittajan muiden tekijöiden tulon on oltava jaollinen m:llä, jotta binomikertoimen kokonaisluku voidaan taata. Tästä seuraa, että hakasulkeissa oleva relaatio on luonnollinen luku N ja haluttu tulos tulee ilmeiseksi:

Tämän tuloksen avulla voidaan todeta, että Pascalin kolmion, jonka sisäiset alkiot ovat jaollisia annetulla alkuluvulla p, ääriviivojen luvut ovat p:n potenssia, eli ne ovat muotoa n=p k . Erityisesti jos p=3, niin alkuluku p jakaa rivin 3 kaikkien sisäisten elementtien lisäksi esimerkiksi 9. vaakatason (9, 36, 84 ja 126). Toisaalta Pascalin kolmiossa on mahdotonta löytää vaakasuuntaa, jonka kaikki sisäiset elementit ovat jaollisia yhdistelmäluvulla. Muuten tällaisen vaakatason numeron tulee olla samalla yhdistelmäluvun alkujakajan aste, jolla kaikki sen sisäiset elementit jaetaan, mutta tämä on ilmeisistä syistä mahdotonta.

Tarkastettujen näkökohtien avulla voimme muotoilla seuraavan yleisen kriteerin Pascalin kolmion vaakasuuntaisten elementtien jaettavuudelle. Pascalin kolmion, jonka vaaka on numerolla n, kaikkien sisäisten elementtien suurin yhteinen jakaja (gcd) on yhtä suuri kuin alkuluku p, jos n=pk tai 1 kaikissa muissa tapauksissa:

GCD(Cmn) = ( ) mille tahansa 0:lle< m < n .

Horisontaalisten tekijöiden analyysin päätteeksi kannattaa ottaa huomioon yksi omituinen ominaisuus, joka niitä muodostavilla binomikertoimilla on. Jos minkä tahansa vaakatason, jonka luku on n, binomiaaliset kertoimet kerrotaan luvun 10 peräkkäisillä potenssilla ja sitten kaikki nämä tulot lasketaan yhteen, saadaan 11 n. Tämän tuloksen muodollinen perustelu on arvojen X=10 ja Y=1 (tai Z=1) korvaaminen Newtonin binomikaalissa. Seuraava numeerinen esimerkki havainnollistaa tämän ominaisuuden toteutusta arvolle n=5:

Pascalin suorakulmaisen kolmion vertikaalien ominaisuuksien analyysi voidaan aloittaa niiden muodostavien elementtien yksittäisten ominaisuuksien tutkimuksella. Muodollisesti jokainen pystysuora m muodostuu seuraavasta äärettömästä binomiaalikertoimien sarjasta, jossa on vakio yläindeksi (m) ja alaindeksin lisäys:

Ilmeisesti kun m = 0, saadaan ykkösten sarja ja kun m = 1, muodostuu luonnollisten lukujen sarja. Kun m = 2, pystysuora muodostuu kolmioluvuista. Jokainen kolmioluku voidaan kuvata tasossa tasasivuisena kolmiona, joka on täytetty mielivaltaisilla objekteilla (ytimillä), jotka on järjestetty shakkitaulukuvioon. Tässä tapauksessa kunkin kolmioluvun T k arvo määrittää edustavien ytimien lukumäärän ja indeksi osoittaa kuinka monta riviä ytimiä tarvitaan sen esittämiseen. Esimerkiksi neljä ensimmäistä kolmionumeroa edustavat seuraavia kokoonpanoja vastaavasta määrästä ytimen merkkejä "@":

On huomattava, että samalla tavalla voidaan ottaa huomioon neliöluvut S k , jotka saadaan neliöimällä luonnolliset luvut, ja yleensä monikulmiokuvalliset luvut, jotka on muodostettu säännöllisten monikulmioiden säännöllisellä täytöllä. Erityisesti neljä aloitusneliönumeroa voidaan esittää seuraavasti:

Palatakseni Pascalin kolmion vertikaalien analyysiin, voidaan todeta, että seuraava pystysuora kohdassa m=3 on täytetty tetraedrisillä (pyramidi-) luvuilla. Jokainen tällainen luku P k määrittelee ytimien lukumäärän, joka voidaan järjestää tetraedrin muotoon, ja indeksi määrittää kuinka monta vaakasuuntaista kolmiomaista kerrosta ydinriveistä tarvitaan edustamaan sitä kolmiulotteisessa avaruudessa. Tässä tapauksessa kaikki vaakasuorat tasot tulee esittää peräkkäisinä kolmiolukuina. Pascalin kolmion seuraavien pystysuorien elementit m>3:lle muodostavat hypertetraedisten lukujen rivejä, joilla ei ole selkeää geometrista tulkintaa tasossa tai kolmiulotteisessa avaruudessa, mutta jotka vastaavat muodollisesti kolmio- ja tetraedaalilukujen moniulotteisia analogeja.

Vaikka Pascalin kolmion pystysuorassa numeerisessa sarjassa on harkitut yksittäiset kiharat ominaisuudet, mutta niille on mahdollista laskea alkuelementtien arvojen osasummat samalla tavalla käyttämällä kaavaa yhdistelmien lukumäärän summaamiseksi alaindeksillä . Pascalin kolmiossa tällä kaavalla on seuraava geometrinen tulkinta. Minkä tahansa pystysuoran n ylemmän binomikertoimen arvojen summa on yhtä suuri kuin seuraavan pystysuoran elementin arvo, joka sijaitsee yhden rivin alapuolella. Tämä tulos on myös yhdenmukainen kolmio-, tetraedri- ja hypertetraedisten lukujen geometrisen rakenteen kanssa, koska kunkin tällaisen luvun esitys koostuu ydinkerroksista, jotka edustavat alemman kertaluvun lukuja. Erityisesti n:s kolmioluku T n voidaan saada summaamalla kaikki sen lineaarikuituja edustavat luonnolliset luvut:

Samoin on helppo löytää tetraedriluku P n laskemalla seuraava summa ensimmäisistä n kolmioluvuista, jotka muodostavat sen vaakasuuntaiset ydinkerrokset:

Pascalin suorakulmaisen kolmion vaaka- ja pystysuorien lisäksi voidaan jäljittää elementtien diagonaalirivit, joiden ominaisuuksien tutkiminen on myös erityisen kiinnostavaa. Tällöin yleensä erotetaan laskeva ja nouseva diagonaali. Laskevat diagonaalit ovat yhdensuuntaisia ​​Pascalin suorakulmaisen kolmion hypotenuusan kanssa. Ne muodostetaan binomiaalisten kertoimien sarjoista molempien indeksien lisäyksellä. Symmetrian identiteetin vuoksi laskevat lävistäjät ovat elementtien arvoissa yhtäpitäviä Pascalin kolmion vastaavien pystysuorien rivien kanssa ja toistavat siksi kaikki niiden edellä tarkastellut ominaisuudet. Määritetty vastaavuus voidaan jäljittää laskevan lävistäjän ja pystysuoran elementtien arvojen yhteensopivuudella millä tahansa numerolla n, jos pystysuoraa nollia ei oteta huomioon:

Nousevat diagonaalit muodostavat numerorivejä, jotka ovat geometrisesti kohtisuorassa Pascalin suorakulmaisen kolmion hypotenuusan kanssa. Ne on täytetty binomiaalisilla kertoimilla, joissa on alaindeksin lisäys ja yläindeksin lisäys. Erityisesti 7 ylempää nousevaa diagonaalia muodostavat seuraavan numeerisen sekvenssin, pois lukien loppunollat:

Yleisessä tapauksessa seuraavat binomikertoimet ovat nousevalla diagonaalilla numerolla n, joiden kunkin indeksien summa on yhtä suuri kuin (n1):

Yhdistelmänumeroiden summausidentiteetin ansiosta jokainen diagonaalielementti on yhtä suuri kuin kahden edellisen nousevan diagonaalin indeksejä vastaavien kahden elementin summa. Tämä mahdollistaa jokaisen seuraavan nousevan lävistäjän rakentamisen summaamalla pareittain vierekkäiset vaakasuuntaiset elementit kahdesta edellisestä lävistäjästä, laajentaen loputtomasti Pascalin kolmiota diagonaalia pitkin. Seuraava Pascalin kolmion fragmentti havainnollistaa nousevan diagonaalin rakentamista numerolla 8 pitkin diagonaaleja numeroilla 6 ja 7:

Tällä rakennusmenetelmällä minkä tahansa nousevan lävistäjän elementtien summa alkaen 3:sta on yhtä suuri kuin kahden edellisen nousevan diagonaalin elementtien summa, ja ensimmäiset 2 diagonaalia koostuvat vain yhdestä elementistä, arvosta. josta on 1. Vastaavien laskelmien tulokset muodostavat seuraavan numeerisen sarjan, jonka mukaan on mahdollista varmistaa Pascalin suorakulmaisen kolmion nousevien diagonaalien tarkastelun kohteen pätevyys:

Näitä lukuja analysoimalla näet, että samanlaisen lain mukaan muodostuu Fibonacci-lukujen tunnettu sarja, jossa jokainen peräkkäinen luku on yhtä suuri kuin kahden edellisen summa ja kaksi ensimmäistä lukua ovat yhtä kuin 1 :

Siten voidaan tehdä seuraava tärkeä johtopäätös: Pascalin kolmion alkioiden diagonaaliset summat muodostavat Fibonacci-sekvenssin. Tämän ominaisuuden avulla voimme perustaa toisen mielenkiintoisen Pascalin kolmion piirteen. Laajentamalla Fibonaccin kaavaa rekursiivisesti on helppo todistaa, että ensimmäisen n Fibonacci-luvun summa on yhtä suuri kuin (F n+2 1).

Siksi myös n ylin diagonaalia täyttävien binomiaalikertoimien summa on yhtä suuri kuin (F n+2 1). Tästä seuraa, että Pascalin kolmion ensimmäisten n lävistäjän summa on 1 pienempi kuin niiden binomikertoimien summa, jotka ovat sen diagonaalissa numerolla (n + 2).

Lopuksi on huomattava, että Pascalin kolmion vaaka-, pysty- ja diagonaalien tarkastelut ominaisuudet eivät suinkaan tyhjennä sitä valtavaa valikoimaa mahdollisuuksia, jotka yhdistävät erilaisia ​​matemaattisia näkökohtia, joilla ei ensi silmäyksellä ole mitään yhteistä. Tällaiset epätavalliset ominaisuudet antavat mahdollisuuden pitää Pascalin kolmiota yhtenä edistyneimmistä numeerisista järjestelmistä, jonka kaikkia mahdollisuuksia ei voida luetella ja jota on vaikea yliarvioida.

Algoritmi yhdistelmien lukumäärän laskemiseksi Pascalin kolmiolla on esitetty alla:

Yksityinen funktio SochTT (ByVal n kokonaislukuna, ByVal k kokonaislukuna) Double Dim i kokonaislukuna Dim j kokonaislukuna Dim TT () Double ReDim TT (n, k) i = 0 - n TT (0, i) = 1 TT (i, i) = 1 Seuraava Jos i = 2 - n Jos j = 1 To i - 1 TT (i, j) = TT (i - 1, j - 1) + TT (i - 1, j) Seuraava Seuraava SochTT = TT (n, k) Lopputoiminto

Jos sinun on laskettava yhdistelmien lukumäärä useita kertoja, voi olla kätevämpää rakentaa Pascalin kolmio kerran ja saada tiedot sitten taulukosta.

Dim TT () Double Private Sub CreateTT () ReDim TT (0, 0) BuildTT 0, 0 End Sub Private Function SochTT (ByVal n Kokonaislukuna, ByVal k Kokonaislukuna) Double If n > Ubound (TT) Sitten BuildTT Ubound (TT) + 1, n SochTT = TT (n, k) Lopetustoiminto Yksityinen Sub TerminateTT () Redim TT (0, 0) Lopeta Sub Yksityinen Sub BuildTT (ByVal alku kokonaislukuna, ByVal loppu kokonaislukuna) Dim i kokonaislukuna Dim j Kokonaislukuna ReDim Säilytä TT (loppu, loppu) For i = alku Loppuun TT (0, i) = 1 TT (i, i) = 1 Seuraava Jos loppu< 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

Ensin sinun on kutsuttava CreateTT-menettely. Voit sitten saada yhdistelmien määrän SochTT-toiminnolla. Kun et enää tarvitse kolmiota, soita TerminateTT:lle. Yllä olevassa koodissa SochTT-toimintoa kutsuttaessa, jos kolmiota ei ole vielä täydennetty vaaditulle tasolle, se suoritetaan BuildTT-menettelyllä. Funktio saa sitten vaaditun elementin TT-taulukosta ja palauttaa sen.

Dim X () Kokonaislukuna Dim Laskuri () Kokonaislukuna Dim K Kokonaislukuna Dim N Kokonaislukuna Julkinen Sub Soch() Dim i Kokonaislukuna N = CInt(InputBox("Enter N")) K = CInt(InputBox("Syötä K ")) K = K + 1 ReDim X(N) For i = 1 To N X(i) = i Seuraava txtOut.Text = "" Redim Counter(K) Counter(0) = 1 SochGenerate 1 End Sub Private Sub SochGenerate( ByVal c Kokonaislukuna) Dim i Kokonaislukuna Dim j Kokonaislukuna Dim n1 Kokonaislukuna Dim Out() Kokonaislukuna Dim X1() Kokonaislukuna Jos c = K Sitten Dim Out(K) X1 = X For i = 1 To K - 1 n1 = 0 Jos j = 1 - N Jos X1(j)<>0 Sitten n1 = n1 + 1 Jos n1 = Laskuri(i) Sitten Out(i) = X1(j) X1(j) = 0 Poistu loppuun, jos seuraavaksi txtOut.Text = txtOut.Text & CStr(Out(i)) Seuraava txtOut.Text = txtOut.Text & vbCrLf Else For Counter(c) = Counter(c - 1) To N - c + 1 SochGenerate c + 1 Next End If End Sub

Luonnollisten lukujen yhdistelmien laskenta

Monien käytännön ongelmien ratkaisemiseksi on tarpeen luetella kaikki kiinteän kardinalisuuden yhdistelmät, jotka voidaan saada tietyn äärellisen joukon elementeistä, eikä vain määrittää niiden lukumäärää. Kun otetaan huomioon aina olemassa oleva mahdollisuus minkä tahansa äärellisen joukon alkioiden kokonaislukunumerointiin, on useimmissa tapauksissa sallittua rajoittua käyttämään algoritmeja luonnollisten lukujen yhdistelmien laskemiseen. Luonnollisin ja yksinkertaisin niistä on algoritmi luonnollisten lukujen yhdistelmien listaamiseksi leksigrafinen järjestys.

Tämän algoritmin muodollista kuvausta varten on tarkoituksenmukaista olettaa, että pääjoukko, jonka kaikki m elementin yhdistelmät on lueteltava, muodostaa peräkkäisiä luonnollisia lukuja 1:stä n:ään. Sitten mikä tahansa yhdistelmä m

Järjestyksen seurauksena tällaisen yhdistelmävektorin arvo kussakin paikassa osoittautuu luonnollisesti rajoittuneeksi ylhäältä ja alhaalta seuraavasti:

Leksigrafinen algoritmi generoi peräkkäin sellaiset yhdistelmävektorit, alkaen leksigrafisesti pienimmistä vektoreista, joissa kaikki paikat sisältävät seuraavat elementtien mahdolliset vähimmäisarvot, jotka vastaavat niiden indeksejä:

Jokainen seuraava yhdistelmävektori muodostetaan nykyisestä sen elementtien tarkastelun jälkeen vasemmalta oikealle löytääkseen oikeanpuoleisin elementti, joka ei ole vielä saavuttanut raja-arvoaan:

Tällaisen elementin arvoa tulisi kasvattaa yhdellä. Jokaiselle sen oikealla puolella olevalle elementille tulee antaa pienin mahdollinen arvo, joka on 1 enemmän kuin vasemmalla oleva naapuri. Näiden muutosten jälkeen seuraavalla yhdistelmävektorilla on seuraava alkuainekoostumus:

Siten seuraava yhdistelmävektori on leksigrafisesti suurempi kuin edellinen, koska niiden alkualkioiden (j1) arvot ovat yhtä suuret ja asemassa j olevan elementin arvo on 1 suurempi kuin edellisen. . Määrätty kasvavan leksigrafisen järjestyksen suhde toteutuu taatusti kaikissa algoritmin iteraatioissa. Tuloksena muodostuu kasvava leksigrafinen sekvenssi, jonka täydentää leksigrafisesti suurin yhdistelmävektori, jossa elementeillä kaikissa paikoissa on seuraavat maksimiarvot:

Tarkasteltu leksigrafinen algoritmi havainnollistaa seuraavaa esimerkkiä, jossa on tarpeen luetella nousevassa leksigrafisessa järjestyksessä kaikki 15 yhdistelmää n = 6 ensimmäistä luonnollista lukua m = 4 numerolla, eli kaikki mahdolliset päägeneraattorijoukon 4-alkioiset osajoukot ( 1, 2, 3, 4 , 5, 6) 6 elementistä. Laskentatulokset on esitetty seuraavassa taulukossa:

Tässä esimerkissä suurimmat sallitut lukuarvot yhdistelmävektoreiden paikoissa ovat 3, 4, 5 ja 6. Tulosten tulkinnan helpottamiseksi kussakin yhdistelmävektorissa oikeanpuoleisin elementti, jolla ei ole kuitenkin saavuttanut maksimiarvonsa, on alleviivattu. Yhdistelmävektorien numeeriset indeksit määrittelevät niiden numerot leksigrafisessa järjestyksessä. Yleisessä tapauksessa minkä tahansa n elementin yhdistelmän leksigrafinen luku N voidaan laskea seuraavalla kaavalla, jossa kosmeettisista syistä yhdistelmien lukumäärää käytetään Appelin symboliikassa:

Erityisesti seuraavat laskelmat käyttämällä tätä kaavaa n=6 elementin yhdistelmäluvulle (1, 3, 4, 6) ja m=4 leksigrafisessa järjestyksessä antavat tuloksen N=8, joka vastaa edellä käsiteltyä esimerkkiä:

Yleisessä tapauksessa käyttämällä identiteettiä molempien indeksien yhdistelmälukujen summalle, voidaan osoittaa, että leksigrafisesti pienimmän yhdistelmän numero (1, ... i, ... m) laskettaessa sitä tällä avulla kaava on aina yhtä suuri kuin 1:

On myös selvää, että leksigrafisesti suurimman yhdistelmän (m, ... nm+i, ... n) lukumäärä laskettaessa sitä tämän kaavan mukaan on yhtä suuri kuin n elementin yhdistelmien lukumäärä m:llä:

Yhdistelmien leksigrafisten lukujen laskentakaavaa voidaan käyttää käänteisen ongelman ratkaisemiseen, jossa yhdistelmävektori on määritettävä sen numeron perusteella leksigrafisessa järjestyksessä. Tällaisen käänteisongelman ratkaisemiseksi se on kirjoitettava yhtälöksi, jossa halutun yhdistelmän vektorin alkioiden kaikki tuntemattomat arvot (C 1 , ... C i , ... C m) keskittyvät sen oikean puolen yhdistelmien numerot ja yhdistelmien lukumäärän tunnettu ero L kirjoitetaan n elementin vasemmalle puolelle m:llä ja halutun yhdistelmän numerolla N:

Tämän yhtälön ratkaisu tarjoaa seuraavan "ahneen" algoritmin, jonka iteraatioissa valitaan peräkkäin halutun yhdistelmän vektorin elementtien arvot. Alkuiteroinnissa valitaan pienin mahdollinen (rajoitustensa puitteissa) arvo C 1, jossa oikean puolen ensimmäisellä termillä on maksimiarvo, joka ei ylitä L:tä:

Nyt L:n vasenta puolta tulee pienentää ensimmäisellä yhdistelmällä oikealla puolella valitulla arvolla C 1 ja C 2:n arvo määritetään samalla tavalla toisessa iteraatiossa:

Samoin kaikki myöhemmät iteraatiot tulisi suorittaa halutun yhdistelmän kaikkien muiden elementtien C i arvojen valitsemiseksi viimeiseen elementtiin C m asti:

Ilmeisistä syistä viimeisen elementin C m arvo voidaan määrittää perustuen sen yhdistelmien määrän yhtäläisyyteen L:n vasemman puolen jäännösarvon kanssa:

On huomattava, että yhdistelmän C m viimeisen elementin arvo voidaan löytää vielä yksinkertaisemmin, ilman sen mahdollisten arvojen luettelemista:

Tarkastelun algoritmin iteraatioiden toteutusta havainnollistaa seuraava esimerkki, jossa on tarpeen määrittää yhdistelmät numerolla N=8 leksigrafisessa järjestyksessä, jos n=6 ja m=4:

Algoritmista kykyä määrittää yhdistelmä tietyllä numerolla leksigrafisessa järjestyksessä voidaan käyttää useisiin suuntiin. Erityisesti kun luetellaan yhdistelmiä leksigrafisessa järjestyksessä, on palautettava mihin tahansa aikaisemmin saatuun yhdistelmään, riittää, että tietää vain sen numeron. Lisäksi on mahdollista luoda yhdistelmiä missä tahansa järjestyksessä, joka säätelee mielivaltaisesti annettua niiden leksigrafisten numeroiden sarjaa.

Nyt esittelemme algoritmin yhdistelmien luomiseksi leksikografisessa järjestyksessä:

2 i:= 1 - k tekee A[i] := i;

5 aloita kirjoitus(A, …, A[k]);

6 jos A[k] = n niin p:= p 1 muuten p:= k;

8 i:= k alas p do A[i] := A[p] + i p + 1

YHDISTELMÄT ELEMENTIEN TOISTOJEN KANSSA

Päinvastoin kuin klassisessa yhdistelmässä, jossa kaikki elementit ovat erilaisia, yhdistelmä toistojen kanssa muodostaa rajallisen joukon elementtien järjestämättömän valikoiman, jossa mikä tahansa elementti voi esiintyä rajattoman usein eikä välttämättä ole yhdessä kopiossa. Samanaikaisesti elementtien toistojen määrää rajoittaa yleensä vain yhdistelmän pituus, ja yhdistelmiä, jotka eroavat ainakin yhdellä elementillä, pidetään erilaisina. Esimerkiksi valitsemalla 4 valinnaisesti erilaista numeroa joukosta 1, 2 ja 3, voit tehdä seuraavat 15 yhdistelmää toistoilla:

1111 1112 1113 1122 1123 1133 1222 1223 1233 1333 2222 2223 2233 2333 3333.

Yleisessä tapauksessa yhdistelmät toistojen kanssa voidaan muodostaa valitsemalla n mielivaltaisen tyyppistä elementtiä. Ne voidaan kuitenkin aina liittää peräkkäisiin luonnollisiin lukuihin 1:stä n:ään. Sitten mikä tahansa m valinnaisesti erilaisen luvun yhdistelmä tällä alueella voidaan kirjoittaa vektorimuotoon järjestämällä ne ei-laskevaan järjestykseen vasemmalta oikealle:

Luonnollisesti tällä kirjoitusmuodolla kaikki viereiset elementit voivat olla samanarvoisia rajoittamattomien toistojen mahdollisuuden vuoksi. Jokainen yhdistelmävektori, jossa on n elementtiä toistoa m:llä, voidaan kuitenkin yhdistää (n + m − 1) elementin yhdistelmävektoriin m:llä, joka rakennetaan seuraavasti:

On selvää, että millä tahansa vektorin f elementtien arvoilla vektorin C elementit ovat taatusti erilaisia ​​ja tiukasti järjestettyjä arvojensa nousevassa järjestyksessä välillä 1 - (n+m1) :

Yhdistelmävektoreiden f ja C elementtien välinen yksi-yhteen vastaavuus antaa meille mahdollisuuden ehdottaa seuraavaa yksinkertaista menetelmää yhdistelmien systemaattiseen laskemiseen, joissa n elementtiä toistetaan yli m. On tarpeen vain luetella esimerkiksi leksigrafisessa järjestyksessä kaikki (n + m1) elementtien C-yhdistelmät m:llä muuntamalla kunkin elementin elementit peräkkäin vastaaviksi yhdistelmien elementeiksi, joissa on toistoja f seuraavan kaavan mukaan:

Tämän seurauksena muodostuu yhdistelmävektoreiden sarja elementtien toistoilla, jotka on järjestetty vastaavien yhdistelmien luettelemalla generoituun järjestykseen ilman elementtien toistoja. Erityisesti edellä mainitun 3 numeron 1, 2 ja 3 yhdistelmän 4 numeron toistojen sarjan saamiseksi on lueteltava leksigrafisessa järjestyksessä kaikki yhdistelmät ilman 6 numeron toistoja 1,2,3,4, 5 ja 6 x 4 numeroa muuttamalla ne määritetyllä tavalla. Seuraava esimerkki esittää sellaisen yhdistelmän (1,3,4,6) muunnoksen leksigrafisella numerolla 8:

Harkittu yksi-yhteen vastaavuus yhdistelmien välillä, joissa on toistoja ja ilman toistoja elementtejä, tarkoittaa, että niiden joukot ovat ekvivalentteja. Siksi yleisessä tapauksessa n elementin toistoa sisältävien yhdistelmien lukumäärä yli m:n on yhtä suuri kuin yhdistelmät ilman toistoja (n + m1) elementistä yli m. Käyttämällä samaa symboliikkaa merkitsemään f:n toistoja ja ilman C:n toistoja olevien yhdistelmien lukumäärää, tämä yhtälö voidaan kirjoittaa seuraavasti:

On helppo tarkistaa, että yllä olevassa esimerkissä, jossa n=3 ja m=4, toistoa sisältävien yhdistelmien lukumäärä on 15, mikä vastaa niiden suoran laskennan tulosta:

On huomattava, että toisin kuin klassisessa versiossa, yhdistelmäparametrien arvot toistoilla n ja m eivät liity suoraan toisiinsa, joten f(n,m)>0 mille tahansa niiden positiivisten arvojen yhdistelmälle. Vastaavat rajaehdot määritetään arvojen (n+m1) ja (n1) tai (n+m1) ja m välisestä yhtälöstä:

Pitäisi myös olla aivan ilmeistä, että jos m on yhtä suuri kuin 1, niin elementtien toistuminen ei ole mahdollista ja näin ollen mille tahansa positiiviselle arvolle n>0 seuraava yhtälö pätee:

Lisäksi n:n ja m:n positiivisten arvojen toistoja sisältävien yhdistelmien lukumäärälle pätee seuraava toistuvuussuhde, joka on samanlainen kuin yhdistelmien lukumäärän lisäysidentiteetti ilman elementtien toistoja:

Itse asiassa se muuttuu määritellyksi lisäys-identiteetiksi korvaamalla muodollisesti vastaava määrä yhdistelmiä ilman toistoja sen vasemmassa ja oikeassa osassa:

Tarkasteltavalla toistuvuusrelaatiolla voidaan tehokkaasti määrittää toistoyhdistelmien lukumäärää, kun on tärkeää eliminoida työläs tekijätulojen laskennan operaatiot ja korvata ne yksinkertaisemmilla summausoperaatioilla. Samanaikaisesti f(n,m) arvon laskemiseksi sinun tarvitsee vain soveltaa tätä toistuvuussuhdetta, kunnes saat muotoa f(1,m) ja f(i,1) olevien termien summan, jossa i ottaa arvot välillä n - 1. Määritelmän mukaan tällaiset termit ovat yhtä suuria kuin 1 ja i, vastaavasti. Seuraava esimerkki havainnollistaa tämän muunnostekniikan käyttöä tapauksissa n=3 ja m=4:

Binääriyhdistelmien luettelo

Toteutettaessa yhdistelmiä laitteistossa tai ohjelmoitaessa kokoonpanokielellä on tärkeää pystyä käsittelemään yhdistelmätietueita binäärimuodossa. Tässä tapauksessa mikä tahansa n elementin yhdistelmä m:llä on määritettävä n-bittisen binaariluvun muodossa (B n ,…B j ,…B 1), jossa m yksinumeroinen numero ilmaisee yhdistelmän alkioita, ja jäljellä olevilla (nm) numeroilla on nolla-arvot. On selvää, että tällä kirjoitusmuodolla eri yhdistelmien täytyy poiketa toisistaan ​​yksiköiden järjestelyssä ja n-bittisessä binäärijoukossa on vain C (n, m) tapaa järjestää m ykkösiä tai (nm) nollia. Esimerkiksi seuraavassa taulukossa luetellaan kaikki kuusi tällaista binääriyhdistelmää, jotka tarjoavat 4-bittiset binääriluvut kaikille mielivaltaisen joukon (E 1 , E 2 , E 3 , E 4 ) neljän elementin yhdistelmille kahdella:

Yleisessä tapauksessa tällaisten binääriyhdistelmien numeroinnin tehtävä rajoittuu kaikkien n-bittisten binäärijoukkojen systemaattiseen luetteloimiseen erilaisilla m yksittäisen ja (nm) nollabitin järjestelyillä. Yksinkertaisimmassa muodossa tällainen luettelointi toteutetaan erilaisilla menetelmillä vierekkäisten numeroiden transponoimiseksi siirrolla (transpositiivinen-siirtoalgoritmit). Nämä ovat iteratiivisia algoritmeja, ja niiden nimet kuvastavat kussakin vaiheessa suoritettavien toimintojen luonnetta. Transpositiivisten siirtoalgoritmien iteratiiviset proseduurit muodostavat binääriyhdistelmien sekvenssejä, jotka alkavat binäärijoukolla, jossa kaikki ovat keskittyneet alemmille biteille (oikealla) ja päättyvät, kun kaikki ovat ylemmissä biteissä (vasemmalla):

Nämä sekvenssit ovat yhteneväisiä alku- ja loppuyhdistelmissä, ja ne eroavat binäärivälijoukkojen luettelointijärjestyksessä. Kuitenkin kaikissa tapauksissa jokainen seuraava binääriyhdistelmä muodostetaan edellisen mukaisesti vastaavien transponointi- ja siirtotoimintojen suorittamisen seurauksena. Samanaikaisesti erilaiset transpositiivisen siirto-algoritmit eroavat tavassa valita numeropari transponointia varten ja numeroryhmä siirtoa varten. Tätä spesifisyyttä tarkastellaan alla transponointialgoritmeille, joissa on vasemmalle ja oikealle siirtyminen.

Transponointialgoritmissa, jossa jokaisessa vaiheessa siirretään vasemmalle, seuraava binääriyhdistelmä saadaan nykyisestä yhdistelmästä korvaamalla vasemmanpuoleisin bittipari 01 luvulla 10 (transponointi) ja siirtämällä johtavien yksikköbittien ryhmä, jos sellainen on, lähelle pari 10 saatu transponoinnin (siirron) jälkeen. Jos tässä tapauksessa nykyisessä binääriyhdistelmässä ei ole yhtään korkeimmassa bitissä, siirtoa ei suoriteta, vaikka johtava yksikkö saadaan transponoinnin jälkeen tässä vaiheessa. Siirtoa ei myöskään suoriteta, kun korkean kertaluvun biteissä ei ole nollia ennen transponoinnin jälkeen saatua 10s paria. Tarkasteltuja toimia havainnollistetaan seuraavalla esimerkillä tämän algoritmin kahden peräkkäisen iteroinnin suorittamisesta, jossa yhdessä iteraatiossa (15) suoritetaan vain transponointi (T") ja toisessa iteraatiossa (16) transponointia täydennetään siirrolla. (T"+S"):

Oikean siirron transponointialgoritmissa käsitteellisesti samanlaiset toiminnot suoritetaan jokaisessa vaiheessa. Vain transponointi varmistaa, että oikeanpuoleiset numerot 01 korvataan 10:llä (vasemmanpuoleisimpien sijasta), ja sitten kaikki sen oikealla olevat yksiköt siirtyvät alemmille numeroille. Kuten ennenkin, siirto suoritetaan vain, jos on yksiköitä, jotka voidaan siirtää oikealle. Tarkasteltuja toimia havainnollistetaan seuraavalla esimerkillä tämän algoritmin kahden peräkkäisen iteroinnin suorittamisesta, jossa yhdessä iteraatiossa (3) suoritetaan vain transponointi (T") ja toisessa iteraatiossa (4) transponointia täydennetään vaihto (T"+S"):

On huomattava, että molempien algoritmien iteraatiot voidaan kirjoittaa additiiviseen muotoon, jos binääriyhdistelmät tulkitaan kokonaislukuina 2-kantaisessa lukujärjestelmässä. Erityisesti transponointialgoritmissa, jossa on siirto oikealle, jokainen seuraava binääriyhdistelmä (B" n) ,…B" j , …B" 1) voidaan aina saada nykyisestä yhdistelmästä (B n ,…B j ,…B 1) suorittamalla kokonaislukujen summausoperaatioita seuraavalla summauskaavalla:

Tässä additiivisessa kaavassa kakkojen f ja t eksponentit osoittavat vastaavasti nykyisen binääriyhdistelmän nollien lukumäärää ja niiden vasemmalla puolella olevan rivin ykkösten määrää. Esimerkiksi n=6 bitin 4. binääriyhdistelmälle (001110), f =1 ja t =3. Siksi seuraavan binääriyhdistelmän laskeminen additiivinen kaavalla iteraatiossa 5 antaa seuraavan tuloksen, joka vastaa transponointi- ja siirtotoimintojen suorittamista:

Tarkasteltavien transponointialgoritmien vertailevaa analyysiä varten vasemmalle ja oikealle siirtymällä on suositeltavaa verrata binääriyhdistelmien sekvenssejä, joita ne generoivat iteraatioissaan. Seuraavassa taulukossa on kaksi tällaista binääriyhdistelmien sarjaa, joissa on 4 elementtiä kahdella ja jotka saadaan vasemmalle (TSL) ja oikealle (TSR) siirtoalgoritmeilla, vastaavasti:

Vertaamalla näitä kahta sekvenssiä voit nähdä, että ne ovat käänteispeili. Tämä tarkoittaa, että mitkä tahansa kaksi binaariyhdistelmää, jotka sijaitsevat niissä samalla etäisyydellä sekvenssiensä vastakkaisista päistä, ovat toistensa peilikuva, eli ne ovat yhteneväisiä vaihdettaessa bittien käänteiseen indeksointiin missä tahansa niistä. Esimerkiksi toinen binäärikuvio TSL-sekvenssin alusta (0101) on peilikuva binäärikuviosta (1010), joka on toinen TSR-sekvenssin lopusta. Yleisessä tapauksessa mikä tahansa binääriyhdistelmä, jossa on yhden sekvenssin numero i, on peilikuva binääriyhdistelmästä, jossa on toisen sekvenssin numero (ni + 1). Tällainen näiden sekvenssien suhde on seurausta transponointi- ja siirtooperaatioiden symmetrisyydestä kahdessa tarkastelussa binääriyhdistelmien luettelointialgoritmissa.

On huomattava, että binäärimuotoa voidaan käyttää myös elementtien toistoyhdistelmien kirjoittamiseen. Tätä varten sinun on luotava yksi yhteen vastaavuus toistoyhdistelmien ja binääriyhdistelmien välille, jotka on rakennettu seuraavasti. Olkoon mielivaltainen yhdistelmä toistoineen, joka saadaan valitsemalla m valinnaisesti eri elementtiä generointijoukon n alkiosta. Halutun vastaavuuden määrittämiseksi sinun on ensin liitettävä yhdistelmään kaikki generointijoukon (kissa) elementit ja sitten lajiteltava tuloksena oleva ketjutus (lajittelu) niin, että kaikki identtiset elementit ovat lähellä. Tuloksena on (n+m) elementtien sarja, jossa n ryhmää identtisiä elementtejä. Elementtien välillä on vain (n+m1) rakoa, joista identtisten elementtien ryhmien välillä on (n1) rakoa ja ryhmien sisällä olevien elementtien välillä m rakoa. Selvyyden vuoksi voit sijoittaa merkit "|" määritetyille aikaväleille. ja vastaavasti. Jos nyt kartoitetaan 1 ryhmien välisiin aukkoihin (|) ja 0 kaikkiin muihin aukkoihin (), niin saadaan binääriyhdistelmä. Se muodostuu (n+m1) numeroiden binäärijoukosta, jossa (n1) on ykkösiä ja m nollanumeroa, joiden sijainti vastaa yksiselitteisesti alkuperäistä yhdistelmää, jossa on toistoja alkioista n - m. Tarkasteltua muunnostekniikkaa havainnollistaa seuraava esimerkki binääriyhdistelmän (1001101) muodostamisesta yhdistämällä toistoja (BBD), jonka elementit valitaan viiden ensimmäisen latinalaisen kirjaimen generaattorijoukosta:

Yleensä tällaisten binäärijoukkojen lukumäärä määrää, kuinka monta tapaa järjestää (n1) ykkösiä (tai m nollaa) (n+m1) binäärinumeroihin. Tämä arvo on luonnollisesti yhtä suuri kuin yhdistelmien lukumäärä (n+m1) yli (n1) tai yli m, eli C(n+m1,n1) tai C(n+m1,m), mikä on yhtä suuri kuin n elementin toistojen f(n,m) lukumäärä m:llä. Siten, koska toistoja ja binääriyhdistelmiä sisältävien yhdistelmien välillä on yksi yhteen vastaavuus, on oikeutettua pelkistää toistoja sisältävien yhdistelmien luettelo binääriyhdistelmien luetteloon, esimerkiksi käyttämällä transponointialgoritmeja, joissa on siirto vasemmalle tai oikealle. Sen jälkeen sinun tarvitsee vain palauttaa halutut yhdistelmät toistoilla saaduista binääriyhdistelmistä. Tämä voidaan aina tehdä käyttämällä seuraavaa palautustekniikkaa.

Olkoon pääjoukko, jonka alkioista muodostetaan yhdistelmiä m valinnaisesti eri elementin toistolla, järjestettävä mielivaltaisesti niin, että jokaisella sen alkiolla on tietty sarjanumero 1 - n. Toteutetaan myös (n+m1) binäärinumeroiden binääriyhdistelmien laskeminen, missä (n1) on yksi ja m nollanumeroa. Jokaista tuloksena olevaa binääriyhdistelmää voidaan täydentää vasemmalla fiktiivisellä yksikkönumerolla ja kaikki yksikkönumerot voidaan numeroida vasemmalta oikealle kokonaisluvuilla 1 - n. Tällöin binääriyhdistelmän jokaisen i:nnen yksikön jälkeen rivissä olevien nollien lukumäärä on yhtä suuri kuin pääjoukon i:nnen elementin esiintymien lukumäärä vastaavassa yhdistelmässä toistoineen. Tarkasteltua tekniikkaa havainnollistaa seuraava esimerkki, jossa binääriyhdistelmä (1001101) palauttaa yhdistelmän BBD-toistoilla, joiden elementit valitaan viiden ensimmäisen aakkosjärjestyksessä kirjoitetun latinalaisen kirjaimen generaattorijoukosta ja yliviivaus osoittaa elementit, jotka puuttuvat tästä yhdistelmästä:

Suorittamalla samanlaisia ​​toimia tämän esimerkin olosuhteissa voit luetella kaikki 35 binääriyhdistelmää, jotka muodostavat 7-bittiset binäärijoukot, joissa 4 ykköstä ja 3 nollaa, ja palauttaa vastaavat yhdistelmät 5 elementin toistolla kolmella.

Joskus valitsemme monista tilauksesta riippumatta. Tällaista valintaa kutsutaan yhdistelmä . Jos pelaat esimerkiksi korttia, tiedät, että useimmissa tilanteissa järjestyksellä, jossa pidät korttia, ei ole väliä.

Esimerkki 1 Etsi kaikki kolmen kirjaimen yhdistelmät, jotka on otettu 5 kirjaimen joukosta (A, B, C, D, E).

Ratkaisu Nämä yhdistelmät ovat:
(A, B, C), (A, B, D),
(A, B, E), (A, C, D),
(A, C, E), (A, D, E),
(B, C, D), (B, C, E),
(B, D, E), (C, D, E).
On 10 kolmen kirjaimen yhdistelmää, jotka valitaan viidestä kirjaimesta.

Kun löydämme kaikki yhdistelmät joukosta, jossa on 5 objektia, jos otamme 3 objektia kerralla, löydämme kaikki 3-elementtiset osajoukot. Tässä tapauksessa objektien järjestystä ei oteta huomioon. Sitten,
(A, C, B) kutsutaan samaksi joukoksi kuin (A, B, C).

Osajoukko
Joukko A on B:n osajoukko ja tarkoittaa, että A on osajoukko ja/tai sama kuin B, jos jokainen A:n alkio on B:n alkio.

Osajoukon elementtejä ei ole järjestetty. Kun yhdistelmiä harkitaan, järjestystä ei oteta huomioon!

Yhdistelmä
Yhdistelmä, k objektia sisältävä osajoukko, joka koostuu k objektista.

Haluamme kirjoittaa kaavan n kohteen yhdistelmien lukumäärän laskemiseksi, jos k objektia otetaan samanaikaisesti.

Yhdistelmämerkintä
Samanaikaisesti otettujen n kohteen yhdistelmien lukumäärä merkitään n C k :llä.

Kutsumme n C k yhdistelmien määrä . Haluamme kirjoittaa yleisen kaavan n C k:lle mille tahansa k ≤ n:lle. Ensinnäkin on totta, että n C n = 1, koska joukolla, jossa on n alkiota, on vain yksi osajoukko, jossa on n alkiota, on itse joukko. Toiseksi n C 1 = n, koska joukossa, jossa on n alkiota, on vain n osajoukkoa, joissa kussakin on 1 alkio. Lopuksi n C 0 = 1, koska joukossa, jossa on n alkiota, on vain yksi osajoukko, jossa on 0 alkiota, eli tyhjä joukko ∅. Muiden yhdistelmien tarkastelussa palataan esimerkkiin 1 ja verrataan yhdistelmien määrää permutaatioiden määrään.

Huomaa, että jokaisella 3 elementin yhdistelmällä on 6 tai 3 permutaatiota.
3! . 5 C 3 \u003d 60 \u003d 5 P 3 \u003d 5. neljä . 3,
niin
.
Yleensä k elementin yhdistelmien lukumäärän, jotka on valittu n objektista, n C k kertaa näiden elementtien permutaatiot k!, on oltava yhtä suuri kuin n elementin permutaatioiden lukumäärä k elementin yli:
k!. n C k = n P k
n C k = n P k /k!
n Ck = (1/k!). nP k
n Ck =

K objektin yhdistelmät n objektista
K alkion yhdistelmien kokonaismäärä n:stä objektista on merkitty n Ck:lla, jonka määrittää
(1) n C k = ,
tai
(2) n C k =

Toinen merkintätapa n C k:lle on binomikerroin . Syy tälle terminologialle selviää alla.

Binomiaalinen kerroin

Esimerkki 2 Laske kaavojen (1) ja (2) avulla.

Ratkaisu
a) kohdan (1) mukaan
.
b) kohdan 2 mukaan

Muista, että se ei tarkoita n/k.

Esimerkki 3 Laske ja.

Ratkaisu Käytämme kaavaa (1) ensimmäiselle lausekkeelle ja kaavaa (2) toiselle. Sitten
,
käyttämällä (1) ja
,
käyttämällä kaavaa (2).

ota huomioon, että
,
ja esimerkin 2 tuloksen käyttäminen antaa meille
.
Tämä tarkoittaa, että 7 elementin joukon 5-elementtisen osajoukon lukumäärä on sama kuin 7 elementin joukon 2-alkioisen osajoukon lukumäärä. Kun joukosta valitaan 5 elementtiä, ne eivät sisällä kahta elementtiä. Jos haluat nähdä tämän, harkitse joukkoa (A, B, C, D, E, F, G):


Yleisesti ottaen meillä on seuraavat asiat. Tämä tulos antaa vaihtoehtoisen tavan laskea yhdistelmä.

K-koon ja koon osajoukot
ja nCk = nCn-k
K-kokoisten osajoukkojen määrä joukossa, jossa on n objektia, on sama kuin osajoukkojen määrä, joiden koko on n - k. K objektin yhdistelmien määrä n kohteen joukosta on sama kuin n:n yhdistelmien määrä samaan aikaan otettuja esineitä.

Nyt ratkaisemme ongelmia yhdistelmillä.

Esimerkki 4 Michigan Lotto. Michiganin osavaltiossa kahdesti viikossa järjestettävä WINFALL tarjoaa jättipotin, jonka mukaan vähintään, on 2 miljoonaa Yhdysvaltain dollaria. Yhtä dollaria vastaan ​​pelaaja voi yliviivata 6 numeroa väliltä 1–49. Jos nämä numerot vastaavat lotossa osuvia numeroita, pelaaja voittaa. (

Kombinatoriikka on matematiikan haara, joka tutkii kysymyksiä siitä, kuinka monta erilaista yhdistelmää voidaan tietyin ehdoin tehdä annetuista objekteista. Kombinatoriikan perusteet ovat erittäin tärkeitä satunnaisten tapahtumien todennäköisyyksien arvioinnissa, koska juuri niiden avulla on mahdollista laskea periaatteessa mahdollinen määrä erilaisia ​​tapahtumien kehityksen skenaarioita.

Kombinatoriikan peruskaava

Olkoon alkioryhmiä k, ja i:s ryhmä koostuu n i alkiosta. Valitaan yksi elementti jokaisesta ryhmästä. Tällöin kokonaismäärä N tapoja, joilla tällainen valinta voidaan tehdä, määräytyy suhteella N=n 1 *n 2 *n 3 *...*n k .

Esimerkki 1 Selvitetään tämä sääntö yksinkertaisella esimerkillä. Olkoon kaksi elementtiryhmää, joista ensimmäinen koostuu n 1 elementistä ja toinen - n 2 elementistä. Kuinka monta eri elementtiparia näistä kahdesta ryhmästä voidaan tehdä niin, että pari sisältää yhden elementin jokaisesta ryhmästä? Oletetaan, että otimme ensimmäisen elementin ensimmäisestä ryhmästä ja muuttamatta sitä käymme läpi kaikki mahdolliset parit vaihtamalla vain toisen ryhmän elementit. Tälle elementille on n 2 tällaista paria. Sitten otamme toisen elementin ensimmäisestä ryhmästä ja teemme sille myös kaikki mahdolliset parit. Tällaisia ​​pareja on myös n 2. Koska ensimmäisessä ryhmässä on vain n 1 elementtiä, mahdollisia vaihtoehtoja on n 1 *n 2.

Esimerkki 2 Kuinka monta kolminumeroista parillista lukua voidaan tehdä numeroista 0, 1, 2, 3, 4, 5, 6, jos numerot voidaan toistaa?
Ratkaisu: n 1 \u003d 6 (koska voit ottaa minkä tahansa luvun 1, 2, 3, 4, 5, 6 ensimmäiseksi numeroksi), n 2 \u003d 7 (koska voit ottaa minkä tahansa luvun 0:sta toiseksi numeroksi, 1 , 2, 3, 4, 5, 6), n 3 \u003d 4 (koska voit ottaa minkä tahansa luvun 0, 2, 4, 6 kolmanneksi numeroksi).
Joten N = n 1 * n 2 * n 3 = 6 * 7 * 4 = 168.

Siinä tapauksessa, että kaikki ryhmät koostuvat samasta määrästä elementtejä, ts. n 1 =n 2 =...n k =n voidaan olettaa, että jokainen valinta tehdään samasta ryhmästä ja elementti palaa ryhmään valinnan jälkeen. Tällöin kaikkien valintatapojen lukumäärä on yhtä suuri kuin n k . Tätä kombinatoriikan valintatapaa kutsutaan palauttaa näytteitä.

Esimerkki 3 Kuinka monta nelinumeroista lukua voidaan tehdä luvuista 1, 5, 6, 7, 8?
Ratkaisu. Nelinumeroisen luvun kullekin numerolle on viisi mahdollisuutta, joten N=5*5*5*5=5 4 =625.

Tarkastellaan joukkoa, joka koostuu n elementistä. Tätä joukkoa kombinatoriikassa kutsutaan yleinen väestö.

Sijoittelujen määrä n elementistä m:llä

Määritelmä 1. Majoitus alkaen n elementtejä m kombinatoriikassa kutsutaan mitä tahansa tilattu setti alkaen m erilaisia ​​elementtejä, jotka on valittu yleisestä väestöstä n elementtejä.

Esimerkki 4 Kolmen elementin (1, 2, 3) eri järjestelyt kaksi kerrallaan muodostavat joukot (1, 2), (2, 1), (1, 3), (3, 1), (2, 3), (3) , 2). Sijoittelut voivat poiketa toisistaan ​​sekä elementeissä että järjestyksessä.

Sijoitusten lukumäärä kombinatoriikassa on merkitty A n m:llä ja se lasketaan kaavalla:

Kommentti: n!=1*2*3*...*n (lue: "en factorial"), lisäksi oletetaan, että 0!=1.

Esimerkki 5. Kuinka monta kaksinumeroista lukua on, joissa kymmenluku ja yksikkönumero ovat erilaisia ​​ja parittomia?
Ratkaisu: koska on viisi paritonta numeroa, nimittäin 1, 3, 5, 7, 9, niin tämä ongelma rajoittuu siihen, että valitaan ja asetetaan kaksi viidestä eri numerosta kahteen eri paikkaan, ts. annetut numerot ovat:

Määritelmä 2. Yhdistelmä alkaen n elementtejä m kombinatoriikassa kutsutaan mitä tahansa tilaamaton setti alkaen m erilaisia ​​elementtejä, jotka on valittu yleisestä väestöstä n elementtejä.

Esimerkki 6. Sarjan (1, 2, 3) yhdistelmät ovat (1, 2), (1, 3), (2, 3).

N elementin yhdistelmien lukumäärä m:llä

Yhdistelmien lukumäärä on merkitty C n m:llä ja se lasketaan kaavalla:

Esimerkki 7 Kuinka monella tavalla lukija voi valita kaksi kirjaa kuudesta saatavilla olevasta?

Ratkaisu: Tapamäärä on yhtä suuri kuin kuuden kirjan yhdistelmien lukumäärä kahdella, ts. vastaa:

N elementin permutaatiot

Määritelmä 3. Permutaatio alkaen n elementtejä kutsutaan millä tahansa tilattu setti näitä elementtejä.

Esimerkki 7a. Kolmesta elementistä (1, 2, 3) koostuvan joukon kaikki mahdolliset permutaatiot ovat: (1, 2, 3), (1, 3, 2), (2, 3, 1), (2, 1, 3) , ( 3, 2, 1), (3, 1, 2).

N alkion erilaisten permutaatioiden lukumäärä merkitään P n:llä ja lasketaan kaavalla P n =n!.

Esimerkki 8 Kuinka monella tavalla eri kirjailijoiden seitsemän kirjaa voidaan järjestää hyllylle riviin?

Ratkaisu: Tämä ongelma koskee seitsemän eri kirjan permutaatioiden määrää. P 7 =7!=1*2*3*4*5*6*7=5040 tapaa järjestää kirjat.

Keskustelu. Näemme, että mahdollisten yhdistelmien määrä voidaan laskea eri sääntöjen mukaan (permutaatiot, yhdistelmät, sijoittelut), ja tulos on erilainen, koska laskentaperiaate ja itse kaavat ovat erilaisia. Kun tarkastelet määritelmiä tarkasti, voit nähdä, että tulos riippuu useista tekijöistä samanaikaisesti.

Ensinnäkin, kuinka monesta elementistä voimme yhdistää niiden joukot (kuinka suuri on elementtien yleinen populaatio).

Toiseksi tulos riippuu siitä, minkä kokoisia elementtijoukkoja tarvitsemme.

Lopuksi on tärkeää tietää, onko joukon elementtien järjestyksellä meille merkitystä. Selvitetään viimeinen tekijä seuraavalla esimerkillä.

Esimerkki 9 Vanhempainkokouksessa on 20 henkilöä. Kuinka monta eri vaihtoehtoa vanhempaintoimikunnan kokoonpanolle on olemassa, jos siihen pitäisi kuulua 5 henkilöä?
Ratkaisu: Tässä esimerkissä emme ole kiinnostuneita komitealuettelon nimien järjestyksestä. Jos sen seurauksena samat ihmiset esiintyvät sen koostumuksessa, niin merkityksen kannalta tämä on meille sama vaihtoehto. Siksi voimme käyttää kaavaa luvun laskemiseen yhdistelmiä 20 elementistä, 5.

Asiat ovat toisin, jos jokainen komitean jäsen on aluksi vastuussa tietystä työalueesta. Sitten samalla komitean palkkalistalla 5 on mahdollista sen sisällä! vaihtoehtoja permutaatioita tuo asia. Erilaisten (sekä kokoonpanon että vastuualueen) vaihtoehtojen lukumäärä määräytyy tässä tapauksessa numeron mukaan sijoittelut 20 elementistä, 5.

Tehtävät itsetestaukseen
1. Kuinka monta kolminumeroista parillista lukua voidaan tehdä luvuista 0, 1, 2, 3, 4, 5, 6, jos luvut voidaan toistaa?

2. Kuinka monta viisinumeroista numeroa on, jotka luetaan samalla tavalla vasemmalta oikealle ja oikealta vasemmalle?

3. Luokassa on kymmenen ainetta ja viisi oppituntia päivässä. Kuinka monella tavalla voit tehdä aikataulun yhdelle päivälle?

4. Kuinka monella tavalla konferenssiin voidaan valita 4 delegaattia, jos ryhmässä on 20 henkilöä?

5. Kuinka monella tavalla kahdeksan erilaista kirjainta voidaan laittaa kahdeksaan eri kirjekuoreen, jos jokaiseen kirjekuoreen laitetaan vain yksi kirje?

6. Kolmesta matemaatikosta ja kymmenestä taloustieteilijästä on tarpeen tehdä komissio, joka koostuu kahdesta matemaatikosta ja kuudesta ekonomistista. Kuinka monella tavalla tämä voidaan tehdä?