Елементи комбинаторике и појам скупа
Скуп је основни математички појам и не дефинише се. Скуп се може описати (не и дефинисати)
као целина различитих елемената који имају неку особину.
То се записује
и чита се А је скуп х-ова таквих да важи особина 
.
Скупове можемо записати и у следећем облику
,
.
У овом запису су елементи скупа А набројани.
За скупове није битан редослед елемената,
није ни битно да ли се неки елементи понављају или не.
{1, 2, 3} = {1, 1, 2, 3, 3, 3} = {3, 2, 1}.
Од елемената скупа А можемо правити различите распореде или низове, правити нове подскупове и пребројавати њихове елементе.
Комбинаторика је грана математике која се бави проучавањем тих распореда, подскупова и пребројавањем елемената тих скупова.
Пример 1.
Дат је скуп цифара А = {1, 2, 3, 4, 6, 7, 8}. Колико се различитих петоцифрених бројева може формирати од овог скупа цифара, ако се цифре не понављају?
У првом разреду су ови задаци решавани без коришћења формула и без навођења који је тип распореда у питању.
Тај начин решавања задатака је, често пута, најбољи начин да се дође до решења. Па да се подсетимо.
Формирају се петоцифрени бројеви и посматрамо сваку позицију цифре посебно и на колико начина се она може формирати.
Посматрамо прву цифру броја и на колико начина је можемо одабрати. На располагању је седам цифара, значи на седам начина
За избор друге цифре је преостало шест цифара
За трећу цифру је преостало пет цифара
и редом
Таквих бројева има
При решавању задатак овог типа треба уочити две важне особине формирања избора.
I Да ли је битан редослед избора елемената?
II Да ли се елементи могу понављати у избору?
У претходном примеру је битан редослед избора (12 је различито од 21). Некада се у тексту задатка нагласи да ли се eлементи могу понављати или не.
Ако се то не нагласи онда морамо на основу избора који се формирају одредити да ли се елементи могу понављати или не.
Пример 2.
Дат је скуп цифара А = {1, 2, 3, 4, 6, 7, 8}. Колико се различитих петоцифрених бројева може формирати од овог скупа цифара?
У тексту задатка није наведено да ли се цифре могу понављати или не. У овом случају нпр. број 11111 испуњава услове дате у задатку,
а то значи да се цифре могу понављати.
Укупан број оваквих бројева се може одредити следећим поступком.
Прва цифра се може одабрати на седам начина
Цифре се могу понављати па се за избор друге цифре могу користити све цифре
и редом
Таквих бројева има
■
Пример 3.
Из одељења
IV-1 које има 26 ученика треба одабрати делегацију од три ученика. На колико се начина то може урадити?
Првог ученика можемо одабрати на 26 начина
Избор се не може поновити па је преостало 25 ученика
и последњег ученика бирамо од преостала 24 ученика
Приликом избора делегације није битно којим редом су одабрани ученици па важи
А Б В = А В Б = Б А В = Б В А = В А Б = В Б А
То значи да је 6 пута поновљен исти избор. Без набрајања истих избора могли смо тај
број понављања одредити и тако што посматрамо на колико начина смо могли распоредити три А, Б и В ученика, а то је
Укупан број различитих делегација је
Пример 4.
Дат је скуп цифара А = {0, 1, 2, 3, 4, 6, 7, 8}. Колико се различитих петоцифрених бројева може формирати од овог скупа ако се
а) цифре могу понављати;
б) цифре не могу понављати.
■
Пример 5.
Дат је скуп цифара А = {0, 1, 2, 3, 4, 6, 7, 8}. Колико се различитих парних/непарних петоцифрених бројева може формирати
од овог скупа ако се
а) цифре могу понављати;
б) цифре не могу понављати.
■
Пример 6.
Дат је скуп цифара А = {0, 1, 2, 3, 4, 6, 7, 8}. Колико се различитих петоцифрених бројева дељивих са 4 може формирати
од овог скупа ако се
а) цифре могу понављати;
б) цифре не могу понављати.
■
Пермутације без понављања
Основни проблем комбинаторике је одређивање броја начина на који се неки елементи скупа
,
,
могу распоредити по неком датом правилу.
Потребно је одредити две карактеристике распореда.
Прва карактеристика је да ли је битан редослед избора или ређања елемената скупа.
Ако је редослед битан и бира се
к елемената, онда се добијају уређене к-торке или низови од к елемената.
Ако редослед није битан онда се добијају неуређене к-торке.
Друга карактеристика је да ли се елементи могу понављати или не.
На основу тих карактеристика разликују се три основна типа распореда.
1о Пермутације;
2о Варијације и
3о Комбинације.
Нека је дат скуп
,
.
Под пермутацијом од
n елемената без понављања скупа А подразумева се свака уређена
n-торка
или низ од
n елемената скупа А, при чему се сваки елеменат појављује тачно једанпут.
Код пермутација је битан редослед избора елемената, тј. редослед ређања елемената у низ. Распоређују се сви елементи скупа А.
Пермутације овог типа биће обележаване са
P, а укупан број пермутација од
n елемената
без понављања ће се обележавати са
P(n).
Пример 1.
Колико се различитих речи може формирати од слова речи "КОМБИНАТ" (добијене речи не морају имати смисла).
При фомирању речи битан је редослед избора слова, учествују сва слова и нема понављања слова, а то значи да су
речи пермутације без понављања од 8 елемената.
Број оваквих речи може да се одреди као што су решавани претходни примери.
Формирају се осмочлани избори.
Прво слово бирамо на осам начина
друго на седам
и редом
Укупан број речи је
Ако скуп има
n елемената онда се сличном логиком може доћи до формуле за одређивање укупног броја пермутација
без понављања од
n елемената.
n! се чита
n факторијел.
Пример 2.
Колико се различитих осмоцифрених бројева може добити од скупа А = {0, 1, 2, 3, 4, 5, 6, 7}, aко се свака цифра појављује тачно једанпут.
Ти бројеви су пермутације без понављања, али се од укупног броја пермутација
морају одбацити пермутације код којих је нула на првом месту.
Задатак се могао решити и старом логиком без формула. Прву цифру бирамо на седам начина јер су на располагању цифре без нуле.
На другом месту може да се бира нула, али је једна цифра већ одабрана па преостаје седам цифара.
Трећу цифру бирамо на 6 начина, четврту на 5, итд.
Пример 3.
■
Пример 4.
а) Решити неједначину
а) Скратити разломак
■
Пермутације са понављањем
Нека је дат скуп
.
Под пермутацијом од
n елемената са понављањем подразумева се свака уређена
n-торка елемената скупа А,
при чему се елеменат
понавља
пута,
елеменат
понавља
пута, ...
елеменат
понавља
пута, и
.
Укупан број пермутација са понављањем се рачуна по формули
Пример 1.
Колико се различитих речи може формирати од слова речи "МАТЕМАТИКА"
Слово М се понавља 2 пута, слово А 3 пута, Т - 2 пута, Е - једанпут, И - једанпут и К једанпут.
Пример 2.
Која је по реду пермутација АВАЛА од почетне пермутације АААВЛ?
Напомена: при формирању пермутација поштује се лексикографски поредак, у овом примеру азбучни.
■
Пример 3.
Одредити 500. пермутацију скупа {a, b, c, d, e, f}.
У овом примеру се поштује abc-дни поредак.
■
Пример формирања пермутација
Нека је дат скуп цифара {1, 2, 3, 4}.
Цифре се ређају у растућем поретку па је прва пермутација 1234.
Од овог скупа се може формирати Р(4)=4!=24 пермутације без понављања.
Редослед пермутација је
1. 1234
2. 1243
3. 1324
4. 1342
5. 1423
6. 1432
Јединица не може више бити на првом месту па је седма пермутација
7. 2134
8. 2143
9. 2314
. . .
12. 2431
13. 3124
. . .
Последња пермутација је
24. 4321
Сваки од елемената скупа се појављује на првом месту P(n):n = n!:n = (n-1)! пута.
■
Пример 4.
Колико се различитих десетоцифрених бројева може формирати од скупа {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
ако се свака цифра појављује тачно једанпут и јединица не може бити на првом месту,
двојка не може бити на прва два места и тројка не може бити на прва три места.
За одређивање укупног броја оваквих бројева не постоји формула која би се директно применила.
Ако је нула на првом месту број неће бити десетоцифрен. Са датим условима на првој позицији могу се користити цифре
I: {4, 5, 6, 7, 8, 9}
на другој позицији не могу бити двојка и тројка али могу нула и јединица
II: {0, 1, 4, 5, 6, 7, 8, 9}
на трећој позицији не може бити само тројка
III: {0, 1, 2, 4, 5, 6, 7, 8, 9}
на осталим позицијама може бити било која цифра
IV-X: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
Прву цифру бирамо на 6 начина. За другу позицију се може бирати једна од 8 цифара,
али је једна већ извучена па се друга цифра бира на 7 начина. Трећа цифра се бира на 7 начина (од 9 цифара 2 су извучене).
Четврта цифра се бира на 7 начина (извучене су 3 цифра), пета на 6 начина (извучене 4 цифре) итд.
Укупан број бројева је
x = 6*7*7*7!
Напомена: Ако се праве пермутације без понављања скупа {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, онда нула може бити на првој позицији.
■
Варијације без понављања
Нека је дат скуп
,
.
Под варијацијом без понављања од
n елемената
k-те класе
скупа А подразумева се свака уређена
k-торка различитих
елемената скупа А, при чему је
k <= n.
Код варијација је битан редослед избора елемената, тј. редослед ређања елемената у низ.
Ако је
k = n, онда су варијације без понављања исто што и пермутације без понављања.
Пример 1.
Колико се различитих петоцифрених бројева може формирати од скупа {1, 2, 3, 4, 5, 6, 7, 8, 9} тако да се
свака цифра појављује највише једанпут.
Прву цифру бирамо на 9 начина, другу на 8, трећу на 7, четврту на 6 и пету на 5 начина.
Оваквих бројева има
x =
9
8
7
6
5 = 15120
Укупан број варијација од
n елемената
k-те класе без понављања једнак је
У производу су узастопни природни бројеви и има их
k.
Означавање овог броја није једнозначно. Овде ће се број елемената увек писати у заградама а класа у индексу. Ово важи и за пермутације и за комбинације.
Увек треба проверити како се у некој збирци, уџбенику или раду обележавају ови бројеви.
Пример 2.
Колико се различитих петоцифрених бројева може формирати од скупа {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} тако да се
свака цифра појављује највише једанпут.
Задатак се може решити тако што одредимо укупан број варијација и одбацимо варијације код којих је нула на првом месту.
Задатак се могао решити и без формула. Посматрамо сваку позицију и одређујемо на колико начина бирамо цифре.
Прву цифру бирамо на 9 начина (без нуле), другу на 9 (нула може да се бира али је једна цифра већ извучена),
трећу на 8, четврту на 7 и пету на 6 начина.
Оваквих бројева има
x =
9
9
8
7
6
5
Пример 3.
Колико се различитих петоцифрених бројева дељивих са 4 може формирати од скупа {0, 1, 2, 3, 4, 5, 7, 9} тако да се
свака цифра појављује највише једанпут?
■
Пример 4.
Доказати да је
.
Пример 5.
Решити једначине
а)
;
б)
;
в)
.
Решење примера под в)
Варијације са понављањем
Нека је дат скуп
,
.
Под варијацијом са понављањем од
n елемената
k-те класе
скупа А подразумева се свака уређена
k-торка елемената скупа А.
Сваки елемeнат скупа А се може поновити највише
k пута, при чему
k може бити мање, једнако или веће од
n.
Код пермутација са понављањем број појављивања сваког елемента је фиксиран а код варијација са понављањем одређен је највећи број
понављања сваког елемета (елеменат се не мора појавити).
Пример 1.
Колико се различитих двоцифрених бројева може формирати од скупа {1, 2, 3}?
То су бројеви {11, 12, 13, 21, 31, 22, 23, 32, 33}.
Свака цифра се појавила највише два пута.
У овом примеру су набројани сви избори.
■
Пример 2.
Колико се различитих петоцифрених бројева може формирати од скупа {1, 2, 3, 4, 5, 6, 7, 8, 9}?
У овом примеру број бројева је велики па би набрајање било непрактично.
Посматрамо позиције избора и на колико начина се могу одабрати.
Прву цифру бирамо на 9 начина (на располагању је девет цифара), другу цифру бирамо опет на девет начина
(цифре се могу понављати па су на располагању све цифре),
трећу, четврту и пету бирамо на девет начина па је укупан број бројева
Укупан број варијација са понављањем од
n елемената
k-те класе једанак је
Пример 3.
Колико се различитих петоцифрених бројева може формирати од скупа {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}?
Задатак се може решити тако што се одреди укупан број варијација и одбаце варијације код којих је нула на првој позицији.
II начин
Посматрамо позиције избора и на колико начина се могу одабрати.
Прву цифру бирамо на 9 начина (цифаре без нуле). На осталим позицијама се цифре могу бирати на 10 начина (све цифре).
Пример 4.
Колико се Морзеових знакова може формирати од елементарних знакова
. и
–,
ако се један знак састоји од највише пет елеметарних знакова.
Пример 5.
На тикету спортске прогнозе налази се 15 сусрета. За сваки сусрет се бира један од три знака 0,1 или 2.
Колико треба попунити колона да би погодак био сигуран?
Не играјте спртску прогнозу! Број варијација је огроман!
Комбинације без понављања
Нека је дат скуп
,
.
Под кобинацијом без понављања од
n елемената
k-те класе скупа А
подразумева се сваки подскуп од
k елемената скупа А.
Редослед избора елемената није битан.
Пример 1.
Колико се највише различитих троуглова/четвороуглова може формирати од скупа са десет тачака?
Прву тачку бирамо на 10 начина, другу на 9 и трећу на 8 начина.
Редослед избора тачака није битан АВС=ACB=BAC=BCA=CAB=CBA, па је највећи број троуглова који се може формирати једнак
Најећи број различитих четвороуглова који се може добити
Укупан број комбинација без понављања од
n елемената
k-те класе једанак је
Комбинација без понављања се обично обележавају са
Комбинације без понављања се могу представити помоћу варијација и пермутација без понављања
Пример 2.
Одредити вредност израза
.
Пример 3.
Да би добио позитивну оцену на писменом задатку ученик од 10 задатака треба да уради 4.
На колико начина ученик може "преписати" та 4 задатка?
Није битан редослед решавања и не може се поновити исти задатак па су у питању комбинације. Број могућности је
Пример 4.
На колико начина се у игри лото од 39 бројева може извући 7 бројева?
Не играјте лото, шансе за добитак су веома мале -
1 : 15.380.937 за једну комбинацију.
Пример 5.
Из одељења
IV-1, које има 11 ученика и 15 ученица, треба одабрати делегацију од четири ученика
тако да у тој делегацији буде бар једна ученица. На колико се начина то може урадити?
Делегација се може састојати од 4 ученице, или 3 ученице и 1 ученика, или 2 ученице и 2 ученика, или 1 ученицe и 3 ученика.
Укупан број могућих делегација је
Напомене
Пример 6.
■
Пример 7.
Кошаркашки тим сачињавају 5 бекова, три центра, четири крила и Лазар Ковачевић.
На колико се начина може саставити петорка, ако у њој морају да играју бар два бека, бар један центар и Лазар?
■
Комбинације са понављањем
Комбинације
k-те класе од
n елемената у којима се елементи могу понављати највише
k пута,
су комбинације са понављањем.
Пример формирања комбинација са понављањем од скупа {1, 2, 3, 4} треће класе.
|
1 1 1
1 1 2
1 1 3
1 1 4
1 2 3
1 2 4
|
2 2 2
2 2 1
2 2 3
2 2 4
2 3 4
|
3 3 3
3 3 1
3 3 2
3 3 4
3 1 4
|
4 4 4
4 4 1
4 4 2
4 4 3
|
Избори 112, 121 и 211 су различите варијације, али иста комбинација.
Укупан број комбинација са понављањем је
Пример 1.
У посластичарници се продају три врсте колача. На колико начина је могуће купити 6 колача?
Редослед куповине није битан. При куповини се могу куповати исти колачи (могу се понављати избори).
Пример 2.
Колико се различитих троуглова може формирати од дужи чије су дужине дате у скупу {6, 7, 8, 9, 10} ?
Избори страница троуглова су комбинације са понављањем од пет елемената треће класе.
Пример 3.
Број комбинација са понављањем друге класе од n елемената је 276. Одредити n.
■
Пример 4.
Број комбинација са понављањем треће класе од n елемената односи се према броју комбинација без понављања
треће класе од n елемената као 15:7. Одредити n.
■
Пример 5.
Укротитељ у циркуску арену уводи пет лавова и четири тигра при чему два тигра не могу ићи један за другим.
На колико начина укротитељ може увести животиње?
Могући положаји тигрова Т Л Т Л Т Л Т Л Т Л Т
■
БИНОМНИ ОБРАЗАЦ
Биномни (Њутнов) образац или формула описује коефицијенте степена бинома
у развијеном облику.
Врло често ученици и студенти степен бинома примењују погрешно у облику
или
.
Ова грешка се зове „бруцошки сан“ (
The Freshman’s dream).
Развоји бинома почев од нултог степена су
Ако се запишу само коефицијенти уз степене чланова бинома добија се шема бројева у облику троугла позната као Паскалов троугао.
или
Уочава се правило како се формирају биномни коефицијенти. У нултој колони и на главној дијагонали су јединице.
Сви остали коефицијенти се добијају као збир броја из претходне врсте и исте колоне и броја из претходне врсте и претходне колоне.
Преко ове шеме се веома брзо одређују коефицијенти у развоју бинома.
Ово правило је први документовао Паскал, али су многи и пре њега знали и користили ову особину (Омар Хајам, XI век и други).
Ако се направе збирови по дијагоналама као на слици добија се Фибоначијев низ.
Ови бројеви се појављују у многим природним процесима, нпр. у генетици код деобе ћелија...
Фибоначијев низ се формира тако што су прва два елемента једнака јединици а остали се добијају као збирови претходна два елемента:
,
,
.
Биномни образац
важи
или
Формула важи и у скупу комплексних бројева.
Општи члан у развијеном облику бинома је
Коефицијенти уз чланове бинома у развоју су бројеви
.
Ови бројеви се зову и биномни коефицијенти. Њима се одређују и комбинације без понављања,
тј. одређује се број
k-то чланих подскупова скупа са
n елемената.
Пример 1.
Доказати следеће особине биномних коефицијената
1
o 
2
o 
3
o 
Напомена
1
o Симетрија биномних коефицијената
2o Паскалова формула
3
o Збир биномних коефицијената
■
Пример 2.
Применити биномну формулу на следеће биноме
1
o 
;
2
o 
;
3
o 
.
Пример 3.
Одредити пети члан у развијеном облику бинома
.
Решење
Пример 4.
Одредити члан који не садржи
x у развијеном облику бинома
.
Решење
Пример 5.
Одредити дванаести члан у развијеном облику бинома
,
ако је биномни коефицијенат трећег члана једнак 105.
Решење
Напомена
Биномни коефицијенти у развоју бинома и коефицијенти у развоју бинома се могу разликовати.
У овом примеру је биномни коефицијенат уз 12. члан
,
а коефицијенат уз 12. члан је
.
Пример 6.
■
Пример 7.
■
Пример 8.
Одредити коефицијенат уз
у развоју израза
.
Решење
За први бином у изразу треба одредити члан са трећим степеном по
x.
За други бином у изразу треба одредити члан са четвртим степеном по
x.
За трећи бином у изразу треба одредити члан који не садржи
x.
Члан уз
у развоју израза је
Пример 9.
Колико је чланова у развоју бинома
природан број?
Решење
Општи члан у развоју је
Да би члан био цео или природан број изложиоци морају бити природни бројеви.
Бројеви
2022-k морају бити дељиви са 3, а бројеви
k морају бити дељиви са 2.
Бројеви
и
су исти, па морају бити дељиви са 6.
Таквих бројева има
.
Мора се проверити даљивост и за
k=0.
.
Природних бројева у развоју датог бинома има
337+1 = 338.
Пример 10.
Колико је чланова у развоју бинома
негативан цео број,
ако је збир свих биномних коефицијената једнак
?
Решење
Бројеви
2020-k морају бити дељиви са 3. Њих има
Мора се проверити и за
k=2020
Целих бројева у развоју датог бинома има
673+1 = 674. Од тога је
337 негативно.
Пример 11.
Дат је бином
.
а) Одредити
n тако да прва три коефицијента у развијеном облику датог бинома образују аритметички низ.
б) За нађене вредности
n одредити све рационалне чланове у развијеном облику датог бинома.
Решење
a)
Потребно је одредити коефицијенте у развоју бинома и они се разликују од биномних коефицијената.
Чланови аритметичког низа су
,
и
.
Применом особина аритметичког низа добија се решење за
n.
б)
Општи члан у развоју датог бинома је
Члан је рационалан ако су изложиоци дељиви са 4.
Рационални чланови у развоју датог бинома су
Пример 12.
Дат је бином
.
а) Одредити
n тако да биномни коефицијенти другог, трећег и четвртог члана у развијеном облику датог бинома
буду први, трећи и пети члан аритметичке прогресије.
б) Одредити
x тако да је шести члан у развијеном облику бинома једнак 21.
Решење
a)
Чланови аритметичког низа су
б)
.
и нека је
паран број.
Збир свих биномних коефицијената у развоју бинома 
је четири пута већи од збира свих биномних коефицијената у развоју бинома 
.
Одредити збир чланова ова два бинома који не садрже x.
збир прва три биномна коефицијента је 121. Одредити члан који садржи
.
