Калкулатор за можни комбинации. Комбинации без повторувања: Комбинаторика во MS EXCEL

Оваа статија ќе се фокусира на посебна гранка од математиката наречена комбинаторика. Формули, правила, примери за решавање проблеми - сето ова можете да го најдете овде со читање на статијата до самиот крај.

Значи, што е овој дел? Комбинаториката се занимава со прашањето за броење на какви било предмети. Но, во овој случај, предметите не се сливи, круши или јаболка, туку нешто друго. Комбинаториката ни помага да ја најдеме веројатноста за настан. На пример, кога играте карти - колкава е веројатноста противникот да има адут? Или таков пример - колкава е веројатноста да добиете точно бело од вреќа со дваесет топчиња? Токму за ваквите задачи треба да ги знаеме барем основите на овој дел од математиката.

Комбинаторни конфигурации

Со оглед на прашањето за основните концепти и формули на комбинаториката, не можеме, а да не обрнеме внимание на комбинаторните конфигурации. Тие се користат не само за формулирање, туку и за решавање на различни примери на такви модели се:

сместување;
пермутација;
комбинација;
состав на броеви;
делење на бројот.

За првите три ќе зборуваме подетално подоцна, но ќе обрнеме внимание на составот и разделувањето во овој дел. Кога зборуваат за составот на одреден број (да речеме, а), тие значат претставување на бројот а како подреден збир на некои позитивни броеви. Сплит е ненарачана сума.

Секции

Пред да продолжиме директно до формулите на комбинаториката и разгледувањето на проблемите, вреди да се обрне внимание на фактот дека комбинаториката, како и другите гранки на математиката, има свои подсекции. Тие вклучуваат:

нумеративен;
структурни;
екстремен;
Ремзи теорија;
веројатност;
тополошки;
бесконечна.

Во првиот случај, зборуваме за нумеративна комбинаторика, проблемите го разгледуваат набројувањето или броењето на различни конфигурации кои се формираат од елементи на множества. Како по правило, на овие множества се наметнуваат одредени ограничувања (посебност, неразличност, можност за повторување итн.). И бројот на овие конфигурации се пресметува со користење на правилото за собирање или множење, за што ќе зборуваме малку подоцна. Структурната комбинаторика ги вклучува теориите на графиконите и матроидите. Пример за проблем со екстремна комбинаторика е која е најголемата димензија на графикот што ги задоволува следните својства... Во четвртиот пасус ја споменавме теоријата на Ремзи, која го проучува присуството на правилни структури во случајни конфигурации. Веројатната комбинаторика е способна да одговори на прашањето - колкава е веројатноста даденото множество да има одредено својство. Како што може да претпоставите, тополошката комбинаторика применува методи во топологијата. И, конечно, седмата точка - бесконечната комбинаторика ја проучува примената на методите на комбинаторика на бесконечни множества.

Правило за додавање

Меѓу формулите на комбинаторика, може да се најдат и прилично едноставни, со кои сме запознаени долго време. Пример е правилото за збир. Да претпоставиме дека ни се дадени две дејства (C и E), ако тие меѓусебно се исклучуваат, дејството C може да се изврши на неколку начини (на пример, a), а дејството E може да се направи на b-начини, тогаш било кое од нив (C или Е) може да се направи на a + b начини .

Теоретски, ова е доста тешко да се разбере, ќе се обидеме да ја пренесеме целата поента со едноставен пример. Да го земеме просечниот број на ученици во едно одделение - да речеме дека е дваесет и пет. Меѓу нив има петнаесет девојчиња и десет момчиња. Секој ден на час се доделува по еден придружник. Колку начини постојат денес да се додели придружник на класот? Решението на проблемот е прилично едноставно, ќе прибегнеме кон правилото за додавање. Во текстот на проблемот не пишува дека можат да дежураат само момчиња или само девојчиња. Затоа, тоа може да биде било кое од петнаесетте девојчиња или кое било од десетте момчиња. Применувајќи го правилото за збир, добиваме прилично едноставен пример со кој ученик од основно училиште може лесно да се справи: 15 + 10. Откако пресметавме, го добиваме одговорот: дваесет и пет. Односно, постојат само дваесет и пет начини да се додели дежурен час за денес.

правило за множење

Правилото за множење исто така припаѓа на основните формули на комбинаториката. Да почнеме со теорија. Да претпоставиме дека треба да извршиме неколку дејства (а): првото дејство се изведува на 1 начин, второто - на 2 начини, третото - на 3 начини, и така натаму додека последното a-дејство не се изврши на начин. Тогаш сите овие дејства (од кои имаме вкупно) може да се изведат на N начини. Како да се пресмета непознатото N? Формулата ќе ни помогне во ова: N \u003d c1 * c2 * c3 * ... * ca.

Повторно, ништо не е јасно во теорија, да преминеме на едноставен пример за примена на правилото за множење. Да го земеме истиот клас од дваесет и пет луѓе, во кој учат петнаесет девојки и десет момчиња. Само овој пат треба да избереме двајца придружници. Тие можат да бидат или само момчиња или девојчиња, или момче со девојка. Се свртуваме кон елементарното решение на проблемот. Го избираме првиот придружник, како што решивме во последниот пасус, добиваме дваесет и пет можни опции. Вториот дежурен може да биде кој било од преостанатите лица. Имавме дваесет и пет студенти, избравме еден, што значи дека секој од преостанатите дваесет и четири лица може да биде втор дежурен. Конечно, го применуваме правилото за множење и откриваме дека двајцата придружници можат да се изберат на шестотини начини. Овој број го добивме со множење на дваесет и пет и дваесет и четири.

пермутација

