СЕМИНАРСКИ РАД
ИЗ МАТЕМАТИКЕ
Тема: ЕЛЕМЕНТИ КОМБИНАТОРИКЕ
www.BesplatniSeminarskiRadovi.com
ВАРИАЦИЈЕ, ПЕРМУТАЦИЈЕ
И КОМБИНАЦИЈЕ
При решавању комбинаторних задатака пребројавање готово увек се срећу
основне комбинаторне конфигурације
варијације, пермутације и комбинације.
Оне се формирају на одређени начин од елемената неког скупа (на пример,
ређањем елеманата тог скупа у низ, формирањем новог скупа од елемената датог
скупа, . . . )
1. Вариација
Дефинацијa:
K-варијација
елемената
n –
скупа
А
је
к-
торка елеманата скупа
А,
тј. елемант скупа А
к
.
Пример 1.1. Нека је А = {a, b}. Запишимо ове три вариације елемената
a
и
b.
Добијамо
aaa, aab, aba, baa, abb, bab, bba, bbb
а
b, ac, ad, ba, bc, bd, ca, cb, cd, da, db, dc.
2
Теорема:
Нека је К ≤
n. К-вариација без понављања елемената n-скипа А
једнак је n(n - 1). . . (n – k + 1).
Доказ:
У К – торки
(a
1,
a
2
, . . . ,a
n
)
различитих елемената n-скупа
А
, први члан
а
1
може бити било који елемент n-скупа
А
, други члан
а
2
може бити било који
елемент
(n – 1)
-скупа
А / {a
1
}, . . . k
– ти члан
а
к
може бити било који елемент (n
– k + 1)-скупа
A
{
a
1
, a
2
, . . . . , a
k
– 1
}. Према томе, број
К –
торки различитих
елемената n-скупа
А
једнак је
n(n-1). . . (n-k+1).
*Пример 2:
Колико има петоцифрених бројева у чијем запису нема
понављања цифара и нема цифре нула?
Тражени број једнак је 9 8 7 6 5 = 15 120
∙ ∙ ∙ ∙
3. Пермутација
Дефиниција:
Пемутација n-
скупа
А
је
n-
вариација без понављања елемената
скупа
А
.
Јасно је да је пермутација скупа
А
одређена бијекцијом скупа
А
на себе.
*Пример 1:
Нека је
А
= {
a, b, c, d
}. Запишимо све пермутације скупа
А
:
abcd, abdc, acbd, acdb, adbc, adcb
bacd, badc, bcad, bcda, bdac, bdca
cabd, cadb, cbad, cbda, cdab, cdba
dabc, dacb, dbac, dbca, dcab, dcba
Број пермутација 4-скупа
А
једнак је 24.
3
Теорема:
Број пермутација n-скупа А једнак је n!
*Пример 2:
Одговоримо на следећа два питања:
(а) На колико начина можемо поређати у низ елементе 1, 2, 3, 4 и 5?
(б) На колико начина можемо поређати у низ елементе 1, 2, 3, 4 и 5, тако да на
прва два места стоје парни бројеви?
КОРИСТЕЋИ ТЕОРЕМУ, ДОБИЈАМО:
(а) 5 датих елемената можемо поређати у низ на 5! = 120 начина.
(б) Бројеве 2 и 4 можемо распоредити на прва два места на 2! начина, а
бројеве 1, 3 и 5 можемо распоредити на остала три места на 3! начина, па је
укупан број распореда једнак 2! 3! = 12.
*Пример 3:
На колико начина 8 ученика могу поделити 8 различитих књига,
тако да сваки ученик добије једну књигу?
Тражени број једнак је 8! = 8 7 6 5 4 3 2 1 = 40 320
∙ ∙ ∙ ∙ ∙ ∙ ∙
4. Комбинација
Дефиниција: Нека је
k ≤ n. k-комбинација
елемената
n-
скупа
А
је k-подскуп
А.
*
Пример 1:
Нека је
А = {a, b, c, d}.
3-комбинације елемената скупа
А
су
следећи подскупови скупа
А: {a, b, c}, {a, b, d}, {a, c, d}, {b, c, d}
Теорема:
Број k-комбинација елемената n-скупа А једнак је
