Si të gjeni numrin e opsioneve të mundshme. Kombinimet me përsëritje të elementeve

Vendi i parë në një rresht mund të jetë cilido nga N elementët, prandaj, ekzistojnë N opsione. Në vendin e dytë - çdo, përveç atij që tashmë është përdorur për vendin e parë. Prandaj, për secilën prej N opsioneve të gjetura tashmë, ka (N - 1) opsione të vendit të dytë, dhe numri i përgjithshëm i kombinimeve bëhet N*(N - 1).
E njëjta gjë mund të përsëritet për elementët e mbetur të serisë. Për vendin e fundit, ka mbetur vetëm një opsion - elementi i fundit i mbetur. Për të parafundit ka dy opsione, e kështu me radhë.
Prandaj, për një seri N elementësh jopërsëritës, permutacionet e mundshme janë të barabarta me prodhimin e të gjithë numrave të plotë nga 1 në N. Ky produkt quhet N dhe N! (lexo "en factorial").

Në rastin e mëparshëm, sasia elementet e mundshme dhe numri i vendeve në rresht përkonte dhe numri i tyre ishte i barabartë me N. Por një situatë është e mundur kur ka më pak vende në rresht se sa ka elementë të mundshëm. Me fjalë të tjera, numri i elementeve në mostër është i barabartë me një numër të caktuar M, dhe M< N. В этом случае задача определения возможных комбинаций может иметь два различных варианта.
Së pari, mund t'ju duhet të numëroni numrin total mënyrat e mundshme, i cili mund të përdoret për të rregulluar M elemente nga N në një rresht.
Së dyti, studiuesi mund të interesohet për numrin e mënyrave në të cilat elementet M mund të zgjidhen nga N. Në këtë rast, rendi i elementeve nuk është më i rëndësishëm, por çdo dy opsione duhet të ndryshojnë nga njëri-tjetri për të paktën një element. . Metoda të tilla quhen kombinime.

Për të gjetur numrin e vendosjeve të elementeve M jashtë N, mund të përdorni të njëjtën metodë arsyetimi si në rastin e permutacioneve. Mund të ketë ende N elementë në radhë të parë, N - 1 në vendin e dytë, e kështu me radhë. Por për vendin e fundit, numri i opsioneve të mundshme nuk është i barabartë me një, por (N - M + 1), pasi kur të përfundojë vendosja, do të ketë ende (N - M) elementë të papërdorur.
Kështu, numri i vendosjeve të elementeve M nga N është i barabartë me prodhimin e të gjithë numrave të plotë nga (N - M + 1) në N, ose, sa është i njëjtë, herësi N!/(N - M)!.

Natyrisht, numri i kombinimeve të elementeve M nga N do të jetë më i vogël se numri i vendosjeve. Për çdo kombinim të mundshëm ka një M! vendosjet e mundshme në varësi të renditjes së elementeve të këtij kombinimi. Prandaj, për të gjetur këtë sasi, duhet të ndani numrin e vendosjeve të elementeve M nga N me N!. Me fjalë të tjera, numri i kombinimeve të elementeve M nga N është i barabartë me N!/(M!*(N - M)!).

Burimet:

numri i kombinimeve

Faktorial një numër natyror është prodhimi i të gjithë numrave natyrorë të mëparshëm, duke përfshirë edhe vetë numrin. Faktorial zero është e barabartë me një. Duket se llogaritja e faktorialit të një numri është shumë e thjeshtë - mjafton të shumëzosh të gjithë numrat natyrorë që nuk e kalojnë atë të dhënë. Sidoqoftë, vlera e faktorialit rritet aq shpejt sa që disa kalkulatorë nuk mund ta përballojnë këtë detyrë.

Do t'ju duhet

kalkulator, kompjuter

Udhëzimet

Për të llogaritur faktorialin e një numri natyror, shumëzoni të gjitha, duke mos e tejkaluar atë të dhënë. Çdo numër numërohet vetëm një herë. Në formën e një formule, kjo mund të shkruhet si më poshtë: n! = 1*2*3*4*5*…*(n-2)*(n-1)*n, ku n është një numër natyror faktoriali i të cilit duhet të llogaritet.
0! merret si një (0!=1) Me rritjen e argumentit, vlera e faktorialit rritet shumë shpejt, kështu që ai i zakonshëm (kontabël), tashmë për një faktorial prej 15, mund të japë një gabim në vend të një). rezultat.

Për të llogaritur faktorialin e një numri të madh natyror, merrni një kalkulator inxhinierik. Kjo do të thotë, një kalkulator i tillë në tastierë ka simbole të funksioneve matematikore (cos, sin, √). Shkruani numrin origjinal në kalkulator dhe më pas klikoni butonin faktorial. Zakonisht një buton si "n!" ose në mënyrë të ngjashme (në vend të "n" mund të ketë "N" ose "x", por pikëçuditja "!" në përcaktimin e faktorialit duhet të jetë e pranishme në çdo rast).
Në vlera të mëdha Argumenti, rezultatet e llogaritjes fillojnë të shfaqen në formën "eksponenciale" (eksponenciale). Kështu, për shembull, një faktorial prej 50 do të përfaqësohej në formën: 3.0414093201713378043612608166065e+64 (ose të ngjashme). Për të marrë rezultatin e llogaritjeve në formën e zakonshme, shtoni aq zero në numrin e treguar përpara simbolit "e" siç tregohet pas "e+" (nëse, sigurisht, ka hapësirë të mjaftueshme).

Ne ndonjëherë bëjmë një zgjedhje nga shumë pa marrë parasysh porosinë. Kjo zgjedhje quhet kombinim . Nëse luani letra, për shembull, e dini se në shumicën e situatave rendi në të cilin i mbani letrat nuk ka rëndësi.

Shembulli 1 Gjeni të gjitha kombinimet e 3 shkronjave të marra nga një grup prej 5 shkronjash (A, B, C, D, E).

Zgjidhje Këto kombinime janë si më poshtë:
(A, B, C), (A, B, D),
(A, B, E), (A, C, D),
(A, C, E), (A, D, E),
(B, C, D), (B, C, E),
(B, D, E), (C, D, E).
Ka 10 kombinime të tre shkronjave të zgjedhura nga pesë shkronja.

Kur gjejmë të gjitha kombinimet nga një grup me 5 objekte, nëse marrim 3 objekte në të njëjtën kohë, gjejmë të gjitha nëngrupet me 3 elementë. Në këtë rast, rendi i objekteve nuk merret parasysh. Pastaj,
(A, C, B) quhet e njëjta bashkësi si (A, B, C).

Nëngrupi
Një grup A është një nëngrup i B, që do të thotë se A është një nëngrup i dhe/ose i njëjtë me B nëse çdo element i A është një element i B.

Elementet e nëngrupit nuk janë të renditur. Kur merren parasysh kombinimet, rendi nuk merret parasysh!

Kombinimi
Kombinim, që përmban k objekte është një nëngrup i përbërë nga k objekte.

Ne duam të shkruajmë një formulë për llogaritjen e numrit të kombinimeve të n objekteve nëse k objekte merren në të njëjtën kohë.

Emërtimet e kombinimit
Numri i kombinimeve të n objekteve, nëse k objekte merren njëkohësisht, shënohet n C k .

Ne e quajmë n C k numri i kombinimeve . Ne duam të shkruajmë një formulë të përgjithshme për n C k për çdo k ≤ n. Së pari, është e vërtetë që n C n = 1, sepse një grup me n elementë ka vetëm një nëngrup me n elementë, që është vetë bashkësia. Së dyti, n C 1 = n sepse një grup me n elementë ka vetëm n nënbashkësi me nga 1 element secila. Së fundi, n C 0 = 1 sepse një bashkësi me n elementë ka vetëm një nëngrup me 0 elemente, pra bashkësinë boshe ∅. Për të parë kombinimet e tjera, le të kthehemi te Shembulli 1 dhe të krahasojmë numrin e kombinimeve me numrin e permutacioneve.

Ju lutemi vini re se çdo kombinim i 3 elementeve ka 6, ose 3!, permutacione.
3! . 5 C 3 = 60 = 5 P 3 = 5. 4. 3,
pra
.
Në përgjithësi, numri i kombinimeve të k elementeve të zgjedhur nga n objekte, n C k herë permutacionet e këtyre elementeve k!, duhet të jetë i barabartë me numrin e permutacioneve të n elementeve sipas k elementeve:
k!. n C k = n P k
n C k = n P k /k!
n C k = (1/k!). n P k
n C k =

Kombinimet e k objekteve nga n objekte
Numri i përgjithshëm i kombinimeve të k elementeve nga n objekte shënohet me n C k , i përcaktuar me
(1) n C k = ,
ose
(2) n C k =

Një lloj tjetër shënimi për n C k është koeficienti binom . Arsyeja për këtë terminologji do të bëhet e qartë më poshtë.

Koeficienti binominal

Shembulli 2 Llogaritni duke përdorur formulat (1) dhe (2).

Zgjidhje
a) Sipas (1),
.
b) Sipas (2),

Mbani në mend se n/k nuk do të thotë.

Shembulli 3 Llogaritni dhe .

Zgjidhje Ne përdorim formulën (1) për shprehjen e parë dhe formulën (2) për të dytën. Pastaj
,
duke përdorur (1), dhe
,
duke përdorur formulën (2).

vini re se
,
dhe duke përdorur rezultatin e shembullit 2 na jep
.
Nga kjo rrjedh se numri i një nëngrupi 5-elementësh të një grupi prej 7 elementësh është i njëjtë me numrin e një nëngrupi 2-elementësh të një grupi prej 7 elementësh. Kur zgjidhen 5 elementë nga një grup, ato nuk përfshijnë 2 elementë. Për ta parë këtë, merrni parasysh grupin (A, B, C, D, E, F, G):

Në përgjithësi, ne kemi sa vijon. Ky rezultat jep mënyrë alternative llogaritjet e kombinimit.

Nëngrupe të madhësisë k dhe madhësisë
dhe n C k = n C n-k
Numri i nëngrupeve me madhësi k të një grupi me n objekte është i njëjtë me numrin e nëngrupeve të madhësisë n - k Numri i kombinimeve të k objekteve nga një grup prej n objektesh është i njëjtë me numrin e kombinimeve të n. objektet e marra në të njëjtën kohë.

Tani do të zgjidhim problemet me kombinime.