Сега ќе разгледаме уште една формула на комбинаторика. Во овој дел од статијата, ќе зборуваме за пермутации. Размислете за проблемот веднаш со пример. Да земеме топчиња за билијард, имаме n-ти број од нив. Треба да пресметаме: колку опции има за да ги распоредиме по ред, односно да направиме нарачан сет.

Да почнеме, ако немаме топки, тогаш имаме и нула опции за пласман. И ако имаме една топка, тогаш распоредот е исто така (математички, ова може да се напише вака: Р1 = 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 \u003d 1, потоа A \u003d 1, m \u003d 2, потоа A \u003d n * (n - 1). Ако дополнително ја поедноставиме формулата и се префрлиме на нотација користејќи фактори, добиваме прилично концизна формула: A \u003d n! / (n - m)!

Комбинација

Речиси сите основни формули на комбинаторика ги разгледавме со примери. Сега да преминеме на последната фаза на разгледување на основниот курс на комбинаторика - запознавање со комбинацијата. Сега ќе избереме m ставки од n што го имаме, додека сите ќе ги избереме на сите можни начини. Како тогаш ова се разликува од сместувањето? Ние нема да размислуваме за ред. Овој неуреден сет ќе биде комбинација.

Веднаш ја воведуваме ознаката: C. Земаме сместувања на m топчиња од n. Престануваме да внимаваме на редот и добиваме повторливи комбинации. За да го добиеме бројот на комбинации, треба да го поделиме бројот на сместувања со m! (m факторски). Тоа е, C \u003d A / m! Така, постојат неколку начини да изберете од n топки, приближно еднакви на тоа колку да изберете речиси сè. За ова постои логичен израз: да се избере малку е исто како да се фрли речиси сè. Исто така, важно е да се спомене во овој момент дека максималниот број на комбинации може да се постигне кога се обидувате да изберете половина од ставките.

Како да изберете формула за решавање на проблем?

Детално ги испитавме основните формули на комбинаториката: поставеност, пермутација и комбинација. Сега наша задача е да го олесниме изборот на потребната формула за решавање на проблемот во комбинаториката. Можете да ја користите следнава прилично едноставна шема:

Поставете си го прашањето: дали е земен предвид редоследот на елементите во текстот на задачата?
Ако одговорот е не, тогаш користете ја формулата за комбинација (C \u003d n! / (m! * (n - m))).
Ако одговорот е не, тогаш треба да се одговори уште едно прашање: дали сите елементи се вклучени во комбинацијата?
Ако одговорот е да, тогаш користете ја формулата за пермутација (P = n!).
Ако одговорот е не, тогаш користете ја формулата за распределба (A = n! / (n - m)!).

Пример

Разгледавме елементи на комбинаторика, формули и некои други прашања. Сега да преминеме на вистинскиот проблем. Замислете дека имате пред вас киви, портокал и банана.

Прашање еден: на колку начини може да се преуредат? За да го направите ова, ја користиме формулата за пермутација: P = 3! = 6 начини.

Прашање 2: На колку начини може да се избере едно овошје? Ова е очигледно, имаме само три опции - изберете киви, портокал или банана, но ја применуваме формулата за комбинација: C \u003d 3! / (2! * 1!) = 3.

Прашање 3: На колку начини може да се изберат две плодови? Какви опции имаме? Киви и портокал; киви и банана; портокал и банана. Тоа е, три опции, но ова е лесно да се провери со помош на формулата за комбинација: C \u003d 3! / (1! * 2!) = 3

Прашање 4: На колку начини може да се изберат три плодови? Како што можете да видите, постои само еден начин да изберете три овошја: земете киви, портокал и банана. C=3! / (0! * 3!) = 1.

Прашање 5: На колку начини можете да изберете барем едно овошје? Оваа состојба подразбира дека можеме да земеме едно, две или сите три плодови. Затоа, додаваме C1 + C2 + C3 = 3 + 3 + 1 = 7. Односно, имаме седум начини да земеме барем едно парче овошје од масата.

Треба да се напомене дека комбинаториката е независен дел од вишата математика (а не дел од терверот) и во оваа дисциплина се напишани тешки учебници, чија содржина, понекогаш, не е полесна од апстрактната алгебра. Сепак, мал дел од теоретското знаење ќе ни биде доволен, а во оваа статија ќе се обидам да ги анализирам основите на темата со типични комбинаторни проблеми во достапна форма. И многу од вас ќе ми помогнат ;-)

Што ќе правиме? Во потесна смисла, комбинаторика е пресметка на различни комбинации кои можат да се направат од одредено множество дискретнипредмети. Предметите се подразбираат како какви било изолирани предмети или живи суштества - луѓе, животни, печурки, растенија, инсекти итн. Воедно, на комбинаториката воопшто не и е грижа што комплетот се состои од чинија гриз, рачка за лемење и барска жаба. Основно е важно овие објекти да се бројни - има три од нив. (дискретност)и од суштинско значење е ниту еден од нив да не биде ист.

Со многу средени, сега за комбинациите. Најчести типови на комбинации се пермутации на предмети, нивно избирање од множество (комбинација) и дистрибуција (поставување). Ајде да видиме како се случува ова во моментов:

Пермутации, комбинации и сместувања без повторување

Не плашете се од нејасни термини, особено затоа што некои од нив навистина не се многу успешни. Да почнеме со опашката на насловот - што значи " без повторување"? Ова значи дека во овој дел ќе разгледаме множества што се состојат од различнипредмети. На пример, ... не, нема да понудам каша со рачка за лемење и жаба, нешто повкусно е подобро =) Замислете на масата пред вас да се материјализирале јаболко, круша и банана (ако има се какви било, ситуацијата може да биде симулирана и реална). Ние ги поставуваме плодовите од лево кон десно по следниот редослед:

