Кобинаторика Flashcards
(21 cards)
Правило на производ:
Ако една работа се извршува во два чекори (со две подзадачи), такви што првиот
чекор може да се изврши на n-начини, и без разлика кој начин бил избран во првиот чекор имаме m- начини за да се изврши вториот чекор, тогаш постојат mхn-начини за завршување на целата
работата.
Обопштено правило на производ:
Ако некоја работа се извршува во k чекори, од кои i-тиот чекор може да се изврши на ni-начини, независно од останатите чекори,
тогаш постојат n1 х n2 х … х nk начини за завршување на работата.
Ако А и В се конечни множества. Тогаш бројот на
елементите во нивниот Декартов производ е
|AхB|=|A|·|B|
Нека имаме k конечни множества. Тогаш бројот на
елементите во нивниот Декартов производ е
|A1 х A2 х … х Ak| = |A1 | х |A2| х… х |Ak|
Правило на собирање:
Нека претпоставиме дека има2различни пристапи за завршување на една работа. Акопостојат m-начини за да се заврши работата со користењена првиот пристап и n-нaчини да се заврши со вториотпристап, тогаш постојат вкупно m+n начинизазавршување на работата.
Обопштено правило на збир:
Нека претпоставиме деказа завршување на една работа имаме k различнипристапи. Нека постојат ni
-начини за да се завршиработата со користење на i-тиот пристап. Тогаш постојатn1 + n2 + … + nk
начини за завршување на работата.
Нека А и В се конечни дисјунктни множества. Тогашбројот на елементите во нивната унија е
|A u B|=|A|+|B|.
Нека имаме k конечни дисјунктни множества, Ai пресек Aj=празно множество за i не е j Тогаш бројот на елементите во нивната унија е
|A1 u A2 u … u Ak| = |A1|+ |A2|+ … +|Ak|
Решение или излез од двосмисленоста може да се најде ако тојшто го задава проблемот, истиот ___________________, или тој што го решава, при решавањето на проблемот, покрај неговото решение да додаде _____________________________
добро го дефинира, „под претпоставка дека …..“ и ја наведепретпоставката за која не е сигурен дали важи.
Пермутација на множество S од различни елементи е
подредено разместување на елементите од S, при што секој елемент се јавува само еднаш.
Нека S = {1, 2, 3}. пермутации на S се:
- 1 2 3,
- 2 1 3,
- 3 1 2.
Теорема: Бројот на пермутации од множество од n
елементи e
производ на првите n природни броеви:
n · (n -1) · … · 1 = n!
Што е r пермутација од множество со n елементи / или
r-пермутација од класа n.
Подредено разместување на r различни
елементи од множеството S
Подредено разместување на r различни
елементи од множеството S е вика
Што е r пермутација од множество со n елементи / или
r-пермутација од класа n.
Теорема: Бројот на r-пермутации на
множеството S со n=|S| елементи е
P(n,r) = n(n−1)…(n−r+1) = n!/(n−r)!
r-пермутација со повторување на
множество S со n елементи е
подредено
разместување со должина r на елементите од S, при што некои од елементите можат да се јавуваат и
повеќе пати.
подредено
разместување со должина r на елементите од S, при што некои од елементите можат да се јавуваат и повеќе пати е
r-пермутација со повторување на
множество S со n елементи
Теорема: Бројот на r-пермутации на множество со nелементи во кое е дозволено повторување на
елементите е
n на степен r
Теорема: _________________________________________________________________________________ е n на степен r
Бројот на r-пермутации на множество со nелементи во кое е дозволено повторување на
елементите е
Теорема: Бројот на r-пермутации на множество со nелементи во кое е дозволено повторување на
елементите е n на степен r
. Доказ:
За секоја од r-те позиции постојат по n
начини да се избере елемент од множеството.
Колку стрингови со должина n може да се
формираат од Македонската азбука?
Решение: 31n
