Комбинација е неуреден избор на елементи од конечно множество со фиксен број и без повторувања на елементите. Различните комбинации мора да се разликуваат барем во еден елемент, а редоследот на елементите не е важен. На пример, од множеството на сите самогласки на латински букви (AEIOU), можете да направите 10 различни комбинации од 3 букви, формирајќи ги следните неподредени тројки:
AEI, AEO, AEU, AIO, AIU, AOU, EIO, EIU, EOU, IOU.
Интересно е да се забележи дека од истите пет букви можете да добиете и 10 различни комбинации ако ги комбинирате по 2 букви истовремено, правејќи ги следните неподредени парови:
AE, AI, AO, AU, EI, EO, EU, IO, IU, OU.
Меѓутоа, ако ги комбинирате истите самогласки латински букви за 4, ќе ги добиете само следните 5 различни комбинации:
AEIO, AEIU, AIOU, EIOU, AEOU.
Општо земено, за означување на бројот на комбинации на n различни елементи на m елементи, се користи следната функционална, индексна или векторска (Appel) симболика:
Без оглед на формата на нотација, бројот на комбинации на n елементи по m елементи може да се одреди со помош на следните мултипликативни и факторски формули:
Лесно е да се провери дали резултатот од пресметките користејќи ги овие формули се совпаѓа со резултатите од примерот дискутиран погоре со комбинации на самогласки со латински букви. Особено, со n=5 и m=3, пресметките со користење на овие формули ќе го дадат следниот резултат:
Во општиот случај, формулите за бројот на комбинации имаат комбинирано значење и важат за сите цели броеви од n и m, така што n > m > 0. Ако m > n и m< 0, то число сочетаний равно 0, так как в этом случае основное множество из n элементов вообще не имеет подмножеств мощности m:
Дополнително, корисно е да се запаметат следните ограничувачки броеви на комбинации, кои лесно може да се проверат со директна замена во мултипликативните и факторските формули:
Исто така, треба да се забележи дека формулата за множење останува валидна дури и кога n е реален број, сè додека m е сè уште цел број. Меѓутоа, тогаш резултатот од пресметката користејќи го, додека ја одржува формалната важност, го губи своето комбинаторно значење.
ИДЕНТИТЕТИ НА КОМБИНАЦИИ
Практичната употреба на мултипликативни и факторски формули за одредување на бројот на комбинации за произволни вредности на n и m се покажува како мала продуктивност поради експоненцијалниот раст на факторителните производи на нивниот броител и именител. Дури и за релативно мали вредности од n и m, овие производи често ги надминуваат можностите за претставување цели броеви во современите компјутерски и софтверски системи. Покрај тоа, нивните вредности се покажаа значително поголеми од добиената вредност на бројот на комбинации, што може да биде релативно мал. На пример, бројот на комбинации од n=10 по m=8 елементи е само 45. Меѓутоа, за да ја пронајдете оваа вредност користејќи ја факторската формула, прво мора да пресметате многу поголеми вредности од 10! во броител и 8! во именителот:
За да ги елиминирате операциите кои одземаат многу време за обработка на големи количини, за да го одредите бројот на комбинации, можете да користите различни релации за повторување, кои директно произлегуваат од мултипликативните и факторските формули. Конкретно, следната рецидивна релација следи од мултипликативната формула, која ни овозможува да го земеме односот на неговите индекси надвор од знакот на бројот на комбинации:
Конечно, одржувањето на подлогата константна ја обезбедува следната рецидивна релација, која лесно се добива од факторската формула за бројот на комбинации:
По елементарните трансформации, трите релации на повторување може да се претстават во следните форми:
Ако сега ги собереме левата и десната страна на првите 2 формули и го намалиме резултатот за n, ќе добиеме важна рецидивна релација, која се нарекува идентитет на собирање комбинации на броеви:
Идентитетот на собирање обезбедува основно правило за повторување за ефикасно одредување на бројот на комбинации за големи вредности од n и m, бидејќи овозможува операциите за множење во факторските производи да се заменат со поедноставни операции за собирање и за помал број комбинации. Конкретно, користејќи го идентитетот на собирање, сега е лесно да се одреди бројот на комбинации на n=10 по m=8 елементи, што беше дискутирано погоре, со извршување на следнава низа на повторливи трансформации:
Дополнително, неколку корисни односи за пресметување на конечни суми може да се изведат од идентитетот на собирање, особено формулата за сумирање по подлога, која ја има следната форма:
Оваа релација се добива ако во идентитетот на собирање го прошириме повторувањето долж членот со најголемиот надреден знак додека неговиот подредник е поголем од 0. Следниот нумерички пример го илустрира овој процес на повторливи трансформации:
Формулата за сумирање на бројката често се користи за пресметување на збирот на силите на природните броеви. Конкретно, под претпоставка m=1, користејќи ја оваа формула лесно е да се најде збирот на првите n броеви од природната серија:
Друга корисна верзија на формулата за сумирање може да се добие со проширување на повторувањето на идентитетот на собирање долж членот со најмалиот надреден знак. Следниот нумерички пример ја илустрира оваа верзија на повторливи трансформации:
Во општ случај, како резултат на таквите трансформации, се добива збирот на броевите на комбинации, чиишто и двата индекса се разликуваат по еден од соседните членови, а разликата во индексите останува константна (во разгледуваниот пример е исто така еднакво на еден). Така, ја добиваме следната формула за собирање за двата индекса на комбинациски броеви:
Во прилог на релациите за повторување и формулите за сумирање дискутирани погоре, многу други корисни идентитети за комбинираните броеви се добиени во комбинаторната анализа. Најважната меѓу нив е симетрија идентитет, што изгледа вака:
Валидноста на идентитетот на симетријата може да се потврди во следниот пример со споредување на броевите на комбинации од 5 елементи со 2 и со (5 2) = 3:
Идентитетот на симетријата има очигледно комбинаторно значење, бидејќи, со одредување на бројот на опции за избор на m елементи од n елементи, истовремено го утврдува бројот на комбинации од преостанатите (nm) неизбрани елементи. Наведената симетрија веднаш се добива со замена на m со (nm) во факторската формула за бројот на комбинации:
Броевите и комбинираните идентитети се широко користени во различни области на модерната пресметковна математика. Сепак, нивните најпопуларни апликации се поврзани со Њутновиот бином и Паскаловиот триаголник.
БИНОМИНА ТЕОРЕМА
За да се извршат различни математички трансформации и пресметки, важно е да може да се претстави која било природна моќ на алгебарски бином (бином) во форма на полином. За мали сили, саканиот полином може лесно да се добие со директно множење на биномите. Конкретно, следните формули за квадрат и коцка од збир од два члена се добро познати од курсот по елементарна математика:
Во општиот случај, за произволен степен n на бином, бараното претставување во форма на полином е обезбедено со биномната теорема на Њутн, која ја декларира следнава еднаквост за вистинита:
Оваа еднаквост обично се нарекува Њутнов бином. Полиномот од неговата десна страна се формира од збирот на производите од n членови X и Y од биномот од левата страна, а коефициентите пред нив се нарекуваат биномни и се еднакви на бројот на комбинации со индекси, кои се добиваат од нивните овластувања. Со оглед на особената популарност на Њутновата биномна формула во комбинаторната анализа, поимите биномен коефициент и број на комбинации генерално се сметаат за синоними.
Очигледно, формулите за квадрат и коцка со збир се посебни случаи на биномната теорема за n=2 и n=3, соодветно. За справување со повисоки степени (n>3), треба да се користи Њутновата биномна формула. Неговата примена за бином од четврти степен (n=4) е прикажана со следниот пример:
Треба да се забележи дека биномната формула им била позната уште пред Њутн на средновековните математичари од Арапскиот Исток и Западна Европа. Затоа, неговото општо прифатено име не е историски фер. Заслугата на Њутн е што тој ја генерализирал оваа формула на случајот на произволен реален експонент r, кој може да земе какви било позитивни или негативни рационални и ирационални вредности. Во општиот случај, таквата Њутнова биномна формула има бесконечен збир на десната страна и обично се пишува на следниов начин:
На пример, со позитивна фракциона вредност на експонентот r=1/2, земајќи ги предвид вредностите на биномните коефициенти, се добива следново проширување:
Во општиот случај, биномната формула на Њутн за кој било експонент е специјална верзија на формулата на Маклаурин, која дава проширување на произволна функција во серија на моќност. Њутн покажа дека за |z|< 1 этот ряд сходится, и сумма в правой части становится конечной. При любой натуральной степени r = n в правой части также получается конечная сумма из (n+1) первых слагаемых, так как все C(n, k>n) = 0 . Ако сега поставиме Z=X/Y и ги помножиме левата и десната страна со Yn, ќе добиеме верзија на Њутновата биномна формула дискутирана погоре.
И покрај неговата универзалност, биномната теорема го задржува своето комбинаторно значење само за ненегативните цели броеви на биномот. Во овој случај, може да се користи за докажување на неколку корисни идентитети за биномни коефициенти. Конкретно, формулите за сумирање на броевите на комбинации по подлога и по двата индекса беа дискутирани погоре. Идентитетот на сумирање на надреден знак што недостасува може лесно да се добие од биномната формула на Њутн со ставање X = Y = 1 или Z = 1 во неа:
Друг корисен идентитет ја утврдува еднаквоста на збировите на биномните коефициенти со парни и непарни броеви. Веднаш се добива од биномната формула на Њутн ако X = 1 и Y = 1 или Z = 1:
Конечно, од двата разгледани идентитети го добиваме идентитетот на збирот на биномни коефициенти со само парни или само непарни броеви:
Врз основа на разгледуваните идентитети и повторливото правило за отстранување на индексите од под знакот на бројот на комбинации, може да се добијат голем број интересни врски. На пример, ако во формулата за сумирање на надредениот знак го замениме n насекаде со (n1) и ги отстраниме индексите во секој член, ја добиваме следната релација:
Користејќи слична техника во формулата за збир на биномни коефициенти со парни и непарни броеви, можно е да се докаже валидноста на, на пример, следнава врска:
Друг корисен идентитет ви овозможува лесно да го пресметате збирот на производите на симетрично лоцираните биномни коефициенти на два биноми со произволни степени n и k користејќи ја следната Коши формула:
Валидноста на оваа формула произлегува од потребната еднаквост на коефициентите за кој било степен m од променливата Z на левата и десната страна на следната идентична релација:
Во специјалниот случај кога n=k=m, земајќи го предвид идентитетот на симетрија, се добива попопуларна формула за збир на квадрати на биномни коефициенти:
Многу други корисни идентитети за биномните коефициенти може да се најдат во обемната литература за комбинаторна анализа. Сепак, нивната најпозната практична примена е поврзана со триаголникот на Паскал.
ТРИАГОЛНИК НА ПАСКАЛ
Паскаловиот аритметички триаголник формира бесконечна нумеричка табела составена од биномни коефициенти. Неговите линии се подредени според моќта на биномите од врвот до дното. Во секоја линија, биномните коефициенти се подредени по растечки редослед на надписите на соодветните комбинации од лево кон десно. Паскаловиот триаголник обично се пишува или во рамнокрак или во правоаголна форма.
Повизуелен и почест е форматот на рамнокрак, каде што биномните коефициенти, зашеметени, формираат бесконечен рамнокрак триаголник. Неговиот почетен фрагмент за биноми до 4 степен (n=4) ја има следната форма:
Општо земено, Паскаловиот рамнокрак триаголник обезбедува погодно геометриско правило за одредување биномни коефициенти, кое се заснова на идентитетите на собирање и симетријата на комбинациите на броеви. Конкретно, според идентитетот на собирање, секој биномен коефициент е збир од двата коефициенти од претходниот ред најблиску до него. Според идентитетот на симетријата, Паскаловиот рамнокрак триаголник е симетричен во однос на неговата симетрала. Така, секоја од неговите линии е нумерички палиндром на биномни коефициенти. Посочените алгебарски и геометриски карактеристики овозможуваат лесно проширување на рамнокрак триаголник на Паскал и постојано наоѓање на вредностите на биномните коефициенти на произволни моќи.
Меѓутоа, за да се проучат различните својства на триаголникот на Паскал, попогодно е да се користи формално построгиот правоаголен формат. Во овој формат, тој е одреден со пониска триаголна матрица на биномни коефициенти, каде што тие формираат бесконечен правоаголен триаголник. Почетниот фрагмент од правоаголен триаголник на Паскал за биноми до 9-ти степен (n=9) ја има следната форма:
Геометриски, ваква правоаголна табела се добива со хоризонтално деформирање на Паскаловиот рамнокрак триаголник. Како резултат на тоа, сериите на броеви паралелни на страничните страни на рамнокрак триаголник на Паскал се претвораат во вертикали и дијагонали на правоаголен триаголник на Паскал, а хоризонталните линии на двата триаголници се совпаѓаат. Во исто време, правилата за собирање и симетрија на биномните коефициенти остануваат валидни, иако правоаголен триаголник на Паскал ја губи визуелната симетрија карактеристична за неговиот рамнокрак пандан. За да се компензира ова, станува попогодно формално да се анализираат различните нумерички својства на биномните коефициенти за хоризонталите, вертикалите и дијагоналите на правоаголен триаголник на Паскал.
Започнувајќи ја анализата на хоризонталите на правоаголен триаголник на Паскал, лесно може да се забележи дека збирот на елементите од која било редица со број n е еднаков на 2n во согласност со формулата за собирање биноми по надреден знак. Од ова произлегува дека збирот на елементите над која било од хоризонталните линии со број n е еднаков на (2 n 1). Овој резултат станува сосема очигледен ако вредноста на збирот на елементите на секоја хоризонтална е запишана во бинарниот броен систем. На пример, за n=4 ова собирање може да се напише на следниов начин:
Еве уште неколку интересни својства на хоризонталите кои исто така се поврзани со моќноста на два. Излегува дека ако хоризонталниот број е сила од два (n=2 k), тогаш сите негови внатрешни елементи (освен надворешните) се парни броеви. Напротив, сите броеви на хоризонтална права ќе бидат непарни ако нејзиниот број е за еден помал од моќта од два (n=2 k 1). Валидноста на овие својства може да се потврди со проверка на парноста на внатрешните биномни коефициенти, на пример, во хоризонталите n=4 и n=3 или n=8 и n=7.
Сега бројот на редот на правоаголен триаголник на Паскал нека биде прост број p. Тогаш сите негови внатрешни биномни коефициенти се деливи со стр. Овој имот е лесно да се провери за мали вредности на прости контури броеви. На пример, сите внатрешни биномни коефициенти на петтата хоризонтална (5, 10 и 5) очигледно се деливи со 5. За да го докажете овој резултат за кој било прост хоризонтален број p, треба да ја напишете формулата за множење за неговите биномни коефициенти на следниов начин:
Бидејќи p е прост број и затоа не е делив со m!, производот на преостанатите множители на броителот на оваа формула мора да биде делив со m! за да се гарантира цел бројна вредност на биномниот коефициент. Следи дека односот во квадратни загради е природен број N и посакуваниот резултат станува очигледен:
Користејќи го овој резултат, можеме да утврдиме дека броевите на сите хоризонтални линии на триаголникот на Паскал, чии внатрешни елементи се деливи со даден прост број p, се сили на p, односно имаат форма n=p k. Конкретно, ако p=3, тогаш простиот број p ги дели не само сите внатрешни елементи од редот 3, како што е утврдено погоре, туку, на пример, 9-тата хоризонтална (9, 36, 84 и 126). Од друга страна, во триаголникот на Паскал е невозможно да се најде хоризонтална линија чии внатрешни елементи се деливи со композитен број. Во спротивно, бројот на таква хоризонтална линија мора истовремено да биде и моќ на прости делители на композитниот број со кој се делат сите негови внатрешни елементи, но тоа е невозможно од очигледни причини.
Разгледаните размислувања ни овозможуваат да го формулираме следниот општ критериум за деливост на хоризонталните елементи на триаголникот на Паскал. Најголемиот заеднички делител (GCD) на сите внатрешни елементи на која било хоризонтална права на триаголникот на Паскал со број n е еднаков на простиот број p ако n=pk или 1 во сите други случаи:
GCD(Cmn) = ( ) за која било 0< m < n .
Како заклучок од анализата на хоризонталите, вреди да се разгледа уште едно интересно својство што го има серијата биномни коефициенти што ги формираат. Ако биномните коефициенти на која било хоризонтална права со број n се помножат со последователните сили на бројот 10, а потоа се соберат сите овие производи, резултатот е 11 n. Формалното оправдување за овој резултат е замена на вредностите X=10 и Y=1 (или Z=1) во Њутновата биномна формула. Следниот нумерички пример го илустрира исполнувањето на ова својство за n=5:
Анализата на својствата на вертикалите на правоаголен триаголник на Паскал може да започне со проучување на индивидуалните карактеристики на нивните составни елементи. Формално, секоја вертикална m е формирана од следнава бесконечна низа од биномни коефициенти со константен надреден знак (m) и зголемување на знакот:
Очигледно, кога m=0 се добива низа од единици, а кога m=1 се формира низа природни броеви. Кога m=2 вертикалата е составена од триаголни броеви. Секој триаголен број може да се прикаже на рамнина во форма на рамностран триаголник, кој е исполнет со произволни предмети (јадра) распоредени во шаховска табла. Во овој случај, вредноста на секој триаголен број T k го одредува бројот на репрезентативни кернели, а индексот покажува колку редови на кернели се потребни за негово претставување. На пример, 4 почетни триаголни броеви ги претставуваат следните конфигурации на соодветниот број нуклеарни „@“ симболи:
Треба да се забележи дека на сличен начин може да се воведат во предвид квадратните броеви S k, кои се добиваат со квадратирање на природните броеви и, генерално, полигоналните фигурирани броеви формирани со редовно пополнување правилни многуаголници. Конкретно, 4-те почетни квадратни броеви може да се претстават на следниов начин:
Навраќајќи се на анализата на вертикалите на триаголникот на Паскал, можеме да забележиме дека следната вертикала на m=3 е исполнета со тетраедарски (пирамидални) броеви. Секој таков број P k го одредува бројот на јадра што може да се подредат во форма на тетраедар, а индексот одредува колку хоризонтални триаголни слоеви од редови на јадра се потребни за да се прикаже во тродимензионален простор. Во овој случај, сите хоризонтални слоеви мора да бидат претставени како последователни триаголни броеви. Елементите на следните вертикали на Паскаловиот триаголник за m>3 формираат низа хипертетраедални броеви, кои немаат визуелна геометриска интерпретација на рамнината или во тродимензионалниот простор, туку формално одговараат на повеќедимензионални аналози на триаголни и тетраедални броеви.
Иако вертикалните броеви серии на триаголникот на Паскал ги имаат разгледуваните поединечни обликувани карактеристики, за нив е можно да се пресметаат парцијалните збирови на вредностите на почетните елементи на ист начин, користејќи ја формулата за сумирање на броевите на комбинации по знак. . Во триаголникот на Паскал, оваа формула ја има следната геометриска интерпретација. Збирот на вредностите на n горните биномни коефициенти на која било вертикала е еднаков на вредноста на елементот од следната вертикала, која се наоѓа една линија подолу. Овој резултат е исто така конзистентен со геометриската структура на триаголните, тетраедарните и хипертетраедалните броеви, бидејќи претставувањето на секој таков број се состои од основни слоеви кои претставуваат броеви од понизок ред. Особено, n-тиот триаголен број Tn може да се добие со собирање на сите природни броеви што ги претставуваат неговите линеарни слоеви:
Слично на тоа, не е тешко да се најде тетраедарскиот број Pn со пресметување на следнава сума од првите n триаголни броеви што ги сочинуваат неговите хоризонтални јадрени слоеви:
Покрај хоризонталите и вертикалите во правоаголен триаголник на Паскал, може да се следат дијагонални редови на елементи, чие проучување на својствата е исто така од одреден интерес. Во овој случај, обично се прави разлика помеѓу опаѓачки и растечки дијагонали. Дијагоналите надолу се паралелни со хипотенузата на правоаголен триаголник на Паскал. Тие се формираат со серија биномни коефициенти со зголемување на двата индекса. Поради идентитетот на симетријата, опаѓачките дијагонали се совпаѓаат во вредностите на нивните елементи со соодветните вертикални редови на триаголникот на Паскал и затоа ги повторуваат сите нивни својства дискутирани погоре. Посочената кореспонденција може да се следи со совпаѓање на вредностите на елементите на опаѓачката дијагонала и вертикалата со кој било број n, ако не се земат предвид вертикалните нули:
Растечките дијагонали формираат бројна серија геометриски нормална на хипотенузата на правоаголен триаголник на Паскал. Пополнети се со биномни коефициенти со намалување на долниот и зголемување на надредениот. Особено, 7 горните растечки дијагонали ја формираат следната нумеричка низа без да ги земат предвид заостанатите нули:
Општо земено, растечкиот дијагонален број n ги содржи следните биномни коефициенти, збирот на индексите на секој од нив е еднаков на (n1):
Врз основа на идентитетот на собирање за комбинираните броеви, секој дијагонален елемент е еднаков на збирот на два елементи што одговараат во индексите од двете претходни растечки дијагонали. Ова овозможува секоја следна растечка дијагонала да се конструира со парно собирање на соседните хоризонтални елементи од двете претходни дијагонали, бесконечно проширување на триаголникот на Паскал долж дијагоналата. Следниот фрагмент од триаголникот на Паскал ја илустрира конструкцијата на растечка дијагонала број 8 по дијагоналите нумерирани 6 и 7:
Со овој метод на градба, збирот на елементите на која било растечка дијагонала, почнувајќи од 3-та, ќе биде еднаков на збирот на елементите на двете претходни растечки дијагонали, а првите 2 дијагонали се состојат од само еден елемент, вредноста од кои е 1. Резултатите од соодветните пресметки ја формираат следната нумеричка серија, според која можете да ја проверите валидноста на разгледуваното својство на растечките дијагонали на правоаголен триаголник на Паскал:
Анализирајќи ги овие бројки, можете да видите дека според сличен закон, се формира добро познатата низа од броеви на Фибоначи, каде што секој следен број е еднаков на збирот на двата претходни, а првите два броја се еднакви на 1:
Така, можеме да го извлечеме следниов важен заклучок: дијагоналните збирови на елементите на триаголникот на Паскал ја сочинуваат низата Фибоначи. Ова својство ни овозможува да воспоставиме уште една интересна карактеристика на триаголникот на Паскал. Проширувајќи ја формулата Фибоначи рекурзивно, лесно е да се докаже дека збирот на првите n Фибоначи броеви е еднаков на (F n+2 1).
Според тоа, збирот на биномните коефициенти што ги пополнуваат горните n дијагонали е исто така еднаков на (F n+2 1). Следи дека збирот на првите n дијагонали на триаголникот на Паскал е за 1 помал од збирот на биномните коефициенти што стојат на неговата дијагонала со број (n+2).
Како заклучок, треба да се забележи дека разгледаните својства на хоризонталите, вертикалите и дијагоналите на триаголникот на Паскал не ја исцрпуваат огромната разновидност на можности што поврзуваат различни математички аспекти кои на прв поглед немаат ништо заедничко. Ваквите необични својства ни овозможуваат да го сметаме триаголникот на Паскал за еден од најсовршените нумерички системи, чиишто способности не можат да се наведат и тешко е да се прецени.
Алгоритмот за пресметување на бројот на комбинации со помош на триаголникот на Паскал е претставен подолу:
Приватна функција SochTT (ByVal n како цел број, ByVal k како цел број) Како двојно затемнување i како цел број Dim j како цел број Dim TT () Како двојно ReDim TT (n, k) За i = 0 до n TT (0, i) = 1 TT (i, i) = 1 Следно За i = 2 До n За j = 1 До i - 1 TT (i, j) = TT (i - 1, j - 1) + TT (i - 1, j) Следно Следно SochTT = TT (n, k) Крајна функција
Ако треба многу пати да го пресметате бројот на комбинации, тогаш можеби е попогодно да го конструирате триаголникот на Паскал еднаш, а потоа да примате податоци од низата.
Dim TT () како двојно приватно Sub CreateTT () ReDim TT (0, 0) BuildTT 0, 0 Крај на Sub Private Function SochTT (ByVal n како цел број, ByVal k како цел број) Како двојно ако n > Ubound (TT) Потоа BuildTT Ubound (TT) + 1, n SochTT = TT (n, k) Крајна функција Private Sub TerminateTT () ReDim TT (0, 0) End Sub Private Sub BuildTT (ByVal почеток како цел број, ByVal крај како цел број) Dim i As Integer Dim j Како цел број ReDim Зачувај TT (крај, крај) За i = почеток До крај TT (0, i) = 1 TT (i, i) = 1 Следно Ако крај< 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
Прво треба да ја повикате процедурата CreateTT. Потоа можете да го добиете бројот на комбинации користејќи ја функцијата SochTT. Кога повеќе не ви треба триаголникот, повикајте ја процедурата TerminateTT. Во горната шифра, при повикување на функцијата SochTT, ако триаголникот сè уште не е пополнет до потребното ниво, тогаш се пополнува со помош на процедурата BuildTT. Функцијата потоа го добива саканиот елемент од низата ТТ и го враќа.
Dim X () Како цел број Димен бројач () Како цел број Dim K како цел број Dim N како цел број јавен Sub Soch() Dim i како цел број N = CInt(InputBox("Внесете N")) K = CINT(InputBox("Внесете K ")) K = K + 1 ReDim X(N) За i = 1 До N X(i) = i Следен txtOut.Text = "" Бројач ReDim(K) Бројач(0) = 1 SochGenerate 1 Крај Под Приватен Под SochGenerate( ByVal c како цел број) Dim i како цел број Dim j како цел број Dim n1 Како цел број Dim Out() Како цел број Dim X1() Како цел број Ако c = K Потоа ReDim Out(K) X1 = X За i = 1 до K - 1 n1 = 0 За j = 1 до N Ако X1 (j)<>0 Тогаш n1 = n1 + 1 Ако n1 = Бројач(i) Потоа Out(i) = X1(j) X1(j) = 0 Излезете за крај ако следно txtOut.Text = txtOut.Text & CStr(Out(i)) Следен txtOut.Text = txtOut.Text & vbCrLf Друго за бројач(c) = бројач(c - 1) до N - c + 1 SochGenerate c + 1 Следен крај Ако Крај Под
КОМБИНАЦИИ НА ПРИРОДНИ БРОЕВИ
За да се решат многу практични проблеми, неопходно е да се наведат сите комбинации на фиксна кардиналност што може да се добијат од елементите на даденото конечно множество, а не само да се одреди нивниот број. Имајќи ја предвид секогаш постоечката можност за целобројно нумерирање на елементите на кое било конечно множество, во повеќето случаи е дозволено да се ограничиме на употребата на алгоритми за набројување комбинации на природни броеви. Најприроден и наједноставен од нив е алгоритмот за наведување на комбинации на природни броеви во лексиграфски ред.
За формално да се опише овој алгоритам, погодно е да се претпостави дека главното множество, чиишто комбинации од m елементи мора да бидат наведени, формира последователни природни броеви од 1 до n. Тогаш било која комбинација од м Како резултат на нарачката, вредноста во секоја позиција на таков вектор на комбинации природно се покажува дека е ограничена во вредност од горе и долу како што следува: Лексиграфскиот алгоритам секвенцијално генерира такви комбинирани вектори, почнувајќи од лексиграфски најмалиот вектор, каде што сите позиции ги содржат следните минимални можни вредности на елементи еднакви на нивните индекси: Секој последователен комбиниран вектор се формира од тековниот по скенирањето на неговите елементи од лево кон десно со цел да се најде најдесниот елемент кој сè уште не ја достигнал својата гранична вредност: Вредноста на таков елемент треба да се зголеми за 1. На секој елемент десно од него треба да му се додели најмалата можна вредност, која е за 1 поголема од соседот лево. По овие промени, следниот вектор на комбинации ќе го има следниот елементарен состав: Така, следниот комбиниран вектор ќе биде лексиграфски поголем од претходниот, бидејќи вредностите на нивните почетни (j1) елементи се еднакви по вредност, а вредноста на елементот на позицијата j е 1 поголема од онаа на претходната. . Наведената релација на растечки лексиграфски редослед гарантирано е задоволена при сите повторувања на алгоритмот. Резултатот е зголемена лексиграфска низа, која се комплетира со лексиграфски најголемиот комбиниран вектор, каде што елементите во сите позиции ги имаат следните максимални вредности: Разгледаниот лексиграфски алгоритам е илустриран со следниов пример, каде што е неопходно да се наведат во зголемен лексиграфски редослед сите 15 комбинации од n=6 први природни броеви по m=4 броеви, односно сите можни подмножества од 4 елементи на главната генераторска сет (1, 2, 3, 4, 5, 6) од 6 елементи. Резултатите од пресметката се прикажани во следната табела: Во овој пример, најголемите дозволени вредности на броевите во позициите на векторите на комбинација се, соодветно, 3, 4, 5 и 6. За полесно толкување на резултатите, во секој вектор на комбинација е најдесниот елемент, кој има се уште не ја достигнала својата максимална вредност, се подвлекува. Нумеричките индекси на комбинираните вектори ги одредуваат нивните броеви по лексиграфски редослед. Во општ случај, лексиграфскиот број N на која било комбинација од n елементи по m може да се пресмета со следнава формула, каде што, од козметички причини, симболиката на Апел се користи за означување на броевите на комбинации: Конкретно, следните пресметки користејќи ја оваа формула за комбинацијата број (1, 3, 4, 6) од n=6 елементи од m=4 по лексиграфски редослед ќе го дадат резултатот N=8, што одговара на примерот дискутиран погоре: Во општиот случај, користејќи го идентитетот за збирот на броевите на комбинации за двата индекса, можно е да се покаже дека бројот на лексиграфски најмалата комбинација (1, ... i, ... m) кога се пресметува со користење на овој формулата секогаш ќе биде еднаква на 1: Исто така, очигледно е дека бројот на лексиграфски најголемата комбинација (m, … nm+i, … n) кога ќе се пресмета со оваа формула ќе биде еднаков на бројот на комбинации на n елементи по m: Формулата за пресметување на броеви на лексиграфски комбинации може да се користи за решавање на инверзната задача, каде што треба да го одредите векторот на комбинација по неговиот број по лексиграфски редослед. За да се реши таков инверзен проблем, мора да се напише во форма на равенка, каде што сите непознати вредности на елементите на векторот на саканата комбинација (C 1, ... C i, ... C m ) се концентрирани во броевите на комбинации на неговата десна страна, а познатата разлика L од бројот на комбинации е запишана на левата страна од n елементи секој m и бројот на потребната комбинација N: Решението на оваа равенка е дадено со следниот „алчен“ алгоритам, при чии повторувања секвенцијално се избираат вредностите на елементите на векторот на саканата комбинација. При почетното повторување, се избира минималната можна (во рамките на нејзините ограничувања) вредност на C 1, при што првиот член од десната страна ќе има максимална вредност што не надминува L: Сега левата страна на L треба да се намали за првиот број на комбинации на десната страна со избраната вредност C 1, и слично да ја одреди вредноста на C 2 при втората итерација: Слично на тоа, сите последователни повторувања треба да се извршат за да се изберат вредностите на сите други елементи C i од саканата комбинација, до последниот елемент C m: Од очигледни причини, вредноста на последниот елемент C m може да се одреди врз основа на еднаквоста на неговиот број на комбинации со преостанатата вредност на левата страна на L: Треба да се напомене дека вредноста на последниот елемент од комбинацијата C m може да се најде уште поедноставно, без да се набројуваат неговите можни вредности: Имплементацијата на повторувањата на разгледуваниот алгоритам е илустрирана со следниот пример, каде што е потребно да се одредат комбинации со бројот N=8 по лексиграфски редослед, ако n=6 и m=4: Алгоритамската способност да се определи комбинација со даден број по лексиграфски редослед може да се користи во различни насоки. Конкретно, кога се набројуваат комбинациите по лексиграфски редослед, потребно е да се обезбеди враќање на која било комбинација што е добиена порано, доволно е да се знае само нејзиниот број. Покрај тоа, станува возможно да се генерираат комбинации по кој било редослед, што е регулирано со произволно дадена низа од нивните лексиграфски броеви. Сега ви претставуваме алгоритам за генерирање комбинации по лексикографски редослед: 2 за i:= 1 до k направи A[i] := i; 5 почнуваат да пишуваат (A, …, A[k]); 6 ако A[k] = n тогаш p:= p 1 друго p:= k; 8 за i:= k надолу до p направи A[i] := A[p] + i p + 1 КОМБИНАЦИИ СО ПОВТОРУВАЧКИ ЕЛЕМЕНТИ За разлика од класичната комбинација, каде што сите елементи се различни, комбинацијата со повторувања формира неуреден избор на елементи од конечно множество, каде што секој елемент може да се појавува неопределено често и не мора да биде присутен во една копија. Во овој случај, бројот на повторувања на елементи обично е ограничен само со должината на комбинацијата, а комбинациите што се разликуваат во барем еден елемент се сметаат за различни. На пример, со избирање на 4 опционално различни броеви од множеството 1, 2 и 3, можете да ги креирате следните 15 комбинации со повторувања: 1111 1112 1113 1122 1123 1133 1222 1223 1233 1333 2222 2223 2233 2333 3333.
Општо земено, комбинации со повторувања може да се формираат со избирање на n елементи од произволни типови. Сепак, тие секогаш можат да се поврзат со последователни природни броеви од 1 до n. Потоа, секоја комбинација од m опционално различни броеви во овој опсег може да се запише во векторска форма, подредувајќи ги по редослед што не се намалува од лево кон десно: Природно, со оваа форма на нотација, сите соседни елементи можат да бидат еднакви поради можноста за неограничени повторувања. Сепак, секој комбиниран вектор со повторувања на n елементи за m може да се поврзе со комбиниран вектор од (n+m−1) елементи по m, кој е конструиран на следниов начин: Јасно е дека за која било вредност на елементите на векторот f, се гарантира дека елементите на векторот C се различни и строго подредени по зголемен редослед на нивните вредности од опсегот од 1 до (n+m1) : Присуството на кореспонденција еден-на-еден помеѓу елементите на комбинираните вектори f и C ни овозможува да го предложиме следниот едноставен метод за систематско наведување на комбинации со повторувања на n елементи по m. Потребно е само да се наведат, на пример, по лексиграфски редослед, сите C комбинации на (n+m1) елементи на m, секвенцијално трансформирајќи ги елементите на секој од нив во соодветните елементи на комбинации со повторувања f користејќи ја следната формула: Како резултат на тоа, се формира низа вектори на комбинации со повторувања на елементи, кои се наредени по редоследот генериран со наведување на соодветните комбинации без повторувања на елементите. Конкретно, за да се добие горенаведената низа на комбинации од 3 цифри 1, 2 и 3 со повторувања од 4 цифри, потребно е да се наведат по лексиграфски редослед сите комбинации без повторувања од 6 цифри 1,2,3,4, 5. и 6 се по 4 цифри, претворајќи ги како што е наведено. Следниот пример покажува таква конверзија на комбинацијата (1,3,4,6) со лексикографскиот број 8: Разгледуваната кореспонденција еден-на-еден помеѓу комбинациите со и без повторувања на елементи значи дека нивните множества се подеднакво моќни. Затоа, во општиот случај, бројот на комбинации со повторувања на n елементи за m е еднаков на бројот на комбинации без повторувања на (n+m1) елементи за m. Користејќи ја истата симболика за означување на броевите на комбинации со повторувања f и без повторувања C, оваа еднаквост може да се запише на следниов начин: Лесно е да се провери дека за примерот разгледан погоре, каде што n=3 и m=4, бројот на комбинации за повторување ќе биде еднаков на 15, што се совпаѓа со резултатот од нивното директно наведување: Треба да се напомене дека, за разлика од класичната верзија, вредностите на параметрите на комбинацијата со повторувања n и m не се директно поврзани едни со други, затоа f(n,m)>0 за која било комбинација од нивните позитивни вредности. Соодветните гранични услови се одредуваат од еднаквоста помеѓу вредностите на (n+m1) и (n1) или (n+m1) и m: Исто така, треба да биде сосема очигледно дека ако m е еднакво на 1, тогаш не се можни повторувања на елементите и, според тоа, за која било позитивна вредност од n>0 ќе биде точно следната еднаквост: Дополнително, за броеви на комбинации со повторувања за какви било позитивни вредности од n и m, важи следнава релација за повторување, која е слична на идентитетот на собирање за броеви на комбинации без повторувања на елементите: Всушност, тој се претвора во посочениот идентитет на додавање при формална замена на соодветните броеви на комбинации без повторувања во неговата лева и десна страна: Разгледуваната релација на повторување може да се користи за ефикасно одредување на броевите на комбинации со повторувања, кога е важно да се елиминираат трудоинтензивните операции на пресметување на факторските производи и да се заменат со поедноставни операции за собирање. Во овој случај, за да ја пресметате вредноста на f(n,m), треба само да ја примените оваа рекурентна релација додека не го добиете збирот на членовите од формата f(1,m) и f(i,1), каде што i зема вредности во опсег од n до 1. Според дефиницијата на количината, овие поими се еднакви на 1 и i, соодветно. Следниот пример ја илустрира употребата на оваа техника на трансформација за случајот n=3 и m=4: ЛИСТ НА БИНАРНИ КОМБИНАЦИИ При имплементирање на комбинации во хардвер или програмирање во асемблерски јазик, важно е да се биде во можност да се обработуваат комбинационите записи во бинарен формат. Во овој случај, секоја комбинација од n елементи од m треба да биде наведена во форма на n-битен бинарен број (B n,...B j,...B 1), каде што цифрите на m единица ги означуваат елементите на комбинација, а останатите (nm) цифри имаат нула вредности. Очигледно, со оваа форма на нотација, различните комбинации мора да се разликуваат во распоредот на цифрите на 1-та, а постојат само C(n,m) начини да се распоредат m единици или (nm) нули во n-битно бинарно множество. На пример, следната табела ги наведува сите 6 такви бинарни комбинации, кои обезбедуваат 4-битни бинарни броеви за сите комбинации од 4 елементи од произволно множество (E 1 , E 2 , E 3 , E 4 ) со 2: Во општиот случај, задачата за набројување на таквите бинарни комбинации се сведува на систематско пребарување на сите n-битни бинарни множества со различни распореди на m еден и (nm) нула битови. Во наједноставна форма, ваквото пребарување се спроведува со различни методи за транспонирање на соседните битови со поместување (алгоритми со транспозитивно поместување). Ова се итеративни алгоритми, а нивните имиња ја одразуваат природата на операциите извршени на секој чекор. Итеративните процедури на алгоритмите со транспозитивно поместување формираат секвенци од бинарни комбинации кои започнуваат со бинарно множество, каде што сите се концентрирани во цифрите од низок ред (десно) и завршуваат кога сите 1 се во цифри од висок ред ( лево): Додека се совпаѓаат во почетните и финалните комбинации, овие секвенци се разликуваат по редоследот по кој се наведени средните бинарни множества. Меѓутоа, во сите случаи, секоја следна бинарна комбинација се формира од претходната како резултат на извршување на соодветните операции за транспозиција и поместување. Во исто време, различните алгоритми со транспозитивно поместување се разликуваат во начинот на кој избираат пар битови за транспозиција и група битови за поместување. Оваа специфичност е дискутирана подолу за алгоритми за транспозиција со поместување лево и десно. Во алгоритмот за транспозиција со лево поместување, на секој чекор, следната бинарна комбинација се добива од тековната со замена на најлевиот пар цифри 01 со 10 (транспозиција) и поместување на групата цифри од водечките единици, доколку ги има, блиску до парот 10 добиен по транспозицијата (смената). Ако во овој случај нема единици во водечките цифри во тековната бинарна комбинација, тогаш поместувањето не се врши, дури и кога водечката единица се добива по транспонирањето на овој чекор. Поместувањето исто така не се врши кога нема нули во најзначајните битови пред парот 10 добиен по транспозицијата. Разгледаните дејства се илустрирани со следниов пример за извршување на две последователни повторувања на овој алгоритам, каде што на едната итерација (15) се врши само транспозиција (T"), а на другата итерација (16) транспозицијата се надополнува со поместување ( T"+S"): Во алгоритмот за транспозиција со поместување десно, концептуално слични чекори се изведуваат на секој чекор. Само транспозицијата гарантира дека најдесните битови од 01 се заменуваат со 10 (наместо најлевите), а потоа сите оние десно од него се префрлаат на најмалку значајните битови. Како и досега, поместувањето се врши само ако има единици што може да се префрлат надесно. Разгледаните дејства се илустрирани со следниов пример за извршување на две последователни повторувања на овој алгоритам, каде што при едната итерација (3) се врши само транспозиција (Т"), а при другата итерација (4) транспозицијата се надополнува со поместување ( T"+S"): Треба да се забележи дека повторувањата на двата алгоритма може да се напишат во адитивна форма ако бинарните комбинации се толкуваат како цели броеви во броениот систем на база 2. Особено, за алгоритам за транспозиција со десно поместување, секоја следна бинарна комбинација (B" n ,…B" j , …B" 1), секогаш може да се добие од тековната комбинација (B n,...B j,...B 1) со извршување на операциите на собирање цели броеви користејќи ја следната формула за адитив: Во оваа адитивна формула, експонентите на силите на двојки f и t го означуваат, соодветно, бројот на нула цифри од низок ред на тековната бинарна комбинација и бројот на оние по ред лево од нив. На пример, за 4-та бинарна комбинација (001110) од n=6 цифри f =1 и t =3. Затоа, пресметувањето на следната бинарна комбинација со помош на формулата за адитив при повторување 5 ќе го даде следниов резултат, што е еквивалентно на извршување на операциите за транспозиција и поместување: За компаративна анализа на разгледуваните алгоритми за транспозиција со лево и десно поместувања, препорачливо е да се споредат низите од бинарни комбинации што тие ги создаваат во нивните повторувања. Следната табела прикажува две такви секвенци на бинарни комбинации од 4 елементи од 2, кои се добиени со алгоритмите за поместување лево (TSL) и десно (TSR), соодветно: Споредувајќи ги овие 2 секвенци, можете да видите дека тие се обратно огледало. Тоа значи дека кои било две бинарни комбинации кои се наоѓаат во нив на исто растојание од меѓусебно спротивните краеви на нивните секвенци се огледална слика една на друга, односно се совпаѓаат кога индексирањето на битовите во кој било од нив е обратно. На пример, втората бинарна шема од почетокот на TSL секвенцата (0101) е огледална слика на бинарната шема (1010) која е втора од крајот на TSR секвенцата. Општо земено, секоја бинарна комбинација со број i од една низа е огледална слика на бинарна комбинација со број (ni+1) од друга низа. Оваа врска помеѓу овие секвенци е последица на симетричната природа на операциите за транспозиција и поместување во двата разгледувани алгоритми за набројување на бинарни комбинации. Треба да се напомене дека бинарниот формат може да се користи и за снимање комбинации со повторувања на елементи. За да го направите ова, неопходно е да се воспостави кореспонденција еден-на-еден помеѓу комбинациите со повторувања и бинарни комбинации, кои се конструирани на следниов начин. Нека има произволна комбинација со повторувања, која се добива со избирање на m опционално различни елементи од n елементите на генерациското множество. За да го воспоставите посакуваното совпаѓање, прво мора да ги додадете сите елементи од множеството за формирање (мачка) во комбинацијата, а потоа да ја сортирате добиената конкатенација (сортирање) така што сите идентични елементи се еден до друг. Резултатот е низа од (n+m) елементи, каде што има n групи на идентични елементи. Ќе има вкупно (n+m1) празнини помеѓу елементите, меѓу кои ќе има (n1) празнини помеѓу групи на идентични елементи и m празнини помеѓу елементите во групите. За јасност, можете да ги поставите симболите „|“ на наведените празни места. и соодветно. Ако сега поклопиме 1 со празни места помеѓу групите (|) и 0 со сите други празни места (), добиваме бинарна комбинација. Таа е формирана од бинарно множество од (n+m1) битови, каде што (n1) се едно и m нула битови, чија локација уникатно одговара на оригиналната комбинација со повторувања на елементите n преку m. Разгледуваната техника на трансформација е илустрирана со следниов пример за конструирање бинарна комбинација (1001101) со користење на комбинација со повторувања (BBD), чии елементи се избрани од генераторското множество од првите пет латински букви: Општо земено, бројот на такви бинарни множества го одредува бројот на начини за распоредување (n1) едно (или m нули) во (n+m1) бинарни цифри. Оваа вредност е очигледно еднаква на бројот на комбинации од (n+m1) со (n1) или со m, односно C(n+m1,n1) или C(n+m1,m), што е еднакво на број на комбинации со повторувања f( n,m) од n елементи, m секој. Така, имајќи кореспонденција еден-на-еден помеѓу комбинациите со повторувања и бинарни комбинации, легитимно е да се намали набројувањето на комбинации со повторувања на набројување на бинарни комбинации, на пример, со користење на алгоритми за транспозиција со лево или десно поместување. По ова, потребно е само да ги вратите потребните комбинации со повторувања користејќи ги добиените бинарни комбинации. Ова секогаш може да се направи со користење на следнава техника за обновување. Нека главното множество, од чии елементи се формираат комбинации со повторувања на m не мора да се формираат различни елементи, да се подреди на произволен начин така што секој од неговите елементи има одреден сериски број од 1 до n. Дозволете ни да го спроведеме и набројувањето на бинарни комбинации на (n+m1) бинарни цифри, каде што (n1) единки и m нула цифри. Секоја добиена бинарна комбинација може да се дополни лево со фиктивна единична цифра, а сите единични цифри може да се нумерираат од лево кон десно со цели броеви од 1 до n. Тогаш бројот на нули по ред по секоја i-та единица од бинарната комбинација ќе биде еднаков на бројот на примероци на i-тиот елемент од главното множество во соодветната комбинација со повторувања. Разгледуваната техника е илустрирана со следниов пример, каде што, користејќи бинарна комбинација (1001101), се обновува комбинација со повторувања на BBD, чии елементи се избрани од генераторското множество од првите пет латински букви, напишани по азбучен ред , а преку линијата означува елементи кои се отсутни во оваа комбинација: Со извршување на слични дејства во условите на овој пример, можете да ги наведете сите 35 бинарни комбинации кои формираат 7-битни бинарни множества, каде што има 4 една и 3 нули, и да ги вратите соодветните комбинации со повторувања на 5 елементи од 3. Во комбинаториката проучуваат прашања за тоа колку комбинации од одреден тип можат да се направат од дадени предмети (елементи). Раѓањето на комбинаториката како гранка е поврзано со делата на Б. Паскал и П. Ферма за теоријата на коцкањето. Голем придонес во развојот на комбинаторните методи даде Г.В. Лајбниц, Ј. Бернули и Л. Ојлер. Францускиот филозоф, писател, математичар и физичар Блез Паскал (1623–1662) рано ги покажал своите извонредни математички способности. Опсегот на математички интереси на Паскал беше многу разновиден. Паскал докажа едно Готфрид Вилхелм Лајбниц (1646–1716) бил германски филозоф, математичар, физичар и пронаоѓач, правник, историчар и лингвист. Во математиката, заедно со И. Њутн, развил диференцијална и интегрална пресметка. Тој даде важен придонес во комбинаториката. Неговото име, особено, е поврзано со теоретски проблеми на броеви. Готфрид Вилхелм Лајбниц имаше малку импресивен изглед и затоа остави впечаток на прилично обичен човек. Еден ден во Париз, тој отишол во книжарница со надеж дека ќе купи книга од филозоф што го познавал. Кога еден посетител прашал за оваа книга, книжарецот, откако го прегледал од глава до пети, со потсмев рекол: „Зошто ти треба? Дали навистина сте способни да читате такви книги?“ Пред научникот да има време да одговори, самиот автор на книгата влезе во продавницата со зборовите: „Поздрав и почит до големиот Лајбниц! Продавачот не можеше да разбере дека ова е навистина познатиот Лајбниц, чии книги беа многу барани меѓу научниците. Во иднина, следново ќе игра важна улога Лема.Нека во збир на елементи, а во множество - елементи. Тогаш бројот на сите различни парови каде што ќе биде еднаков на . Доказ.Навистина, со еден елемент од множество можеме да направиме толку различни парови, а вкупно во множество елементи. Пласмани, пермутации, комбинации Дозволете ни да имаме збир од три елементи. На кој начин можеме да избереме два од овие елементи? . Дефиниција.Распоредот на множество различни елементи по елементи се комбинации кои се составени од дадени елементи по > елементи и се разликуваат или по самите елементи или по редоследот на елементите. Бројот на сите распореди на збир на елементи по елементи се означува со (од почетната буква на францускиот збор „arrangement“, што значи распоред), каде и . Теорема.Бројот на сместувања на збир на елементи по елементи е еднаков на Доказ.Да речеме дека имаме елементи. Нека бидат можни пласмани. Овие места ќе ги изградиме последователно. Прво, да го дефинираме првиот елемент за поставување. Од даден сет на елементи може да се избере на различни начини. По изборот на првиот елемент, сè уште има начини да го изберете вториот елемент, итн. Бидејќи секој таков избор дава нова поставеност, сите овие избори можат слободно да се комбинираат еден со друг. Затоа имаме: Пример.На колку начини знамето може да биде составено од три хоризонтални ленти со различни бои ако има материјал во пет бои? Решение.Потребен број на знаменца со три појаси: Дефиниција.Пермутација на збир на елементи е распоред на елементи во одреден редослед. Така, сите различни пермутации на множество од три елементи се Наведен е бројот на сите пермутации на елементите (од почетната буква на францускиот збор „пермутација“, што значи „пермутација“, „движење“). Затоа, бројот на сите различни пермутации се пресметува со формулата Пример.На колку начини може да се постават корпата на шаховската табла за да не се напаѓаат едни со други? Решение.Потребниот број на корпи А-приорите! Дефиниција.Комбинации на различни елементи по елементи се комбинации кои се составени од дадени елементи по елементи и се разликуваат во најмалку еден елемент (со други зборови, подмножества на елементи на дадено множество елементи). Како што можете да видите, во комбинациите, за разлика од пласманите, редоследот на елементите не се зема предвид. Наведен е бројот на сите комбинации на елементи, елементи во секоја (од почетната буква на францускиот збор „комбинација“, што значи „комбинација“). Броеви Сите комбинации од сет од две се . Својства на броевите (\sf C)_n^k Навистина, секое подмножество -елемент од дадено множество -елементи одговара на едно и само едно подмножество -елемент од истото множество. Навистина, можеме да избереме подмножества на елементи на следниов начин: поправете еден елемент; бројот на подмножества на елементите што го содржат овој елемент е еднаков на ; бројот на подмножества на елементи кои не го содржат овој елемент е еднаков на . Паскалов триаголник Во овој триаголник, екстремните броеви во секој ред се еднакви на 1, а секој неекстремен број е еднаков на збирот на двата броја над него од претходниот ред. Така, овој триаголник ви овозможува да пресметате броеви. Теорема. Доказ.Да разгледаме множество елементи и да го решиме следниот проблем на два начина: колку низи може да се направат од елементите на дадена 1 начин. Го избираме првиот член на низата, потоа вториот, третиот итн. член Метод 2. Ајде прво да избереме елементи од дадено множество, а потоа да ги подредиме по одреден редослед Помножете ги броителите и именителот на оваа дропка со: Пример.На колку начини можете да изберете 5 броеви од 36 во играта „Спортлото“? Потребен број начини Задачи. 1.
Регистерските таблички на автомобили се состојат од 3 букви од руската азбука (33 букви) и 4 бројки. Колку различни броеви на регистарски таблички има? Партициите се сметаат за различни ако се разликуваат или по број или по редослед на нивните термини. Колку различни партиции на број во поими има? Број на комбинации Комбинацијаод nОд страна на кнаречен сет келементи избрани од податоци nелементи. Комплетовите кои се разликуваат само по редоследот на елементите (но не и по составот) се сметаат за идентични, затоа комбинациите се разликуваат од сместувањата. Број на комбинации на nОд страна на к
еднаков на биномниот коефициент За фиксна вредност nгенерирачка функција на броеви на комбинации со повторувања од nОд страна на ке: Дводимензионалната генерирана функција на броеви на комбинации со повторувања е: Фондацијата Викимедија. 2010 година. 70 седумдесет 67 68 69 70 71 72 73 40 50 60 70 80 90 100 Факторизација: 2×5×7 Римска нотација: LXX Бинарна: 100 0110 ... Википедија Светлосен број, условен број кој единствено го изразува надворешното услови за време на фотографирањето (обично осветленоста на субјектот и фотосензитивноста на користениот фотографски материјал). Секоја вредност на E. h. може да се избере неколку пати. комбинации на решетка број... ... Голем енциклопедиски политехнички речник Форма на број што разликува два објекти и во однос на еден објект и во однос на многу предмети. Оваа форма не постои во современиот руски јазик, но остануваат остатоци од неговото влијание. Значи, комбинации од две табели (сп. множина... ... Речник на лингвистички поими Комбинаторна математика, комбинаторика, гранка на математиката посветена на решавање проблеми на избор и уредување на елементи на одредено, обично конечно, поставено во согласност со дадените правила. Секое такво правило го одредува начинот на градба... ... Математичка енциклопедија Во комбинаториката, комбинација од by е збир на елементи избрани од дадено множество кое содржи различни елементи. Комплетовите кои се разликуваат само по редоследот на елементите (но не и по составот) се сметаат за идентични, овие комбинации ... ... Википедија Се занимава со проучување на настани чиешто настанување не е познато со сигурност. Тоа ни овозможува да ја процениме разумноста да се очекува појава на некои настани во споредба со други, иако доделувањето нумерички вредности на веројатностите на настаните често е непотребно... ... Енциклопедија на Колиер 1) исто како и математичката комбинаторна анализа. 2) Дел од елементарната математика поврзана со проучување на бројот на комбинации, кои подлежат на одредени услови, кои можат да бидат составени од даден конечен сет на објекти... ... Голема советска енциклопедија - (грчки парадокс неочекуван, чуден) во широка смисла: изјава што остро се разликува од општоприфатеното, воспоставено мислење, негирање на она што изгледа „безусловно точно“; во потесна смисла, две спротивставени изјави, за... ... Филозофска енциклопедија - (или принципот на инклузии и исклучувања) комбинаторна формула која ви овозможува да ја одредите кардиналноста на унијата на конечен број на конечни множества, кои во општ случај можат да се вкрстуваат едни со други ... Википедија Математичка теорија која се занимава со одредување на бројот на различни начини на дистрибуција на дадените објекти по познат редослед; е особено важно во теоријата на равенки и теоријата на веројатност. Наједноставните задачи од овој вид се... ... Енциклопедиски речник Ф.А. Брокхаус и И.А. Ефрон Во оваа статија ќе зборуваме за посебна гранка од математиката наречена комбинаторика. Формули, правила, примери за решавање проблеми - сето ова можете да го најдете овде со читање на статијата до самиот крај. Значи, што е овој дел? Комбинаториката се занимава со прашањето за броење на какви било предмети. Но, во овој случај, предметите не се сливи, круши или јаболка, туку нешто друго. Комбинаториката ни помага да ја најдеме веројатноста за настан. На пример, кога играте карти - колкава е веројатноста противникот да има адут? Или овој пример: колкава е веројатноста дека ќе добиете бела од вреќа со дваесет џамлии? Токму за ваков проблем треба да ги знаеме барем основите на оваа математичка гранка. Имајќи го предвид прашањето за основните концепти и формули на комбинаториката, не можеме а да не обрнеме внимание на комбинаторните конфигурации. Тие се користат не само за формулирање, туку и за решавање на различни примери.Примери за такви модели се: За првите три ќе зборуваме подетално подоцна, но ќе обрнеме внимание на составот и партиционирањето во овој дел. Кога зборуваат за составот на одреден број (на пример, а), тие подразбираат претставување на бројот a како подреден збир на одредени позитивни броеви. А партицијата е ненарачана сума. Пред да преминеме директно на формулите на комбинаториката и разгледувањето на проблемите, вреди да се обрне внимание на фактот дека комбинаториката, како и другите гранки на математиката, има свои подсекции. Тие вклучуваат: Во првиот случај, зборуваме за калкулативна комбинаторика; проблемите го разгледуваат набројувањето или броењето на различни конфигурации кои се формираат од елементи на множества. Како по правило, на овие множества се наметнуваат некои ограничувања (посебност, неразличност, можност за повторување итн.). И бројот на овие конфигурации се пресметува со користење на правилата за собирање или множење, за кои ќе зборуваме малку подоцна. Структурната комбинаторика ги вклучува теориите на графикони и матроиди. Пример за проблем со екстремна комбинаторика е која е најголемата димензија на графикот што ги задоволува следните својства... Во четвртиот пасус ја споменавме теоријата на Ремзи, која го проучува присуството на правилни структури во случајни конфигурации. Веројатната комбинаторика е способна да одговори на прашањето - колкава е веројатноста даденото множество да има одредено својство. Како што може да претпоставите, тополошката комбинаторика применува методи во топологијата. И конечно, седмата точка - бесконечната комбинаторика ја проучува примената на методите на комбинаторика на бесконечни множества. Помеѓу формулите за комбинаторика можете да најдете прилично едноставни, со кои сме запознаени доста долго. Пример е правилото за збир. Да претпоставиме дека ни се дадени две дејства (C и E), ако тие меѓусебно се исклучуваат, дејството C може да се изврши на неколку начини (на пример, a), а дејството E може да се изврши на b-начини, тогаш било кое од нив ( C или E) може да се изврши на a + b начини. Теоретски, ова е доста тешко да се разбере; ќе се обидеме да ја пренесеме целата поента користејќи едноставен пример. Да го земеме просечниот број на ученици во едно одделение - да речеме дека е дваесет и пет. Меѓу нив има петнаесет девојчиња и десет момчиња. Секој ден на секој час е распоредено по едно дежурно лице. Колку начини постојат денес да се назначи монитор за класа? Решението на проблемот е прилично едноставно, ќе прибегнеме кон правилото за додавање. Во текстот на проблемот не пишува дека можат да дежураат само момчиња или само девојчиња. Затоа, тоа може да биде било кое од петнаесетте девојчиња или кое било од десетте момчиња. Применувајќи го правилото за збир, добиваме прилично едноставен пример со кој ученик од основно училиште може лесно да се справи: 15 + 10. По броењето го добиваме одговорот: дваесет и пет. Односно, има само дваесет и пет начини да се додели дежурен час за денес. Основните формули на комбинаториката го вклучуваат и правилото за множење. Да почнеме со теоријата. Да речеме дека треба да извршиме неколку дејства (а): првото дејство се изведува на 1 начин, второто - на 2 начини, третото - на 3 начини и така натаму до последното a-акција, изведено на 3 начини. Тогаш сите овие дејства (од кои имаме вкупно) може да се изведат на N начини. Како да се пресмета непознатиот N? За ова ќе ни помогне формулата: N = c1 * c2 * c3 *…* ca. Повторно, ништо не е јасно во теорија, па да продолжиме да разгледуваме едноставен пример за примена на правилото за множење. Да ја земеме истата класа од дваесет и пет луѓе, во која има петнаесет девојки и десет момчиња. Само што овој пат треба да избереме двајца дежурни. Тие можат да бидат само момчиња или девојчиња, или момче и девојче. Да преминеме на елементарното решение на проблемот. Го избираме првиот дежурен, како што решивме во последниот пасус, добиваме дваесет и пет можни опции. Вториот дежурен може да биде кој било од преостанатите лица. Имавме дваесет и пет студенти, избравме еден, што значи дека вториот дежурен би можел да биде кој било од преостанатите дваесет и четири лица. Конечно, го применуваме правилото за множење и откриваме дека двајца дежурни службеници можат да бидат избрани на шестотини начини. Овој број го добивме со множење на дваесет и пет и дваесет и четири. Сега ќе разгледаме друга формула за комбинаторика. Во овој дел од статијата ќе зборуваме за пермутации. Предлагаме веднаш да го разгледаме проблемот користејќи пример. Ајде да земеме топчиња за билијард, имаме n-ти број од нив. Треба да броиме колку опции има за да ги подредиме по ред, односно да создадеме подреден сет. Да почнеме, ако немаме топки, тогаш имаме и нула опции за пласман. И ако имаме една топка, тогаш распоредот е исто така (математички ова може да се напише на следниов начин: P1 = 1). Двете топки може да се постават на два различни начини: 1,2 и 2,1. Затоа, P2 = 2. Три топки може да се подредат на шест начини (P3 = 6): 1,2,3; 1,3,2; 2,1,3; 2,3,1; 3,2,1; 3,1,2. Што ако нема три такви топки, туку десет или петнаесет? Ќе треба многу долго време да ги наведеме сите можни опции, тогаш комбинаториката ни доаѓа на помош. Формулата за пермутација ќе ни помогне да го најдеме одговорот на прашањето што не интересира. Pn = n *P (n-1). Ако се обидеме да ја поедноставиме формулата, добиваме: Pn = n* (n - 1) *…* 2 * 1. И ова е производ на првите природни броеви. Овој број се нарекува фактор, и се означува како n! Да го разгледаме проблемот. Секое утро советникот го поредува својот одред (дваесет луѓе). Во тимот има тројца најдобри пријатели - Костја, Саша и Леша. Која е веројатноста тие да застанат еден до друг? За да го најдете одговорот на прашањето, треба да ја поделите веројатноста за „добар“ исход со вкупниот број на исходи. Вкупниот број на пермутации е 20! = 2,5 квинтилиони. Како да се брои бројот на „добри“ резултати? Да претпоставиме дека Костја, Саша и Леша се еден супермен. Тогаш имаме само осумнаесет предмети. Бројот на пермутации во овој случај е 18 = 6,5 квадрилиони. Со сето ова, Костја, Саша и Леша можат произволно да се движат меѓу себе во нивните неделиви три, а тоа се уште 3! = 6 опции. Тоа значи дека имаме вкупно 18 „добри“ аранжмани! * 3! Сè што треба да направиме е да ја пронајдеме посакуваната веројатност: (18! * 3!) / 20! Што е приближно 0,016. Ако се претвори во проценти, излегува дека е само 1,6%. Сега ќе разгледаме уште една многу важна и неопходна формула за комбинаторика. Пласманот е нашиот следен број, кој ве покануваме да го разгледате во овој дел од статијата. Одиме на компликации. Да претпоставиме дека сакаме да ги разгледаме можните пермутации, не од целото множество (n), туку од помало (m). Односно, разгледуваме пермутации на n ставки по m. Основните формули на комбинаториката не само што треба да се запаметат, туку и да се разберат. Иако стануваат покомплицирани, бидејќи немаме еден параметар, туку два. Да претпоставиме дека m = 1, потоа A = 1, m = 2, а потоа A = n * (n - 1). Ако дополнително ја поедноставиме формулата и се префрлиме на нотација со помош на факториел, добиваме целосно лаконска формула: A = n! / (n - m)! Ги разгледавме речиси сите основни формули за комбинаторика со примери. Сега да преминеме на последната фаза на разгледување на основниот курс по комбинаторика - запознавање со комбинациите. Сега ќе избереме m ставки од n што го имаме и ќе избереме сè на секој можен начин. Како тогаш ова се разликува од поставувањето? Ние нема да ја земеме предвид нарачката. Овој неуреден сет ќе биде комбинација. Веднаш да ја воведеме ознаката: C. Го вадиме поставувањето на m топчиња од n. Престануваме да внимаваме на редот и завршуваме со повторувачки комбинации. За да го добиеме бројот на комбинации треба да го поделиме бројот на сместувања со m! (m факторски). Тоа е, C = A / m! Така, постојат само неколку начини за избор од n топки, што е приближно еднакво на бројот на начини за избор на речиси сите. За ова постои логичен израз: да се избере малку е исто како да се исфрли речиси сè. Исто така, важно е да се спомене во овој момент дека максималниот број на комбинации може да се постигне кога се обидувате да изберете половина од ставките. Детално ги испитавме основните формули на комбинаториката: поставеност, пермутација и комбинација. Сега наша задача е да го олесниме изборот на потребната формула за решавање на комбинаторика. Можете да ја користите следнава прилично едноставна шема: Разгледавме елементи на комбинаторика, формули и некои други прашања. Сега да продолжиме да го разгледаме вистинскиот проблем. Замислете дека имате пред вас киви, портокал и банана. Прашање еден: на колку начини може да се преуредат? За да го направите ова, ќе ја користиме формулата за пермутација: P = 3! = 6 начини. Прашање второ: на колку начини можете да изберете едно овошје? Ова е очигледно, имаме само три опции - изберете киви, портокал или банана, но ајде да ја примениме формулата за комбинација: C = 3! / (2! * 1!) = 3. Трето прашање: на колку начини можете да изберете две овошја? Какви опции воопшто имаме? Киви и портокал; киви и банана; портокал и банана. Тоа е, постојат три опции, но ова е лесно да се провери со помош на формулата за комбинација: C = 3! / (1! * 2!) = 3 Прашање четири: на колку начини можете да изберете три овошја? Како што можете да видите, постои само еден начин да изберете три овошја: земете киви, портокал и банана. C = 3! / (0! * 3!) = 1. Прашање пет: на колку начини можете да изберете барем едно овошје? Оваа состојба значи дека можеме да земеме едно, две или сите три плодови. Затоа, додаваме C1 + C2 + C3 = 3 + 3 + 1 = 7. Тоа е, имаме седум начини да земеме барем едно овошје од масата. Да го изброиме во MS EXCEL бројот на комбинации на n елементи за k. Користејќи формули, ќе ги прикажеме на листот сите варијанти на комбинации (англиски превод на терминот: Комбинации без повторување). Комбинации од n различни елементи на k елементи се комбинации кои се разликуваат барем во еден елемент. На пример, подолу се СИТЕ комбинации од 3 елементи земени од множество кое се состои од 5 елементи (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) Забелешка: Ова е статија за броење на бројот на комбинации со помош на MS EXCEL. Препорачуваме да ги прочитате теоретските основи во специјализиран учебник. Учењето комбинации од овој напис е лоша идеја. Во примерната датотека, се креираат формули за прикажување на сите Комбинации за дадени n и k. Со одредување на бројот на елементи од множеството (n) и бројот на елементи што ги избираме од него (k), користејќи формули можеме да ги прикажеме сите Комбинации. Автомобилски превозник може да превезе 4 автомобили. Неопходно е да се превезат 7 различни автомобили (LADA Granta, Hyundai Solaris, KIA Rio, Renault Duster, Lada Kalina, Volkswagen Polo, Lada Largus). На колку различни начини може да се пополни првиот автомобилски транспортер? Специфичното место на автомобилот во автомобилскиот транспортер не е важно. Треба да го одредиме бројот Комбинации 7 автомобили на 4 места на автопревозник. Оние. n=7 и k=4. Излегува дека има 35 такви опции =NUMCOMB(7,4).
од основните теореми на проективната геометрија (теорема на Паскал), дизајнираше машина за собирање (машина за собирање на Паскал), даде метод за пресметување на биномни коефициенти (Паскалов триаголник), беше првиот што точно го дефинираше и примени методот на математичка индукција за докажување, направи значаен чекор во развојот на бесконечно мала анализа, одигра важна улога во појавата на теоријата на веројатност. Во хидростатиката, Паскал го воспоставил својот фундаментален закон (законот на Паскал). „Писма до еден провинцијал“ на Паскал беше ремек-дело на француската класична проза.
множества во кои ниту еден елемент не се појавува двапати?
2.
На клавирот има 88 копчиња. На колку начини можете да произведете 6 звуци последователно?
3.
Колку шестцифрени броеви се деливи со 5?
4.
На колку начини може да се стават 7 различни монети во три џебови?
5.
Колку петцифрени броеви можете да направите што ја имаат цифрата 5 барем еднаш во децималната нотација?
6.
На колку начини може да седнат 20 луѓе на тркалезна маса, со оглед на тоа дека начините се исти, ако може да се добијат еден од друг со движење во круг?
7.
Колку петцифрени броеви се деливи со 5 и не содржат идентични цифри?
8.
На карирана хартија со клеточна страна од 1 cm е нацртан круг со радиус 100 cm што не поминува низ врвовите на ќелиите и не ги допира страните на ќелиите. Колку ќелии може да се сечат овој круг?
9.
На колку начини броевите можат да се подредат по ред така што броевите се соседни и во растечки редослед?
10.
Колку петцифрени броеви може да се направат од цифри ако секоја цифра може да се користи само еднаш?
11.
Од зборот ROT, со преуредување на буквите, можете да ги добиете следните зборови: TOP, ORT, OTR, TRO, RTO. Тие се нарекуваат анаграми. Колку анаграми можете да направите од зборот ЛОГАРИТАМ?
12.
Ајде да се јавиме разделувањеприроден број, негово претставување како збир на природни броеви. Еве, на пример, сите партиции на број:
13.
Колку трицифрени броеви има со нерастечки цифрен ред?
14.
Колку четирицифрени броеви има со нерастечки цифрен ред?
15.
На колку начини може 17 луѓе да седнат во низа за да завршат рамо до рамо?
16.
девојчињата и момчињата се седнуваат по случаен избор во низа седишта. На колку начини можат да седнат за да не седат две девојки една до друга?
17.
девојчињата и момчињата се седнуваат по случаен избор во низа седишта. На колку начини можат да седнат така што сите девојки седат една до друга?Експлицитни формули
Врски
Погледнете што е „Број на комбинации“ во другите речници:
Книги
Комбинаторни конфигурации
Секции
Правило за додавање
Правило за множење
Преуредување
Сместување
Комбинација
Како да изберете формула за решавање на проблем?
Пример
Разлика помеѓу комбинации и пласмани
Прикажување на сите комбинации на комбинации
Задача