En kombinasjon er et uordnet utvalg av elementer i et begrenset sett med et fast antall og uten gjentakelser av elementer. Ulike kombinasjoner må være forskjellige i minst ett element, og rekkefølgen på elementene spiller ingen rolle. For eksempel fra settet med alle vokaler latinske bokstaver(AEIOU) du kan lage 10 forskjellige kombinasjoner av 3 bokstaver, som danner følgende uordnede trillinger:
AEI, AEO, AEU, AIO, AIU, AOU, EIO, EIU, EOU, IOU.
Det er interessant å merke seg at fra de samme fem bokstavene kan du også få 10 forskjellige kombinasjoner hvis du kombinerer dem 2 bokstaver om gangen, slik at følgende uordnede par:
AE, AI, AO, AU, EI, EO, EU, IO, IU, OU.
Men hvis du kombinerer de samme latinske vokalbokstavene med 4, vil du bare få følgende 5 forskjellige kombinasjoner:
AEIO, AEIU, AIOU, EIOU, AEOU.
I generell sak for å angi antall kombinasjoner av n forskjellige elementer av m elementer, brukes følgende funksjonelle, indeks- eller vektorsymbolikk (Appel):
Uavhengig av notasjonsformen, kan antall kombinasjoner av n elementer med m elementer bestemmes ved hjelp av følgende multiplikasjons- og faktorformler:
Det er lett å kontrollere at resultatet av beregninger ved bruk av disse formlene sammenfaller med resultatene av eksemplet diskutert ovenfor med kombinasjoner av vokaler i latinske bokstaver. Spesielt med n=5 og m=3 vil beregninger ved hjelp av disse formlene gi følgende resultat:
I det generelle tilfellet har formler for antall kombinasjoner en kombinatorisk betydning og er gyldige for alle heltallsverdier av n og m, slik at n > m > 0. Hvis m > n og m< 0, то число сочетаний равно 0, так как в этом случае основное множество из n элементов вообще не имеет подмножеств мощности m:
I tillegg er det nyttig å huske følgende begrensende antall kombinasjoner, som enkelt kan kontrolleres ved direkte substitusjon i multiplikasjons- og faktorformlene:
Det bør også bemerkes at multiplikasjonsformelen forblir gyldig selv når n er ekte nummer, med samme heltallsverdi på m. Men da mister resultatet av beregningen ved å bruke det, mens det opprettholder formell gyldighet, sin kombinatoriske betydning.
IDENTITETER AV KOMBINASJONER
Den praktiske bruken av multiplikative og faktorielle formler for å bestemme antall kombinasjoner for vilkårlige verdier av n og m viser seg å være av liten produktivitet på grunn av den eksponentielle veksten av faktorproduktene til deres teller og nevner. Selv for relativt små verdier på n og m overskrider disse produktene ofte evnene til å representere heltall i moderne databehandling og programvaresystemer. Dessuten viser deres verdier seg å være betydelig større enn den resulterende verdien av antall kombinasjoner, som kan være relativt liten. For eksempel er antall kombinasjoner av n=10 med m=8 elementer bare 45. For å finne denne verdien ved å bruke faktorformelen, må du først beregne mye større verdier på 10! i telleren og 8! i nevneren:
For å eliminere tidkrevende operasjoner for behandling av store mengder, for å bestemme antall kombinasjoner, kan du bruke forskjellige gjentakelsesrelasjoner, som direkte følger av multiplikasjons- og faktorformlene. Spesielt følger følgende gjentakelsesforhold fra den multiplikative formelen, som lar oss ta forholdet mellom indeksene utover tegnet på antall kombinasjoner:
Til slutt, å holde abonnenten konstant gir følgende gjentakelsesrelasjon, som enkelt oppnås fra faktorformelen for antall kombinasjoner:
Etter elementære transformasjoner De tre resulterende gjentaksrelasjonene kan representeres i følgende former:
Hvis vi nå legger til venstre og høyre side av de to første formlene og reduserer resultatet med n, får vi en viktig gjentakelsesrelasjon, som kalles identiteten for å legge til kombinasjonstall:
Addisjonsidentiteten gir en grunnleggende gjentakelsesregel for effektivt å bestemme antall kombinasjoner for store verdier av n og m, siden den lar multiplikasjonsoperasjonene i faktorielle produkter erstattes av de enklere addisjonsoperasjonene, og for mindre antall kombinasjoner. Spesielt ved å bruke addisjonsidentiteten er det nå enkelt å bestemme antall kombinasjoner av n=10 med m=8 elementer, som ble diskutert ovenfor, ved å utføre følgende sekvens av tilbakevendende transformasjoner:
I tillegg kan flere nyttige relasjoner for å beregne endelige summer utledes fra addisjonsidentiteten, spesielt formelen for summering med abonnent, som har følgende form:
Denne relasjonen oppnås hvis vi i addisjonsidentiteten utvider gjentakelsen over begrepet med den største hevet skriften så lenge dens underskrift er større enn 0. Følgende numeriske eksempel illustrerer spesifisert prosess tilbakevendende transformasjoner:
Subscript summeringsformelen brukes ofte til å beregne summen av potenser naturlige tall. Spesielt, forutsatt m=1, ved å bruke denne formelen er det lett å finne summen av de første n tallene i den naturlige rekken:
En annen nyttig versjon av summeringsformelen kan oppnås ved å utvide gjentakelsen av addisjonsidentiteten langs begrepet med det minste hevet opp. Følgende numeriske eksempel illustrerer denne versjonen av tilbakevendende transformasjoner:
I det generelle tilfellet, som et resultat av slike transformasjoner, oppnås summen av antall kombinasjoner, hvor begge indeksene avviker med en fra naboleddene, og forskjellen i indeksene forblir konstant (i det betraktede eksemplet er det også lik én). Dermed får vi følgende summeringsformel for begge indeksene for kombinasjonstall:
I tillegg til gjentaksrelasjonene og summeringsformlene diskutert ovenfor, har mange andre nyttige identiteter for kombinasjonstall blitt oppnådd i kombinatorisk analyse. Den viktigste blant dem er symmetri identitet, som ser slik ut:
Gyldigheten til symmetriidentiteten kan verifiseres i følgende eksempel ved å sammenligne antall kombinasjoner av 5 elementer med 2 og med (5 2) = 3:
Symmetriidentiteten har en åpenbar kombinatorisk betydning, siden den ved å bestemme antall alternativer for å velge m elementer fra n elementer, samtidig etablerer antall kombinasjoner fra de gjenværende (nm) uvalgte elementene. Den angitte symmetrien oppnås umiddelbart ved å erstatte m med (nm) i faktorformelen for antall kombinasjoner:
Tall og kombinasjonsidentiteter er mye brukt i ulike områder moderne beregningsmatematikk. Imidlertid er deres mest populære applikasjoner relatert til Newtons binomiale og Pascals trekant.
BINOMIALTEOREM
For å utføre ulike matematiske transformasjoner og beregninger er det viktig å kunne representere enhver naturlig potens til et algebraisk binomial (binomial) i form av et polynom. For små potenser kan det ønskede polynomet enkelt oppnås ved å direkte multiplisere binomialer. Spesielt fra kurset elementær matematikk Følgende formler for kvadratet og terningen av summen av to ledd er velkjente:
I det generelle tilfellet, for en vilkårlig grad n av et binomial, er den nødvendige representasjonen i form av et polynom gitt av Newtons binomiale teorem, som erklærer følgende likhet for å være sann:
Denne likheten kalles vanligvis Newtons binomiale. Polynomet på høyre side er dannet av summen av produktene av n ledd X og Y av binomialet på venstre side, og koeffisientene foran dem kalles binomiale og er lik antall kombinasjoner med indekser, som er hentet fra deres krefter. Gitt den spesielle populariteten til Newtons binomiale formel i kombinatorisk analyse, anses begrepene binomial koeffisient og antall kombinasjoner generelt som synonyme.
Tydeligvis er kvadrat- og terningssumformlene spesielle tilfeller av binomialsetningen for henholdsvis n=2 og n=3. For å behandle mer høye grader(n>3) Newtons binomiale formel skal brukes. Dens anvendelse for en fjerdegrads binomial (n=4) demonstreres av følgende eksempel:
Det skal bemerkes at binomialformelen var kjent allerede før Newton for middelalderske matematikere fra det arabiske østen og Vest-Europa. Derfor henne vanlig navn er ikke historisk rettferdig. Newtons fortjeneste er at han generaliserte denne formelen til tilfellet med en vilkårlig reell eksponent r, som kan ta hvilken som helst positiv eller negativ rasjonal og irrasjonelle verdier. I det generelle tilfellet har en slik Newton binomial formel en uendelig sum på høyre side og skrives vanligvis som på følgende måte:
For eksempel, med en positiv brøkverdi av eksponenten r=1/2, tatt i betraktning verdiene til de binomiale koeffisientene, oppnås følgende utvidelse:
I det generelle tilfellet er Newton-binomialformelen for enhver eksponent en spesiell versjon av Maclaurin-formelen, som gir utvidelsen vilkårlig funksjon i en kraftserie. Newton viste det for |z|< 1 этот ряд сходится, и сумма в правой части становится конечной. При любой naturlig grad r = n på høyre side resulterer også i en endelig sum av (n+1) første ledd, siden alle C(n, k>n) = 0 . Hvis vi nå setter Z=X/Y og multipliserer venstre og høyre side med Yn, får vi en versjon av Newton binomialformelen diskutert ovenfor.
Til tross for sin universalitet, beholder binomialsetningen sin kombinatoriske betydning bare for ikke-negative heltallskrefter til binomialet. I dette tilfellet kan det brukes til å bevise flere nyttige identiteter for binomiale koeffisienter. Spesielt formler for å summere antall kombinasjoner etter abonnent og etter begge indekser ble diskutert ovenfor. Den manglende hevet oppsummeringsidentiteten kan enkelt fås fra Newtons binomiale formel ved å sette X = Y = 1 eller Z = 1 i den:
En annen nyttig identitet etablerer likheten mellom summene av binomiale koeffisienter med partall og oddetall. Det er umiddelbart hentet fra Newtons binomiale formel hvis X = 1 og Y = 1 eller Z = 1:
Til slutt, fra begge betraktede identiteter får vi identiteten til summen av binomiale koeffisienter med bare partall eller bare oddetall:
Basert på de vurderte identitetene og den tilbakevendende regelen om å fjerne indekser fra under tegnet med antall kombinasjoner, kan vi oppnå hele linjen interessante forhold. For eksempel, hvis vi i den hevede summeringsformelen erstatter n overalt med (n1) og fjerner indeksene i hvert ledd, får vi følgende relasjon:
Ved å bruke en lignende teknikk i formelen for summen av binomiale koeffisienter med partall og oddetall, er det mulig å bevise gyldigheten av for eksempel følgende relasjon:
En annen nyttig identitet lar deg enkelt beregne summen av produktene av symmetrisk plasserte binomiale koeffisienter av to binomialer med vilkårlige grader n og k in følgende formel Cauchy:
Gyldigheten av denne formelen følger av den nødvendige likheten av koeffisienter for enhver grad m av variabelen Z på venstre og høyre side av følgende identiske relasjon:
I det spesielle tilfellet når n=k=m, med tanke på symmetriidentiteten, oppnås en mer populær formel for summen av kvadrater av binomiale koeffisienter:
Mange andre nyttige identiteter for binomiale koeffisienter kan finnes i den omfattende litteraturen om kombinatorisk analyse. Imidlertid er deres mest kjente praktiske anvendelse relatert til Pascals trekant.
PASCALS TREKANT
Pascals aritmetiske trekant danner en uendelig numerisk tabell som består av binomiale koeffisienter. Linjene er ordnet etter potenser av binomialer fra topp til bunn. I hver linje er de binomiale koeffisientene ordnet i stigende rekkefølge av de hevete til de tilsvarende kombinasjonstallene fra venstre til høyre. Pascals trekant er vanligvis skrevet enten i likebenet eller rektangulær form.
Mer visuelt og vanlig er det likebenede formatet, der de binomiale koeffisientene, forskjøvet, danner en uendelig likebenet trekant. Det første fragmentet for binomialer opp til 4. grad (n=4) har følgende form:
Generelt gir Pascals likebente trekant en praktisk geometrisk regel for å bestemme binomiale koeffisienter, som er basert på identitetene til addisjon og symmetrien til tallkombinasjoner. Spesielt, i henhold til addisjonsidentiteten, er enhver binomial koeffisient summen av de to koeffisientene i den forrige raden nærmest den. I følge symmetriidentiteten er Pascals likebente trekant symmetrisk med hensyn til halveringslinjen. Dermed er hver av linjene et numerisk palindrom av binomiale koeffisienter. De angitte algebraiske og geometriske egenskapene gjør det mulig å enkelt utvide Pascals likebenede trekant og konsekvent finne verdiene til binomiale koeffisienter for vilkårlige potenser.
For å studere ulike egenskaper ved Pascals trekant er det imidlertid mer praktisk å bruke det formelt mer strenge rektangulære formatet. I dette formatet er det spesifisert av en lavere trekantet matrise av binomiale koeffisienter, der de danner en uendelig rettvinklet trekant. Det første fragmentet av Pascals rettvinklede trekant for binomialer opp til 9. grad (n=9) har følgende form:
Geometrisk dette rektangulært bord oppnådd ved horisontal deformasjon likebent trekant Pascal. Som et resultat blir tallserien parallelt med sidesidene av Pascals likebente trekant til vertikaler og diagonaler av Pascals rettvinklede trekant, og horisontalene til begge trekantene faller sammen. Samtidig forblir reglene for addisjon og symmetri for binomiale koeffisienter gyldige, selv om Pascals rettvinklede trekant mister den visuelle symmetrien som er karakteristisk for sin likebente motpart. For å kompensere for dette, blir det mer praktisk å formelt analysere ulike numeriske egenskaper binomiale koeffisienter for horisontaler, vertikaler og diagonaler av Pascals rettvinklede trekant.
Ved å starte analysen av horisontalene til Pascals rettvinklede trekant, er det lett å legge merke til at summen av elementene i en hvilken som helst rad med nummer n er lik 2n i samsvar med formelen for å summere binomialer med hevet skrift. Det følger av dette at summen av elementene over noen av de horisontale linjene med nummer n er lik (2 n 1). Dette resultatet blir ganske åpenbart hvis verdien av summen av elementene til hver horisontal er skrevet i det binære tallsystemet. For eksempel, for n=4 kan dette tillegget skrives som følger:
Her er et par til interessante egenskaper horisontale linjer, som også er forbundet med to potenser. Det viser seg at hvis det horisontale tallet er en potens av to (n=2 k), så er alle dets indre elementer (bortsett fra de ytre) partall. Tvert imot vil alle tallene på en horisontal linje være oddetall hvis tallet er én mindre grad toere (n=2 k 1). Gyldigheten av disse egenskapene kan verifiseres ved å kontrollere pariteten til de interne binomiale koeffisientene, for eksempel i horisontalene n=4 og n=3 eller n=8 og n=7.
La nå radnummeret til Pascals rettvinklede trekant være et primtall p. Da er alle dens interne binomiale koeffisienter delbare med p. Denne egenskapen er lett å sjekke for små verdier av prime konturtall. For eksempel er alle de interne binomiale koeffisientene til den femte horisontale (5, 10 og 5) åpenbart delbare med 5. For å bevise dette resultatet for et hvilket som helst horisontalt primtall p, må du skrive multiplikasjonsformelen for dens binomiale koeffisienter som følger:
Siden p er et primtall og derfor ikke er delelig med m!, må produktet av de gjenværende faktorene til telleren til denne formelen være delelig med m for å garantere en heltallsverdi av binomialkoeffisienten. Det følger at forholdet i firkantede parenteser er et naturlig tall N og det ønskede resultatet blir åpenbart:
Ved å bruke dette resultatet kan vi fastslå at tallene til alle horisontale linjer i Pascals trekant, hvis indre elementer er delbare med et gitt primtall p, er potenser av p, det vil si at de har formen n=p k. Spesielt hvis p=3, deler primtallet p ikke bare alle interne elementer i rad 3, som etablert ovenfor, men for eksempel den niende horisontale (9, 36, 84 og 126). På den annen side, i Pascals trekant er det umulig å finne en horisontal linje hvis indre elementer er delbare med et sammensatt tall. I ellers tallet på en slik horisontal linje må samtidig være en potens av primdelere sammensatt tall, som alle dens interne elementer er delt inn i, men dette er iht åpenbare grunner umulig.
De vurderte betraktningene tillater oss å formulere følgende generelle kriterium for delbarheten til de horisontale elementene i Pascals trekant. Størst felles deler(GCD) av alle interne elementer i enhver horisontal i Pascals trekant med nummer n er lik primtall p hvis n=pk eller 1 i alle andre tilfeller:
GCD(Cmn) = ( ) for enhver 0< m < n .
Som konklusjon av analysen av horisontaler er det verdt å vurdere en mer interessant egenskap som rekken av binomiale koeffisienter som danner dem har. Hvis de binomiale koeffisientene til en horisontal linje med nummer n multipliseres med påfølgende potenser av tallet 10, og deretter alle disse produktene legges til, er resultatet 11 n. Den formelle begrunnelsen for dette resultatet er substitusjonen av verdiene X=10 og Y=1 (eller Z=1) i Newton-binomialformelen. Følgende numeriske eksempel illustrerer oppfyllelsen av denne egenskapen for n=5:
Analysen av egenskapene til vertikalene til Pascals rettvinklede trekant kan begynne med studiet av de individuelle egenskapene til deres bestanddeler. Formelt er hver vertikal m dannet av den følgende uendelige sekvensen av binomiale koeffisienter med en konstant hevet skrift (m) og en økning av underskriften:
Det er klart at når m=0 oppnås en sekvens av enere, og når m=1 dannes en serie med naturlige tall. Når m=2 er vertikalen bygd opp av trekantetall. Hvert trekantet tall kan representeres på et plan som likesidet trekant, som er fylt med vilkårlige objekter (kjerner) arrangert i et sjakkbrettmønster. I dette tilfellet bestemmer verdien av hvert trekantet tall Tk antallet representerende kjerner, og indeksen viser hvor mange rader med kjerner som trengs for å representere det. For eksempel representerer 4 innledende trekantetall følgende konfigurasjoner fra det tilsvarende antallet kjernefysiske "@"-symboler:
Det skal bemerkes at man på lignende måte kan introdusere kvadrattall S k , som oppnås ved å kvadrere naturlige tall og generelt mangekantet tall dannet ved vanlig fylling vanlige polygoner. Spesielt 4 initialer kvadrattall kan avbildes som følger:
For å gå tilbake til analysen av vertikalene i Pascals trekant, kan vi merke oss at den neste vertikalen ved m=3 er fylt med tetraedriske (pyramideformede) tall. Hvert slikt tall Pk spesifiserer antall kjerner som kan ordnes i form av et tetraeder, og indeksen bestemmer hvor mange horisontale trekantede lag med rader med kjerner som kreves for å skildre det i tredimensjonalt rom. I dette tilfellet må alle horisontale lag representeres som påfølgende trekanttall. Elementene i de følgende vertikalene i Pascals trekant for m>3 danner serier av hypertetraedale tall, som ikke har en visuell geometrisk tolkning på planet eller i tredimensjonalt rom, men formelt tilsvarer flerdimensjonale analoger av trekantede og tetraedale tall.
Selv om den vertikale tallserien til Pascals trekant har de betraktede individuelle formfunksjonene, er det for dem mulig å beregne delsummene av verdiene til de innledende elementene på samme måte, ved å bruke formelen for å summere antall kombinasjoner med subscript . I Pascals trekant har denne formelen følgende geometriske tolkning. Summen av verdiene til de n øvre binomiale koeffisientene til enhver vertikal er lik verdien av elementet til neste vertikal, som ligger en linje under. Dette resultatet samsvarer også geometrisk struktur trekantede, tetraedriske og hypertetraedale tall, siden representasjonen av hvert slikt tall består av kjernelag som representerer tall av lavere orden. Spesielt, nte trekantet tallet T n kan oppnås ved å summere alle de naturlige tallene som representerer dets lineære lag:
På samme måte er det ikke vanskelig å finne det tetraedriske tallet Pn ved å beregne følgende sum av de første n trekanttallene som utgjør de horisontale kjernelagene:
I tillegg til horisontalene og vertikalene i Pascals rettvinklede trekant, kan man spore diagonale rader med elementer, som også er av interesse å studere egenskapene til. I dette tilfellet skilles det vanligvis mellom synkende og stigende diagonaler. De nedadgående diagonalene er parallelle med hypotenusen til Pascals rettvinklede trekant. De er dannet av serier av binomiale koeffisienter med en økning av begge indeksene. På grunn av identiteten til symmetri, faller de synkende diagonalene sammen i verdiene til elementene deres med de tilsvarende vertikale radene i Pascals trekant og gjentar derfor alle egenskapene deres diskutert ovenfor. Den angitte korrespondansen kan spores ved sammenfall av verdiene til elementene i den synkende diagonalen og den vertikale med et hvilket som helst tall n, hvis vertikale nuller ikke tas i betraktning:
Stigende diagonaler danner tallrekker geometrisk vinkelrett på hypotenusen til Pascals rettvinklede trekant. De er fylt med binomiale koeffisienter med en dekrement av den nedre og inkrement av hevet skrift. Spesielt danner de 7 øvre stigende diagonalene følgende numerisk rekkefølge unntatt etterfølgende nuller:
Generelt inneholder det stigende diagonale tallet n følgende binomiale koeffisienter, summen av indeksene til hver av dem er lik (n1):
I kraft av addisjonsidentiteten for kombinasjonstall er hvert diagonalelement lik summen av to elementer som korresponderer i indekser fra de to foregående stigende diagonalene. Dette gjør at hver påfølgende stigende diagonal kan konstrueres ved parvis summering av tilstøtende horisontale elementer fra de to foregående diagonalene, og utvider Pascals trekant uendelig langs diagonalen. Følgende fragment av Pascals trekant illustrerer konstruksjonen av en stigende diagonal nummer 8 langs diagonaler nummerert 6 og 7:
Med denne konstruksjonsmetoden vil summen av elementene til enhver stigende diagonal, fra den tredje, være lik summen av elementene i de to foregående stigende diagonalene, og de to første diagonalene består av bare ett element, verdien hvorav er 1. Resultatene av de tilsvarende beregningene danner følgende numeriske serier, i henhold til hvilke du kan sjekke gyldigheten til den betraktede egenskapen til de stigende diagonalene til Pascals rettvinklede trekant:
Ved å analysere disse tallene kan du se at i henhold til en lignende lov dannes den velkjente sekvensen av Fibonacci-tall, der hvert neste tall er lik summen av de to foregående, og de to første tallene er lik 1:
Dermed kan vi trekke følgende viktige konklusjon: de diagonale summene av elementene i Pascals trekant utgjør Fibonacci-sekvensen. Denne egenskapen lar deg angi en annen interessant funksjon Pascals trekant. Ved å utvide Fibonacci-formelen rekursivt, er det lett å bevise at summen av de første n Fibonacci-tallene er lik (F n+2 1).
Derfor er summen av de binomiale koeffisientene som fyller de øvre n diagonalene også lik (F n+2 1). Det følger at summen av de første n diagonalene i Pascals trekant er 1 mindre enn summen av de binomiale koeffisientene som står på diagonalen med tall (n+2).
Avslutningsvis bør det bemerkes at de vurderte egenskapene til horisontalene, vertikalene og diagonalene til Pascals trekant ikke uttømmer det store utvalget av muligheter som forbinder ulike matematiske aspekter som ved første øyekast ikke har noe til felles. Så uvanlige egenskaper tillate oss å betrakte Pascals trekant som et av de mest perfekte numeriske systemene, hvis evner ikke kan listes opp og er vanskelige å overvurdere.
Algoritmen for å beregne antall kombinasjoner ved å bruke Pascals trekant er presentert nedenfor:
Privat funksjon SochTT (ByVal n As Integer, ByVal k As Integer) As Double Dim i As Integer Dim j As Integer Dim TT () As Double ReDim TT (n, k) For i = 0 To n TT (0, i) = 1 TT (i, i) = 1 Neste For i = 2 Til n For j = 1 Til i - 1 TT (i, j) = TT (i - 1, j - 1) + TT (i - 1, j) Neste Neste SochTT = TT (n, k) Sluttfunksjon
Hvis du trenger å beregne antall kombinasjoner mange ganger, kan det være mer praktisk å konstruere Pascals trekant én gang, og deretter motta data fra matrisen.
Dim TT () As Double Private Sub CreateTT () ReDim TT (0, 0) BuildTT 0, 0 End Sub Private Function SochTT (ByVal n As Integer, ByVal k As Integer) As Double If n > Ubound (TT) Then BuildTT Ubound (TT) + 1, n SochTT = TT (n, k) End Function Private Sub TerminateTT () ReDim TT (0, 0) End Sub Private Sub BuildTT (ByVal start As Integer, ByVal end As Integer) Dim i As Integer Dim j Som heltall ReDim Bevar TT (slutt, slutt) For i = start Til slutt TT (0, i) = 1 TT (i, i) = 1 Neste Hvis slutt< 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
Først må du ringe CreateTT-prosedyren. Du kan da finne antall kombinasjoner ved å bruke SochTT-funksjonen. Når du ikke lenger trenger trekanten, ring TerminateTT-prosedyren. I koden ovenfor, når du kaller SochTT-funksjonen, hvis trekanten ennå ikke er fullført til det nødvendige nivået, fullføres den ved å bruke BuildTT-prosedyren. Funksjonen henter deretter ønsket element i TT-matrisen og returnerer det.
Dim X () Som heltall Dim teller () Som heltall Dim K Som heltall Dim N Som heltall Public Sub Soch() Dim i Som heltall N = CInt(InndataBox("Skriv inn N")) K = CInt(Inntastingsboks("Skriv inn K ")) K = K + 1 ReDim X(N) For i = 1 Til N X(i) = i Neste txtOut.Text = "" ReDim Counter(K) Counter(0) = 1 SochGenerate 1 End Sub Private Sub SochGenerate( ByVal c Som heltall) Dim i Som heltall Dim j Som heltall Dim n1 Som heltall Dim ut() Som heltall Dim X1() Som heltall Hvis c = K Så Redim ut(K) X1 = X For i = 1 Til K - 1 n1 = 0 For j = 1 Til N Hvis X1(j)<>0 Da n1 = n1 + 1 Hvis n1 = Teller(i) Da Ut(i) = X1(j) X1(j) = 0 Avslutt For Slutt Hvis Neste txtOut.Text = txtOut.Text & CStr(Out(i)) Next txtOut.Text = txtOut.Text & vbCrLf Else For Counter(c) = Counter(c - 1) To N - c + 1 SochGenerate c + 1 Next End If End Sub
LISTER KOMBINASJONER AV NATURLIGE NUMMER
For å løse mange praktiske problemer det er nødvendig å liste opp alle kombinasjoner av fast kardinalitet som kan oppnås fra elementene i et gitt begrenset sett, og ikke bare bestemme antallet. Med tanke på den alltid eksisterende muligheten for heltallsnummerering av elementene i et begrenset sett, er det i de fleste tilfeller tillatt å begrense oss til bruken av algoritmer for å telle kombinasjoner av naturlige tall. Den mest naturlige og enkle av dem er algoritmen for å liste kombinasjoner av naturlige tall i leksigrafisk rekkefølge.
For å formelt beskrive denne algoritmen, er det praktisk å anta at hovedsettet, alle kombinasjoner av m elementer som må være oppført, danner påfølgende naturlige tall fra 1 til n. Deretter enhver kombinasjon av m Som et resultat av bestilling viser verdien i hver posisjon av en slik vektor av kombinasjoner seg naturlig å være begrenset i verdi ovenfra og under som følger: Den leksigrafiske algoritmen genererer sekvensielt slike kombinasjonsvektorer, og starter med den leksigrafisk minste vektoren, der alle posisjoner inneholder følgende minimumsverdier av elementer som er lik deres indekser: Hver suksessiv kombinasjonsvektor dannes fra den gjeldende etter å ha skannet elementene fra venstre til høyre for å finne elementet lengst til høyre som ennå ikke har nådd grenseverdien: Verdien av et slikt element bør økes med 1. Hvert element til høyre for det bør tildeles den minste mulige verdien, som er 1 mer enn naboen til venstre. Etter disse endringene vil den neste vektoren av kombinasjoner ha følgende elementsammensetning: Dermed vil den neste kombinasjonsvektoren være leksigrafisk større enn den forrige, siden verdiene til deres innledende (j1) elementer er like i verdi, og verdien av elementet i posisjon j er 1 større enn den forrige. . Det spesifiserte forholdet til økende leksigrafisk rekkefølge er garantert tilfredsstilt ved alle iterasjoner av algoritmen. Resultatet er en økende leksigrafisk sekvens, som fullføres av den leksigrafisk største kombinasjonsvektoren, der elementene i alle posisjoner har følgende maksimumsverdier: Den betraktede leksigrafiske algoritmen er illustrert av følgende eksempel, der det er nødvendig å liste opp i økende leksigrafisk rekkefølge alle 15 kombinasjoner av n=6 første naturlige tall med m=4 tall, det vil si alle mulige 4-elements undersett av hovedgenereringen sett (1, 2, 3, 4, 5, 6) fra 6 elementer. Beregningsresultatene er presentert i følgende tabell: I dette eksemplet er de største tillatte verdiene av tall i posisjonene til kombinasjonsvektorene henholdsvis 3, 4, 5 og 6. For å lette tolkningen av resultatene, i hver kombinasjonsvektor, elementet lengst til høyre, som har ennå ikke nådd sin maksimale verdi, er understreket. Numeriske indekser av kombinasjonsvektorer bestemmer tallene deres i leksigrafisk rekkefølge. I det generelle tilfellet kan det leksigrafiske tallet N for en hvilken som helst kombinasjon av n elementer med m beregnes ved å bruke følgende formel, der, av kosmetiske årsaker, Appel-symbolikk brukes til å betegne antall kombinasjoner: Spesielt vil følgende beregninger som bruker denne formelen for kombinasjonstallet (1, 3, 4, 6) av n=6 elementer av m=4 i leksigrafisk rekkefølge gi resultatet N=8, som tilsvarer eksemplet diskutert ovenfor: I det generelle tilfellet, ved å bruke identiteten for summen av antall kombinasjoner for begge indeksene, er det mulig å vise at tallet på den leksigrafisk minste kombinasjonen (1, ... i, ... m) når det beregnes ved hjelp av denne formel vil alltid være lik 1: Det er også åpenbart at tallet på den leksigrafisk største kombinasjonen (m, … nm+i, … n) når det beregnes ved hjelp av denne formelen, vil være lik antall kombinasjoner av n elementer med m: Formelen for å beregne leksigrafiske kombinasjonstall kan brukes til å løse det omvendte problemet, der du må bestemme kombinasjonsvektoren etter tallet i leksigrafisk rekkefølge. For å løse et slikt omvendt problem, må det skrives i form av en ligning, der alle de ukjente verdiene til elementene i vektoren til ønsket kombinasjon (C 1, ... C i, ... C m ) er konsentrert i antall kombinasjoner på høyre side, og den kjente forskjellen L av antall kombinasjoner er skrevet på venstre side av n elementer hver m og nummeret på den nødvendige kombinasjonen N: Løsningen på denne ligningen er gitt av følgende "grådige" algoritme, i løpet av iterasjonene som verdiene til elementene i vektoren til ønsket kombinasjon velges sekvensielt. Ved den innledende iterasjonen velges den minste mulige (innenfor sine begrensninger) verdi av C 1, der det første leddet på høyre side vil ha en maksimal verdi som ikke overstiger L: Nå skal venstre side av L reduseres med det første antallet kombinasjoner på høyre side med den valgte verdien av C 1, og på samme måte bestemme verdien av C 2 ved den andre iterasjonen: På samme måte bør alle påfølgende iterasjoner utføres for å velge verdiene til alle andre elementer C i av ønsket kombinasjon, opp til det siste elementet C m: Av åpenbare grunner kan verdien av det siste elementet C m bestemmes basert på likheten mellom dets antall kombinasjoner og restverdien til venstre side av L: Det skal bemerkes at verdien av det siste elementet i kombinasjonen C m kan finnes enda enklere, uten å oppgi de mulige verdiene: Implementeringen av iterasjoner av den betraktede algoritmen er illustrert av følgende eksempel, der det er nødvendig å bestemme kombinasjoner med tallet N=8 i leksigrafisk rekkefølge, hvis n=6 og m=4: Den algoritmiske evnen til å bestemme en kombinasjon med et gitt tall i leksigrafisk rekkefølge kan brukes i ulike retninger. Spesielt når du oppgir kombinasjoner i leksigrafisk rekkefølge, er det nødvendig å sikre en retur til enhver kombinasjon som ble oppnådd tidligere, det er nok å bare vite nummeret. I tillegg blir det mulig å generere kombinasjoner i hvilken som helst rekkefølge, som er regulert av en vilkårlig gitt sekvens av deres leksigrafiske tall. Nå presenterer vi en algoritme for å generere kombinasjoner i leksikografisk rekkefølge: 2 for i:= 1 til k gjør A[i] := i; 5 begynn å skrive(A, …, A[k]); 6 hvis A[k] = n så p:= p 1 ellers p:= k; 8 for i:= k ned til p do A[i] := A[p] + i p + 1 KOMBINASJONER MED RETTENDE ELEMENTER I motsetning til en klassisk kombinasjon, der alle elementer er forskjellige, danner en kombinasjon med repetisjoner et uordnet utvalg av elementer i et begrenset sett, der ethvert element kan vises uendelig ofte og ikke nødvendigvis er til stede i en enkelt kopi. I dette tilfellet er antallet gjentakelser av elementer vanligvis bare begrenset av lengden på kombinasjonen, og kombinasjoner som er forskjellige i minst ett element anses som forskjellige. For eksempel, ved å velge 4 valgfritt forskjellige tall fra settet 1, 2 og 3, kan du lage følgende 15 kombinasjoner med repetisjoner: 1111 1112 1113 1122 1123 1133 1222 1223 1233 1333 2222 2223 2233 2333 3333.
Generelt kan kombinasjoner med repetisjoner dannes ved å velge n elementer av vilkårlige typer. Imidlertid kan de alltid assosieres med påfølgende naturlige tall fra 1 til n. Da kan enhver kombinasjon av m valgfritt forskjellige tall i dette området skrives i vektorform, og ordne dem i ikke-avtagende rekkefølge fra venstre til høyre: Naturligvis, med denne formen for notasjon, kan alle tilstøtende elementer være like på grunn av muligheten for ubegrensede repetisjoner. Imidlertid kan hver kombinasjonsvektor med repetisjoner av n elementer med m assosieres med en kombinasjonsvektor av (n+m−1) elementer med m, som er konstruert som følger: Det er klart at for alle verdier av elementene i vektoren f, er elementene i vektoren C garantert forskjellige og strengt ordnet i økende rekkefølge av verdiene fra området fra 1 til (n+m1) : Tilstedeværelsen av en en-til-en korrespondanse mellom elementene i kombinasjonsvektorene f og C tillater oss å foreslå følgende enkle metode for systematisk å liste kombinasjoner med repetisjoner av n elementer med m. Det er bare nødvendig å liste, for eksempel, i leksigrafisk rekkefølge, alle C-kombinasjoner av (n+m1) elementer av m, sekvensielt transformere elementene til hver av dem til de tilsvarende elementene av kombinasjoner med repetisjoner f ved å bruke følgende formel: Som et resultat dannes en sekvens av vektorer av kombinasjoner med gjentakelser av elementer, som er ordnet i rekkefølgen generert ved å liste de tilsvarende kombinasjonene uten gjentakelser av elementer. Spesielt for å oppnå ovennevnte sekvens av kombinasjoner av 3 sifre 1, 2 og 3 med repetisjoner av 4 sifre, er det nødvendig å liste opp i leksigrafisk rekkefølge alle kombinasjoner uten repetisjoner av 6 sifre 1,2,3,4, 5 og 6 er 4 sifre hver, og konverterer dem som angitt. Følgende eksempel viser en slik konvertering av kombinasjonen (1,3,4,6) med det leksikografiske tallet 8: Den vurderte en-til-en-korrespondansen mellom kombinasjoner med og uten gjentakelser av elementer betyr at settene deres er like kraftige. Derfor, i det generelle tilfellet, er antall kombinasjoner med repetisjoner av n elementer med m lik antall kombinasjoner uten repetisjoner av (n+m1) elementer med m. Ved å bruke den samme symbolikken for å betegne antall kombinasjoner med repetisjoner f og uten repetisjoner C, kan denne likheten skrives som følger: Det er lett å sjekke at for eksemplet vurdert ovenfor, hvor n=3 og m=4, vil antall repetisjonskombinasjoner være lik 15, som sammenfaller med resultatet av deres direkte liste: Det skal bemerkes at, i motsetning til den klassiske versjonen, er verdiene til kombinasjonsparametrene med repetisjoner n og m ikke direkte relatert til hverandre, derfor f(n,m)>0 for enhver kombinasjon av deres positive verdier. De tilsvarende grensebetingelsene bestemmes fra likheten mellom verdiene av (n+m1) og (n1) eller (n+m1) og m: Det burde også være ganske åpenbart at hvis m er lik 1, så er ingen repetisjoner av elementer mulig, og derfor vil følgende likhet være sann for enhver positiv verdi på n>0: I tillegg for antall kombinasjoner med repetisjoner for evt positive verdier n og m gjelder følgende gjentakelsesrelasjon, som ligner addisjonsidentiteten for kombinasjonstall uten repetisjon av elementer: Faktisk blir den til den indikerte tilleggsidentiteten ved formell substitusjon av tilsvarende antall kombinasjoner uten repetisjoner til venstre og høyre side: Den betraktede gjentakelsesrelasjonen kan brukes til å effektivt bestemme antall kombinasjoner med repetisjoner, når det er viktig å eliminere de arbeidskrevende operasjonene med å beregne faktorielle produkter og erstatte dem med enklere addisjonsoperasjoner. I dette tilfellet, for å beregne verdien av f(n,m), trenger du bare å bruke denne gjentakelsesrelasjonen til du får summen av leddene på formen f(1,m) og f(i,1), der i tar verdier i området fra n til 1. Per definisjon av mengden er slike termer lik henholdsvis 1 og i. Følgende eksempel illustrerer bruken av denne transformasjonsteknikken for tilfellet med n=3 og m=4: LISTING AV BINÆRE KOMBINASJONER Ved implementering av kombinasjoner i maskinvare eller programmering i assemblerspråk er det viktig å kunne behandle kombinasjonsposter i binært format. I dette tilfellet bør enhver kombinasjon av n elementer av m spesifiseres i form av et n-bits binært tall (B n,...B j,...B 1), der m enhetssifre indikerer elementene i kombinasjon, og de resterende (nm) sifrene har nullverdier. Åpenbart, med denne formen for notasjon, må forskjellige kombinasjoner avvike i arrangementet av 1-sifrene, og det er bare C(n,m) måter å arrangere m enere eller (nm) nuller i et n-bit binært sett. For eksempel viser følgende tabell alle 6 slike binære kombinasjoner, som gir 4-bits binære tall for alle kombinasjoner av 4 elementer i et vilkårlig sett (E 1 , E 2 , E 3 , E 4 ) med 2: I det generelle tilfellet kommer oppgaven med å telle opp slike binære kombinasjoner ned til et systematisk søk av alle n-bit binære sett med forskjellige arrangementer av m en og (nm) null biter. I den enkleste formen implementeres en slik oppregning ulike metoder transposisjoner av tilstøtende biter med et skift (transpositive-shift-algoritmer). Dette er iterative algoritmer, og deres navn gjenspeiler arten av operasjonene som utføres på hvert trinn. Iterative prosedyrer for transpositive-shift-algoritmer danner sekvenser av binære kombinasjoner som begynner med et binært sett, der alle er konsentrert i sifrene med lav orden (til høyre), og slutter når alle 1-ene er i sifrene av høy orden ( til venstre): Mens de samsvarer i innledende og endelige kombinasjoner, er disse sekvensene forskjellige i rekkefølgen som mellomliggende binære sett er oppført. I alle tilfeller dannes imidlertid hver påfølgende binær kombinasjon fra den forrige som et resultat av å utføre de tilsvarende transposisjons- og skiftoperasjonene. Samtidig er forskjellige transpositive-shift-algoritmer forskjellige i måten de velger et par biter for transponering og en gruppe biter for å skifte. Denne spesifisiteten er diskutert nedenfor for transposisjonsalgoritmer med venstre og høyre skift. I transposisjonsalgoritmen med et venstreskift, ved hvert trinn, oppnås den neste binære kombinasjonen fra den gjeldende ved å erstatte sifferparet 01 lengst til venstre med 10 (transponering) og forskyve gruppen av ledende enhetssiffer, hvis noen, nær til paret 10 oppnådd etter transposisjonen (skift). Hvis det i dette tilfellet ikke er noen enheter i de ledende sifrene i den gjeldende binære kombinasjonen, foretas ikke skiftet, selv når den ledende enheten er oppnådd etter transponering av dette trinnet. Skiftet utføres heller ikke når det ikke er nuller i de mest signifikante bitene før paret 10 oppnådd etter transposisjonen. De betraktede handlingene er illustrert av følgende eksempel på å utføre to suksessive iterasjoner av denne algoritmen, hvor ved en iterasjon (15) bare transposisjon (T") utføres, og ved den andre iterasjonen (16) blir transposisjonen supplert med et skifte ( T"+S"): I høyreskift-transponeringsalgoritmen utføres konseptuelt lignende trinn ved hvert trinn. Bare transponering sikrer at bitene lengst til høyre av 01 erstattes med 10 (i stedet for de lengst til venstre), og så blir alle bitene til høyre for den forskjøvet til de minst signifikante bitene. Som tidligere utføres skiftet kun hvis det er enheter som kan forskyves til høyre. De betraktede handlingene er illustrert av følgende eksempel på å utføre to påfølgende iterasjoner av denne algoritmen, hvor ved en iterasjon (3) bare transposisjon (T") utføres, og ved den andre iterasjonen (4) blir transposisjonen supplert med et skifte ( T"+S"): Det skal bemerkes at iterasjonene til begge algoritmene kan skrives i additiv form hvis binære kombinasjoner tolkes som heltall i base 2-tallsystemet. Spesielt for transposisjonsalgoritmen med høyre skift, hver neste binære kombinasjon (B" n ,...B" j , ...B" 1), kan alltid hentes fra den gjeldende kombinasjonen (B n,...B j,...B 1) ved å utføre operasjonene med å legge til heltall ved å bruke følgende additive formel: I denne additive formelen betegner eksponentene for potenser av toer f og t henholdsvis antall lavordens nullsiffer i den gjeldende binære kombinasjonen og antall enere på rad til venstre for dem. For eksempel, for den fjerde binære kombinasjonen (001110) av n=6 sifre f =1 og t =3. Derfor vil beregning av neste binære kombinasjon ved å bruke additivformelen ved iterasjon 5 gi følgende resultat, tilsvarende å utføre transposisjons- og skiftoperasjoner: Til komparativ analyse av de betraktede transposisjonsalgoritmene med venstre og høyre skift, er det tilrådelig å sammenligne sekvensene av binære kombinasjoner som de genererer i sine iterasjoner. Følgende tabell viser to slike sekvenser av binære kombinasjoner av 4 elementer av 2, som oppnås av henholdsvis venstre (TSL) og høyre (TSR) skiftalgoritme: Ved å sammenligne disse to sekvensene kan du se at de er omvendt speil. Dette betyr at to binære kombinasjoner som er plassert i dem i samme avstand fra de innbyrdes motsatte ender av sekvensene deres, er et speilbilde av hverandre, det vil si at de faller sammen når indekseringen av bitene i noen av dem reverseres. For eksempel er det andre binære mønsteret fra begynnelsen av TSL-sekvensen (0101) et speilbilde av det binære mønsteret (1010) som er andre fra slutten av TSR-sekvensen. Generelt er enhver binær kombinasjon med nummer i i en sekvens et speilbilde av en binær kombinasjon med nummer (ni+1) i en annen sekvens. Dette forholdet mellom disse sekvensene er en konsekvens av den symmetriske karakteren til transposisjons- og skiftoperasjonene i de to betraktede algoritmene for oppregning av binære kombinasjoner. Det skal bemerkes at det binære formatet også kan brukes til å registrere kombinasjoner med gjentakelser av elementer. For å gjøre dette er det nødvendig å etablere en en-til-en-korrespondanse mellom kombinasjoner med repetisjoner og binære kombinasjoner, som er konstruert som følger. La det være en vilkårlig kombinasjon med repetisjoner, som oppnås ved å velge m valgfritt forskjellige elementer fra de n elementene i generatorsettet. For å etablere ønsket match, må du først legge til alle elementene i formingssettet (katten) til kombinasjonen, og deretter sortere den resulterende sammenkoblingen (sortere) slik at alle identiske elementer er side ved side. Resultatet er en sekvens av (n+m) elementer, der det er n grupper av identiske elementer. Det vil være totalt (n+m1) gap mellom elementer, blant disse vil det være (n1) gap mellom grupper av identiske elementer og m gap mellom elementer innenfor grupper. For klarhet, i angitte intervaller du kan plassere symbolene "|" og tilsvarende. Hvis vi nå matcher 1 med mellomrommene mellom gruppene (|) og 0 til alle andre mellomrom (), får vi en binær kombinasjon. Den er dannet av et binært sett med (n+m1) biter, der (n1) er enere og m nullbiter, hvis plassering unikt tilsvarer den opprinnelige kombinasjonen med repetisjoner av elementene n til m. Den betraktede transformasjonsteknikken er illustrert av følgende eksempel på å konstruere en binær kombinasjon (1001101) ved å bruke en kombinasjon med repetisjoner (BBD), hvis elementer er valgt fra generasjonssettet med de fem første latinske bokstavene: Generelt sett bestemmer antallet slike binære sett antall måter å ordne (n1) enere (eller m nuller) i (n+m1) binære sifre. Denne verdien er åpenbart lik antall kombinasjoner fra (n+m1) med (n1) eller med m, det vil si C(n+m1,n1) eller C(n+m1,m), som er lik antall kombinasjoner med repetisjoner f( n,m) av n elementer, m hver. Å ha en en-til-en korrespondanse mellom kombinasjoner med repetisjoner og binære kombinasjoner, er det legitimt å redusere opptellingen av kombinasjoner med repetisjoner til oppregning av binære kombinasjoner, for eksempel ved å bruke transposisjonsalgoritmer med venstre- eller høyreforskyvning. Etter dette trenger du bare å gjenopprette de nødvendige kombinasjonene med repetisjoner ved å bruke de resulterende binære kombinasjonene. Dette kan alltid gjøres ved å bruke følgende gjenopprettingsteknikk. La hovedsettet, fra elementene hvor kombinasjoner med repetisjoner av m ikke nødvendigvis forskjellige elementer dannes, ordnes på en vilkårlig måte slik at hvert av elementene har et visst serienummer fra 1 til n. La oss også implementere opptellingen av binære kombinasjoner av (n+m1) binære sifre, der (n1) enere og m null sifre. Hver resulterende binær kombinasjon kan suppleres til venstre med et fiktivt enhetssiffer, og alle enhetssiffer kan nummereres fra venstre til høyre med heltall fra 1 til n. Deretter antall nuller på rad etter hver i-te enhet binær kombinasjon vil være lik antall forekomster av det i-te elementet i hovedsettet i den tilsvarende kombinasjonen med repetisjoner. Den betraktede teknikken er illustrert av følgende eksempel, der ved å bruke en binær kombinasjon (1001101) gjenopprettes en kombinasjon med repetisjoner av BBD, hvis elementer er valgt fra generasjonssettet av de fem første latinske bokstavene skrevet i alfabetisk rekkefølge, og overlinjen indikerer elementer som mangler i denne kombinasjonen: Utføre lignende handlinger under forhold dette eksemplet, kan du liste alle de 35 binære kombinasjonene som danner 7-bits binære sett, der det er 4 enere og 3 nuller, og gjenopprette de tilsvarende kombinasjonene med repetisjoner av 5 elementer av 3. I kombinatorikk studerer de spørsmål om hvor mange kombinasjoner av en bestemt type som kan lages av gitte objekter (elementer). Fødselen av kombinatorikk som en gren er assosiert med verkene til B. Pascal og P. Fermat om teorien om gambling. Et stort bidrag til utviklingen av kombinatoriske metoder ble gitt av G.V. Leibniz, J. Bernoulli og L. Euler. Den franske filosofen, forfatteren, matematikeren og fysikeren Blaise Pascal (1623–1662) viste sin fremragende matematiske ferdigheter. Pascals utvalg av matematiske interesser var svært mangfoldig. Pascal beviste én ting Gottfried Wilhelm Leibniz (1646–1716) var en tysk filosof, matematiker, fysiker og oppfinner, advokat, historiker og språkforsker. I matematikk utviklet han sammen med I. Newton differensial- og integralregning. Viktig bidrag bidro til kombinatorikk. Navnet hans er spesielt assosiert med tallteoretiske problemer. Gottfried Wilhelm Leibniz hadde lite imponerende utseende og ga derfor inntrykk av en ganske vanlig person. En dag i Paris gikk han inn i en bokhandel i håp om å kjøpe en bok av en filosof han kjente. Da en besøkende spurte om denne boken, sa bokhandleren, etter å ha undersøkt ham fra topp til tå, hånende: «Hvorfor trenger du den? Er du virkelig i stand til å lese slike bøker?» Før forskeren rakk å svare, gikk forfatteren av boken selv inn i butikken med ordene: "Hilsen og respekt til den store Leibniz!" Selgeren kunne ikke forstå at dette virkelig var den berømte Leibniz, hvis bøker var etterspurt blant forskere. I fremtiden vil følgende spille en viktig rolle Lemma. Slipp inn et sett med elementer, og i et sett - elementer. Da vil antallet av alle distinkte par hvor være lik . Bevis. Med ett element fra et sett kan vi faktisk lage så forskjellige par, og totalt i et sett med elementer. Plasseringer, permutasjoner, kombinasjoner La oss ha et sett med tre elementer. På hvilke måter kan vi velge to av disse elementene? . Definisjon. Arrangementer av et sett av forskjellige elementer etter elementer er kombinasjoner som er bygd opp av gitte elementer av > elementer og er forskjellige enten i elementene selv eller i rekkefølgen på elementene. Antallet alle plasseringer av et sett med elementer etter elementer er angitt med (fra forbokstav fransk ord"arrangement", som betyr plassering), hvor og . Teorem. Antall plasseringer av et sett med elementer etter elementer er lik Bevis. La oss si at vi har elementer. La være mulige plasseringer. Vi vil bygge disse plasseringene sekvensielt. La oss først definere det første plasseringselementet. Fra et gitt sett med elementer kan det velges forskjellige måter. Etter å ha valgt det første elementet, er det fortsatt måter å velge det andre elementet på osv. Siden hvert slikt valg gir en ny plassering, kan alle disse valgene fritt kombineres med hverandre. Derfor har vi: Eksempel. På hvor mange måter kan et flagg være sammensatt av tre horisontale striper? ulike farger, hvis det er materiale med fem farger? Løsning. Det nødvendige antallet tre-bånds flagg: Definisjon. Permutasjon av et sett med elementer er arrangementet av elementer i en bestemt rekkefølge. Dermed er alle forskjellige permutasjoner av et sett med tre elementer Antallet permutasjoner av elementer er angitt (fra den første bokstaven i det franske ordet "permutasjon", som betyr "permutasjon", "bevegelse"). Derfor er antallet av alle ulike permutasjoner beregnet med formelen Eksempel. På hvor mange måter kan tårnene plasseres på sjakkbrettet slik at de ikke angriper hverandre? Løsning. Nødvendig antall tårn A-priory! Definisjon. Kombinasjoner av forskjellige elementer etter elementer er kombinasjoner som er bygd opp av gitte elementer for elementer og avviker i minst ett element (med andre ord -elementdelmengder av et gitt sett med elementer). Som du kan se, i kombinasjoner, i motsetning til plasseringer, tas det ikke hensyn til rekkefølgen på elementene. Antallet av alle kombinasjoner av elementer, elementer i hver, er angitt (fra den første bokstaven i det franske ordet "kombinasjon", som betyr "kombinasjon"). Tall Alle kombinasjoner fra et sett på to er . Egenskaper for tall (\sf C)_n^k Faktisk tilsvarer hvert -element-undersett av et gitt -elementsett én og bare ett -element-undersett av det samme settet. Faktisk kan vi velge undersett av elementer på følgende måte: fikse ett element; antall -element undersett som inneholder dette elementet er lik ; antall -element-delsett som ikke inneholder dette elementet er lik . Pascals trekant I denne trekanten er de ekstreme tallene i hver rad lik 1, og hvert ikke-ekstreme tall er lik summen av de to tallene over den fra forrige rad. Dermed lar denne trekanten deg beregne tall. Teorem. Bevis. La oss vurdere et sett med elementer og løse følgende problem på to måter: hvor mange sekvenser kan lages fra elementene i en gitt 1 vei. Vi velger det første medlemmet av sekvensen, deretter det andre, tredje osv. medlem Metode 2. La oss først velge elementer fra et gitt sett, og deretter ordne dem i en eller annen rekkefølge Multipliser telleren og nevneren til denne brøken med: Eksempel. På hvor mange måter kan du velge 5 tall av 36 i spillet "Sportloto"? Nødvendig antall måter Oppgaver. 1.
Bilskilt består av 3 bokstaver i det russiske alfabetet (33 bokstaver) og 4 tall. Hvor mange forskjellige skiltnummer er det? Partisjoner betraktes som forskjellige hvis de er forskjellige enten i antall eller i rekkefølgen på vilkårene. Hvor mange forskjellige partisjoner av et tall i termer er det? Antall kombinasjoner Kombinasjon fra n Av k kalt et sett k elementer valgt fra data n elementer. Sett som bare avviker i rekkefølgen på elementene (men ikke i sammensetning) anses som identiske, dette er grunnen til at kombinasjoner er forskjellige fra plasseringer. Antall kombinasjoner av n Av k
lik binomial koeffisient For en fast verdi n generere funksjon av antall kombinasjoner med repetisjoner fra n Av k er: Den todimensjonale genereringsfunksjonen til antall kombinasjoner med repetisjoner er: Wikimedia Foundation. 2010. 70 sytti 67 68 69 70 71 72 73 40 50 60 70 80 90 100 Faktorisering: 2×5×7 romersk notasjon: LXX Binær: 100 0110 ... Wikipedia Lett tall, et betinget tall som unikt uttrykker det ytre forhold under fotografering (vanligvis lysstyrken til motivet og fotosensitiviteten til det fotografiske materialet som brukes). Enhver verdi av E. h kan velges flere ganger. kombinasjoner blenderåpning nummer ... ... Big Encyclopedic Polytechnic Dictionary En tallform som skiller to objekter både i forhold til et enkelt objekt og i forhold til mange objekter. Denne formen eksisterer ikke i moderne russisk, men det gjenstår rester av dens innflytelse. Så kombinasjoner av to tabeller (jf. flertall... ... Ordbok over språklige termer Kombinatorisk matematikk, kombinatorikk, en gren av matematikk viet til å løse problemer med å velge og arrangere elementer av et visst, vanligvis begrenset, sett i samsvar med gitte regler. Hver slik regel bestemmer konstruksjonsmetoden ... ... Matematisk leksikon I kombinatorikk er en kombinasjon av by et sett med elementer valgt fra et gitt sett som inneholder forskjellige elementer. Sett som bare avviker i rekkefølgen på elementene (men ikke i sammensetning) anses som identiske, disse kombinasjonene ... ... Wikipedia Engasjert i studiet av hendelser hvis forekomst ikke er kjent med sikkerhet. Det lar oss bedømme rimeligheten av å forvente at noen hendelser inntreffer sammenlignet med andre, selv om attribusjonen numeriske verdier sannsynligheter for hendelser er ofte unødvendig... ... Colliers leksikon 1) det samme som matematisk kombinatorisk analyse. 2) En del av elementær matematikk assosiert med studiet av antall kombinasjoner, underlagt visse betingelser, som kan komponeres fra et gitt begrenset sett med objekter ... ... Stor Sovjetisk leksikon
- (greske paradokser uventet, merkelig) i i vid forstand: et utsagn som avviker kraftig fra allment akseptert, etablert oppfatning, en fornektelse av det som fremstår som «ubetinget riktig»; i en snevrere forstand, to motstridende utsagn, for... ... Filosofisk leksikon - (eller prinsippet om inkluderinger og ekskluderinger) en kombinatorisk formel som lar deg bestemme kraften til en kombinasjon endelig antall endelige mengder, som generelt kan krysse hverandre ... Wikipedia En matematisk teori opptatt av å bestemme antall forskjellige måter å distribuere gitte objekter i en kjent rekkefølge; er spesielt viktig i likningsteori og sannsynlighetsteori. De enkleste oppgavene av denne typen er... ... encyklopedisk ordbok F. Brockhaus og I.A. Efron I denne artikkelen vi vil snakke om en spesiell gren av matematikken kalt kombinatorikk. Formler, regler, eksempler på problemløsning – alt dette finner du her ved å lese artikkelen helt til slutt. Så hva er denne delen? Kombinatorikk tar for seg spørsmålet om å telle objekter. Men i i dette tilfellet gjenstandene er ikke plommer, pærer eller epler, men noe annet. Kombinatorikk hjelper oss å finne sannsynligheten for en hendelse. For eksempel når man spiller kort – hva er sannsynligheten for at motstanderen har et trumfkort? Eller dette eksemplet: hva er sannsynligheten for at du får en hvit fra en pose med tjue klinkekuler? Det er for denne typen problemer vi trenger å vite i det minste det grunnleggende om denne grenen av matematikk. Med tanke på spørsmålet om grunnleggende konsepter og formler for kombinatorikk, kan vi ikke unngå å ta hensyn til kombinatoriske konfigurasjoner. De brukes ikke bare til å formulere, men også til å løse ulike eksempler slike modeller er: Vi vil snakke om de tre første mer detaljert senere, men vi vil ta hensyn til komposisjon og partisjonering denne seksjonen. Når de snakker om sammensetningen av et bestemt tall (for eksempel a), mener de representasjonen av tallet a i form av en ordnet sum av visse positive tall. Og en skillevegg er en uordnet sum. Før vi går direkte til kombinatoriske formler og vurdering av problemer, er det verdt å være oppmerksom på det faktum at kombinatorikk, som andre grener av matematikken, har sine egne underseksjoner. Disse inkluderer: I det første tilfellet vi snakker om om kalkulativ kombinatorikk vurderer problemer oppregning eller telling av forskjellige konfigurasjoner som er dannet av elementene i sett. Som regel er det pålagt noen begrensninger for disse settene (særpreg, umulig å skille, mulighet for repetisjon og så videre). Og antallet av disse konfigurasjonene beregnes ved å bruke reglene for addisjon eller multiplikasjon, som vi vil snakke om litt senere. Strukturell kombinatorikk inkluderer teoriene om grafer og matroider. Et eksempel på et ekstremt kombinatorisk problem er hva som er den største dimensjonen til en graf som tilfredsstiller følgende egenskaper... I fjerde avsnitt nevnte vi Ramsey-teorien, som studerer tilstedeværelsen i tilfeldige konfigurasjoner vanlige strukturer. Probabilistisk kombinatorikk er i stand til å svare på spørsmålet - hva er sannsynligheten for at et gitt sett har bestemt eiendom. Som du kanskje gjetter, topologisk kombinatorikk anvender metoder innen topologi. Og til slutt, det syvende punktet - infinitær kombinatorikk studerer anvendelsen av kombinatoriske metoder på uendelige sett. Blant kombinatoriske formler kan du finne ganske enkle, som vi har vært kjent med ganske lenge. Et eksempel er sumregelen. Anta at vi får to handlinger (C og E), hvis de er gjensidig utelukkende, kan handling C utføres på flere måter (for eksempel a), og handling E kan utføres på b-veier, så kan hvilken som helst av dem ( C eller E) kan utføres på a + b måter. I teorien er dette ganske vanskelig å forstå, vi skal prøve å formidle hele poenget ved hjelp av et enkelt eksempel. La oss ta gjennomsnittlig antall elever i en klasse – la oss si at det er tjuefem. Blant dem er femten jenter og ti gutter. En person på vakt er tildelt hver klasse hver dag. Hvor mange måter er det å utnevne en klassemonitor i dag? Løsningen på problemet er ganske enkel vi vil ty til tilleggsregelen. Oppgaveteksten sier ikke at bare gutter eller bare jenter kan være på vakt. Derfor kan det være hvilken som helst av de femten jentene eller hvilken som helst av de ti guttene. Ved å bruke sumregelen får vi et ganske enkelt eksempel som et skolebarn lett kan håndtere primærklasser: 15 + 10. Etter telling får vi svaret: tjuefem. Det vil si at det bare er tjuefem måter å tildele en klasse på vakt for i dag. De grunnleggende formlene for kombinatorikk inkluderer også multiplikasjonsregelen. La oss starte med teorien. La oss si at vi må utføre flere handlinger (a): den første handlingen utføres på 1 måter, den andre - på 2 måter, den tredje - på 3 måter, og så videre til siste a-handling, utført på samme måter. Da kan alle disse handlingene (som vi har totalt) utføres på N måter. Hvordan beregne ukjent N? Formelen vil hjelpe oss med dette: N = c1 * c2 * c3 *...* ca. Igjen, ingenting er klart i teorien, la oss gå videre til vurdering enkelt eksempelå bruke multiplikasjonsregelen. La oss ta den samme klassen på tjuefem personer, der det er femten jenter og ti gutter. Bare denne gangen må vi velge to personer på vakt. De kan enten være gutter eller jenter, eller en gutt og en jente. La oss gå videre til den elementære løsningen av problemet. Vi velger den første personen på vakt, som vi bestemte i siste avsnitt, får vi tjuefem mulige alternativer. Den andre personen på vakt kan være hvilken som helst av de gjenværende personene. Vi hadde tjuefem studenter, vi valgte én, noe som betyr at den andre personen på vakt kan være hvilken som helst av de resterende tjuefire personene. Til slutt bruker vi multiplikasjonsregelen og finner at to tjenestemenn på vakt kan velges på seks hundre måter. Vi fikk dette tallet ved å multiplisere tjuefem og tjuefire. Nå skal vi se på en annen kombinatorisk formel. I denne delen av artikkelen vil vi snakke om permutasjoner. Vi foreslår å umiddelbart vurdere problemet ved å bruke et eksempel. La oss ta biljardballer, vi har n-te nummer av dem. Vi må beregne hvor mange alternativer det er for å ordne dem på rad, det vil si å lage et bestilt sett. La oss begynne, hvis vi ikke har baller, så har vi også null alternativer for plassering. Og hvis vi har én kule, så er også arrangementet det samme (matematisk kan dette skrives slik: P1 = 1). De to ballene kan plasseres på to forskjellige måter: 1,2 og 2,1. Derfor er P2 = 2. Tre kuler kan ordnes på seks måter (P3 = 6): 1,2,3; 1,3,2; 2,1,3; 2,3,1; 3,2,1; 3,1,2. Hva om det ikke er tre slike baller, men ti eller femten? List opp alt mulige alternativer i veldig lang tid, så kommer kombinatorikk til unnsetning. Permutasjonsformelen vil hjelpe oss å finne svaret på spørsmålet som interesserer oss. Pn = n *P (n-1). Hvis vi prøver å forenkle formelen, får vi: Pn = n* (n - 1) *...* 2 * 1. Og dette er produktet av de første naturlige tallene. Dette tallet kalles faktorielt, og er betegnet som n! La oss vurdere problemet. Hver morgen stiller rådgiveren opp i troppen sin (tjue personer). Det er tre i troppen bestevenn- Kostya, Sasha og Lesha. Hva er sannsynligheten for at de står ved siden av hverandre? For å finne svaret på spørsmålet må du dele sannsynligheten for et "godt" utfall på det totale antallet utfall. Totalt antall permutasjoner er 20! = 2,5 kvintillioner. Hvordan telle antall "gode" utfall? La oss anta at Kostya, Sasha og Lesha er en supermann. Da har vi bare atten fag. Antall permutasjoner i dette tilfellet er 18 = 6,5 kvadrillioner. Med alt dette kan Kostya, Sasha og Lesha vilkårlig bevege seg mellom seg i sine udelelige tre, og det er 3 til! = 6 alternativer. Det betyr at vi har 18 «gode» arrangementer totalt! *3! Alt vi trenger å gjøre er å finne ønsket sannsynlighet: (18! * 3!) / 20! Som tilsvarer omtrent 0,016. Omregnet til prosenter viser det seg å være bare 1,6 %. Nå skal vi se på en annen veldig viktig og nødvendig kombinatorisk formel. Plassering er vår neste utgave, som vi inviterer deg til å vurdere i denne delen av artikkelen. Vi går for komplikasjoner. Anta at vi ønsker å vurdere mulige permutasjoner, ikke fra hele settet (n), men fra en mindre (m). Det vil si at vi vurderer permutasjoner av n elementer med m. De grunnleggende formlene for kombinatorikk bør ikke bare huskes, men forstås. Selv om de blir mer kompliserte, siden vi ikke har én parameter, men to. Anta at m = 1, så A = 1, m = 2, så A = n * (n - 1). Hvis vi forenkler formelen ytterligere og går over til notasjon ved hjelp av faktorialer, vil vi få en helt lakonisk formel: A = n! / (n - m)! Vi gjennomgikk nesten alle de grunnleggende kombinatoriske formlene med eksempler. La oss nå gå videre til sluttfasen av å vurdere det grunnleggende kombinatorikkkurset - bli kjent med kombinasjoner. Nå skal vi velge m varer fra den n vi har, og vi skal velge alle mulige måter. Hvordan er dette forskjellig fra plassering? Vi vil ikke ta hensyn til bestillingen. Dette uordnede settet vil være en kombinasjon. La oss umiddelbart introdusere notasjonen: C. Vi tar plasseringen av m kuler ut av n. Vi slutter å ta hensyn til orden og ender opp med gjentatte kombinasjoner. For å få antall kombinasjoner må vi dele antall plasseringer på m! (m faktoriell). Det vil si C = A/m! Dermed er det bare noen få måter å velge mellom n baller på, som er omtrent lik antall måter å velge nesten alle på. Dette har logisk uttrykk: å velge litt er det samme som å kaste ut nesten alt. Det er også viktig å nevne på dette punktet maksimalt antall kombinasjoner kan oppnås ved å prøve å velge halvparten av elementene. Vi undersøkte i detalj de grunnleggende formlene for kombinatorikk: plassering, permutasjon og kombinasjon. Nå er vår oppgave å gjøre valget enklere nødvendig formelå løse et kombinatorisk problem. Du kan bruke følgende ganske enkle skjema: Vi så på elementer av kombinatorikk, formler og noen andre problemstillinger. La oss nå gå videre til å vurdere det virkelige problemet. Tenk deg at du har en kiwi, en appelsin og en banan foran deg. Spørsmål én: på hvor mange måter kan de omorganiseres? For å gjøre dette bruker vi permutasjonsformelen: P = 3! = 6 måter. Spørsmål to: på hvor mange måter kan du velge én frukt? Dette er åpenbart, vi har bare tre alternativer - velg kiwi, appelsin eller banan, men la oss bruke kombinasjonsformelen: C = 3! / (2! * 1!) = 3. Spørsmål tre: på hvor mange måter kan du velge to frukter? Hvilke alternativer har vi til og med? Kiwi og appelsin; kiwi og banan; appelsin og banan. Det vil si at det er tre alternativer, men dette er enkelt å sjekke ved hjelp av kombinasjonsformelen: C = 3! / (1! * 2!) = 3 Spørsmål fire: På hvor mange måter kan du velge tre frukter? Som du kan se, er det bare én måte å velge tre frukter på: ta kiwi, appelsin og banan. C = 3! / (0! * 3!) = 1. Spørsmål fem: på hvor mange måter kan du velge minst én frukt? Denne tilstanden betyr at vi kan ta en, to eller alle tre fruktene. Derfor legger vi til C1 + C2 + C3 = 3 + 3 + 1 = 7. Det vil si at vi har syv måter å ta minst én frukt fra bordet på. La oss telle i MS EXCEL antall kombinasjoner av n elementer med k. Ved å bruke formler viser vi alle kombinasjonsalternativer på arket ( engelsk oversettelse begrep: Kombinasjoner uten repetisjon). Kombinasjoner av n forskjellige elementer av k elementer er kombinasjoner som er forskjellige i minst ett element. Nedenfor er for eksempel ALLE 3-elementkombinasjoner hentet fra et sett bestående av 5 elementer (1; 2; 3; 4; 5): (1; 2; 3); (1; 2; 4); (1; 2; 5); (1; 3; 4); (1; 3; 5); (1; 4; 5); (2; 3; 4); (2; 3; 5); (2; 4; 5); (3; 4; 5) Merk: Dette er en artikkel om å telle antall kombinasjoner med MS EXCEL. Teoretisk grunnlag Vi anbefaler å lese den i en spesialisert lærebok. Å lære kombinasjoner fra denne artikkelen er en dårlig idé. I eksempelfilen lages formler for å vise alle kombinasjoner for gitte n og k. Ved å spesifisere antall elementer i settet (n) og antall elementer som vi velger fra det (k), ved å bruke formler kan vi vise alle kombinasjoner. En biltransporter kan frakte 4 biler. Det er nødvendig å transportere 7 forskjellige biler (LADA Granta, Hyundai Solaris, KIA Rio, Renault Duster, Lada Kalina, Volkswagen Polo, Lada Largus). På hvor mange forskjellige måter kan den første biltransportøren fylles? Den spesifikke plasseringen av bilen i biltransporteren er ikke viktig. Vi må bestemme antallet Kombinasjoner 7 biler på 4 plasser av en biltransporter. De. n=7 og k=4. Det viser seg at det er 35 slike alternativer =NUMBERCOMB(7,4).
fra de grunnleggende teoremer for projektiv geometri (Pascals teorem), designet en summeringsmaskin (Pascals adderingsmaskin), ga en metode for å beregne binomiale koeffisienter (Pascals trekant), var den første som nøyaktig definerte og anvendte metoden for bevis matematisk induksjon, gjorde et betydelig skritt i utviklingen av infinitesimal analyse, spilte viktig rolle i opprinnelsen til sannsynlighetsteori. I hydrostatikk etablerte Pascal sin grunnleggende lov (Pascals lov). Pascals "Letters to a Provincial" var et mesterverk av fransk klassisk prosa.
sett i hver av dem som ingen element vises to ganger?
2.
Det er 88 tangenter på pianoet. På hvor mange måter kan du produsere 6 lyder etter hverandre?
3.
Hvor mange sekssifrede tall er det som er delbare med 5?
4.
På hvor mange måter kan 7 forskjellige mynter plasseres i tre lommer?
5.
Hvor mange femsifrede tall kan du lage som har sifferet 5 minst én gang i desimalnotasjonen?
6.
På hvor mange måter kan 20 personer sitte? rundt bord, vurderer metodene de samme hvis de kan oppnås fra hverandre ved å bevege seg i en sirkel?
7.
Hvor mange femsifrede tall er det som er delbare med 5 og ikke inneholder identiske sifre?
8.
På rutete papir med en celleside på 1 cm tegnes en sirkel med radius 100 cm som ikke går gjennom toppen av cellene og ikke berører sidene av cellene. Hvor mange celler kan denne sirkelen skjære?
9.
På hvor mange måter kan tall ordnes på rad slik at tallene er tilstøtende og i stigende rekkefølge?
10.
Hvor mange femsifrede tall kan lages av sifre hvis hvert siffer bare kan brukes én gang?
11.
Fra ordet ROT, ved å omorganisere bokstavene, kan du få følgende ord: TOP, ORT, OTR, TRO, RTO. De kalles anagrammer. Hvor mange anagrammer kan du lage av ordet LOGARITME?
12.
La oss ringe splitting naturlig tall, dets representasjon som en sum av naturlige tall. Her er for eksempel alle partisjonene til et tall:
13.
Hvor mange finnes tresifrede tall med ikke-økende rekkefølge av sifre?
14.
Hvor mange firesifrede tall er det med ikke-økende tallrekkefølge?
15.
På hvor mange måter kan 17 personer sitte på rad slik at de havner side om side?
16.
jenter og gutter sitter tilfeldig på en seterad. På hvor mange måter kan de sitte slik at ikke to jenter sitter ved siden av hverandre?
17.
jenter og gutter sitter tilfeldig på en seterad. På hvor mange måter kan de sitte slik at alle jentene sitter ved siden av hverandre?Eksplisitte formler
Linker
Se hva "Antall kombinasjoner" er i andre ordbøker:
Bøker
Kombinatoriske konfigurasjoner
Seksjoner
Tilleggsregel
Multiplikasjonsregel
Omorganisering
Overnatting
Kombinasjon
Hvordan velge en formel for å løse et problem?
Eksempel
Forskjellen mellom kombinasjoner og plasseringer
Viser alle kombinasjoner av kombinasjoner
Oppgave