Shembulli 4 Lotaria e Miçiganit. Lotaria dy herë në javë e Miçiganit WINFALL ka një çmim të parë prej të paktën 2 milionë dollarë. Për një dollar, një lojtar mund të kalojë çdo 6 numra nga 1 në 49. Nëse këta numra përputhen me ato të hedhura në llotari, lojtari fiton. (

Numri i kombinimeve

Kombinimi nga n Nga k quajtur një grup k elementet e zgjedhur nga të dhënat n elementet. Kompletet që ndryshojnë vetëm në renditjen e elementeve (por jo në përbërje) konsiderohen identike, kjo është arsyeja pse kombinimet ndryshojnë nga vendosjet.

Formula eksplicite

Numri i kombinimeve të n Nga k e barabartë me koeficientin binomial

Për një vlerë fikse n funksioni gjenerues i numrave të kombinimeve me përsëritje nga n Nga kështë:

Funksioni gjenerues dydimensional i numrave të kombinimeve me përsëritje është:

Lidhjet

R. Stanley Kombinatorika numerative. - M.: Mir, 1990.
Llogaritni numrin e kombinimeve në internet

Fondacioni Wikimedia.

2010.

Shihni se çfarë është "Numri i kombinimeve" në fjalorë të tjerë:

70 shtatëdhjetë 67 68 69 70 71 72 73 40 50 60 70 80 90 100 Faktorizimi: 2×5×7 Shënimi romak: LXX Binar: 100 0110 … Wikipedia Numër i lehtë, një numër i kushtëzuar që shpreh në mënyrë unike të jashtmen kushtet gjatë fotografimit (zakonisht shkëlqimi i subjektit dhe fotosensitiviteti i materialit fotografik të përdorur). Çdo vlerë e E. h mund të zgjidhet disa herë. kombinime numri i diafragmës... ...

Fjalori i madh enciklopedik politeknik Fjalor i termave gjuhësor

Matematika kombinatorike, kombinatorika, një degë e matematikës kushtuar zgjidhjes së problemeve të zgjedhjes dhe rregullimit të elementeve të një grupi të caktuar, zakonisht të fundëm, në përputhje me rregullat e dhëna. Çdo rregull i tillë përcakton mënyrën e ndërtimit... ... Enciklopedia Matematikore

Në kombinatorikë, një kombinim i by është një grup elementësh të zgjedhur nga një grup i caktuar që përmban elementë të ndryshëm. Kompletet që ndryshojnë vetëm në renditjen e elementeve (por jo në përbërje) konsiderohen identike, këto kombinime ... ... Wikipedia

Angazhohet në studimin e ngjarjeve, ndodhja e të cilave nuk dihet me siguri. Na lejon të gjykojmë arsyeshmërinë e pritjes së ndodhjes së disa ngjarjeve në krahasim me të tjerat, megjithëse caktimi i vlerave numerike për probabilitetet e ngjarjeve është shpesh i panevojshëm... ... Enciklopedia e Collier

1) njëlloj si analiza kombinuese matematikore. 2) Seksioni matematikë elementare e lidhur me studimin e numrit të kombinimeve që i nënshtrohen kushteve të caktuara që mund të përbëhen nga një grup i caktuar i caktuar objektesh... ... Enciklopedia e Madhe Sovjetike

- (Greqisht paradokse të papritura, të çuditshme) në një kuptim të gjerë: një deklaratë që ndryshon ashpër nga opinioni i pranuar përgjithësisht, i vendosur, një mohim i asaj që duket "e saktë pa kushte"; në një kuptim më të ngushtë, dy deklarata të kundërta, për... ... Enciklopedia Filozofike

- (ose parimi i përfshirjeve dhe përjashtimeve) një formulë kombinuese që ju lejon të përcaktoni kardinalitetin e bashkimit të një numri të fundëm grupesh të fundme, të cilat në rastin e përgjithshëm mund të kryqëzohen me njëra-tjetrën ... Wikipedia

Teoria matematikore që merret me përcaktimin e numrit në mënyra të ndryshme shpërndarja e këtyre artikujve sipas një radhe të njohur; është veçanërisht e rëndësishme në teorinë e ekuacioneve dhe teorinë e probabilitetit. Detyrat më të thjeshta të këtij lloji janë... ... Fjalor Enciklopedik F. Brockhaus dhe I.A. Efroni

librat

Numri i fatit. Horoskopi i përputhshmërisë. Dëshirat. Pasioni. Fantazitë (numri i vëllimeve: 3), Mayer Maxim. Numri i fatit. Si të bëni një parashikim numerologjik individual.

Një kombinim është një përzgjedhje e parregulluar e elementeve të një grupi të fundëm me një numër fiks dhe pa përsëritje të elementeve. Kombinimet e ndryshme duhet të ndryshojnë në të paktën një element, dhe rendi i elementeve nuk ka rëndësi. Për shembull, nga grupi i të gjitha zanoreve të shkronjave latine (AEIOU), mund të bëni 10 kombinime të ndryshme prej 3 shkronjash, duke formuar treshe të parregulluara të mëposhtme:

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

Është interesante të theksohet se nga të njëjtat pesë shkronja mund të merrni edhe 10 kombinime të ndryshme nëse i kombinoni 2 shkronja në të njëjtën kohë, duke bërë çiftet e mëposhtme të pa renditura:

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

Sidoqoftë, nëse kombinoni të njëjtat zanore shkronja latine me 4, do të merrni vetëm 5 kombinimet e mëposhtme të ndryshme:

AEIO, AEIU, AIOU, EIOU, AEOU.

Në përgjithësi, për të treguar numrin e kombinimeve të n elementeve të ndryshëm të m elementeve, përdoret simbolika e mëposhtme funksionale, treguese ose vektoriale (Appel):

Pavarësisht nga forma e shënimit, numri i kombinimeve të n elementeve me m element mund të përcaktohet duke përdorur formulat e mëposhtme shumëzuese dhe faktoriale:

Është e lehtë të kontrollohet nëse rezultati i llogaritjeve duke përdorur këto formula përkon me rezultatet e shembullit të diskutuar më sipër me kombinime zanoresh me shkronja latine. Në veçanti, me n=5 dhe m=3, llogaritjet duke përdorur këto formula do të japin rezultatin e mëposhtëm:

Në rastin e përgjithshëm, formulat për numrin e kombinimeve kanë një kuptim kombinues dhe janë të vlefshme për çdo vlerë të plotë të n dhe m, të tilla që n > m > 0. Nëse m > n dhe m< 0, то число сочетаний равно 0, так как в этом случае основное множество из n элементов вообще не имеет подмножеств мощности m:

Përveç kësaj, është e dobishme të mbani mend numrat kufizues të mëposhtëm të kombinimeve, të cilat mund të kontrollohen lehtësisht me zëvendësim të drejtpërdrejtë në formulat shumëzuese dhe faktoriale:

Duhet të theksohet gjithashtu se formula shumëzuese mbetet e vlefshme edhe kur n është një numër real, për sa kohë që m është ende një vlerë e plotë. Sidoqoftë, atëherë rezultati i llogaritjes duke e përdorur atë, duke ruajtur vlefshmërinë formale, humbet kuptimin e tij kombinues.

IDENTITETET E KOMBINIMIT

Përdorimi praktik i formulave shumëzuese dhe faktoriale për të përcaktuar numrin e kombinimeve për vlerat arbitrare të n dhe m rezulton të jetë me produktivitet të vogël për shkak të rritjes eksponenciale të produkteve faktoriale të numëruesit dhe emëruesit të tyre. Edhe për vlera relativisht të vogla të n dhe m, këto produkte shpesh tejkalojnë aftësitë e përfaqësimit të numrave të plotë në sistemet moderne kompjuterike dhe softuerike. Për më tepër, vlerat e tyre rezultojnë të jenë dukshëm më të mëdha se vlera rezultuese e numrit të kombinimeve, e cila mund të jetë relativisht e vogël. Për shembull, numri i kombinimeve të n=10 me m=8 elementë është vetëm 45. Megjithatë, për të gjetur këtë vlerë duke përdorur formulën faktoriale, fillimisht duhet të llogaritni vlera shumë më të mëdha prej 10! në numërues dhe 8! në emërues:

Për të eliminuar operacionet që kërkojnë kohë për përpunimin e sasive të mëdha, për të përcaktuar numrin e kombinimeve, mund të përdorni marrëdhënie të ndryshme të përsëritjes, të cilat rrjedhin drejtpërdrejt nga formulat shumëzuese dhe faktoriale. Në veçanti, lidhja e mëposhtme e përsëritjes rrjedh nga formula shumëzuese, e cila na lejon të marrim raportin e indekseve të saj përtej shenjës së numrit të kombinimeve:

Së fundi, mbajtja konstante e nënshkrimit siguron lidhjen e mëposhtme të përsëritjes, e cila merret lehtësisht nga formula faktoriale për numrin e kombinimeve:

Pas transformimeve elementare, tre marrëdhëniet e përsëritjes që rezultojnë mund të përfaqësohen në format e mëposhtme:

Nëse tani shtojmë anën e majtë dhe të djathtë të 2 formulave të para dhe e zvogëlojmë rezultatin me n, marrim një lidhje të rëndësishme përsëritjeje, e cila quhet identiteti i mbledhjes së numrave të kombinimit:

Identiteti shtesë ofron një rregull bazë të përsëritjes për përcaktim efektiv numri i kombinimeve për vlera të mëdha n dhe m, pasi ju lejon të zëvendësoni operacionet e shumëzimit në produktet faktoriale me operacione më të thjeshta të mbledhjes dhe për një numër më të vogël kombinimesh. Në veçanti, duke përdorur identitetin e mbledhjes, tani është e lehtë të përcaktohet numri i kombinimeve të n=10 me m=8 elementë, i cili u diskutua më lart, duke kryer sekuencën e mëposhtme të transformimeve të përsëritura:

Për më tepër, disa marrëdhënie të dobishme për llogaritjen e shumave të fundme mund të nxirren nga identiteti i mbledhjes, në veçanti, formula për mbledhjen sipas nënshkrimit, e cila ka formën e mëposhtme:

Kjo lidhje fitohet nëse në identitetin e mbledhjes zgjerojmë përsëritjen përgjatë termit me mbishkrimin më të madh ndërsa nënshkrimi i tij është më i madh se 0. Shembulli numerik i mëposhtëm ilustron këtë proces të transformimeve të përsëritura:

Formula e përmbledhjes së nënshkrimit shpesh përdoret për të llogaritur shumën e fuqive të numrave natyrorë. Në veçanti, duke supozuar m=1, duke përdorur këtë formulë është e lehtë të gjesh shumën e n numrave të parë të serisë natyrore:

Një tjetër opsion i dobishëm formulat e përmbledhjes mund të merren duke zgjeruar përsëritjen e identitetit të mbledhjes përgjatë termit me mbishkrimin më të vogël. Shembulli numerik i mëposhtëm ilustron këtë version të transformimeve të përsëritura:

Në rastin e përgjithshëm, si rezultat i transformimeve të tilla, fitohet shuma e numrave të kombinimeve, të dy indekset e të cilave ndryshojnë me një nga termat fqinjë, dhe ndryshimi në indekset mbetet konstant (në shembullin e konsideruar, është gjithashtu e barabartë me një). Kështu, marrim formulën e mëposhtme të mbledhjes për të dy indekset e numrave të kombinimit:

Përveç marrëdhënieve të përsëritjes dhe formulave të përmbledhjes të diskutuara më sipër, shumë identitete të tjera të dobishme për numrat e kombinimit janë marrë në analizën kombinuese. Më e rëndësishmja ndër to është identiteti i simetrisë, e cila duket si kjo:

Vlefshmëria e identitetit të simetrisë mund të verifikohet në shembullin e mëposhtëm duke krahasuar numrat e kombinimeve të 5 elementeve me 2 dhe me (5 2) = 3:

Identiteti i simetrisë ka një kuptim të dukshëm kombinues, pasi, duke përcaktuar numrin e opsioneve për zgjedhjen e m elementeve nga n elemente, ai njëkohësisht përcakton numrin e kombinimeve nga elementët e mbetur (nm) të pazgjedhur. Simetria e treguar merret menjëherë duke zëvendësuar m me (nm) në formulën faktoriale për numrin e kombinimeve:

Numrat dhe identitetet e kombinimeve përdoren gjerësisht në fusha të ndryshme të matematikës kompjuterike moderne. Sidoqoftë, aplikimet e tyre më të njohura lidhen me binomin e Njutonit dhe trekëndëshin e Paskalit.

TEOREMA BINOMIALE

Për të kryer transformime dhe llogaritje të ndryshme matematikore, është e rëndësishme të jeni në gjendje të përfaqësoni çdo fuqi natyrore të një binomi algjebrik (binomi) në formën e një polinomi. Për fuqitë e vogla, polinomi i dëshiruar mund të merret lehtësisht duke shumëzuar drejtpërdrejt binomet. Në veçanti, formulat e mëposhtme për katrorin dhe kubin e shumës së dy termave janë të njohura mirë nga kursi i matematikës elementare:

Në rastin e përgjithshëm, për një shkallë arbitrare n të një binomi, paraqitja e kërkuar në formën e një polinomi sigurohet nga teorema binomiale e Njutonit, e cila deklaron barazinë e mëposhtme si të vërtetë:

