Комбинаторика - шта је то? Елементи комбинаторике

Специјалисти у различитим областима морају да решавају комбинационе проблеме: преуређивање бројева, знакова и других објеката. На пример, глава продавнице треба да дистрибуира различите типове рада између радних машина. Комбинаторика је значајна грана математике, која, као што није тешко погодити, налази своју нишу у различитим пољима и специјалностима: физици, биологији, лингвистици, хемији, инжењерству, теорији кодирања и још много тога. Принципи комбинаторике су такође основа решења пробабилистичких проблема.

Хистори оф

Први предуслови комбинаторике као науке појавили су се у 16. веку. Допринос развоју ове области знања у великој мери, фасцинираност људи коцкањем: картама, коцкицама, лутријом су изгубили не само злато и драгуље, већ и палате и имања. Зато, питајући се, на пример, колико често можете бацити добар сет тачака на кости или добити два аса, људи су постепено долазили до основа комбинаторике и вероватноће. Да ли комбинаторика помаже некоме да победи или да изгуби мање? Питање је интересантно, али његово разматрање је изван оквира овог чланка.

Први математичар који је био активно заинтересован за комбинаторику био је италијански италијански Тартаглиа (1499-1557), након чега су се еминентни научници као што су Пасцал, Фермат, Берноулли, Леибнитз, Еулер и други активно укључили у проучавање ових питања. и даље је остала, ако не и забавна игра са бројевима, онда теорија која се користи искључиво у коцкању и нема право да се користи на другим местима.

Развој комбинаторика

Значајни помаци у комбинаторици догодили су се са појавом 20. века. компјутери, програмирање, и најважније - дискретна математика. Током овог периода, комбинаторика добија врхунац свог брзог развоја и постаје пуноправна наука. Комбинаторне методе почињу да се користе свуда:

• решавање транспортних проблема;
• сцхедулинг;
• припрема планова за производњу и продају робе;
• у теорији насумичних процеса;
• у математичкој статистици и теорији вероватноће;
• у припреми и спровођењу експеримената;
• у шаху;
• у термодинамици;
• у геометрији;
• иу многим другим областима.

Суперститиоус Леадер Цхалленге

Постојао је лидер у свету који је веровао да му број 8 доноси тоталне неуспехе. Стога је одлучио да се отараси свих бројева који би садржали бројку осам. 600 људи је радило под његовим надзором. Сви су имали идентификациони број пасус за рад, који се састоји од три броја. Не размишљајући двапут, менаџер је одлучио да из броја пролаза искључи број 8. И онда се питао да ли има довољно различитих бројева за 600 људи из распона од 000 до 999, што не би укључивало 8?

Очигледно решење овог проблема је ручно исписати све бројеве од 000 до 999 и прецртати оне бројеве у којима их има осам. Да ли је могуће ријешити проблем на једноставнији начин? Ако за 999 бројева задатак са бројањем свих варијанти изгледа изводљиво, онда ће опсег од 000000 до 999999 захтијевати много већи напор. То је уштеда времена и напора дизајнираних комбинаторика формула.

Решење проблема сујеверног вође

Друго решење је следеће. Уклањањем 8 из серије, добијамо да су 0, 1, 2, 3, 4, 5, 6, 7, 9 - ових девет бројева валидни. Након тога би требало да нађете све двоцифрене бројеве који не би садржали 8. То је урађено једноставно: потребно је узети било који број од важећег и додати му било који број од важећег. Тако ћемо лако добити све двоцифрене бројеве који одговарају услову. Као резултат тога, добијамо да свака појединачна цифра даје 9 различитих двоцифрених бројева. Укупан број таквих цифара ће бити 9 * 9 = 9 ² = 81.

Настављајући аналогију, можемо закључити да је за добијање свих трознаменкастих бројева без осмица неопходно додијелити трећу знаменку постојећим двознаменкастим бројевима, такођер из дозвољених вриједности. Тада ћемо добити број таквих цифара 9 ² * 9 = 9 * 9 * 9 = 729. Тако смо сазнали да ће глава нашег менаџера лако моћи да обезбеди 600 запослених са празнинама, чији бројеви неће садржати 8. Покушајте сами да решите проблем за себе. са пет цифара.

И шта ће се десити ако менаџер не воли број 2? Испоставља се да ће број дозвољених бројева бити 8, и то: 0, 1, 3, 4, 5, 6, 7, 9. Затим, процјењујући број комбинација бројева без 2 и 8, можемо закључити да је њихов број 8 * 8 * 8 = 512, а то очигледно није довољно да обезбеди 600 људи са пропусницама. Комбинаторика је наука која помаже да се одговори на таква питања учинковитије него што се може урадити бруталном силом.

Лото проблем

Сви знају игру. Ту је и торба у којој се налазе бачве са бројевима од 1 до 90. Улазнице се дистрибуирају свим учесницима, у којима је потребно обојити одређени број ћелија бројевима. Након тога, водећи лото излази из торбе један од бројева. Победник ће бити онај који је прецртао већину бројева у тикету, што се подудара са онима које је домаћин игре извукао.