јаболко / круша / банана

Прашање еден: На колку начини може да се преуредат?

Една комбинација е веќе напишана погоре и нема проблеми со останатите:

јаболко / банана / круша
круша / јаболко / банана
круша / банана / јаболко
банана / јаболко / круша
банана / круша / јаболко

Вкупно: 6 комбинации или 6 пермутации.

Па, не беше тешко да се наведат сите можни случаи овде, но што ако има повеќе ставки? Веќе со четири различни овошја, бројот на комбинации значително ќе се зголеми!

Отворете референтен материјал (Прирачникот е лесен за печатење)а во став број 2 најдете ја формулата за бројот на пермутации.

Без маки - 3 предмети може да се преуредат на начини.

Прашање второ: На колку начини можете да изберете а) едно овошје, б) две овошја, в) три плодови, г) барем едно овошје?

Зошто да изберете? Така, тие направија апетит во претходниот пасус - за да јадат! =)

а) Едно овошје може да се избере, очигледно, на три начини - земете или јаболко, круша или банана. Формалното пребројување се заснова на формула за бројот на комбинации:

Влезот во овој случај треба да се разбере на следниов начин: „на колку начини можете да изберете 1 овошје од три?

б) Ги наведуваме сите можни комбинации на две овошја:

јаболко и круша;
јаболко и банана;
круша и банана.

Бројот на комбинации е лесно да се провери со користење на истата формула:

Записот се подразбира слично: „на колку начини можете да изберете 2 овошја од три?“.

в) И, конечно, три плодови може да се изберат на единствен начин:

Патем, формулата за бројот на комбинации има смисла и за празен примерок:
На овој начин, не можете да изберете ниту едно овошје - всушност, не земајте ништо и тоа е тоа.

г) На колку начини можете да преземете барем еденовошје? Условот „барем еден“ подразбира дека сме задоволни со 1 овошје (било кое) или кое било 2 овошје или сите 3 овошја:
начини на кои можете да изберете барем едно овошје.

Читатели кои внимателно ја проучувале воведната лекција за теорија на веројатноствеќе сфатив нешто. Но, за значењето на знакот плус подоцна.

За да одговорам на следното прашање, ми требаат двајца волонтери ... ... Па, бидејќи никој не сака, тогаш ќе се јавам на табла =)

Прашање трето: На колку начини може да им се подели едно овошје на Даша и Наташа?

За да дистрибуирате две овошја, прво мора да ги изберете. Според ставот „биди“ од претходното прашање, тоа може да се направи на начини, ќе ги препишам повторно:

јаболко и круша;
јаболко и банана;
круша и банана.

Но сега ќе има двојно повеќе комбинации. Размислете, на пример, првиот пар на овошје:
можете да ја третирате Даша со јаболко, а Наташа со круша;
или обратно - Даша ќе ја добие крушата, а Наташа ќе го добие јаболкото.

И таквата пермутација е можна за секој пар плодови.

Размислете за истата студентска група која отиде на танцот. На колку начини може да се спојат момче и девојче?

Начини на кои можете да изберете 1 млад човек;
начини на кои можете да изберете 1 девојка.

Значи еден млад човек иможе да се избере една девојка: начини.

Кога ќе се избере 1 објект од секое множество, тогаш важи следниот принцип на броење комбинации: секојобјект од едно множество може да формира пар со секојобјект на друго множество.

Односно, Олег може да покани која било од 13-те девојки да танцуваат, Евгениј - исто така која било од тринаесетте, а сличен избор имаат и другите млади луѓе. Вкупно: можни парови.

Треба да се забележи дека во овој пример, „историјата“ на формирање на парови не е важна; но, ако се земе предвид иницијативата, тогаш бројот на комбинации мора да се удвои, бидејќи секоја од 13-те девојки може да покани и секое момче да танцува. Сè зависи од условите на одредена задача!

Сличен принцип важи и за посложени комбинации, на пример: на колку начини може да се изберат две момчиња идве девојки да учествуваат во скитот на КВН?

Унијата Инедвосмислено навестува дека комбинациите мора да се множат:

Можни групи уметници.

Со други зборови, секојможе да се натпреварува пар момчиња (45 уникатни парови). било којнеколку девојки (78 уникатни парови). И ако ја земеме предвид распределбата на улогите меѓу учесниците, тогаш ќе има уште повеќе комбинации. ... Многу сакам, но сепак ќе се воздржам да продолжам, за да не ви всадам одбивност кон студентскиот живот =).

Правилото за множење важи за повеќе множители:

Задача 8

Колку трицифрени броеви се деливи со 5?

Решение: за јасност, овој број го означуваме со три ѕвездички: ***

AT стотици местаможете да напишете кој било од броевите (1, 2, 3, 4, 5, 6, 7, 8 или 9). Нулата не е добра, бидејќи во овој случај бројот престанува да биде трицифрен.

Но во десетици место(„во средината“) можете да изберете која било од 10-те цифри: .

По услов, бројот мора да се дели со 5. Бројот се дели со 5 ако завршува на 5 или 0. Така, во најнезначајната цифра се задоволуваме со 2 цифри.

Вкупно, има: трицифрени броеви кои се деливи со 5.

Во исто време, делото се дешифрира на следниов начин: „9 начини на кои можете да изберете број стотици места и 10 начини да изберете број во десетици место и 2 начини во единица цифра»

Или уште поедноставно: секојод 9 цифри до стотици местакомбинирано со секојод 10 цифри десетици место и со секојод две цифри цифра на единици».

Одговори: 180

И сега…