Kjo barazi zakonisht quhet binomi i Njutonit. Polinomi në anën e tij të djathtë formohet nga shuma e prodhimeve të n termave X dhe Y të binomit në anën e majtë, dhe koeficientët përballë tyre quhen binom dhe janë të barabartë me numrin e kombinimeve me indekse, të cilat janë marrë nga fuqitë e tyre. Duke pasur parasysh popullaritetin e veçantë të formulës binomiale të Njutonit në analizën kombinuese, termat koeficient binomial dhe numri i kombinimeve përgjithësisht konsiderohen sinonime.

Natyrisht, formulat e shumës në katror dhe në kub janë raste të veçanta të teoremës së binomit përkatësisht për n=2 dhe n=3. Për të trajtuar shkallët më të larta (n>3), duhet të përdoret formula binomiale e Njutonit. Zbatimi i tij për një binom të shkallës së katërt (n=4) demonstrohet me shembullin e mëposhtëm:

Duhet të theksohet se formula binomiale ishte e njohur edhe para Njutonit për matematikanët mesjetarë të Lindjes Arabe dhe Evropën Perëndimore. Prandaj, emri i tij i pranuar përgjithësisht nuk është historikisht i saktë. Merita e Njutonit është se ai e përgjithësoi këtë formulë në rastin e një eksponenti real arbitrar r, i cili mund të marrë çdo vlerë racionale dhe irracionale pozitive ose negative. Në rastin e përgjithshëm, një formulë e tillë binomiale e Njutonit ka një shumë të pafundme në anën e djathtë dhe zakonisht shkruhet si më poshtë:

Për shembull, me një vlerë thyesore pozitive të eksponentit r=1/2, duke marrë parasysh vlerat e koeficientëve binomial, fitohet zgjerimi i mëposhtëm:

Në rastin e përgjithshëm, formula binomiale e Njutonit për çdo eksponent është një version i veçantë i formulës së Maclaurin, i cili jep zgjerimin e një funksioni arbitrar në një seri fuqie. Njutoni tregoi se për |z|< 1 этот ряд сходится, и сумма в правой части становится конечной. При любой натуральной степени r = n в правой части также получается конечная сумма из (n+1) первых слагаемых, так как все C(n, k>n) = 0 . Nëse tani vendosim Z=X/Y dhe shumëzojmë anën e majtë dhe të djathtë me Yn, marrim një version të formulës binomiale të Njutonit të diskutuar më sipër.

Pavarësisht universalitetit të saj, teorema e binomit ruan kuptimin e saj kombinues vetëm për fuqitë e plota jo negative të binomit. Në këtë rast, mund të përdoret për të vërtetuar disa identitete të dobishme për koeficientët binomialë. Në veçanti, formulat për përmbledhjen e numrave të kombinimeve sipas nënshkrimit dhe sipas të dy indekseve u diskutuan më lart. Identiteti i përmbledhjes së mbishkrimit që mungon mund të merret lehtësisht nga formula binomiale e Njutonit duke vendosur X = Y = 1 ose Z = 1 në të:

Një tjetër identitet i dobishëm vendos barazinë e shumave të koeficientëve binomialë me numra çift dhe tek. Përftohet menjëherë nga formula binomiale e Njutonit nëse X = 1 dhe Y = 1 ose Z = 1:

Së fundi, nga të dy identitetet e konsideruara marrim identitetin e shumës së koeficientëve binomialë me vetëm numra çift ose vetëm tek:

Bazuar në identitetet e konsideruara dhe rregullin e përsëritur të heqjes së indekseve nën shenjën e numrit të kombinimeve, mund të përftohen një sërë marrëdhëniesh interesante. Për shembull, nëse në formulën e përmbledhjes së mbishkrimit zëvendësojmë n kudo me (n1) dhe heqim indekset në secilin term, marrim relacionin e mëposhtëm:

Duke përdorur një teknikë të ngjashme në formulën për shumën e koeficientëve binomialë me numra çift dhe tek, është e mundur të vërtetohet vlefshmëria, për shembull, e lidhjes së mëposhtme:

Një tjetër identitet i dobishëm ju lejon të llogarisni me lehtësi shumën e produkteve të koeficientëve binomialë të vendosur në mënyrë simetrike të dy binomeve të shkallëve arbitrare n dhe k duke përdorur formulën e mëposhtme të Cauchy:

Vlefshmëria e kësaj formule rrjedh nga barazia e nevojshme e koeficientëve për çdo shkallë m të ndryshores Z në anën e majtë dhe të djathtë të relacionit identik të mëposhtëm:

Në rastin e veçantë kur n=k=m, duke marrë parasysh identitetin e simetrisë, fitohet një formulë më popullore për shumën e katrorëve të koeficientëve binomialë:

Shumë identitete të tjera të dobishme për koeficientët binomialë mund të gjenden në literaturën e gjerë mbi analizën kombinuese. Megjithatë, zbatimi i tyre praktik më i famshëm lidhet me trekëndëshin e Paskalit.

TREKËNDËSHI I PASCALIT

Trekëndëshi aritmetik i Paskalit formon një tabelë numerike të pafundme të përbërë nga koeficientë binomialë. Linjat e tij janë të renditura sipas fuqive të binomeve nga lart poshtë. Në çdo rresht, koeficientët binomial janë renditur në rend rritës të mbishkrimeve të numrave të kombinimit përkatës nga e majta në të djathtë. Trekëndëshi i Paskalit zakonisht shkruhet ose në formë dykëndëshe ose drejtkëndëshe.

Më vizual dhe më i zakonshëm është formati izosceles, ku koeficientët binomialë, të stivosur, formojnë një trekëndësh të pafundmë dykëndësh. Fragmenti fillestar i tij për binomet deri në shkallën e 4-të (n=4) ka këtë formë:

Në përgjithësi, trekëndëshi izosceles i Pascal-it ofron një rregull gjeometrik të përshtatshëm për përcaktimin e koeficientëve binomialë, i cili bazohet në identitetet e mbledhjes dhe simetritë e numrave të kombinimit. Në veçanti, sipas identitetit të mbledhjes, çdo koeficient binomial është shuma e dy koeficientëve të rreshtit të mëparshëm më afër tij. Sipas identitetit të simetrisë, trekëndëshi izoscelular i Paskalit është simetrik në lidhje me përgjysmuesin e tij. Kështu, secila prej rreshtave të saj është një palindrom numerik i koeficientëve binomialë. Karakteristikat e treguara algjebrike dhe gjeometrike bëjnë të mundur zgjerimin e lehtë të trekëndëshit isosceles të Pascal dhe gjetjen e vazhdueshme të vlerave të koeficientëve binomial të fuqive arbitrare.

Sidoqoftë, për të studiuar vetitë e ndryshme të trekëndëshit të Pascal-it, është më e përshtatshme të përdoret formati drejtkëndor zyrtarisht më i rreptë. Në këtë format, ai specifikohet nga një matricë trekëndore më e ulët e koeficientëve binomialë, ku ata formojnë një trekëndësh kënddrejtë të pafund. Fragmenti fillestar trekëndësh kënddrejtë Paskali për binomet deri në shkallën e 9-të (n=9) ka formën e mëposhtme:

Gjeometrikisht, një tabelë e tillë drejtkëndore fitohet nga deformimi horizontal trekëndëshi dykëndësh Paskalin. Si rezultat, seritë e numrave paralele me anët anësore të trekëndëshit dykëndësh të Paskalit kthehen në vertikale dhe diagonale të trekëndëshit kënddrejtë të Paskalit, dhe horizontalet e të dy trekëndëshave përkojnë. Në të njëjtën kohë, rregullat e mbledhjes dhe simetrisë së koeficientëve binomial mbeten të vlefshme, megjithëse trekëndëshi kënddrejtë i Paskalit humbet simetrinë vizuale karakteristike të homologut të tij izosceles. Për të kompensuar këtë, bëhet më e përshtatshme që zyrtarisht të analizohen vetitë e ndryshme numerike të koeficientëve binomialë për horizontalet, vertikalet dhe diagonalet e trekëndëshit kënddrejtë të Paskalit.

Duke filluar analizën e horizontaleve të trekëndëshit kënddrejtë të Paskalit, vërehet lehtë se shuma e elementeve të çdo rreshti me numër n është e barabartë me 2n në përputhje me formulën për mbledhjen e binomeve me mbishkrim. Nga kjo rezulton se shuma e elementeve mbi secilën prej vijave horizontale me numër n është e barabartë me (2 n 1). Ky rezultat bëhet mjaft i dukshëm nëse vlera e shumës së elementeve të secilës vijë horizontale shkruhet në sistemin e numrave binar. Për shembull, për n=4 kjo mbledhje mund të shkruhet si më poshtë:

Ja edhe disa të tjera veti interesante vija horizontale, të cilat shoqërohen edhe me fuqitë e dy. Rezulton se nëse numri horizontal është fuqi dyshe (n=2 k), atëherë të gjithë elementët e brendshëm të tij (përveç atyre të jashtëm) janë numra çift. Përkundrazi, të gjithë numrat e një vije horizontale do të jenë tek nëse numri i saj është me një më pak shkallë dyshe (n=2 k 1). Vlefshmëria e këtyre vetive mund të verifikohet duke kontrolluar paritetin e koeficientëve binomial të brendshëm, për shembull, në horizontalet n=4 dhe n=3 ose n=8 dhe n=7.

Tani le të jetë numri i rreshtit të trekëndëshit kënddrejtë të Paskalit një numër i thjeshtë p. Atëherë të gjithë koeficientët binomialë të brendshëm të tij pjesëtohen me p. Kjo veti është e lehtë për t'u kontrolluar për vlera të vogla të numrave të konturit kryesor. Për shembull, të gjithë koeficientët binomial të brendshëm të horizontalit të pestë (5, 10 dhe 5) janë padyshim të pjesëtueshëm me 5. Për të vërtetuar këtë rezultat për çdo numër të thjeshtë horizontal p, duhet të shkruani formulën shumëzuese për koeficientët binomial të tij si më poshtë:

Meqenëse p është një numër i thjeshtë dhe, për rrjedhojë, nuk është i pjesëtueshëm me m!, prodhimi i faktorëve të mbetur të numëruesit të kësaj formule duhet të jetë i pjesëtueshëm me m për të garantuar një vlerë të plotë të koeficientit binom. Nga kjo rrjedh se raporti në kllapa katroreështë një numër natyror N dhe rezultati i dëshiruar bëhet i dukshëm:

Duke përdorur këtë rezultat, mund të konstatojmë se numrat e të gjitha vijave horizontale të trekëndëshit të Paskalit, elementët e brendshëm të të cilëve janë të pjesëtueshëm me një numër të thjeshtë të dhënë p, janë fuqi të p, domethënë kanë formën n=p k. Në veçanti, nëse p=3, atëherë numri i thjeshtë p ndan jo vetëm të gjithë elementët e brendshëm të rreshtit 3, siç u vendos më lart, por, për shembull, horizontalin e 9-të (9, 36, 84 dhe 126). Nga ana tjetër, në trekëndëshin e Paskalit është e pamundur të gjesh një vijë horizontale, elementët e brendshëm të së cilës janë të gjithë të pjesëtueshëm me një numër të përbërë. Përndryshe, numri i një vije të tillë horizontale duhet të jetë në të njëjtën kohë një fuqi e pjesëtuesve kryesorë numër i përbërë, në të cilin janë ndarë të gjithë elementët e brendshëm të tij, por për arsye të dukshme kjo është e pamundur.

Konsideratat e marra na lejojnë të formulojmë sa vijon tipar i përbashkët pjesëtueshmëria e elementeve horizontale të trekëndëshit të Paskalit. Më i madhi pjesëtues i përbashkët(NOD) të gjithë elementet e brendshmeçdo vijë horizontale e trekëndëshit të Paskalit me numër n është e barabartë me numër i thjeshtë p nëse n=pk ose 1 në të gjitha rastet e tjera:

GCD(Cmn) = ( ) për çdo 0< m < n .

Për të përfunduar analizën e horizontaleve, vlen të merret në konsideratë një veti më interesante që ka seria e koeficientëve binomialë që i formojnë ato. Nëse koeficientët binomialë të cilësdo drejtëz horizontale me numër n shumëzohen me fuqitë e njëpasnjëshme të numrit 10 dhe më pas mblidhen të gjitha këto prodhime, rezultati është 11 n. Arsyetimi formal për këtë rezultat është zëvendësimi i vlerave X=10 dhe Y=1 (ose Z=1) në formulën binomiale të Njutonit. Shembulli numerik i mëposhtëm ilustron përmbushjen e kësaj vetie për n=5:

Analiza e vetive të vertikaleve të trekëndëshit kënddrejtë të Paskalit mund të fillojë duke studiuar karakteristikat individuale elementet përbërëse të tyre. Formalisht, çdo m vertikale formohet nga sekuenca e mëposhtme e pafundme e koeficientëve binomialë me një mbishkrim konstant (m) dhe një rritje të nënshkrimit:

Natyrisht, kur m=0 fitohet një varg njëshe, dhe kur m=1 formohet një seri numrash natyrorë. Kur m=2 vertikalja përbëhet nga numra trekëndësh. Çdo numër trekëndor mund të përshkruhet në një plan në formën e një trekëndëshi barabrinjës, i cili është i mbushur me objekte arbitrare (bërthamë) të rregulluar në një model shahu. Në këtë rast, vlera e çdo numri trekëndor T k përcakton numrin e bërthamave që përfaqësojnë, dhe indeksi tregon se sa rreshta bërthamash nevojiten për ta përfaqësuar atë. Për shembull, 4 numra trekëndësh fillestarë përfaqësojnë konfigurimet e mëposhtme të numrit përkatës të simboleve bërthamore "@":

Duhet të theksohet se në mënyrë të ngjashme mund të futen në konsideratë numrat katrorë S k, të cilët fitohen nga katrori i numrave natyrorë dhe, në përgjithësi, numrat me figura poligonale të formuar me mbushje të rregullt. shumëkëndëshat e rregullt. Në veçanti, 4 fillestar numra katrorë mund të përshkruhet si më poshtë:

Duke iu rikthyer analizës së vertikaleve të trekëndëshit të Paskalit, mund të vërejmë se vertikali tjetër në m=3 është i mbushur me numra tetraedralë (piramidalë). Secili numër i tillë P k specifikon numrin e bërthamave që mund të rregullohen në formën e një katërkëndëshi dhe indeksi përcakton se sa shtresa horizontale trekëndore nga rreshtat e bërthamave kërkohen për ta përshkruar atë në hapësirë tredimensionale. Në këtë rast, të gjitha shtresat horizontale duhet të përfaqësohen si numra trekëndësh të njëpasnjëshëm. Elementet e vertikaleve të mëposhtme të trekëndëshit të Paskalit për m>3 formojnë seri numrash hipertetraedalë, të cilët nuk kanë një interpretim gjeometrik vizual në rrafsh ose në hapësirën tredimensionale, por formalisht korrespondojnë me analoge shumëdimensionale të numrave trekëndësh dhe katërkëndësh.

Megjithëse seritë vertikale të numrave të trekëndëshit të Paskalit kanë veçoritë e konsideruara të formës individuale, për ta është e mundur të llogariten shumat e pjesshme të vlerave të elementeve fillestare në të njëjtën mënyrë, duke përdorur formulën për përmbledhjen e numrave të kombinimeve sipas nënshkrimit. . Në trekëndëshin e Paskalit, kjo formulë ka interpretimin gjeometrik të mëposhtëm. Shuma e vlerave të n koeficientëve binomial të sipërm të çdo vertikale është e barabartë me vlerën e elementit të vertikales tjetër, e cila ndodhet një rresht më poshtë. Ky rezultat është gjithashtu në përputhje me strukturën gjeometrike të numrave trekëndësh, tetraedralë dhe hipertetrahedalë, pasi përfaqësimi i secilit numër të tillë përbëhet nga shtresa bërthamore që përfaqësojnë numra të rendit më të ulët. Në veçanti, trekëndëshi i n-të numri T n mund të merret duke mbledhur të gjithë numrat natyrorë që përfaqësojnë shtresat e tij lineare:

Po kështu, nuk është e vështirë të gjesh numrin tetraedral Pn duke llogaritur shumën e mëposhtme të n numrave të parë trekëndësh që përbëjnë shtresat e bërthamës horizontale të tij:

Përveç horizontaleve dhe vertikaleve në trekëndëshin kënddrejtë të Paskalit, mund të gjurmohen rreshtat diagonale të elementeve, studimi i vetive të të cilave është gjithashtu me një interes. Në këtë rast, zakonisht bëhet një dallim midis diagonaleve zbritëse dhe ngjitëse. Diagonalet në rënie janë paralele me hipotenuzën e trekëndëshit kënddrejtë të Paskalit. Ato formohen nga seria e koeficientëve binomialë me një rritje të të dy indekseve. Për shkak të identitetit të simetrisë, diagonalet zbritëse përkojnë në vlerat e elementeve të tyre me rreshtat vertikale përkatëse të trekëndëshit të Paskalit dhe për këtë arsye përsërisin të gjitha vetitë e tyre të diskutuara më sipër. Korrespondenca e treguar mund të gjurmohet nga koincidenca e vlerave të elementeve të diagonales zbritëse dhe vertikale me çdo numër n, nëse zerat vertikale nuk merren parasysh:

Diagonalet ngjitëse formojnë seri numrash gjeometrikisht pingul me hipotenuzën e trekëndëshit kënddrejtë të Paskalit. Ato janë të mbushura me koeficientë binomialë me zvogëlim të së poshtme dhe rritje të sipërshkrimit. Në veçanti, 7 diagonalet e sipërme ngjitëse formojnë sekuencën numerike të mëposhtme pa marrë parasysh zerot pasuese:

Në përgjithësi, numri diagonal në rritje n përmban koeficientët binomialë të mëposhtëm, shuma e indekseve të secilit prej të cilëve është e barabartë me (n1):

Në bazë të identitetit të mbledhjes për numrat e kombinimit, çdo element diagonal është i barabartë me shumën e dy elementeve që korrespondojnë në indekse nga dy diagonalet e mëparshme ngjitëse. Kjo lejon që çdo diagonale ngjitëse pasuese të ndërtohet nga përmbledhja në çift e elementeve horizontale ngjitur nga dy diagonalet e mëparshme, duke zgjeruar pafundësisht trekëndëshin e Paskalit përgjatë diagonales. Fragmenti i mëposhtëm i trekëndëshit të Paskalit ilustron ndërtimin e një numri diagonal ngjitës 8 përgjatë diagonaleve të numëruara 6 dhe 7:

Me këtë metodë ndërtimi, shuma e elementeve të çdo diagonale në ngjitje, duke filluar nga e treta, do të jetë e barabartë me shumën e elementeve të dy diagonaleve të mëparshme ngjitëse, dhe 2 diagonalet e para përbëhen nga vetëm një element, vlera prej të cilave është 1. Rezultatet e llogaritjeve përkatëse formojnë serinë numerike të mëposhtme, sipas së cilës mund të kontrolloni vlefshmërinë e vetive të konsideruara të diagonaleve ngjitëse të trekëndëshit kënddrejtë të Paskalit:

Duke analizuar këta numra, mund të shihni se sipas një ligji të ngjashëm, formohet sekuenca e njohur e numrave Fibonacci, ku çdo numër tjetër është i barabartë me shumën e dy numrave të mëparshëm, dhe dy numrat e parë janë të barabartë me 1:

Kështu, mund të nxjerrim përfundimin e mëposhtëm të rëndësishëm: shumat diagonale të elementeve të trekëndëshit të Paskalit përbëjnë sekuencën Fibonacci. Kjo veti ju lejon të vendosni një tjetër tipar interesant trekëndëshi i Paskalit. Duke e zgjeruar formulën e Fibonaçit në mënyrë rekursive, është e lehtë të vërtetohet se shuma e n numrave të parë të Fibonacci është e barabartë me (F n+2 1).

Prandaj, shuma e koeficientëve binomialë që mbushin n diagonalet e sipërme është gjithashtu e barabartë me (F n+2 1). Nga kjo rrjedh se shuma e n diagonaleve të para të trekëndëshit të Paskalit është 1 më pak se shuma e koeficientëve binomialë që qëndrojnë në diagonalen e tij me numrin (n+2).

Si përfundim, duhet theksuar se vetitë e konsideruara të horizontaleve, vertikaleve dhe diagonaleve të trekëndëshit të Pascal nuk shterojnë larminë e madhe të mundësive që lidhin së bashku aspekte të ndryshme matematikore që në shikim të parë nuk kanë asgjë të përbashkët. Veti të tilla të pazakonta na lejojnë ta konsiderojmë trekëndëshin e Paskalit një nga sistemet numerike më të përsosura, të gjitha aftësitë e të cilit nuk mund të renditen dhe janë të vështira për t'u mbivlerësuar.

Algoritmi për llogaritjen e numrit të kombinimeve duke përdorur trekëndëshin e Pascal është paraqitur më poshtë:

Funksioni privat SochTT (ByVal n si numër i plotë, ByVal k si numër i plotë) Si zbehje e dyfishtë i si numër i plotë Dim j Si numër i plotë Dim TT () Si Double ReDim TT (n, k) Për i = 0 deri në n TT (0, i) = 1 TT (i, i) = 1 Tjetra Për i = 2 Tek n Për j = 1 Tek i - 1 TT (i, j) = TT (i - 1, j - 1) + TT (i - 1, j) Next Next SochTT = TT (n, k) Funksioni Fund

Nëse ju duhet të llogarisni numrin e kombinimeve shumë herë, atëherë mund të jetë më e përshtatshme të ndërtoni një herë trekëndëshin e Pascal-it dhe më pas të merrni të dhëna nga grupi.

Dim TT () Si Sub Private Double CreateTT () ReDim TT (0, 0) BuildTT 0, 0 Fund Sub Private Function SochTT (ByVal n si numër i plotë, ByVal k si numër i plotë) Si Double If n > Ubound (TT) Pastaj BuildTT Ubound (TT) + 1, n SochTT = TT (n, k) Funksioni Fund Private Sub TerminateTT () ReDim TT (0, 0) Fund Sub Private Sub BuildTT (ByVal start As Integer, ByVal Fund As Integer) Dim i As Integer Dim j Si numër i plotë ReDim ruaj TT (fund, fund) Për i = fillimi Deri në fund TT (0, i) = 1 TT (i, i) = 1 Tjetër Nëse fundi< 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

Së pari ju duhet të telefononi procedurën CreateTT. Më pas mund të merrni numrin e kombinimeve duke përdorur funksionin SochTT. Kur nuk ju nevojitet më trekëndëshi, telefononi procedurën TerminateTT. Në kodin e mësipërm, kur thërrisni funksionin SochTT, nëse trekëndëshi nuk është përfunduar ende nivelin e kërkuar, pastaj plotësohet duke përdorur procedurën BuildTT. Më pas, funksioni merr elementin e dëshiruar të grupit TT dhe e kthen atë.