Једном Нина, играјући лото, мислио је. Често је гледала како водитељ добија исти број из торбе. Али, у исто време, прва два бачва испоставила су се много мање. Онда се питала колико начина можете доследно да извучете из кесе са две буради? Елементи комбинаторике помажу да се одговори на њено питање.

Лото решење

Очигледно, прва бачва може имати бројеве од 1 до 90. Другим речима, постоји 90 начина за извлачење прве бурета. Али шта је са следећим? Ако је, на примјер, бачва бр. 63 уклоњена из торбе, онда се у тренутној игри више неће поновити.

Метод табеле ће нам помоћи да решимо проблем. У наслову иу заглављу ће бити исписани бројеви од 1 до 90. Тако ће на раскрсници било које линије и било које колоне бити пар бројева, или пар бачви уклоњених из вреће. Истовремено ће се на дијагонали табеле налазити исти парови бројева. То је немогуће у зависности од услова, пошто је после уклањања једне цифре из кесе, њено понављање немогуће. Набавите табелу у следећем облику:

Укупно добијамо табелу, у којој је број ћелија 90 * 90 = 8100. Треба имати на уму да је 90 парова знаменки лоцираних дијагонално које су немогуће према условима. Тада ће одговор на питање колико начина можете добити из врећице бити 8100 - 90 = 8010 опција.

Замишљајући мало другачији начин можете доћи до истог одговора. За прву бачву постоји 90 опција. Након што је први изваден, остаће 89 опција за другу бачву. Тако ће укупан број опција бити 90 * 89 = 8010. Елементи комбинаторика могу се користити на различите начине. Једино питање је једноставност и универзалност методе. На пример, метода табеле се може користити за три бурета која се извлаче у низу и, очигледно, то ће бити граница. А шта за четири или више?

Проблем са посадом

Ако избор зависи од тога који су објекти раније изабрани, онда је згодно приказати такав процес као "дрво". У првом кораку, колико је линија постављено из једне тачке јер постоје могући избори у првом кораку. На крајевима сваке линије налазе се и бројне додатне линије које се могу урадити у другом кораку, итд. Као резултат тога, биће нацртана врста стабла или графикона. Комбинаторика и теорија могу звучати збуњујуће и неразумљиво, па погледајмо примјер.

Прије почетка експедицијске године, руководство има задатак - да скупља посаде за путовања. Сваки тим мора имати три особе: командант, инжењер и доктор. Истовремено, број специјалиста у одређеној области може варирати. Дозвољено је, на пример, да се један лекар пошаље у две различите експедиције, јер постоје само два доктора, и може бити по три у сваком команданту и инжењеру. У овом случају, састављач експедиционог плана мора узети у обзир психолошку компатибилност чланова тима. Ова карактеристика је једна од најважнијих у дугим и удаљеним експедицијама за њихово успјешно понашање. На основу свих описаних услова, појављује се следећа слика:

Где су _ја командири, б _и су инжењери и _ја сам доктори. Истовремено, током испитивања сваке особе, утврђено је да се командант а ₁ психички добро слаже са инжењерима б ₁ и б ₃ , а ₂ - са б ₁ и б ₂ , али је лекар ц ₃ неспојив са инжењером б ₁ , итд. Питање које је првобитно постављено руководиоцу пројекта било је колико посада може бити састављено под таквим условима. Из графикона се може видети да може бити укупно 10 таквих посада, али шта би се десило да питање психолошке компатибилности нема тежину? Тада се испоставља да ће након избора команданата а _и бити три алтернативе за сваког од њих у избору инжењера. Према томе, за пар командира и инжењера би постојале и три опције за докторе. Тада ће број комбинација достићи 4 * 3 * 3 = 36 посада.

Положаји, пермутације и комбинације

У горе наведеним примјерима, рјешење проблема се десило такозваним аксиоматским методом. Наиме, може се рећи да постоји низ основних задатака, чије се рјешавање може свести на многе проблеме. Међутим, баш као иу стереометрији, тешко је решавати проблеме који се заснивају искључиво на аксиомима, а за то се користи прикладнији алат назван “теореме”, тако да је у комбинаторици прикладније користити више генерализоване и проверене методе. Током вековног проучавања комбинаторике, постало је очигледно да се велики број задатака сусреће чешће од других, и они су раздвојени у одвојене класе и добили су своја имена, постајући главна комбинаторика - односно, пласмани, пермутације и комбинације.

Комбинаторни проблеми

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

У поједностављеном случају, може се примијетити да комбинаторна математика укључује проблеме који укључују узорке и локације објеката. Истовремено, комбинаторику карактерише рад искључиво са коначним скупом објеката. На основу ових одредби можемо разликовати следеће задатке карактеристичне за комбинаторику:

1. Направите избор објеката, узимајући у обзир сва својства.
2. Доказати или оповргнути постојање узорка под одређеним условима.
3. Пронађите број могућих комбинација.
4. Пронађите све комбинације и одредите алгоритам за њихово пописивање.
5. Пронађите оптимално решење проблема у датим условима.

Ако се дотични проблем може додијелити једном од ових типова, онда је то комбинаторно и комбинаторне формуле ће помоћи у његовом рјешавању.