1. Yhden päivän aikataulu sisältää 5 oppituntia. Määritä tällaisten aikataulujen määrä, kun valitset yhdestätoista tieteenalasta.
2. Toimikuntaan kuuluu puheenjohtaja, hänen varajäsenensä ja viisi muuta henkilöä. Kuinka monella tavalla toimikunnan jäsenet voivat jakaa tehtäviä keskenään?
3. Kuinka monella tavalla 20 hengen ryhmästä voidaan valita kolme hoitajaa?
4. Kuinka monta eri ääniyhdistelmää voidaan ottaa kymmenellä valitulla pianon koskettimella, jos jokainen ääniyhdistelmä voi sisältää kolmesta kymmeneen ääntä.
5. Maljakossa on 10 punaista ja 5 vaaleanpunaista neilikkaa. Kuinka monella tavalla maljakosta voidaan valita viisi samanväristä neilikkaa?
6. Raitiovaunureittien numerot ilmaistaan joskus kahdella värillisellä valolla. Kuinka monta eri reittiä voidaan merkitä kahdeksan värin lyhdyillä.
7. 15 hengen ryhmästä valitaan neljä osallistujaa viestikilpailuun 800 + 400 + 200 + 100. Kuinka monella tavalla urheilijat voidaan sijoittaa viestien vaiheisiin.
8. Viiden hengen joukkue kilpailee uintikilpailussa 20 muun urheilijan kanssa. Kuinka monella tavalla tämän tiimin jäsenten paikat voidaan jakaa.
9. 12 hengen ryhmästä valitaan kaksi hoitajaa päivittäin 6 päivän ajan. Selvitä eri päivystysluetteloiden lukumäärä, jos jokainen on päivystävä kerran.
Kysymyksiä keskusteluun foorumilla
1. Kombinatoriikan tehtävien ratkaiseminen.
Luettelo lisäkirjallisuudesta:
1. Gorbatov V.A. Diskreetin matematiikan perusteet. M.: Korkeakoulu, 2000. - 544 s.
2. V. A. Kofman, Johdatus soveltavaan kombinatoriikkaan. M.: Radio ja viestintä, 1982. 431s.
Seminaari nro 7. Graafiteoria
Työpajan tarkoitus:
Pohdi kysymyksiä, jotka liittyvät graafiteorian käytännön soveltamiseen päätöksenteossa.
Tuntisuunnitelma:
Semina on omistettu graafiteorialle. Ensimmäinen aihe on peruskäsitteet ja kaavioiden toiminnot, sitten aihe on omistettu reiteille ja puille. Työpaja kestää 2 tuntia.
Tehtävä 1. Kuva 7.1 esittää kaavioita, joissa kussakin on neljä kärkeä. Vertaa kaavioita.
Riisi. 7.1. Laskut -
Päätös.
Kaavioiden vertailun tulokset ovat seuraavat:
suuntautumaton;
Suuntautunut;
Täydellinen ja = ;
Se ei ole täydellinen, koska vaikka jokainen kärkipari on yhdistetty reunalla, siinä on silmukka. Joskus täydellinen graafi on graafi, jossa on silmukoita kaikissa pisteissä, joiden jokainen pari on yhdistetty reunalla. Kaavio ei täytä tätä määritelmää.
Tämän graafin kaikki kärjet ovat eristettyjä (graafi, jossa on tyhjä joukko reunoja, eli 0);
Ja ne täydentävät toisiaan: = ja = ;
Multigrafi, koska se sisältää useita reunoja a ja b, yhtä hyvin kuin e ja f;
Suunnattu, vastaa kanonisesti suuntaamatonta graafia;
Ja ei ole yhtä suuri, koska niillä on eri reunat (4,1) - ja (1,4) in ;
Ohjattu monigrafiikka: reunat a ja b ovat kerrannaisia, vaikka se ei ole monigraafi, koska sen reunat a ja b eri tavalla suuntautunut.
Tehtävä 2. Mitkä ovat kuvan 7.2 graafien kärkien asteet?
Riisi. 7.2. Laskee ja
Päätös.
Molemmilla kaavioilla on neljä kärkeä: . Suuntaamattoman graafin kärkien asteet: , , , , jos otetaan huomioon silmukan osuus kärjen asteessa. Graafin kaikkien kärkien asteiden summa on 14, ts. kaksi kertaa kaavion reunojen määrä:
Missä m=7 on graafin reunojen lukumäärä.
Suunnatun graafin kärkien asteet:
Ensimmäisen ja toisen tyyppisen graafin kärkien asteiden summat ovat samat ja ovat yhtä suuria kuin luku m kaavion reunat: .
Tehtävä 3. Kuvassa 7.3 näyttää verkkokaavion (verkkomallin) tietyn ohjelman operaatioiden (töiden) suorittamiseksi. Siinä nuolet osoittavat operaatioita, kärkipisteitä - tapahtumia, jotka kuvaavat joidenkin töiden loppua ja toisten alkua. Nuolien suunta kuvastaa näiden tapahtumien järjestystä. Määritä verkkokaavio eri tavoilla.
Riisi. 7.3. verkkokaavio
Päätös.
Kuvattu verkkomalli on suunnattu graafi, joka voidaan määritellä täysin eri tavoin:
1) graafisesti (katso kuva yllä);
2) määrittämällä kaksi joukkoa: ja ;
3) ilmaantuvuusmatriisi (taulukko 7.1). Verkkomallin ominaisuus on, että nuolet poistuvat alkuperäisestä tapahtumasta 1 ja siirtyvät vain viimeiseen tapahtumaan 6. Siksi esiintymämatriisin ensimmäisellä rivillä on yksiköitä vain miinusmerkillä ja viimeisellä rivillä vain plusmerkillä;
Taulukko 7.1. Ilmaantuvuusmatriisi
4) vierekkäisyysmatriisi (taulukko 7.2). Kohdassa 3 mainitusta syystä vierekkäisyysmatriisin viimeiselle riville sijoitetaan vain nollia;
Taulukko 7.2. Vierekkäisyysmatriisi
5) reunalista määrittelee verkkograafin ilmeisellä tavalla, koska graafin reunat on merkitty niiden päätypisteillä. Tässä tapauksessa "reunat" -sarakkeessa ilmoitettujen kärkien numerot toistetaan luettelon "vertices" -sarakkeessa ja järjestyksessä, jossa nuolet - reunat on merkitty tässä tapauksessa.
Tehtävä 4. Tee kaaviot kuvasta. 7.4 alla ovat Hamiltonin syklit, ketjut.
Riisi. 7.4 Laskee ja
Päätös.
Graafissa on Hamiltonin sykli yksinkertaisena syklinä, joka kulkee graafin kaikkien kärkien läpi - se kulkee reunoja pitkin ( a, b, c, d, e, f, g, q, n, m, l, h, a). B:ssä on myös Hamiltonin ketju, jolle riittää poistamaan kaikki reunat Hamiltonin syklistä.
Graafissa ei ole Hamiltonin sykliä: kulkea kärkien läpi a, b, c graafin ulomman kolmion tulee sisältää kaikki näillä sivuilla olevat reunat, mutta silloin se ei kulje kolmion keskellä sijaitsevan kärjen läpi d. Graafissa on kuitenkin olemassa esim. Hamiltonin ketju, jonka alku on kärjessä a, loppu d ja kärkipisteitä yhdistävien reunojen sarja a, f, b, g, c, e, d.
Tehtävä 5. Lyhimmän polun ongelma. Mikä on lyhin tapa päästä graafin pisteestä toiseen. Tuotannonhallinnan kannalta: kuinka päästä pisteestä A pisteeseen B lyhyimmällä tiellä (ja siten vähimmällä polttoaineen- ja ajankulutuksella) alkupisteestä loppupisteeseen. Harkitse kuvassa olevaa kaaviota. 7.5
Riisi. 7.5 Kaavio
Tilannetta voidaan kuvata paitsi suunnatulla kuvaajalla, jossa kaarille on määritetty painot, myös taulukon avulla (katso alla oleva taulukko). Tässä taulukossa kaksi kärkeä - polun alku ja polun loppu - liittyvät matka-aikaan. Taulukossa. 7.3 ottaa huomioon polut ilman välipysähdyksiä. Monimutkaisemmat reitit koostuvat taulukossa luetelluista perusosista.
Taulukko 7.3. Alkutiedot lyhimmän polun ongelmasta.
Tehtävässä kysytään: kuinka päästä kärjestä 1 kärkeen 4 lyhyimmällä tavalla.
Päätös. Esitellään merkintä: Kanssa(T) - lyhimmän polun pituus kärjestä 1 kärkeen T. (Koska mikä tahansa tarkasteltava polku koostuu kaarista ja kaaria on äärellinen määrä ja jokainen saapuu korkeintaan kerran, lyhimmän polun ehdokkaita on äärettömän monta, ja äärellisen määrän elementtejä on aina saavutettu. ) Tarkasteltavana oleva ongelma on laskea Kanssa(4) ja osoitus polusta, jolla tämä minimi saavutetaan.
Kuvassa esitetyille alustaville tiedoille. yläpuolella ja taulukossa. yllä vain yksi nuoli tulee kärkeen 3, juuri kärjestä 1, ja tämän nuolen lähellä on sen pituus yhtä suuri kuin 1, joten Kanssa(3) = 1. Lisäksi on selvää, että Kanssa(1) = 0.
Pääset kärkeen 4 joko kärjestä 2 kulkiessaan polun, joka on yhtä suuri kuin 4, tai kärjestä 5 kulkiessaan polun, joka on yhtä suuri kuin 5. Siksi relaatio
Kanssa(4) = min(С(2) + 4; Kanssa(5) + 5}.
Siten ongelman uudelleenjärjestely (yksinkertaistaminen) on suoritettu - löydös С(4) on pelkistetty havaintoon С(2) ja Kanssa(5).
Pääset kärkeen 5 joko kärjestä 3 kulkiessaan polun, joka on yhtä suuri kuin 2, tai kärjestä 6 kulkiessaan polun, joka on yhtä suuri kuin 3. Siksi relaatio
Kanssa(5) = min ( Kanssa(3) + 2; Kanssa(6) + 3}.
Tiedämme sen Kanssa(3) = 1. Siksi
Kanssa(5) = min(3; Kanssa(6) + 3}.
Koska se on selvää Kanssa(6) on positiivinen luku, niin viimeisestä suhteesta seuraa, että Kanssa(5) = 3.
Huipulle 2 pääsee joko pisteestä 1 kulkiessaan polun, joka on yhtä suuri kuin 7, tai kärjestä 3 kulkiessaan polun, joka on yhtä suuri kuin 5, tai kärjestä 5 kulkiessaan polun, joka on yhtä suuri kuin 2. Siksi relaatio
Kanssa(2) = min (С(1) + 7; С(3) + 5; Kanssa(5) + 2}.
Tiedämme sen Kanssa(1) = 0, Kanssa(3) = 1, Kanssa(5) = 3. Siksi
Kanssa(2) = min(0 + 7; 1 + 5; 3 + 2) = 5.
Nyt voimme löytää Kanssa(4):
Kanssa(4) = min ( Kanssa(2) + 4; Kanssa(5) + 5) = min(5 + 4; 3 + 5) = 8.
Näin ollen lyhimmän polun pituus on 8. Viimeisestä suhteesta käy selvästi ilmi, että on mentävä kärkeen 4 kärjen 5 kautta. Palatakseni laskelmaan Kanssa(5), näemme, että meidän täytyy mennä kärkeen 5 kärjen 3 kautta. Ja kärkeen 3 pääsee vain kärjestä 1. Lyhin polku on siis seuraava:
1 → 3 → 5 → 4 .
Tehtävä 6. Maksimivirtauksen ongelma Miten (eli millä reiteillä) lähetetään suurin mahdollinen määrä tavaraa lähtöpisteestä loppupisteeseen, jos pisteiden välisten reittien kapasiteetti on rajoitettu.
Tämän ongelman ratkaisemiseksi jokainen siirtojärjestelmää vastaavan suunnatun graafin kaari on liitettävä numeroon - tämän kaaren kapasiteettiin. Harkitse kuvaajaa kuvassa. 7.6.
Riisi. 7.6. Kaavio
Alkutiedot kuljetusjärjestelmästä, esimerkiksi laitoksen sisällä, kuvassa 1. 7.6., Voit myös asettaa taulukon taulukossa 7.4.
Taulukko 7.4. Alkutiedot lyhimmän polun ongelmasta.
Päätös.
Maksimivirtausongelman ratkaisu voidaan saada seuraavista näkökohdista.
Ilmeisesti kuljetusjärjestelmän maksimikapasiteetti ei ylitä 6, koska lähtöpisteestä 0 voidaan lähettää enintään 6 yksikköä rahtia, eli 2 yksikköä kohtaan 1, 3 yksikköä kohtaan 2 ja 1 yksikköä kohtaan 3 .
Seuraavaksi on varmistettava, että kaikki 6 pisteestä 0 lähtevää rahtiyksikköä saavuttavat lopullisen pisteen 4. On selvää, että 2 yksikköä rahtia, jotka saapuivat kohtaan 1, voidaan lähettää suoraan kohtaan 4. Kohteeseen 2 saapuneet tavarat jaettava: 2 yksikköä lähetetään välittömästi kohtaan 4 ja 1 yksikkö - välipisteeseen 3 (pisteiden 2 ja 4 välisen osan rajallisen kapasiteetin vuoksi). Seuraavat lastit toimitettiin kohtaan 3: 1 yksikkö pisteestä 0 ja 1 yksikkö pisteestä 2. Lähetämme ne kohtaan 4.
Joten tarkasteltavana olevan kuljetusjärjestelmän enimmäiskapasiteetti on 6 yksikköä rahtia. Samanaikaisesti ei käytetä sisäosia (haaroja) kohtien 1 ja 2 välillä sekä pisteiden 1 ja 3 välillä. Kohtien 1 ja 4 välinen haara ei ole täysin lastattu - sen mukana lähetetään 2 yksikköä lastia teho 3 yksikköä.
Ratkaisu voidaan esittää taulukon muodossa. 7.5
Taulukko 7.5. Maksimivirtausongelman ratkaiseminen
Omnibus N 9-10 2007.
Reittivalojen merisielu.
Salaperäinen asia on perinne. Aluksi he tarkkailevat sitä huolellisesti, yrittäen kestää kaikki vivahteet, saattaa sen taikauskoksi, sitten he yhtäkkiä huomaavat, että se ei täytä sille asetettuja odotuksia, ei täytä logiikkaa, sillä ei ole tieteellistä perustetta - ja he rikkovat. perinteen kanssa ja huomaa myöhemmin surulla, että hänen kanssaan menetti jotain kaunista ja tarpeellista. . .
Viime aikoina oli perinne antaa raitiovaunureiteille digitaalisen lisäksi myös värimerkintä - reittivalot sytytettiin molemmin puolin reittinumeroa, auton edessä ja takana. Raitioliikenteen kadut erottuivat erityisellä, juhlallisella eleganssilla, kuljettajia, matkustajia, radan työntekijöitä, lähettäjiä ja vaihtajia ohjasivat reittivalot raitiovaunuvirrassa, monet eivät voineet kuvitella raitiovaunua ilman värillisiä valoja. Moskovan reitin valojärjestelmä rakennettiin numeroiden ja värien vastaavuudelle yksi yhteen. "1" on aina punainen, "2" on vihreä, "5" on oliivi, "7" on sininen ja niin edelleen. Mutta Leningradissa valot "puhuivat" eri kielellä, ja heidän lukemisensa "Moskovassa" johti useimmiten hölynpölyyn, koska siellä ei ollut 10 valoa, kuten Moskovassa, vaan vain viisi. Ne erosivat hyvin, ja niiden yhdistelmät näyttivät aina erittäin kauniilta. Viidestä valosta on kuitenkin mahdollista 25 eri yhdistelmää kahdesta, kun taas Pietari-Leningradin reiteistä tuli lopulta noin 70, joten reittien merkit saattoivat toistua. Esimerkiksi kaksi valkoista - 9, 43; punainen ja keltainen - 1, 51, 64; sininen ja punainen - 33, 52, 54; kaksi punaista - 5, 36, 39, 45, 47. Ja vain reitti N 20 oli nimetty samalla tavalla Moskovan ja Pietarin järjestelmien mukaan: vihreä ja valkoinen.
Pietarissa kävi niin, että reittivalot vaihtuivat. Jos kävi niin, että yhden reitin vaihdon jälkeen se toimi riittävän pitkällä osuudella toisella samanvärisellä reitillä, niin jompikumpi näistä reiteistä joutui muuttamaan valojen koostumusta.
Reitti N 4 kulki Dekabristien saarelta Volkovin hautausmaalle ja sitä osoitti kaksi keltaista (oranssia) valoa. Sitten reitti suljettiin ja samalla numerolla se avattiin toiseen paikkaan eri valoilla: sininen + sininen, koska sillä oli yhteinen osuus 35. raitiovaunun kanssa (kaksi keltaista).
Reitillä N 43 oli alun perin valot: punainen + valkoinen. Laajennettaessa satamaan vuonna 1985 valot muuttuivat: valkoinen + valkoinen, kun reitti alkoi jakaa osuuden raitiovaunun N 28 (punainen + valkoinen) kanssa. Reitti 3 oli merkitty vihreällä ja valkoisella. Kun valot kunnostettiin vuonna 2007, yhdistelmä muutettiin keltaiseksi + vihreäksi. Samaan aikaan myös useiden muiden reittien yhdistelmät muuttuivat: 48 (oli: valkoinen + valkoinen, nyt: sininen + sininen); 61 (oli: valkoinen + valkoinen, nyt: valkoinen + keltainen) jne.
Pietarin reittivalojärjestelmä, ulkonäöltään niin yksinkertainen ja monimutkainen, liittyy ennen kaikkea eurooppalaisten raitiovaunukaupunkien perinteeseen. Joten jo vuonna 1907 Novoye Vremya -sanomalehdelle lähetetty kirje sisälsi "Vasilevsky-saaren asukkaiden" pyynnön ottaa käyttöön värilliset valot raitiovaunuissa, "kuten he tekevät ulkomailla, erityisesti Frankfurt am Mainissa". Tällä hetkellä Amsterdamin raitiovaunujen reittiopasteissa on säilynyt aikaisempien järjestelmien jäänteet värillisinä diagonaaleina valaisina. Tämä perinne puolestaan palaa luultavasti navigointivaloihin. Miksi juuri merelle, eikä vaikkapa rautateille? Kyllä, koska reittivalot, kuten merivalot, eivät kiellä mitään, eivät pakota ketään, vaan auttavat vain suuntautumaan pimeässä.
Merenkulun valot on purettu erityisissä merikirjoissa - merien purjehdussuunnissa. Reittivalot on kuvattu myös kaupunkioppaissa. Ensimmäinen näistä oli "Pietarin raitiovaunujen mobiiliopas", jonka julkaisi kustantamo E.I. Marcus (1910).
Pietarin reittivaloissa käytettyjen värien (valkoinen, punainen, oranssi tai keltainen, vihreä, sininen) koostumus eroaa vähän merivalojen väreistä (valkoinen, punainen, oranssi, vihreä, sininen, violetti).
Tarkemmin katsottuna voit löytää muita yhtäläisyyksiä, mutta on paljon tärkeämpää ymmärtää, miksi tällainen ei-tiukka reittivalojärjestelmä on juurtunut järkevään Pietariin, joka vaatii jatkuvaa säätöä. Vastaus on yksinkertainen: Pietari on kuitenkin merenrantakaupunki, ja arkkitehtonisten muotojen ankaruus ja karnevaalin kevytmielisyys ovat yhtä lailla ominaisia, joten myös reitin valojen iloiset värit ovat ominaisia.
Vuonna 2007 perinne sai uuden käänteen. Nyt autot on varustettu LED-valaisimilla reittivaloja varten. Ne loistavat paitsi iltahämärässä, myös päivänvalossa.
Tehtävä numero 3. Taulukko 26 Vaihtoehto Nro Työ
Taulukko 26
c) Metro juna tekee 16 pysäkkiä, joilla kaikki matkustajat jäävät pois. Kuinka monella tavalla 100 matkustajaa junaan päätepysäkillä voidaan jakaa näiden pysäkkien välillä?
KOMBINATORIAN ELEMENTIT.
Summa- ja tuotesäännöt.
Kombinatoriikka (tai yhdisteteoria) on matematiikan haara, joka tutkii kysymyksiä siitä, kuinka monta erilaista yhdistelmiä, jotka täyttävät tietyt ehdot, voidaan tehdä annetuista objekteista.
Siinä tapauksessa, että joukkojen A ja B leikkauspiste ei ole tyhjä, pätee seuraava yhtälö: n(AÈB) = n(A) + n(B) – n(AÇB).
Kolmen joukon liiton alkioiden lukumäärä löytyy kaavasta
n(AÈBÈC) = n(A) + n(B) + n(C) - n(AÇB) -n(AÇC) - n(BÇC) - - n(AÇBÇC)
Esimerkki. Ryhmän 40 opiskelijasta 35 läpäisi matematiikan kokeen ja 37 venäjän kielen kokeen. Kaksi opiskelijaa sai molemmissa aineissa epätyydyttävät arvosanat. Kuinka monella opiskelijalla on akateemista velkaa?
Päätös. Olkoon A joukko opiskelijoita, jotka saivat matematiikassa epätyydyttävän arvosanan, jolloin n(A) = 40 - 35 = 5; ja B on joukko opiskelijoita, jotka saivat epätyydyttävän arvosanan venäjän kielestä, jolloin n(B) = 40 - 37 = 3. Silloin akateemisen velan opiskelijoiden määrä on n(AÈB). Näin ollen n(AÈB) = n(A) + n(B) - n(AÇB) = 5 + 3 - 2 = 6.
Jos AÇB = Æ, niin n(AÈB) = n(A) + n(B)
summa sääntö ja se on muotoiltu seuraavasti: jos elementti x voidaan valita k tavalla ja elementti y m tavalla ja, eikä mikään tapa valita elementti x ole sama kuin mikä tahansa tapa valita elementti y, niin valinta "x tai y" " voidaan tehdä k + m tavalla.
Joukkoja varten meillä on myös n(А´В) = n(А) × n(В)
Kombinatoriikassa tätä sääntöä kutsutaan tuotesääntö ja se on muotoiltu seuraavasti: jos elementti x voidaan valita k tavalla, ja jos jokaisen sellaisen valinnan jälkeen alkio y voidaan valita m tavalla, niin järjestetyn parin valinta m tavalla.
Esimerkki. Kaupungista A kaupunkiin B on 3 tietä ja 2 tietä B:stä C:hen. Kuinka monta tapaa on matkustaa paikasta A paikkaan C B:n kautta?
Päätös. Jos merkitsemme numeroita 1, 2, 3 ja teitä B:stä C:hen - kirjaimia x ja y, niin jokainen vaihtoehto A:sta C:hen on annettu järjestetyllä numero- ja kirjainparilla. Mutta voimme valita numeron kolmella tavalla ja kirjaimen kahdella tavalla, joten tällaisten järjestettyjen parien lukumäärä on 3 × 2 = 6.
Majoitukset.
Olkoon n(A) = m. K-pituista monikkoa (k £ m), jonka komponentit ovat joukon A alkioita ja kaikki komponentit ovat pareittain erillisiä, kutsutaan sijoitus ilman toistoa
Jokaiselle joukolle A, jossa n(A) = m, on merkitty m:n elementin mahdollisten järjestelyjen lukumäärä k:llä.
Ja se lasketaan kaavan mukaan
Esimerkki. Shakkiturnaukseen osallistuu 5 koululaista ja 15 opiskelijaa. Kuinka monella tavalla koululaisten paikat turnauksessa voidaan jakaa, jos tiedetään, että kaksi osallistujaa ei ole saavuttanut yhtä paljon pisteitä?
Päätös. Kaikkiaan turnauksessa on 20 osallistujaa. Näin ollen 20 paikasta koululaiset kuuluvat 5:een. Siksi ongelman ratkaisu liittyy kaikkien mahdollisten pituudeltaan 5 olevien monikoiden muodostamiseen joukon alkioista, joissa on 20 alkiota, eli olemme puhutaan sijoitteluista ilman 20 elementin toistoa 5 elementistä.
Olkoon n(A) = m. Kutsutaan monikkoa, jonka pituus on k, jonka komponentit ovat joukon A elementtejä sijoitus toistoilla m elementistä k elementtiin.
Jokaiselle joukolle A, jossa n(A) = m, mahdollisten järjestelyjen lukumäärä, joissa m elementtiä toistetaan k:lla, merkitään ja lasketaan kaavalla .
Esimerkki. Tarjolla on 5 erilaista tuolia ja 7 rullaa erivärisiä verhoiluja. Kuinka monella tavalla tuolit voidaan verhoilla?
Päätös. Koska tuolit ovat erilaisia, kukin verhoilu on 5 pituinen tuple, joka koostuu tietyn kankaanvärisen sarjan elementeistä ja sisältää 7 elementtiä. Tämä tarkoittaa, että tuolien verhoilutapoja on yhtä monta kuin on sellaisia tupleja, eli sijoitteluja, joissa toistoa on 7 elementtiä 5:llä.
Permutaatiot.
Olkoon n(A) = m. Permutaatio ilman toistoa m elementistä kutsutaan mitä tahansa järjestettyä m-elementtijoukkoa.
M elementin eri permutaatioiden lukumäärä on yhtä suuri kuin peräkkäisten luonnollisten lukujen tulo 1:stä m:ään mukaan lukien, ts.
Esimerkki. Kuinka monta eri viisinumeroista lukua voidaan kirjoittaa käyttämällä numeroita 0, 1, 2, 3, 4, jos yksikään numero ei toistu kahdesti?
Päätös. Kaikkien mahdollisten viiden numeron permutaatioiden lukumäärä on P 5 = 5!. Ja koska numero nolla ei voi olla ensimmäinen paikka, haluttu numero on:
P 5 - P 4 \u003d 5! - 4! = 120 - 24 = 96.
permutaatio toistoilla elementeistä a, b,…,l, jossa nämä alkiot toistuvat vastaavasti m 1 , m 2 , ..., m k kertaa, kutsutaan monikkoksi, jonka pituus on m = m 1 + m 2 + ... + m k , jonka komponenttien joukossa a esiintyy m 1 kertaa, b- m 2 kertaa ja niin edelleen l- mk kertaa.
Permutaatioiden lukumäärä toistoilla on merkitty symbolilla
Erilaisten permutaatioiden lukumäärä elementtien toistoilla a, b,…,l, jossa nämä alkuaineet toistuvat vastaavasti m 1 , m 2 , ..., m k kertaa, määritetään kaavalla
Esimerkki. Kuinka monta kahdeksannumeroista lukua voidaan kirjoittaa käyttämällä numeroita 1, 3, 5, jos luku 1 toistetaan jokaisessa numerossa neljä kertaa, numerot 3 ja 5 - 2 kertaa?
Päätös. Haluttu luku on erilaisten permutaatioiden lukumäärä numeroiden 1, 3, 5 toistoilla, joissa numero 1 toistetaan neljä kertaa ja numerot 3 ja 5 toistetaan kahdesti. Siksi meillä on kaavan mukaan: 
.
Yhdistelmät.
Kutsutaan mikä tahansa m-elementtijoukon (k £ m) k-elementtiosajoukko yhdistelmä ilman toistoa m elementistä k:lla.
M elementin eri yhdistelmien lukumäärä k:llä on merkitty symbolilla
Esimerkki. Kuinka monella tavalla voit valita kolme hoitajaa 30 opiskelijasta?
Päätös. Koska avustajien valintajärjestyksellä ei ole merkitystä, ongelmana on valinta joukosta, jossa on 30 elementtiä osajoukkoja, joissa kussakin on kolme elementtiä, eli yhdistelmiä ilman kolmenkymmenen kolmen elementin toistoja.
Siten, 
.
Yhdistelmä toistoilla annetusta m:stä erityyppisestä elementistä k elementillä kutsutaan mitä tahansa kokoelmaa, joka sisältää k elementtiä, joista jokainen on yksi määritellyn tyypin elementeistä.
Erilaisten yhdistelmien lukumäärä, joissa m elementtiä toistetaan k elementillä, merkitään symbolilla .
Erilaisten yhdistelmien lukumäärä, joissa toistetaan m-tyypin elementtiä k elementille, määräytyy kaavalla
Esimerkki. Posti myy neljää erilaista postikorttia. Kuinka monella tavalla täältä voi ostaa 9 postikorttia?
Päätös. Postikorttien ostotapojen määrä on yhtä suuri kuin erilaisten yhdistelmien lukumäärä 4 elementin toistolla 9:llä, eli yhtä suuri kuin 
.
Äärillisen joukon osajoukkojen lukumäärä.
Olkoon n(A) = m.
Joukon A kaikkien osajoukkojen lukumäärä on 2 n .
Harjoitus 6
1. Fysiikan ja matematiikan valinnaisilla tunneilla luokalla on 30 henkilöä. Molempia aineita tiedetään syvällisesti opiskelevan 10 henkilöä ja matematiikkaa 25. Kuinka moni käy vain fysiikan valinnaisilla tunneilla?
2. 50 opiskelijasta 20 puhuu saksaa ja 15 englantia. Mikä voisi olla molempia kieliä osaavien opiskelijoiden määrä? osaatko ainakin yhtä kieltä?
3. 100 hengestä 28 opiskelee englantia, 30 saksaa, 10 ranskaa, 5 saksaa ja ranskaa, 15 saksaa ja englantia, 6 englantia ja ranskaa. Kaikkia kolmea kieltä opiskelee 3 opiskelijaa. Kuinka moni opiskelija opiskelee vain yhtä kieltä? Kuinka moni opiskelija ei opiskele mitään kieltä?
Tehtävät itsenäiseen työskentelyyn aiheesta "Kombinatoriikka" .
1. Yhden päivän aikataulu sisältää 5 oppituntia eri aineissa. Määritä tällaisten aikataulujen määrä, kun valitset 11 kohteen joukosta.
2. Toimikuntaan kuuluu puheenjohtaja, hänen varajäsenensä ja viisi muuta henkilöä. Kuinka monella tavalla valiokunnan jäsenet voivat jakaa puheenjohtajan ja varapuheenjohtajan tehtävät keskenään?
3. Kuinka monella tavalla 20 hengen ryhmästä voidaan valita kolme hoitajaa?
4. Kuinka monta eri ääniyhdistelmää voidaan ottaa kymmenellä valitulla pianon koskettimella, jos jokainen ääniyhdistelmä voi sisältää kolmesta kymmeneen ääntä?
5. Maljakossa on 10 punaista ja 5 vaaleanpunaista neilikkaa. Kuinka monella tavalla maljakosta voidaan valita viisi samanväristä neilikkaa?
6. Raitiovaunureittien numerot ilmaistaan joskus kahdella värillisellä valolla. Kuinka monta eri reittiä voidaan merkitä kahdeksan värin lyhdyillä?
7. Mestaruus, johon osallistuu 16 joukkuetta, pelataan kahdessa kierroksessa (eli kumpikin joukkue kohtaa joka toinen kahdesti). Päätä pidettävien kokousten lukumäärä.
8. Lukko avautuu vain, jos valitaan tietty kolminumeroinen numero. Yritetään kirjoittaa satunnaisesti kolme numeroa annetuista viidestä numerosta. Numero oli mahdollista arvata vain viimeisellä mahdollisella yrityksellä. Kuinka monta yritystä oli ennen onnistunutta?
9. 15 hengen ryhmästä valitaan neljä viestin osallistujaa 800 + 400 + 200 + 100. Kuinka monella tavalla urheilijat voidaan sijoittaa viestin vaiheisiin?
10. Viiden hengen joukkue kilpailee uintikilpailussa 20 muun urheilijan kanssa. Kuinka monella tavalla tämän tiimin jäsenten paikat voidaan jakaa?
11. Kuinka monella tavalla shakkilaudalle voidaan asettaa kaksi tornia niin, että toinen ei saa kiinni? (Yksi torni voi kaapata toisen, jos se on samassa järjestyksessä tai tiedostossa shakkilaudalla sen kanssa.)
12. Kaksi eriväristä tornia asetetaan shakkilaudalle niin, että kumpikin voi vangita toisensa. Kuinka monta tällaista paikkaa on olemassa?
13. Kilpailun kahdeksan osallistujan suoritusjärjestys määräytyy arvalla. Kuinka monta erilaista arvonnan lopputulosta on mahdollista?
14. Kolmekymmentä henkilöä on jaettu kolmeen kymmenen hengen ryhmään I, II ja III. Kuinka monta erilaista ryhmäkokoonpanoa voi olla?
15. Kuinka monta 5:llä jaollista nelinumeroista lukua voidaan tehdä luvuista 0, 1, 3, 5, 7, jos jokainen luku ei saa sisältää samoja numeroita?
16. Kuinka monta erilaista valorengasta voidaan valmistaa asettamalla 10 moniväristä hehkulamppua ympyrän ympärille (renkaat katsotaan samoiksi, jos värit ovat samassa järjestyksessä)?
17. Kirjahyllyssä on 30 osaa. Kuinka monella tavalla ne voidaan järjestää niin, että ensimmäinen ja toinen osa eivät asetu vierekkäin?
18. Neljän ampujan täytyy osua kahdeksaan maaliin (kaksi kummassakin). Kuinka monella tavalla he voivat jakaa kohteet keskenään?
19. 12 hengen ryhmästä valitaan kaksi päivystävää päivittäin 6 päivän ajan. Selvitä eri päivystysluetteloiden lukumäärä, jos jokainen on päivystävä kerran.
20. Kuinka monta nelinumeroista lukua, joka koostuu luvuista 0, 1, 2, 3, 4, 5, sisältää luvun 3 (lukujen luvut eivät toistu)?
21. Kymmenen ryhmää toimii kymmenessä peräkkäisessä luokkahuoneessa. Kuinka monta aikatauluvaihtoehtoa on olemassa, joissa ryhmät 1 ja 2 olisivat vierekkäisissä luokkahuoneissa?
22. Turnaukseen osallistuu 16 shakinpelaajaa. Määritä ensimmäisen kierroksen eri aikataulujen lukumäärä (aikataulut katsotaan erilaisiksi, jos ne eroavat vähintään yhden pelin osallistujista; nappuloiden väriä ja laudan numeroa ei oteta huomioon).
23. Työmaan viiteen kerrokseen toimitetaan kuusi laatikkoa eri materiaaleja. Kuinka monella tavalla materiaalit voidaan määrittää lattioiden perusteella? Kuinka monessa versiossa jokin materiaali toimitetaan viidenteen kerrokseen?
24. Kahden postinjakajan tulee toimittaa 10 kirjettä 10 osoitteeseen. Kuinka monella tavalla he voivat jakaa työtä?
©2015-2019 sivusto
Kaikki oikeudet kuuluvat niiden tekijöille. Tämä sivusto ei vaadi tekijää, mutta tarjoaa ilmaisen käytön.
Sivun luomispäivämäärä: 20.8.2016
Aiemmin raitiovaunujen numerot oli merkitty kahdella värillisellä lyhdillä. Kuinka monta eri reittiä voidaan merkitä kahdeksalla eri valovärillä?
Vastaukset:
kaava on: 8²=64 64 eri reittiä.
Samanlaisia kysymyksiä
- Muista renessanssin arkkitehtoniset rakennukset ja veistokset, joissa on jotain samanlaista kuin renessanssin katedraali, ja Verrocchion patsas. Kirjoita heidän nimensä muistiin.
- Lisää aukkojen sijasta vastaavien sanojen sarjanumerot ehdotetusta luettelosta. Sanat annetaan luettelossa yksikössä, nimitysmuodossa. HUOM: luettelossa on enemmän sanoja kuin aukkoja tekstissä! Luokitus, joka ____ jäsenyyden perusteista ja ehdoista riippuen on laajasti käytössä ____, erottaa henkilöstön ____ puolueissa. Ensimmäiset eroavat siitä, että ne muodostuvat poliittisen ___-ryhmän ympärille ja niiden rakenteen perustana on aktivistikomitea. Henkilöstöpuolueita muodostetaan yleensä "ylhäältä" erilaisten ___ ryhmittymien, puolueen byrokratian yhdistysten pohjalta. Tällaiset puolueet yleensä tehostavat toimintaansa vain ajaksi ___. Muut puolueet ovat keskitettyjä, kurinalaisia organisaatioita. He pitävät erittäin tärkeänä puolueen jäsenten yhtenäisyyttä. Tällaisia puolueita muodostetaan useimmiten "alhaalta", ammattiliittojen ja muiden ___-liikkeiden pohjalta, jotka heijastavat erilaisia yhteiskunnallisia etuja. ryhmät 1) Sosiologia 10) vaalit 2) julkinen 11) normi 3 tekijä 12) puolue 4) vaalit 13) eduskunta 5) kansallinen 14) konsensus 6) yhteiskunta 15) idiologinen 7) joukko 16) järjestelmä 8) virkasyyte 17) johtaja 9) Valtiotiede
- Nro 1 Ratkaisu: 28/5 * 4 Nro 2 Koordinaattiviivalle on merkitty luku a _______o____|___|___|___________> a -1 0 1 1) a; a -1;\frac(1)(a) 2) a;\frac(1)(a);a-1 3) a-1;\frac(1)(a);a 4)a-1; a;\frac(1)(a)
- onko luku 2008*2011*2012*2014+1 tarkka neliö
- Uusissa taloissa asuntoja on 300. Ensimmäisenä päivänä asuntoja oli 120, toisena päivänä - kolmasosa lopuista. Kuinka monta asuntoa on jäljellä?
- Tolik kertoi viisinumeroisen luvun sen numeroiden summalla. Sitten Tolik kertoi tuloksen (tulos)numeroidensa summalla. Yllättäen se osoittautui jälleen viisinumeroiseksi luvuksi. Minkä luvun Tolik kertoi ensimmäistä kertaa? (Etsi kaikki mahdolliset vastaukset.)