Dim X () Si numër i plotë Dim numërues () Si numër i plotë Dim K si numër i plotë Dim N si numër i plotë publik Sub Soch() Dim i si numër i plotë N = CInt(InputBox("Enter N")) K = CINT(InputBox("Enter K ")) K = K + 1 ReDim X(N) Për i = 1 Në N X(i) = i TxtOut.Text = "" ReDim Counter(K) Counter(0) = 1 SochGenerate 1 Fund Sub Private Sub SochGenerate( ByVal c Si numër i plotë) Dim i Si numër i plotë Dim j Si numër i plotë Dim n1 Si numër i plotë Dim Out() Si numër i plotë Dim X1() Si numër i plotë Nëse c = K Atëherë ReDim Out(K) X1 = X Për i = 1 në K - 1 n1 = 0 Për j = 1 Në N nëse X1 (j)<>0 Atëherë n1 = n1 + 1 Nëse n1 = Numërues(i) Pastaj Out(i) = X1(j) X1(j) = 0 Dil Për Fund Nëse Tjetër txtOut.Text = txtOut.Text & CStr(Out(i)) TxtOut.Text tjetër = txtOut.Text & vbCrLf Tjetër Për numërues(c) = Numërues(c - 1) Tek N - c + 1 SochGenerate c + 1 Fundi tjetër Nëse Fundi Nën

REGJISTIMI I KOMBINIMEVE TË NUMRAVE NATYROR

Për të zgjidhur shumë probleme praktike, është e nevojshme të renditen të gjitha kombinimet e kardinalitetit fiks që mund të merren nga elementët e një grupi të caktuar të fundëm, dhe jo vetëm të përcaktohet numri i tyre. Duke marrë parasysh mundësinë gjithmonë ekzistuese të numërimit të numrave të plotë të elementeve të çdo grupi të fundëm, në shumicën e rasteve lejohet të kufizohemi në përdorimin e algoritmeve për numërimin e kombinimeve të numrave natyrorë. Më e natyrshme dhe më e thjeshta prej tyre është algoritmi për renditjen e kombinimeve të numrave natyrorë në renditja leksigrafike.

Për të përshkruar zyrtarisht këtë algoritëm, është e përshtatshme të supozohet se grupi kryesor, të gjitha kombinimet e m elementeve të të cilave duhet të renditen, formojnë numra natyrorë të njëpasnjëshëm nga 1 në n. Atëherë çdo kombinim i m

Si rezultat i renditjes, vlera në çdo pozicion të një vektori të tillë kombinimesh natyrisht rezulton të jetë e kufizuar në vlerë nga lart dhe poshtë si më poshtë:

Algoritmi leksigrafik gjeneron në mënyrë sekuenciale vektorë të tillë kombinimi, duke filluar me vektorin leksigrafikisht më të vogël, ku të gjitha pozicionet përmbajnë vlerat minimale të mundshme të elementeve të mëposhtme të barabarta me indekset e tyre:

Çdo vektor kombinimi të njëpasnjëshëm formohet nga ai aktual pasi skanon elementët e tij nga e majta në të djathtë për të gjetur elementin më të djathtë që nuk e ka arritur ende vlerën e tij kufi:

Vlera e një elementi të tillë duhet të rritet me 1. Çdo elementi në të djathtë të tij duhet t'i caktohet vlera më e vogël e mundshme, e cila është 1 më shumë se fqinji i tij në të majtë. Pas këtyre ndryshimeve, vektori tjetër i kombinimeve do të ketë përbërjen elementare të mëposhtme:

Kështu, vektori tjetër i kombinimit do të jetë leksigrafikisht më i madh se ai i mëparshmi, pasi vlerat e elementeve të tyre fillestare (j1) janë të barabarta në vlerë, dhe vlera e elementit në pozicionin j është 1 më e madhe se ajo e mëparshme. . Lidhja e specifikuar e rritjes së rendit leksigrafik është e garantuar të përmbushet në të gjitha përsëritjet e algoritmit. Rezultati është një sekuencë leksigrafike në rritje, e cila plotësohet nga vektori i kombinimit më të madh leksigrafik, ku elementët në të gjitha pozicionet kanë vlerat maksimale të mëposhtme:

Algoritmi leksigrafik i konsideruar ilustrohet me shembullin e mëposhtëm, ku është e nevojshme të renditen në rend leksigrafik në rritje të 15 kombinimet e n=6 numrave të parë natyrorë me m=4 numra, domethënë të gjitha nëngrupet e mundshme 4 elementëshe të gjeneruesit kryesor. grup (1, 2, 3, 4, 5, 6) nga 6 elementë. Rezultatet e llogaritjes janë paraqitur në tabelën e mëposhtme:

Në këtë shembull, vlerat më të mëdha të lejuara të numrave në pozicionet e vektorëve të kombinimit janë, përkatësisht, 3, 4, 5 dhe 6. Për lehtësinë e interpretimit të rezultateve, në çdo vektor kombinimi, elementi më i djathtë, i cili ka nuk ka arritur ende vlerën maksimale, nënvizohet. Indekset numerike të vektorëve të kombinuar përcaktojnë numrat e tyre sipas rendit leksigrafik. Në rastin e përgjithshëm, numri leksigrafik N i çdo kombinimi të n elementeve me m mund të llogaritet duke përdorur formulën e mëposhtme, ku, për arsye kozmetike, simbolika e apelit përdoret për të treguar numrat e kombinimeve:

Në veçanti, llogaritjet e mëposhtme duke përdorur këtë formulë për numrin e kombinimit (1, 3, 4, 6) të n=6 elementeve të m=4 sipas rendit leksigrafik do të japin rezultatin N=8, i cili korrespondon me shembullin e diskutuar më sipër:

Në rastin e përgjithshëm, duke përdorur identitetin për shumën e numrave të kombinimeve për të dy indekset, mund të tregojmë se numri i kombinimit leksigrafikisht më të vogël (1, … i, … m) kur llogaritet duke përdorur këtë formulë do të jetë gjithmonë i barabartë me 1:

Është gjithashtu e qartë se numri i kombinimit më të madh leksigrafik (m, … nm+i, … n) kur llogaritet duke përdorur këtë formulë do të jetë i barabartë me numrin e kombinimeve të n elementeve me m:

Formula për llogaritjen e numrave të kombinimeve leksigrafike mund të përdoret për të zgjidhur problemin e anasjelltë, ku duhet të përcaktoni vektorin e kombinimit me numrin e tij sipas rendit leksigrafik. Për të zgjidhur një problem të tillë të kundërt, duhet të shkruhet në formën e një ekuacioni, ku të gjitha vlerat e panjohura të elementeve të vektorit të kombinimit të dëshiruar (C 1, ... C i, ... C m ) janë të përqendruara në numrat e kombinimeve të anës së djathtë të tij, dhe diferenca e njohur L e numrit të kombinimeve shkruhet në anën e majtë të n elementeve çdo m dhe numri i kombinimit të kërkuar N:

Zgjidhja e këtij ekuacioni jepet nga algoritmi i mëposhtëm "i babëzitur", në përsëritjet e të cilit zgjidhen në mënyrë sekuenciale vlerat e elementeve të vektorit të kombinimit të dëshiruar. Në përsëritjen fillestare, zgjidhet vlera minimale e mundshme (brenda kufizimeve të saj) e C 1, në të cilën termi i parë në anën e djathtë do të ketë një vlerë maksimale që nuk e kalon L:

Tani ana e majtë e L duhet të reduktohet me numrin e parë të kombinimeve në anën e djathtë me vlerën e zgjedhur të C 1, dhe në mënyrë të ngjashme të përcaktojë vlerën e C 2 në përsëritjen e dytë:

Në mënyrë të ngjashme, të gjitha përsëritjet pasuese duhet të kryhen për të zgjedhur vlerat e të gjithë elementëve të tjerë C i të kombinimit të dëshiruar, deri në elementin e fundit C m:

Për arsye të dukshme, vlera e elementit të fundit Cm mund të përcaktohet bazuar në barazinë e numrit të tij të kombinimeve me vlerën e mbetur të anës së majtë të L:

Duhet të theksohet se vlera e elementit të fundit të kombinimit C m mund të gjendet edhe më thjeshtë, pa numëruar vlerat e tij të mundshme:

Zbatimi i përsëritjeve të algoritmit të konsideruar ilustrohet me shembullin e mëposhtëm, ku është e nevojshme të përcaktohen kombinimet me numrin N=8 sipas rendit leksigrafik, nëse n=6 dhe m=4:

Aftësia algoritmike për të përcaktuar një kombinim me një numër të caktuar sipas rendit leksigrafik mund të përdoret në drejtime të ndryshme. Në veçanti, kur renditen kombinimet sipas rendit leksigrafik, është e nevojshme të sigurohet kthimi në çdo kombinim që është marrë më herët, mjafton të dihet vetëm numri i tij. Përveç kësaj, bëhet e mundur të gjenerohen kombinime në çdo mënyrë, e cila rregullohet nga një sekuencë e dhënë në mënyrë arbitrare e numrave të tyre leksigrafikë.

Tani paraqesim një algoritëm për gjenerimin e kombinimeve sipas rendit leksikografik:

2 për i:= 1 deri në k bëj A[i] := i;

5 filloni të shkruani (A, …, A[k]);

6 nëse A[k] = n atëherë p:= p 1 tjetër p:= k;

8 për i:= k poshtë në p bëj A[i] := A[p] + i p + 1

KOMBINIMET ME ELEMENTE TË PËRSËRSITUR

Ndryshe nga një kombinim klasik, ku të gjithë elementët janë të ndryshëm, një kombinim me përsëritje formon një përzgjedhje të parregullt të elementeve të një grupi të fundëm, ku çdo element mund të shfaqet pafundësisht shpesh dhe nuk është domosdoshmërisht i pranishëm në një kopje të vetme. Në këtë rast, numri i përsëritjeve të elementeve zakonisht kufizohet vetëm nga gjatësia e kombinimit, dhe kombinimet që ndryshojnë në të paktën një element konsiderohen të ndryshëm. Për shembull, duke zgjedhur 4 numra opsionalisht të ndryshëm nga grupi 1, 2 dhe 3, mund të krijoni 15 kombinimet e mëposhtme me përsëritje:

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

Në përgjithësi, kombinimet me përsëritje mund të formohen duke zgjedhur n elementë të llojeve arbitrare. Sidoqoftë, ato gjithmonë mund të shoqërohen me numra natyrorë të njëpasnjëshëm nga 1 në n. Atëherë çdo kombinim i m numrave opsionalisht të ndryshëm në këtë diapazon mund të shkruhet në formë vektoriale, duke i renditur në mënyrë jo-zvogëluese nga e majta në të djathtë:

Natyrisht, me këtë formë shënimi, çdo element fqinj mund të jetë i barabartë për shkak të mundësisë së përsëritjeve të pakufizuara. Sidoqoftë, çdo vektor kombinimi me përsëritje të n elementeve me m mund të shoqërohet me një vektor kombinimi të (n+m−1) elementeve me m, i cili është ndërtuar si më poshtë:

Është e qartë se për çdo vlerë të elementeve të vektorit f, elementet e vektorit C garantohen të jenë të ndryshëm dhe të renditur rreptësisht në rendin rritës të vlerave të tyre nga diapazoni nga 1 në (n+m1) :

Prania e një korrespondence një-për-një midis elementeve të vektorëve të kombinimit f dhe C na lejon të propozojmë metodën e mëposhtme të thjeshtë për renditjen sistematike të kombinimeve me përsëritje të n elementeve me m. Është e nevojshme vetëm të renditen, për shembull, sipas rendit leksigrafik, të gjitha kombinimet C të (n+m1) elementeve të m, duke i shndërruar në mënyrë sekuenciale elementet e secilit prej tyre në elementët përkatës të kombinimeve me përsëritje f duke përdorur formulën e mëposhtme:

Si rezultat, formohet një sekuencë e vektorëve të kombinimeve me përsëritje të elementeve, të cilët renditen në rendin e gjeneruar duke renditur kombinimet përkatëse pa përsëritje të elementeve. Në veçanti, për të marrë sekuencën e mësipërme të kombinimeve prej 3 shifrash 1, 2 dhe 3 me përsëritje 4 shifrash, është e nevojshme të renditen sipas rendit leksigrafik të gjitha kombinimet pa përsëritje të 6 shifrave 1,2,3,4, 5. dhe 6 janë 4 shifra secila, duke i konvertuar ato siç tregohet. Shembulli i mëposhtëm tregon një shndërrim të tillë të kombinimit (1,3,4,6) me numrin leksikografik 8:

Korrespondenca e konsideruar një-për-një midis kombinimeve me dhe pa përsëritje të elementeve do të thotë që grupet e tyre janë po aq të fuqishme. Prandaj, në rastin e përgjithshëm, numri i kombinimeve me përsëritje të n elementeve me m është i barabartë me numrin e kombinimeve pa përsëritje të (n+m1) elementeve me m. Duke përdorur të njëjtën simbolikë për të treguar numrat e kombinimeve me përsëritje f dhe pa përsëritje C, kjo barazi mund të shkruhet si më poshtë:

Është e lehtë të kontrollohet se për shembullin e konsideruar më sipër, ku n=3 dhe m=4, numri i kombinimeve të përsëritjes do të jetë i barabartë me 15, që përkon me rezultatin e renditjes së tyre të drejtpërdrejtë:

Duhet të theksohet se, ndryshe nga versioni klasik, vlerat e parametrave të kombinimit me përsëritje n dhe m nuk lidhen drejtpërdrejt me njëra-tjetrën, prandaj f(n,m)>0 për çdo kombinim të vlerave të tyre pozitive. Kushtet kufitare përkatëse përcaktohen nga barazia midis vlerave të (n+m1) dhe (n1) ose (n+m1) dhe m:

Duhet të jetë gjithashtu mjaft e qartë se nëse m është e barabartë me 1, atëherë nuk janë të mundshme përsëritje të elementeve dhe, për rrjedhojë, për çdo vlerë pozitive prej n>0 barazia e mëposhtme do të jetë e vërtetë:

Përveç kësaj, për numrat e kombinimeve me përsëritje për cilindo vlerat pozitive n dhe m vlen relacioni i mëposhtëm i përsëritjes, i cili është i ngjashëm me identitetin e mbledhjes për numrat e kombinimit pa përsëritje të elementeve:

Në fakt, ai kthehet në identitetin e treguar të shtimit pas zëvendësimit zyrtar të numrave përkatës të kombinimeve pa përsëritje në anën e majtë dhe të djathtë të tij:

Marrëdhënia e konsideruar e përsëritjes mund të përdoret për të përcaktuar në mënyrë efektive numrin e kombinimeve me përsëritjet, kur është e rëndësishme të eliminohen operacionet intensive të punës të llogaritjes së produkteve faktoriale dhe t'i zëvendësoni ato me operacione më të thjeshta të mbledhjes. Në këtë rast, për të llogaritur vlerën e f(n,m), ju duhet vetëm të aplikoni këtë relacion përsëritje derisa të merrni shumën e termave të formës f(1,m) dhe f(i,1), ku i merr vlera në rangun nga n në 1. Sipas përcaktimit të sasisë, termat e tillë janë të barabartë me 1 dhe i, respektivisht. Shembulli i mëposhtëm ilustron përdorimin e kësaj teknike të transformimit për rastin n=3 dhe m=4:

LISTIMI I KOMBINITEVE BINARE

Kur zbatoni kombinime në harduer ose programim në gjuhën e asamblesë, është e rëndësishme të jeni në gjendje të përpunoni regjistrimet e kombinimeve në format binar. Në këtë rast, çdo kombinim i n elementeve të m duhet të specifikohet në formën e një numri binar n-bit (B n,...B j,...B 1), ku shifrat e njësive m tregojnë elementet e kombinim, dhe shifrat e mbetura (nm) kanë vlera zero. Natyrisht, me këtë formë shënimi, kombinime të ndryshme duhet të ndryshojnë në renditjen e shifrave të 1-së, dhe ka vetëm mënyra C(n,m) për të renditur m njës ose (nm) zero në një grup binar n-bit. Për shembull, tabela e mëposhtme liston të 6 kombinimet e tilla binare, të cilat ofrojnë numra binarë 4-bitësh për të gjitha kombinimet e 4 elementeve të një grupi arbitrar (E 1 , E 2 , E 3 , E 4 ) me 2:

Në rastin e përgjithshëm, detyra e numërimit të kombinimeve të tilla binare zbret në një kërkim sistematik të të gjitha grupeve binare n-bit me rregullime të ndryshme të biteve m një dhe (nm) zero. Në formën më të thjeshtë, një kërkim i tillë zbatohet metoda të ndryshme transpozicionet e biteve ngjitur me zhvendosje (algoritmet transpozitive-shift). Këto janë algoritme përsëritëse dhe emrat e tyre pasqyrojnë natyrën e operacioneve të kryera në çdo hap. Procedurat përsëritëse algoritmet e zhvendosjes transpozitive formojnë sekuenca kombinimesh binare që fillojnë me një grup binar, ku të gjitha janë të përqendruara në shifrat e rendit të ulët (në të djathtë) dhe mbarojnë kur të gjitha 1-të janë në shifrat e rendit të lartë (në të majtë ):

Ndërsa përputhen në kombinimet fillestare dhe përfundimtare, këto sekuenca ndryshojnë në rendin në të cilin renditen grupet binare të ndërmjetme. Sidoqoftë, në të gjitha rastet, çdo kombinim binar pasues formohet nga ai i mëparshmi si rezultat i kryerjes së operacioneve përkatëse të transpozimit dhe zhvendosjes. Në të njëjtën kohë, algoritme të ndryshme të zhvendosjes transpozitive ndryshojnë në mënyrën se si zgjedhin një palë bit për transpozim dhe një grup bitesh për zhvendosje. Kjo specifikë diskutohet më poshtë për algoritmet e transpozimit me zhvendosje majtas dhe djathtas.