Да, речиси заборавив на ветениот коментар на проблемот бр. 5, во кој на Борја, Дима и Володија може да им се дели по една карта на различни начини. Множењето овде го има истото значење: на начини можете да извадите 3 карти од палубата И во секоепримерок за да ги преуредите начини.

И сега проблемот за независно решение ... сега ќе излезам со нешто поинтересно, ... нека се работи за истата руска верзија на блек џек:

Задача 9

Колку добитни комбинации од 2 карти има во играта „точка“?

За оние кои не знаат: победи комбинација 10 + ACE (11 поени) = 21 поен и, ајде да ја разгледаме победничката комбинација од два кеса.

(редоследот на картичките во кој било пар не е важен)

Кратко решение и одговор на крајот од часот.

Патем, не е неопходно да се разгледа пример примитивен. Блек Џек е речиси единствената игра за која постои математички оправдан алгоритам кој ви овозможува да го победите казиното. Оние кои сакаат лесно можат да најдат многу информации за оптималната стратегија и тактика. Точно, таквите мајстори брзо спаѓаат во црната листа на сите претпријатија =)

Време е да се консолидира материјалот покриен со неколку цврсти задачи:

Задача 10

Васија има 4 мачки дома.

а) На колку начини мачките можат да седат во аглите на собата?
б) На колку начини може да им се дозволи на мачките да талкаат?
в) на колку начини Васија може да собере две мачки (едната лево, другата десно)?

Ние одлучуваме: прво, повторно треба да се забележи дека проблемот е за различнипредмети (дури и ако мачките се идентични близнаци). Ова е многу важен услов!

а) Тишина на мачки. Ова извршување е предмет на сите мачки одеднаш
+ нивната локација е важна, така што тука има пермутации:
начини на кои можете да седнете мачки во аглите на собата.

Повторувам дека при пермутирање е важен само бројот на различни објекти и нивната релативна положба. Во зависност од неговото расположение, Васија може да ги седне животните во полукруг на софата, во низа на прозорецот итн. - ќе има 24 пермутации во сите случаи.За погодност, оние кои сакаат можат да замислат дека мачките се повеќебојни (на пример, бели, црни, црвени и пруги) и да ги наведат сите можни комбинации.

б) На колку начини може да им се дозволи на мачките да талкаат?

Се претпоставува дека мачките одат на прошетка само низ вратата, додека прашањето подразбира рамнодушност за бројот на животни - 1, 2, 3 или сите 4 мачки можат да одат на прошетка.

Ги разгледуваме сите можни комбинации:

Начини на кои можете да пуштите да прошета една мачка (било која од четирите);
начини на кои можете да дозволите две мачки да одат на прошетка (наведете ги самите опции);
начини на кои можете да дозволите три мачки да одат на прошетка (една од четирите седи дома);
начин на кој можете да ги ослободите сите мачки.

Веројатно претпоставувате дека добиените вредности треба да се сумираат:
начини да ги оставите мачките да одат на прошетка.

За ентузијастите, нудам комплицирана верзија на проблемот - кога која било мачка од кој било примерок може по случаен избор да излезе надвор, и низ вратата и низ прозорецот на 10-тиот кат. Ќе има повеќе комбинации!

в) На колку начини Васија може да собере две мачки?

Ситуацијата вклучува не само избор на 2 животни, туку и нивно поставување на рацете:
начини на кои можете да земете 2 мачки.

Второто решение: на начини можете да изберете две мачки иначини за садење секојпар во рака:

Одговори: а) 24, б) 15, в) 12

Па, да ми се расчисти совеста, нешто поконкретно за множење на комбинации .... Нека Васија има уште 5 мачки =) На колку начини можете да дозволите 2 мачки да одат на прошетка и 1 мачка?

Односно со секојможе да се ослободат неколку мачки секојмачка.

Уште една хармоника со копче за независна одлука:

Задача 11

3 патници влегле во лифт на 12-катница. Секој, независно од другите, може да излезе на кој било (почнувајќи од 2-ри) кат со иста веројатност. На колку начини:

1) Патниците можат да се симнат на истиот кат (наредбата за излез не е важен);
2) две лица можат да се симнат на еден кат, а трето на друг;
3) луѓето можат да се симнат на различни катови;
4) Дали патниците можат да излезат од лифтот?

И овде често повторно прашуваат, појаснувам: ако 2 или 3 луѓе излезат на ист кат, тогаш редоследот на излегување не е важен. РАЗМИСЛИ, користи формули и правила за комбинации на собирање/множење. Во случај на потешкотии, корисно е патниците да дадат имиња и да образложат во какви комбинации можат да излезат од лифтот. Нема потреба да се вознемирувате ако нешто не успее, на пример, точката број 2 е прилично подмолна.

Комплетно решение со детални коментари на крајот од туторијалот.

Последниот пасус е посветен на комбинации кои исто така се појавуваат доста често - според мојата субјективна проценка, кај околу 20-30% од комбинаторните проблеми:

Пермутации, комбинации и сместувања со повторувања

Наведените типови на комбинации се наведени во став бр. 5 од референтниот материјал Основни формули на комбинаторика, сепак, некои од нив можеби не се многу јасни при првото читање. Во овој случај, препорачливо е прво да се запознаете со практични примери и дури потоа да ја разберете општата формулација. Оди:

Пермутации со повторувања

Во пермутации со повторувања, како во „обични“ пермутации, целиот сет на предмети одеднаш, но има една работа: во ова множество се повторуваат еден или повеќе елементи (објекти). Исполнете го следниот стандард:

Задача 12

Колку различни комбинации на букви може да се добијат со преуредување на картичките со следните букви: K, O, L, O, K, O, L, L, H, I, K?

Решение: во случај сите букви да бидат различни, тогаш треба да се примени тривијална формула, меѓутоа, сосема е јасно дека за предложениот сет на картички, некои манипулации ќе работат „неактивен“, така што, на пример, ако замените некоја две картички со буквите „К во кој било збор, тоа ќе биде истиот збор. Покрај тоа, физички картичките може да бидат многу различни: едната може да биде тркалезна со испечатена буква „К“, другата е квадратна со нацртана буква „К“. Но, според значењето на проблемот, дури и такви картички се смета за исто, бидејќи условот прашува за комбинации на букви.

Сè е исклучително едноставно - вкупно: 11 картички, вклучувајќи го и писмото:

К - се повторува 3 пати;
О - се повторува 3 пати;
L - се повторува 2 пати;
б - се повторува 1 пат;
H - се повторува 1 пат;
И - се повторува 1 пат.

Проверете: 3 + 3 + 2 + 1 + 1 + 1 = 11, што сакавме да го провериме.

Според формулата број на пермутации со повторувања:
може да се добијат различни комбинации на букви. Повеќе од половина милион!

За брзо пресметување на голема факторска вредност, погодно е да се користи стандардната функција Excel: постигнуваме резултати во која било ќелија =ФАКТ(11)и кликнете Внесете.

Во пракса, сосема е прифатливо да не се запишува општата формула и, покрај тоа, да се испуштат единичните фактори:

Но, потребни се прелиминарни коментари за повторените писма!

Одговори: 554400

Друг типичен пример на пермутации со повторувања се среќава во проблемот со распоредот на шаховските фигури, кои може да се најдат во магацинот готови решенијаво соодветниот pdf. И за независно решение, дојдов до помалку шаблон задача:

Задача 13

Алексеј оди за спорт, а 4 дена во неделата - атлетика, 2 дена - вежби за сила и 1 ден одмор. На колку начини може да ги закаже своите неделни часови?

Формулата не функционира овде бидејќи ги зема предвид преклопувачките пермутации (на пример, кога вежбите за сила во среда се заменуваат со вежби за сила во четврток). И повторно - всушност, истите 2 сесии за обука за сила може да бидат многу различни едни од други, но во контекст на задачата (во однос на распоредот), тие се сметаат за исти елементи.

Решение во два реда и одговор на крајот од часот.

Комбинации со повторувања

Карактеристична карактеристика на овој тип на комбинација е тоа што примерокот е извлечен од неколку групи, од кои секоја се состои од исти предмети.

Денеска сите работеа напорно, па време е да се освежите:

Задача 14

Студентската кафетерија продава колбаси во тесто, колачи со сирење и крофни. На колку начини може да се купат пет колачи?

Решение: веднаш обрнете внимание на типичниот критериум за комбинации со повторувања - според условот, не збир на предмети како такви, туку различни видовипредмети; се претпоставува дека во продажба има најмалку пет виршли, 5 чизкејкови и 5 крофни. Питите во секоја група, се разбира, се различни - бидејќи апсолутно идентични крофни може да се симулираат само на компјутер =) Сепак, физичките карактеристики на питите не се суштински за значењето на проблемот, а виршлите / чизкејковите / крофните во нивните групи се сметаат за исти.

Што може да има во примерокот? Пред сè, треба да се забележи дека во примерокот дефинитивно ќе има идентични пити (бидејќи избираме 5 парчиња, а понудени се 3 типа за избор). Опции овде за секој вкус: 5 виршли, 5 чизкејкови, 5 крофни, 3 виршли + 2 чизкејкови, 1 виршли + 2 + чизкејкови + 2 крофни итн.

Како и кај „обичните“ комбинации, редоследот на селекција и поставување на пити во примерокот не е важен - само избрале 5 парчиња и толку.

Ја користиме формулата број на комбинации со повторувања:
начин на кој можете да купите 5 пити.

Пријатен оброк!

Одговори: 21

Каков заклучок може да се извлече од многу комбинаторни проблеми?

Понекогаш, најтешко е да се разбере состојбата.

Сличен пример за решение „направи сам“:

Задача 15

Паричникот содржи прилично голем број монети од 1, 2, 5 и 10 рубли. На колку начини може да се извадат три монети од паричникот?

За целите на самоконтрола, одговорете на неколку едноставни прашања:

1) Дали сите монети во примерокот можат да бидат различни?
2) Наведете ја „најевтината“ и „најскапата“ комбинација на монети.

Решение и одговори на крајот од часот.

Од мое лично искуство можам да кажам дека комбинациите со повторувања се најреткиот гостин во пракса, што не може да се каже за следниот тип на комбинации:

Постави со повторувања

Од множество составено од елементи, се избираат елементи, а редоследот на елементите во секој примерок е важен. И сè би било во ред, но прилично неочекувана шега е дека можеме да избереме кој било предмет од оригиналниот сет онолку пати колку што сакаме. Фигуративно кажано, од „мноштвото нема да се намали“.

Кога тоа се случува? Типичен пример е комбинирана брава со неколку дискови, но поради развојот на технологијата, порелевантно е да се земе предвид неговиот дигитален потомок:

Задача 16

Колку 4-цифрени пински кодови има?

Решение: всушност, за да се реши проблемот, доволно е да се знаат правилата на комбинаториката: можете да ја изберете првата цифра од пин-кодот на начини иначини - втората цифра од пин-кодот ина ист начин - третиот иисто толку - четвртиот. Така, според правилото за множење на комбинации, може да се состави четирицифрен пин код: на начини.

И сега со формулата. По услов, ни се нуди збир на броеви, од кои се избираат и ставаат броеви по одреден редослед, додека броевите во примерокот може да се повторат (т.е. која било цифра од оригиналното множество може да се користи произволен број пати). Според формулата за бројот на места со повторувања:

Одговори: 10000

Што ми паѓа на ум овде ... ... ако банкоматот ја „јаде“ картичката по третиот неуспешен обид за внесување на пин-кодот, тогаш шансите да ја подигнете по случаен избор се многу илузорни.

А кој рече дека нема практична смисла во комбинаториката? Когнитивна задача за сите читатели на страницата:

Задача 17

Според државниот стандард, регистарската табличка на автомобилот се состои од 3 бројки и 3 букви. Во овој случај, број со три нули не е дозволен, а буквите се избираат од множеството A, B, E, K, M, H, O, R, C, T, U, X. (се користат само оние кирилични букви, чиј правопис одговара на латинските букви).

Колку различни регистарски таблички може да се состават за еден регион?

Не е така, патем, и многу. Во големите региони, овој број не е доволен, и затоа за нив има неколку шифри за натписот RUS.

Решение и одговор на крајот од часот. Не заборавајте да ги користите правилата на комбинаториката ;-) ...сакав да се пофалам дека сум ексклузивен, но испадна дека не е ексклузивен =) Ја погледнав Википедија - има пресметки, сепак, без коментари. Иако за едукативни цели, веројатно, малкумина го решија.

Нашата фасцинантна лекција дојде до својот крај, и на крајот сакам да кажам дека не си го изгубивте времето - од причина што формулите за комбинаторика наоѓаат уште една витална практична примена: тие се наоѓаат во различни задачи на теорија на веројатност,
и во задачи за класичната дефиниција на веројатноста- особено често

Ви благодариме на сите за активното учество и се гледаме наскоро!

Решенија и одговори:

Задача 2: Решение: најдете го бројот на сите можни пермутации на 4 карти:

Кога картичката со нула е на прво место, бројот станува трицифрен, така што овие комбинации треба да се исклучат. Нека нулата е на првото место, тогаш преостанатите 3 цифри во најмалку значајните цифри може да се преуредат на начини.

Забелешка : затоа што има неколку картички, лесно е да се наведат сите такви опции овде:
0579
0597
0759
0795
0957
0975

Така, од предложениот сет, можете да направите:
24 - 6 = 18 четирицифрени броеви
Одговори : 18

Задача 4: Решение: 3 карти може да се изберат од 36 начини.
Одговори : 7140

Задача 6: Решение: начини.
Друго решение : начини на кои можете да изберете две лица од групата и и
2) „Најевтиниот“ комплет содржи монети од 3 рубљи, а најскапиот сет содржи 3 монети од десет рубли.

Задача 17: Решение: начини на кои можете да направите дигитална комбинација на број на автомобил, додека еден од нив (000) треба да се исклучи:.
начини на кои можете да направите комбинација на букви од број на автомобил.
Според правилото за множење на комбинации, сè може да се состави:
броеви на автомобили
(секојусогласена дигитална комбинација со секојкомбинација на букви).
Одговори : 1726272

Комбинација е неуреден избор на елементи од конечно множество со фиксен број и без повторување на елементите. Различните комбинации мора да се разликуваат за најмалку еден елемент, а редоследот на елементите не е важен. На пример, од множеството на сите самогласки на латински букви (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 е еднаков на 2 n во согласност со формулата за сумирање за бином по надреден знак. Од ова произлегува дека збирот на елементите над која било од хоризонталите со број 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-тиот триаголен број T n може да се добие со собирање на сите природни броеви што ги претставуваат неговите линеарни влакна:

Слично на тоа, лесно е да се најде тетраедарскиот број P n со пресметување на следнава сума од првите 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) цифри имаат нула вредности. Очигледно, со оваа форма на пишување, различните комбинации мора да се разликуваат во распоредот на единиците и постојат само C (n, m) начини да се подредат m единици или (nm) нули во n-битно бинарно множество. На пример, следната табела ги наведува сите 6 такви бинарни комбинации кои обезбедуваат 4-битни бинарни броеви за сите комбинации од 4 елементи на произволно множество (E 1 , E 2 , E 3 , E 4 ) со 2:

Во општиот случај, задачата за набројување на таквите бинарни комбинации се сведува на систематско набројување на сите бинарни множества n-битни со различни распореди на m единечни и (nm) нула битови. Во наједноставна форма, ваквото набројување се спроведува со различни методи на транспозиција на соседни цифри со поместување (алгоритми со транспозитивно-поместување). Ова се итеративни алгоритми, а нивните имиња ја одразуваат природата на операциите извршени на секој чекор. Итеративните постапки на алгоритмите со транспозитивно поместување формираат секвенци од бинарни комбинации кои започнуваат со бинарно множество, каде што сите се концентрирани во долните битови (десно) и завршуваат кога сите се во повисоките битови (лево):

Коинцидирајќи во почетните и конечните комбинации, овие секвенци се разликуваат по редоследот на набројување на средните бинарни множества. Меѓутоа, во сите случаи, секоја следна бинарна комбинација се формира според претходната како резултат на извршување на соодветните операции за транспозиција и поместување. Во исто време, различните алгоритми со транспозитивно поместување се разликуваат во начинот на избор на пар цифри за транспозиција и група цифри за поместување. Оваа специфичност е разгледана подолу за алгоритми за транспозиција со лево и десно поместувања.

Во алгоритмот за транспозиција со лево поместување на секој чекор, следната бинарна комбинација се добива од тековната со замена на најлевиот пар битови 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.

Ние понекогаш избираме од многу без разлика на редоследот. Таков избор се нарекува комбинација . Ако играте карти, на пример, знаете дека во повеќето ситуации редоследот по кој ги држите картите не е важен.