Në algoritmin e transpozimit me një zhvendosje majtas, në çdo hap, kombinimi binar tjetër fitohet nga ai aktual duke zëvendësuar çiftin më të majtë të shifrave 01 me 10 (transpozim) dhe duke zhvendosur grupin e shifrave të njësive kryesore, nëse ka, afër çifti 10 i marrë pas transpozimit (ndërrimit). Nëse në këtë rast nuk ka njësi në shifrat kryesore në kombinimin binar aktual, atëherë zhvendosja nuk bëhet, edhe kur njësia kryesore fitohet pas transpozimit nga këtë hap. Zhvendosja gjithashtu nuk kryhet kur nuk ka zero në bitet më domethënëse përpara çiftit 10 të marrë pas transpozimit. Veprimet e konsideruara ilustrohen nga shembulli i mëposhtëm i kryerjes së dy përsëritjeve të njëpasnjëshme të këtij algoritmi, ku në një përsëritje (15) kryhet vetëm transpozimi (T") dhe në një përsëritje tjetër (16) transpozimi plotësohet nga një zhvendosje (T"+S"):

Në algoritmin e transpozimit djathtas, hapa konceptualisht të ngjashëm kryhen në çdo hap. Vetëm transpozimi siguron që bitet më të djathta të 01 të zëvendësohen me 10 (në vend të atyre më të majtët), dhe më pas të gjitha ato në të djathtë të tij të zhvendosen në bitet më pak të rëndësishme. Si më parë, zhvendosja kryhet vetëm nëse ka njësi që mund të zhvendosen në të djathtë. Veprimet e marra në shqyrtim ilustrohen nga shembulli i mëposhtëm i kryerjes së dy përsëritjeve të njëpasnjëshme të këtij algoritmi, ku në një përsëritje (3) kryhet vetëm transpozimi (T"), dhe në përsëritjen tjetër (4) transpozimi plotësohet me një zhvendosje ( T"+S"):

Duhet të theksohet se përsëritjet e të dy algoritmeve mund të shkruhen në formë shtesë nëse kombinimet binare interpretohen si numra të plotë në sistemin e numrave bazë 2, në veçanti, për algoritmin e transpozimit me një zhvendosje djathtas, çdo kombinim binar tjetër (B" n ,…B" j , …B" 1), mund të merret gjithmonë nga kombinimi aktual (B n,…B j,…B 1) duke kryer operacionet e mbledhjes së numrave të plotë duke përdorur formulën shtesë të mëposhtme:

Në këtë formulë shtesë, eksponentët e fuqive të dyseve f dhe t tregojnë, përkatësisht, numrin e shifrave zero të rendit të ulët të kombinimit binar aktual dhe numrin e njësheve në një rresht në të majtë të tyre. Për shembull, për kombinimin e katërt binar (001110) me n=6 shifra f =1 dhe t =3. Prandaj, llogaritja e kombinimit binar të ardhshëm duke përdorur formulën shtesë në përsëritjen 5 do të japë rezultatin e mëposhtëm, ekuivalent me kryerjen e operacioneve të transpozimit dhe zhvendosjes:

Për analiza krahasuese nga algoritmet e konsideruara të transpozimit me zhvendosje majtas dhe djathtas, këshillohet të krahasohen sekuencat e kombinimeve binare që ato gjenerojnë në përsëritjet e tyre. Tabela e mëposhtme tregon dy sekuenca të tilla të kombinimeve binare të 4 elementeve nga 2, të cilat përftohen nga algoritmet e zhvendosjes majtas (TSL) dhe djathtas (TSR), përkatësisht:

Duke krahasuar këto 2 sekuenca, mund të shihni se ato janë pasqyrë e kundërt. Kjo do të thotë që çdo dy kombinime binare që ndodhen në to në të njëjtën distancë nga skajet reciprokisht të kundërta të sekuencave të tyre janë një imazh pasqyrë i njëri-tjetrit, domethënë, ato përkojnë kur indeksimi i biteve në cilindo prej tyre është i kundërt. Për shembull, modeli i dytë binar nga fillimi i sekuencës TSL (0101) është një imazh pasqyrë i modelit binar (1010) që është i dyti nga fundi i sekuencës TSR. Në përgjithësi, çdo kombinim binar me numrin i të një sekuence është një imazh pasqyrë i një kombinimi binar me numrin (ni+1) të një sekuence tjetër. Kjo marrëdhënie midis këtyre sekuencave është pasojë e natyrës simetrike të operacioneve të transpozimit dhe zhvendosjes në dy algoritmet e konsideruara për numërimin e kombinimeve binare.

Duhet të theksohet se formati binar mund të përdoret gjithashtu për të regjistruar kombinime me përsëritje të elementeve. Për ta bërë këtë, është e nevojshme të krijohet një korrespondencë një-për-një midis kombinimeve me përsëritje dhe kombinime binare, të cilat janë ndërtuar si më poshtë. Le të ketë një kombinim arbitrar me përsëritjet, i cili përftohet duke zgjedhur m elementë opsionalisht të ndryshëm nga n elementët e grupit gjenerues. Për të vendosur përputhjen e dëshiruar, së pari duhet të shtoni të gjithë elementët e grupit formues (mace) në kombinim dhe më pas të renditni lidhjen (renditjen) që rezulton në mënyrë që të gjithë elementët identikë të jenë krah për krah. Rezultati është një sekuencë e elementeve (n+m), ku ka n grupe elementësh identikë. Do të ketë një total prej (n+m1) boshllëqesh ndërmjet elementeve, ndër të cilat do të ketë (n1) boshllëqe midis grupeve të elementeve identike dhe m boshllëqe midis elementeve brenda grupeve. Për qartësi, mund të vendosni simbolet "|" në hapësirat e treguara. dhe "", respektivisht. Nëse tani përshtatim 1 me hapësirat midis grupeve (|) dhe 0 me të gjitha hapësirat e tjera (), marrim një kombinim binar. Ai formohet nga një grup binar bitësh (n+m1), ku (n1) janë një dhe m zero bit, vendndodhja e të cilave korrespondon në mënyrë unike me kombinimin origjinal me përsëritjet e elementeve n deri në m. Teknika e konsideruar e transformimit ilustrohet nga shembulli i mëposhtëm i ndërtimit të një kombinimi binar (1001101) duke përdorur një kombinim me përsëritje (BBD), elementët e të cilit zgjidhen nga grupi gjenerues i pesë shkronjave të para latine:

Në përgjithësi, numri i grupeve të tilla binare përcakton numrin e mënyrave për të renditur (n1) njësitë (ose m zero) në (n+m1) shifra binare. Kjo vlerë është padyshim e barabartë me numrin e kombinimeve nga (n+m1) me (n1) ose me m, domethënë C(n+m1,n1) ose C(n+m1,m), që është e barabartë me numri i kombinimeve me përsëritje f( n,m) të n elementeve, m secili. Kështu, duke pasur një korrespodencë një-për-një midis kombinimeve me përsëritje dhe kombinime binare, është e ligjshme që të reduktohet numërimi i kombinimeve me përsëritje në numërimin e kombinimeve binare, për shembull, duke përdorur algoritme transpozimi me zhvendosje majtas ose djathtas. Pas kësaj, ju vetëm duhet të rivendosni kombinimet e kërkuara me përsëritje duke përdorur kombinimet binare që rezultojnë. Kjo mund të bëhet gjithmonë duke përdorur teknikën e mëposhtme të rikuperimit.

Lëreni grupin kryesor, nga elementët e të cilit formohen kombinime me përsëritje të m elementeve jo domosdoshmërisht të ndryshëm, të renditet në mënyrë arbitrare në mënyrë që secili prej elementeve të tij të ketë një numër të caktuar serik nga 1 në n. Le të zbatojmë edhe numërimin e kombinimeve binare të (n+m1) shifrave binare, ku (n1) njëshe dhe m zero shifra. Çdo kombinim binar që rezulton mund të plotësohet në të majtë me një shifër fiktive të njësisë dhe të gjitha shifrat e njësive mund të numërohen nga e majta në të djathtë me numra të plotë nga 1 në n. Atëherë numri i zerave në një rresht pas çdo njësie të i-të të kombinimit binar do të jetë i barabartë me numrin e rasteve të elementit të i-të të grupit kryesor në kombinimin përkatës me përsëritje. Teknika e konsideruar ilustrohet nga shembulli i mëposhtëm, ku, duke përdorur një kombinim binar (1001101), rivendoset një kombinim me përsëritjet e BBD, elementët e të cilit janë zgjedhur nga grupi gjenerues i pesë shkronjave të para latine të shkruara në rendit alfabetik, dhe mbivendosja tregon elementet që mungojnë nga ky kombinim:

Kryerja e veprimeve të ngjashme në kushte ky shembull, mund të listoni të 35 kombinimet binare që formojnë grupe binare 7-bitësh, ku ka 4 njësh dhe 3 zero, dhe të rivendosni kombinimet përkatëse me përsëritje të 5 elementeve nga 3.

Për ta bërë materialin më të lehtë për t'u lundruar, unë do të shtoj përmbajtjen e kësaj teme:

Hyrje. Komplete dhe përzgjedhje.

Në këtë temë do të shikojmë konceptet bazë të kombinatorikës: permutacionet, kombinimet dhe vendosjet. Le të zbulojmë thelbin e tyre dhe formulat me të cilat mund të gjeni sasinë e tyre.

Për të punuar, na duhen disa informacione ndihmëse. Le të fillojmë me një koncept kaq themelor matematikor si një grup. Koncepti i një grupi u diskutua në detaje në temën "Koncepti i një grupi. Metodat e përcaktimit të grupeve".

Shumë tregim i shkurtër rreth kompleteve: shfaq\fsheh

Me pak fjalë: një grup është një koleksion objektesh. Shkruani grupe në mbajtëse kaçurrelë. Rendi në të cilin janë shkruar elementet nuk ka rëndësi; nuk lejohen përsëritjet e elementeve. Për shembull, grupi i shifrave të numrit 11115555999 do të jetë: $$1,5,9$$. Bashkësia e bashkëtingëlloreve në fjalën "këlysh tigër" është: $$t, g, r, n, k$$. Shënimi $5\në A$ do të thotë që elementi 5 i përket grupit $A=$1,5,9 $$. Numri i elementeve në një bashkësi të fundme quhet pushtet të këtij grupi dhe shënojnë $|A|$. Për shembull, për një grup $A=$1,5,9 $$ që përmban 3 elementë, kemi: $|A|=3$.

Konsideroni një grup të caktuar të fundëm jo bosh $U$, kardinaliteti i të cilit është $n$, $|U|=n$ (d.m.th., grupi $U$ ka $n$ elementë). Le të prezantojmë një koncept si mostër(disa autorë e quajnë tuple). Me një mostër të vëllimit $k$ nga $n$ elementë (shkurtuar si $(n,k)$-shembull) nënkuptojmë një grup elementësh $(a_1, a_2,\ldots, a_k)$, ku $a_i\in U$. Një përzgjedhje quhet e renditur nëse rendi i elementeve të tij është specifikuar. Dy mostra të renditura që ndryshojnë vetëm në renditjen e elementeve janë të ndryshme. Nëse rendi i elementeve të mostrës nuk është i rëndësishëm, atëherë kampioni quhet i pa renditur.

Vini re se përkufizimi i një përzgjedhjeje nuk thotë asgjë për përsëritjet e elementeve. Ndryshe nga elementët e grupit, elementët e përzgjedhjes mund të përsëriten.

Për shembull, merrni parasysh grupin $U=$a,b,c,d,e$$. Kompleti $U$ përmban 5 elemente, d.m.th. $|U|=5$. Një mostër pa përsëritje mund të jetë: $(a,b,c)$. Kjo përzgjedhje përmban 3 elemente, d.m.th. madhësia e këtij kampioni është 3. Me fjalë të tjera, është një mostër $(5,3)$.

Një mostër me përsëritje mund të jetë si kjo: $(a,a,a,a,a,c,c,d)$. Ai përmban 8 elemente, d.m.th. vëllimi i tij është 8. Me fjalë të tjera, ky është një mostër $(5,8)$.

Le të shqyrtojmë edhe dy modele të tjera $(5,3)$: $(a,b,b)$ dhe $(b,a,b)$. Nëse supozojmë se mostrat tona janë të pa renditura, atëherë mostra $(a,b,b)$ është e barabartë me mostrën $(b,a,b)$, d.m.th. $(a,b,b)=(b,a,b)$. Nëse supozojmë se mostrat tona janë të porositura, atëherë $(a,b,b)\neq(b,a,b)$.

Le të shohim një shembull tjetër, pak më pak abstrakt:) Supozoni se ka gjashtë karamele në një shportë dhe të gjitha janë të ndryshme. Nëse karamelin e parë e lidhim me numrin 1, karamele të dytë me numrin 2, e kështu me radhë, atëherë grupi i mëposhtëm mund të shoqërohet me karamele në shportë: $U=$1,2,3,4, 5,6$$. Imagjinoni që ne rastësisht vendosim dorën në një shportë në mënyrë që të nxjerrim tre karamele. Karamelet e nxjerra janë përzgjedhja. Meqenëse marrim 3 karamele nga 6, marrim një mostër (6,3). Rendi në të cilin vendosen ëmbëlsirat në pëllëmbë është krejtësisht i parëndësishëm, kështu që ky mostër është i pa renditur. Epo, dhe meqenëse të gjitha ëmbëlsirat janë të ndryshme, zgjedhja është pa përsëritje. Pra, në këtë situatë po flasim për një mostër të parregulluar (6,3) pa përsëritje.

Tani le të afrohemi nga ana tjetër. Le të imagjinojmë se jemi në një fabrikë prodhimi karamele, dhe kjo fabrikë prodhon katër lloje karamele. Seti $U$ në këtë situatë është si më poshtë: $U=$1,2,3,4 $$ (çdo numër është përgjegjës për llojin e vet të ëmbëlsirave). Tani le të imagjinojmë që të gjitha ëmbëlsirat derdhen në një gropë të vetme, pranë së cilës jemi duke qëndruar. Dhe, duke vendosur pëllëmbët, ne zgjedhim 20 karamele nga kjo rrjedhë. Një grusht ëmbëlsirash është një shembull. A ka rëndësi radha në të cilën vendosen ëmbëlsirat në një grusht? Natyrisht, jo, kështu që mostra është e parregulluar. Ka vetëm 4 lloje karamele, dhe ne zgjedhim njëzet copa nga rrjedha e përgjithshme - përsëritja e varieteteve është e pashmangshme. Në të njëjtën kohë, mostrat mund të jenë shumë të ndryshme: madje mund të kemi të gjitha karamele të të njëjtit lloj. Prandaj, në këtë situatë kemi të bëjmë me një mostër të parenditur (4,20) me përsëritje.

Le të shohim disa shembuj të tjerë. Le të shkruhen 7 shkronja të ndryshme në kube: k, o, n, f, e, t, a. Këto shkronja formojnë grupin $U=$k,o,n,f,e,t,a$$. Le të themi se nga këto kube duam të bëjmë "fjalë" me 5 shkronja. Shkronjat e këtyre fjalëve (për shembull, "konfe", "tenko" dhe kështu me radhë) formojnë (7,5)-zgjedhje: $(k,o,n,f,e)$, $(t,e,n ,k ,o)$, etj. Natyrisht, rendi i shkronjave në një mostër të tillë është i rëndësishëm. Për shembull, fjalët "nokft" dhe "kfton" janë të ndryshme (megjithëse ato përbëhen nga të njëjtat shkronja), sepse rendi i shkronjave në to nuk përputhet. Nuk ka përsëritje të shkronjave në "fjalë" të tilla, sepse ka vetëm shtatë kube. Pra, grupi i shkronjave të secilës fjalë është një mostër e renditur (7,5) pa përsëritje.

Një shembull tjetër: ne bëjmë të gjitha llojet e numrave tetëshifrorë nga katër shifrat 1, 5, 7, 8. Për shembull, 11111111, 15518877, 88881111 e kështu me radhë. Kompleti $U$ është: $U=$1,5,7,8$$. Shifrat e secilit numër të përbërë formojnë një mostër (4,8). Rendi i shifrave në një numër është i rëndësishëm, d.m.th. mostra është porositur. Përsëritjet janë të lejuara, pra këtu kemi të bëjmë me një mostër të renditur (4,8) me përsëritje.

Vendosjet pa përsëritje të elementeve $n$ me $k$

Vendosja pa përsëritje e elementeve $n$ nga $k$ - e renditur $(n,k)$-përzgjedhja pa përsëritje.

Meqenëse elementet në kampionin në shqyrtim nuk mund të përsëriten, ne nuk mund të zgjedhim më shumë elementë në kampion sesa në grupin origjinal. Prandaj, për mostra të tilla është e vërtetë pabarazia e mëposhtme: $n≥ k$. Numri i vendosjeve pa përsëritje të elementeve $n$ nga $k$ përcaktohet nga formula e mëposhtme:

\fillimi(ekuacioni)A_(n)^(k)=\frac(n{(n-k)!} \end{equation} !}

Çfarë do të thotë shenja "!": shfaq\fsheh

Regjistrimi "n!" (lexo "en faktorial") tregon prodhimin e të gjithë numrave nga 1 në n, d.m.th.

$$ n!=1\cdot2\cdot 3\cdot \ldots\cdot n $$

Sipas përkufizimit, supozohet se $0!=1!=1$. Për shembull, le të gjejmë 5!:

$$ 5!=1\cdot 2\cdot 3\cdot 4\cdot 5=120. $$

Shembulli nr. 1

Alfabeti përbëhet nga një grup simbolesh $E=$+,*,0,1,f$$. Le të përcaktojmë numrin e fjalëve të tilla me tre karaktere në këtë alfabet që nuk përmbajnë shkronja të përsëritura.

Me fjalë me tre karaktere nënkuptojmë shprehje si "+*0" ose "0f1". Kompleti $E$ ka pesë elementë, kështu që shkronjat e fjalëve me tre karaktere formojnë (5,3)-zgjedhje. Pyetja e parë është: a janë këto mostra të porositura apo jo? Fjalët që ndryshojnë vetëm në renditjen e shkronjave të tyre konsiderohen të ndryshme, kështu që renditja e elementeve në mostër është e rëndësishme. Kjo do të thotë që mostra është e porositur. Pyetja e dytë: a lejohen përsëritjet apo jo? Përgjigja për këtë pyetje jepet nga kushti: fjalët nuk duhet të përmbajnë shkronja të përsëritura. Për ta përmbledhur: shkronjat e secilës fjalë që plotëson kushtet e problemit formojnë një mostër të renditur (5,3) pa përsëritje. Me fjalë të tjera, shkronjat e secilës fjalë formojnë një vendosje pa përsëritje të 5 elementeve të 3. Këtu janë shembuj të vendosjeve të tilla:

$$ (+,*,f), \; (*,+,f), \; (1,+,0) $$

Ne jemi të interesuar për numrin total të këtyre vendosjeve. Sipas formulës (1), numri i vendosjeve pa përsëritje të 5 elementeve nga 3 do të jetë si më poshtë:

$$ A_(5)^(3)=\frac(5{(5-3)!}=\frac{5!}{2!}=60. $$ !}

ato. mund të krijoni 60 fjalë me tre karaktere, shkronjat e të cilave nuk do të përsëriten.

Përgjigju: 60.

Vendosjet me përsëritje të elementeve $n$ prej $k$

Vendosje me përsëritje të elementeve $n$ nga $k$ - përzgjedhje e renditur $(n,k)$ me përsëritje.

Numri i vendosjeve me përsëritje të elementeve $n$ prej $k$ përcaktohet nga formula e mëposhtme:

\fillimi(ekuacioni)\bar(A)_(n)^(k)=n^k \fund(ekuacioni)

Shembulli nr. 2

Sa numra pesëshifrorë mund të bëhen nga bashkësia e shifrave $$5,7,2$$?

Nga ky grup numrash mund të bëni numra pesëshifrorë 55555, 75222, e kështu me radhë. Shifrat e secilit numër të tillë formojnë një mostër (3,5): $(5,5,5,5,5)$, $(7,5,2,2,2)$. Le të pyesim veten: çfarë lloj mostrash janë këto? Së pari, shifrat në numra mund të përsëriten, pra kemi të bëjmë me mostra me përsëritje. Së dyti, renditja e shifrave në një numër është e rëndësishme. Për shembull, 27755 dhe 77255 - numra të ndryshëm. Rrjedhimisht kemi të bëjmë me mostra të renditura (3,5) me përsëritje. Ne gjejmë numrin total të mostrave të tilla (d.m.th. numrin e përgjithshëm të numrave pesëshifrorë të kërkuar) duke përdorur formulën (2):

$$ \bar(A)_(3)^(5)=3^5=243. $$

Prandaj, nga shifrat e dhëna mund të bëhen 243 numra pesëshifrorë.

Përgjigju: 243.

Permutacione pa përsëritje të elementeve $n$

Një ndërrim pa përsëritje e elementeve $n$ është një përzgjedhje e renditur $(n,n)$ pa përsëritje.

Në thelb, një ndërrim pa përsëritje është rast i veçantë vendosje pa përsëritje, kur madhësia e kampionit është e barabartë me fuqinë e grupit origjinal. Numri i permutacioneve pa përsëritje të elementeve $n$ përcaktohet nga formula e mëposhtme:

\fillimi(ekuacioni)P_(n)=n! \fund (ekuacion)

Nga rruga, kjo formulë është e lehtë për t'u marrë nëse mendoni se $P_n=A_(n)^(n)$. Pastaj marrim:

$$ P_n=A_(n)^(n)=\frac(n{(n-n)!}=\frac{n!}{0!}=\frac{n!}{1}=n! $$ !}

Shembulli nr. 3

Ka pesë racione akullore në ngrirje nga kompani të ndryshme. Në sa mënyra mund të zgjidhni radhën në të cilën hahen?

Lëreni numrin 1 të korrespondojë me akulloren e parë, numrin 2 me të dytën, e kështu me radhë. Do të marrim grupin $U=$1,2,3,4,5$$, i cili do të përfaqësojë përmbajtjen e ngrirësit. Rendi i ngrënies mund të jetë si më poshtë: $(2,1,3,5,4)$ ose si më poshtë: $(5,4,3,1,2)$. Çdo grup i tillë është një mostër (5,5). Do të jetë e rregullt dhe pa përsëritje. Me fjalë të tjera, çdo mostër e tillë është një ndërrim i 5 elementeve të grupit origjinal. Sipas formulës (3), numri i përgjithshëm i këtyre permutacioneve është:

$$ P_5=5!=120. $$

Rrjedhimisht janë 120 porosi për zgjedhjen e radhës së të ngrënit.

Përgjigju: 120.

Permutacione me përsëritje

Ndërrimi me përsëritje është një shembull i renditur $(n,k)$ me përsëritje, në të cilin elementi $a_1$ përsëritet $k_1$ herë, $a_2$ përsëritet $k_2$ herë dhe kështu me radhë, deri në elementin e fundit $ a_r$, e cila përsëritet $ k_r$ herë. Në këtë rast, $k_1+k_2+\ldots+k_r=k$.

Numri i përgjithshëm i permutacioneve me përsëritje përcaktohet nga formula:

\fillimi(ekuacioni)P_(k)(k_1,k_2,\ldots,k_r)=\frac(k{k_1!\cdot k_2!\cdot \ldots \cdot k_r!} \end{equation} !}

Shembulli nr. 4

Fjalët përbëhen në bazë të alfabetit $U=$a,b,d$$. Sa fjalë të ndryshme mund të përbëhen nga shtatë karaktere nëse në këto fjalë shkronja “a” duhet të përsëritet 2 herë; shkronja "b" - 1 herë, dhe shkronja "d" - 4 herë?

Këtu janë shembuj të fjalëve të kërkimit: "aabdddd", "daddabd" dhe kështu me radhë. Shkronjat e secilës fjalë formojnë një mostër (3,7) me përsëritje: $(a,a,b,d,d,d,d)$, $(d,a,d,d,a,b,d )$ dhe etj. Çdo mostër e tillë përbëhet nga dy elemente "a", një element "b" dhe katër elemente"d". Me fjalë të tjera, $k_1=2$, $k_2=1$, $k_3=4$. Numri i përgjithshëm i përsëritjeve të të gjitha simboleve, natyrisht, është i barabartë me madhësinë e mostrës, d.m.th. $k=k_1+k_2+k_3=7$. Duke i zëvendësuar këto të dhëna në formulën (4), do të kemi:

$$ P_7(2,1,4)=\frac(7{2!\cdot 1!\cdot 4!}=105. $$ !}

Prandaj, numri i përgjithshëm i fjalëve të kërkimit është 105.

Përgjigju: 105.

Kombinime pa përsëritje të elementeve $n$ prej $k$ secili

Një kombinim pa përsëritje të elementeve $n$ nga $k$ është një mostër $(n,k)$-pa renditje pa përsëritje.

Numri i përgjithshëm i kombinimeve pa përsëritje të elementeve $n$ prej $k$ përcaktohet nga formula:

\fillimi(ekuacioni)C_(n)^(k)=\frac(n{(n-k)!\cdot k!} \end{equation} !}

Shembulli nr. 5

Shporta përmban letra me numra të plotë të shkruar nga 1 deri në 10. Nga shporta nxirren 4 letra dhe mblidhen numrat e shkruar në to. Sa grupe letrash të ndryshme mund të nxirren nga shporta?

Pra, në këtë problem grupi fillestar është: $U=$1,2,3,4,5,6,7,8,9,10$$. Nga ky grup ne zgjedhim katër elementë (d.m.th., katër letra nga koshi). Numrat e elementeve të nxjerra formojnë një përzgjedhje (10,4). Përsëritjet në këtë përzgjedhje nuk lejohen, pasi numrat e të gjitha kartave janë të ndryshëm. Pyetja është: a ka rëndësi radha në të cilën përzgjidhen letrat apo jo? Kjo është, për shembull, mostrat $(1,2,7,10)$ dhe $(10,2,1,7)$ janë të barabartë apo jo të barabartë? Këtu duhet t'i drejtoheni kushteve të problemit. Kartat hiqen për të gjetur më vonë shumën e elementeve. Kjo do të thotë që renditja e kartave nuk është e rëndësishme, pasi ndryshimi i vendeve të kushteve nuk do të ndryshojë shumën. Për shembull, mostra $(1,2,7,10)$ dhe mostra $(10,2,1,7)$ do të korrespondojnë me të njëjtin numër $1+2+7+10=10+2+1+ 7 = 20 dollarë. Përfundim: nga kushtet e problemit del se kemi të bëjmë me mostra të pa renditura. ato. duhet të gjejmë numrin total të mostrave të pa renditura (10,4) pa përsëritje. Me fjalë të tjera, ne duhet të gjejmë numrin e kombinimeve të 10 elementeve nga 4. Ne përdorim formulën (5) për këtë:

$$ C_(10)^(4)=\frac(10{(10-4)!\cdot 4!}=\frac{10!}{6!\cdot 4!}=210. $$ !}

Prandaj, numri i përgjithshëm i grupeve të kërkuara është 210.

Përgjigju: 210.

Kombinime me përsëritje të elementeve $n$ prej $k$ secili

Një kombinim me përsëritje të $n$ elementëve të $k$ është një mostër $(n,k)$-e pa renditur me përsëritje.

Numri i përgjithshëm i kombinimeve me përsëritje të elementeve $n$ prej $k$ përcaktohet nga formula:

\fillimi(ekuacioni)\bar(C)_(n)^(k)=\frac((n+k-1){(n-1)!\cdot k!} \end{equation} !}

Shembulli nr. 6

Imagjinoni sikur jemi në një fabrikë ëmbëlsirash, pranë një transportuesi përgjatë të cilit lëvizin katër lloje karamele. Vendosim duart në këtë rrjedhë dhe nxjerrim njëzet pjesë. Sa "kombinime karamele" të ndryshme mund të ketë në një grusht?

Nëse supozojmë se lloji i parë korrespondon me numrin 1, lloji i dytë - numri 2, e kështu me radhë, atëherë grupi fillestar në problemin tonë është si më poshtë: $U=$1,2,3,4$ $. Nga ky grup ne zgjedhim 20 elementë (d.m.th., të njëjtat 20 karamele nga linja e montimit). Një grusht ëmbëlsirash formon një mostër (4,20). Natyrisht, do të ketë përsëritje të varieteteve. Pyetja është, a ka rëndësi renditja e elementeve në mostër apo jo? Nga kushtet e problemit rezulton se radha në të cilën janë renditur elementet nuk ka rëndësi. Për ne nuk ka asnjë ndryshim nëse grushti përmban fillimisht 15 karamele me çokollatë, dhe më pas 4 karamele me çokollatë, ose në fillim 4 karamele me çokollatë dhe vetëm pastaj 15 karamele. Pra, kemi të bëjmë me një kampion të pa renditur (4,20) me përsëritje. Për të gjetur numrin total të këtyre mostrave ne përdorim formulën (6):

$$ \bar(C)_(4)^(20)=\frac((4+20-1){(4-1)!\cdot 20!}=\frac{23!}{3!\cdot 20!}=1771. $$ !}

Prandaj, numri i përgjithshëm i kombinimeve të kërkuara është 1771.