Пример 1Најдете ги сите комбинации од 3 букви земени од збир од 5 букви (A, B, C, D, E).

РешениеОвие комбинации се:
(А, Б, В), (А, Б, Г),
(А, Б, Е), (А, Ц, Г),
(A, C, E), (A, D, E),
(B, C, D), (B, C, E),
(B, D, E), (C, D, E).
Има 10 комбинации од три букви, избрани од пет букви.

Кога ќе ги најдеме сите комбинации од множество со 5 објекти, ако земеме 3 објекти истовремено, ќе ги најдеме сите подмножества од 3 елементи. Во овој случај, редоследот на предметите не се разгледува. Потоа,
(A, C, B) се нарекува исто множество како (A, B, C).

Подмножество
Множеството A е подмножество на B и значи дека A е подмножество на и/или исто како B ако секој елемент од A е елемент на B.

Елементите на подмножеството не се подредени. Кога се разгледуваат комбинациите, редоследот не се смета!

Комбинација
Комбинација, што содржи k објекти е подмножество кое се состои од k објекти.

Сакаме да напишеме формула за пресметување на бројот на комбинации на n објекти ако k објекти се земаат истовремено.

Комбинирана нотација
Бројот на комбинации на n објекти, ако се земат во исто време, се означува со n C k .

Ние го нарекуваме n C k број на комбинации . Сакаме да напишеме општа формула за n C k за кое било k ≤ n. Прво, точно е дека n C n = 1, бидејќи множеството со n елементи има само едно подмножество со n елементи, е самото множество. Второ, n C 1 = n затоа што множество со n елементи има само n подмножества со по 1 елемент. Конечно, n C 0 = 1, бидејќи множество со n елементи има само едно подмножество со 0 елементи, односно празното множество ∅. За да разгледаме други комбинации, да се вратиме на Пример 1 и да го споредиме бројот на комбинации со бројот на пермутации.

Забележете дека секоја комбинација од 3 елементи има 6, или 3!, пермутации.
3! . 5 C 3 \u003d 60 \u003d 5 P 3 \u003d 5. четири. 3,
така
.
Општо земено, бројот на комбинации на k елементи избрани од n објекти, n C k пати пермутации на овие елементи k!, треба да биде еднаков на бројот на пермутации на n елементи над k елементи:
к!. n C k = n P k
n C k = n P k /k!
n C k = (1/k!). nP k
n Ck =

Комбинации на k објекти од n објекти
Вкупниот број на комбинации на k елементи од n објекти се означува со n C k , определен со
(1) n C k = ,
или
(2) n C k =

Друг тип на нотација за n C k е биномен коефициент . Причината за оваа терминологија ќе стане јасна подолу.

Биномен коефициент

Пример 2Пресметајте со помош на формулите (1) и (2).

Решение
а) Според (1),
.
б) Според (2),

Имајте на ум дека тоа не значи n/k.

Пример 3Пресметајте и .

РешениеЈа користиме формулата (1) за првиот израз и формулата (2) за вториот. Потоа
,
користејќи (1) и
,
користејќи ја формулата (2).

Забележи го тоа
,
и користејќи го резултатот од примерот 2 ни дава
.
Ова имплицира дека бројот на подмножество од 5 елементи од множество од 7 елементи е ист со бројот на подмножество од 2 елементи од множество од 7 елементи. Кога се избираат 5 елементи од множество, тие не вклучуваат 2 елементи. За да го видите ова, разгледајте го множеството (A, B, C, D, E, F, G):

Во принцип, го имаме следново. Овој резултат дава алтернативен начин за пресметување на комбинацијата.

Подмножества со големина k и големина
и n C k = n C n-k
Бројот на подмножества со големина k од множество со n објекти е ист со бројот на подмножества со големина n - k. Бројот на комбинации на k објекти од множество од n објекти е ист како бројот на комбинации од n предмети земени во исто време.

Сега ќе решаваме проблеми со комбинации.

Пример 4 Лотарија во Мичиген. Одржан во државата Мичиген двапати неделно, WINFALL има џекпот што, според барем, е еднакво на 2 милиони американски долари. За еден долар, играчот може да пречкрта 6 броеви од 1 до 49. Ако овие бројки се совпаѓаат со оние што паѓаат за време на лотаријата, играчот добива. (

Комбинаториката е гранка на математиката која ги проучува прашањата за тоа колку различни комбинации, кои подлежат на одредени услови, можат да се направат од дадени предмети. Основите на комбинаториката се многу важни за проценка на веројатностите на случајни настани, бидејќи токму тие овозможуваат да се пресмета фундаментално можниот број на различни сценарија за развој на настаните.

Основна формула за комбинаторика

Нека има k групи елементи, а i-тата група се состои од n i елементи. Ајде да избереме по еден елемент од секоја група. Тогаш вкупниот број N на начини на кои може да се направи таков избор се одредува со релацијата N=n 1 *n 2 *n 3 *...*n k .

Пример 1Да го објасниме ова правило со едноставен пример. Нека има две групи на елементи, првата група се состои од n 1 елементи, а втората - од n 2 елементи. Колку различни пара елементи може да се направат од овие две групи, така што парот содржи по еден елемент од секоја група? Да претпоставиме дека го земавме првиот елемент од првата група и, без да го промениме, поминавме низ сите можни парови, менувајќи ги само елементите од втората група. Има n 2 такви парови за овој елемент. Потоа го земаме вториот елемент од првата група и ги правиме сите можни парови за него. Ќе има и n 2 такви пара. Бидејќи има само n 1 елементи во првата група, ќе има n 1 *n 2 можни опции.

Пример 2Колку трицифрени парни броеви може да се направат од цифрите 0, 1, 2, 3, 4, 5, 6 ако цифрите може да се повторат?
Решение: n 1 \u003d 6 (бидејќи може да земете која било цифра од 1, 2, 3, 4, 5, 6 како прва цифра), n 2 \u003d 7 (бидејќи може да земете која било цифра од 0 како втора цифра , 1 , 2, 3, 4, 5, 6), n 3 \u003d 4 (бидејќи можете да земете која било цифра од 0, 2, 4, 6 како трета цифра).
Значи, N=n 1 *n 2 *n 3 =6*7*4=168.

Во случај кога сите групи се состојат од ист број на елементи, т.е. n 1 =n 2 =...n k =n можеме да претпоставиме дека секој избор е направен од истата група, а елементот се враќа во групата по изборот. Тогаш бројот на сите начини на избор е еднаков на n k . Овој начин на избор во комбинаториката се нарекува врати примероци.

Пример 3Колку четирицифрени броеви може да се направат од броевите 1, 5, 6, 7, 8?
Решение.Постојат пет можности за секоја цифра од четирицифрен број, така што N=5*5*5*5=5 4 =625.

Размислете за множество кое се состои од n елементи. Ова множество во комбинаторика се нарекува општата популација.

Број на сместувања од n елементи по m

Дефиниција 1.Сместување од nелементи од мво комбинаториката се нарекува било кој нарачан сетод мразлични елементи избрани од општата популација во nелементи.

Пример 4Различни распореди на три елементи (1, 2, 3) два по два ќе бидат множества (1, 2), (2, 1), (1, 3), (3, 1), (2, 3), (3 , 2). Поставувањата може да се разликуваат едни од други и по елементи и по нивниот редослед.

Бројот на сместувања во комбинаториката се означува со A n m и се пресметува со формулата:

Коментар: n!=1*2*3*...*n (читај: „en factorial“), дополнително се претпоставува дека 0!=1.

Пример 5. Колку двоцифрени броеви има во кои цифрата на десетките и цифрата на единиците се различни и непарни?
Решение:бидејќи има пет непарни цифри, имено 1, 3, 5, 7, 9, тогаш овој проблем се сведува на избор и поставување на две од петте различни цифри во две различни позиции, т.е. дадените бројки ќе бидат:

Дефиниција 2. Комбинацијаод nелементи од мво комбинаториката се нарекува било кој неуреден сетод мразлични елементи избрани од општата популација во nелементи.

Пример 6. За сетот (1, 2, 3), комбинациите се (1, 2), (1, 3), (2, 3).

Број на комбинации на n елементи по m

Бројот на комбинации се означува со C n m и се пресметува со формулата:

Пример 7На колку начини читателот може да избере две книги од шест достапни?

Решение:Бројот на начини е еднаков на бројот на комбинации од шест книги по две, т.е. еднакво на:

Пермутации на n елементи

Дефиниција 3. Пермутацијаод nелементи се нарекува било кој нарачан сетовие елементи.

Пример 7а.Сите можни пермутации на множество составено од три елементи (1, 2, 3) се: (1, 2, 3), (1, 3, 2), (2, 3, 1), (2, 1, 3) , ( 3, 2, 1), (3, 1, 2).

Бројот на различни пермутации на n елементи се означува со P n и се пресметува со формулата P n =n!.

Пример 8На колку начини седум книги од различни автори можат да се подредат по ред на полица?

Решение:овој проблем се однесува на бројот на пермутации на седум различни книги. Постојат P 7 =7!=1*2*3*4*5*6*7=5040 начини за средување на книгите.

Дискусија.Гледаме дека бројот на можни комбинации може да се пресмета според различни правила (пермутации, комбинации, пласмани), а резултатот ќе биде различен, бидејќи принципот на броење и самите формули се различни. Гледајќи внимателно во дефинициите, можете да видите дека резултатот зависи од неколку фактори во исто време.

Прво, од колку елементи можеме да ги комбинираме нивните множества (колку е голема општата популација на елементи).

Второ, резултатот зависи од тоа каква големина ни се потребни комплети елементи.

Конечно, важно е да знаеме дали редоследот на елементите во комплетот е значаен за нас. Да го објасниме последниот фактор со следниот пример.

Пример 9На родителскиот состанок има 20 луѓе. Колку различни опции за составување на матичната комисија има ако треба да вклучи 5 лица?
Решение:Во овој пример, не нè интересира редоследот на имињата на комисиската листа. Ако, како резултат, истите луѓе се појавуваат во неговиот состав, тогаш во смисла на значење за нас ова е истата опција. Затоа, можеме да ја користиме формулата за да го пресметаме бројот комбинацииод 20 елементи, 5.

Работите ќе бидат поинакви ако секој член на комисијата првично е одговорен за одредена област на работа. Тогаш со истиот платен список на комисијата се можни 5 внатре во него! опции пермутациитоа е важно. Бројот на различни (и во однос на составот и во областа на одговорност) опции се одредува во овој случај според бројот пласманиод 20 елементи, 5.

Задачи за само-тестирање
1. Колку трицифрени парни броеви може да се направат од броевите 0, 1, 2, 3, 4, 5, 6 ако броевите може да се повторат?

2. Колку петцифрени броеви се читаат исто од лево кон десно и од десно кон лево?

3. Во класот има десет предмети и пет часови дневно. На колку начини можете да направите распоред за еден ден?

4. На колку начини може да се изберат 4 делегати за конференцијата ако има 20 луѓе во групата?

5. На колку начини може да се стават осум различни букви во осум различни пликови ако во секој плик е ставена само една буква?

6. Од тројца математичари и десет економисти потребно е да се направи комисија составена од двајца математичари и шест економисти. На колку начини може да се направи ова?