Ћекции.ќрг


ѕоиск:




 атегории:

јстрономи€
Ѕиологи€
√еографи€
ƒругие €зыки
»нтернет
»нформатика
»стори€
 ультура
Ћитература
Ћогика
ћатематика
ћедицина
ћеханика
ќхрана труда
ѕедагогика
ѕолитика
ѕраво
ѕсихологи€
–елиги€
–иторика
—оциологи€
—порт
—троительство
“ехнологи€
“ранспорт
‘изика
‘илософи€
‘инансы
’ими€
Ёкологи€
Ёкономика
Ёлектроника

 

 

 

 


 омб≥наторика




1.4.1. ѕ–ј¬»Ћќ —”ћ» ≤ ƒќЅ”“ ”

“≈ќ–≈ћј 1.2. (ѕравило суми)

якщо обТЇкт а може бути обрано р способами, а обТЇкт b Ц другими q способами, то виб≥р Уабо а або b Ф може бути виконаю p+q способами.

ѕри цьому сл≥д мати на уваз≥, що виб≥р аb Ї тут взаЇмно виключним.

≤накше кажучи, необх≥дно сл≥дкувати, щоб н≥ один з≥ способ≥в вибору обТЇкта а не сп≥впадав з €кимсь з≥ способ≥в вибору обТЇкта b. ѕри на€вност≥ таких обмеженостей правило суми не працюЇ ≥ результат дор≥внюЇ p+q-k.

“≈ќ–≈ћј 1.3. (ѕравило множенн€)

якщо обТЇкт а може бути обрано р способами ≥ п≥сл€ кожного з таких вибор≥в обТЇкт b може бути в свою чергу обрано q способами, то виб≥р У аb Ф у вказаному пор€дку можливо зд≥йснити p*q способами.

÷е правило використовуЇтьс€ в тих випадках, коли виб≥р а ≥ в незалежний.

ѕриклад 1-13. —к≥льки чотиризначних чисел можна скласти з цифр 0, 1, 2, 3, 4, 5, €кщо жодна цифра не повторюЇтьс€ б≥льше одного разу?

–озв'€занн€. ѕершою цифрою числа може бути одна з 5 цифр 1, 2, 3,4,5 (0 не може бути, бо тод≥ число не чотиризначне); €кщо перша цифра обрана, то друга може бути обрана 5 способами, трет€ Ч 4, четверта Ч 3. «г≥дно з правилом множенн€ загальне число способ≥в дор≥внюЇ .

1.4.2. ѕ≤ƒћЌќ∆»Ќ» ƒјЌќѓ ћЌќ∆»Ќ».

якщо задана де€ка множина ј, то можна розгл€дати нову множину ћ(ј) Ц множину вс≥х њњ п≥дмножин. „ерез ћk(ј) будемо позначати множину вс≥х п≥дмножин ј, €к≥ мають k елемент≥в: ¬Îћk(ј), €кщо ¬Îћ(ј) ≥ N(B) = k.

“≈ќ–≈ћј 1.3. „исло вс≥х k Ц елементних п≥дмножин множини з n елемент≥в дор≥внюЇ

(1.1)

N(Mk(A)) позначимо через .

ƒов≥льна k елементна п≥дмножина n Ц елементноњ множини називаЇтьс€ сполукою (комб≥нац≥Їю) з n елемент≥в по k. ѕор€док елемент≥в в п≥дмножин≥ не Ї ≥стотним. “аким чином, число комб≥нац≥й (сполук) ≥з n елемент≥в по k дор≥внюЇ

(1.2)

ѕриклад 1-14. —к≥лькома способами читач може в≥д≥брати 3 книжки з 5?
–озвТ€зок. Ўукане число способ≥в дор≥внюЇ числу трьохелементних
п≥дмножин множини з 5 елемент≥в: .

“≈ќ–≈ћј 1.4. ћаЇ м≥сце р≥вн≥сть:

Cnk = Ckn-1+Cn-1k-1 (1.3)

ƒоведенн€ виконуЇтьс€ за допомогою формули (1.1).

“≈ќ–≈ћј 1.5. „исло вс≥х п≥дмножин множини з n елемент≥в дор≥внюЇ 2n.

ƒоведенн€. ѕронумеруЇмо елементи множини ј ≥ дл€ кожноњ п≥дмножини ј побудуЇмо посл≥довн≥сть довжини n з нул≥в та одиниць. “аким чином:

на k-му м≥ст≥ пишемо 1, €кщо елемент з номером k входить до п≥дмножини. ќтже кожн≥й п≥дмножин≥ в≥дпов≥даЇ сво€ посл≥довн≥сть нул≥в та одиниць. Ќаприклад, порожн≥й множин≥ в≥дпов≥даЇ посл≥довн≥сть з одних нул≥в. „исло вс≥х можливих посл≥довностей довжини n, складених з нул≥в та одиниць дор≥внюЇ . ќтже число вс≥х п≥дмножин множини ј дор≥внюЇ 2n.

Ќј—Ћ≤ƒќ  “≈ќ–≈ћ». ћаЇ м≥сце р≥вн≥сть .

ќск≥льки —nk Ц число k елементних п≥дмножин множини з n елемент≥в, то сума в л≥в≥й частин≥ Ї число вс≥х п≥дмножин.

1.4.3. ¬ѕќ–яƒ ќ¬јЌ≤ ћЌќ∆»Ќ». ѕ≈–≈—“јЌќ¬ »
≤ –ќ«ћ≤ў≈ЌЌя

ћножина називаЇтьс€ впор€дкованою, €кщо кожному елементу ц≥Їњ множини поставлено у в≥дпов≥дн≥сть певне число (номер елемента) в≥д 1 до n, де n Ч число елемент≥в множини, так що р≥зним елементам в≥дпов≥дають р≥зн≥ числа.  ожну ск≥нчену множину можна перетворити у впор€дковану, €кщо, наприклад, переписати вс≥ елементи множини у де€кий список а пот≥м поставити у в≥дпов≥дн≥сть кожному елементу номер м≥сц€, на €кому в≥н стоњть у списку Ѕудемо позначати впор€дковану множину, €ка утворена з множини ј через . ќчевидно, що кожну множину, €ка м≥стить б≥льше одного елемента, можна впор€дкувати не одним способом.

¬пор€дкован≥ множини вважаютьс€ р≥зними, €кщо вони в≥др≥зн€ютьс€ або своњми елементами, або њх пор€дком. –≥зн≥ впор€дкован≥ множини, €к≥ в≥др≥зн€ютьс€ лише пор€дком елемент≥в (тобто можуть бути утворен≥ з т≥Їњ самоњ множини), називаютьс€ перестановками ц≥Їњ множини.

ѕриклад 1-15. ѕерестановки множини ј = (а, b, с) з трьох елемент≥в мають вигл€д:

(а, b, с), (а, с, b), (b, а, с),

(b, с, а), (с, а, b), (с, b, а).

«найдемо к≥льк≥сть р≥зних способ≥в, €кими може бути впор€дкована дана множина, тобто к≥льк≥сть перестановок множини ј. Ќехай множина ј маЇ n елемент≥в.

“≈ќ–≈ћј 1.6.  ≥льк≥сть перестановок множини з n елемент≥в позначаЇтьс€ через ≥ дор≥внюЇ

ƒоведенн€. Ѕудемо посл≥довно вибирати елементи множини ј ≥ розташовувати њх у певному пор€дку на n м≥сц€х Ќа перше м≥сце можна поставити будь-€кий з n елемент≥в ѕ≥сл€ того, €к заповнено перше м≥сце, на друге м≥сце можна поставити будь-€кий з тих елемент≥в, €к≥
залишились, ≥ т д. «а правилом множенн€ вс≥ n м≥сць можна заповнити

способами. ќтже, множину ј з елемент≥в можна впор€дкувати способами.
ѕриклад 1-16. —к≥лькома способами можна розташувати на полиц≥ 4 книги (позначимо њх ј, ¬, —, D)?

Ўукане число способ≥в дор≥внюЇ числу способ≥в упор€дкуванн€ множини, що складаЇтьс€ з 4 елемент≥в, тобто .

–озгл€немо тепер впор€дкован≥ п≥дмножини даноњ множини ј. —аму множину ј вважаЇмо невпор€дкованою, тому кожна њњ п≥дмножина може бути впор€дкована будь-€ким можливим способом. „исло вс≥х п≥дмножин множини ј з k елементами дор≥внюЇ .  ожну таку п≥дмножину можна впор€дкувати способами. “ак знайдемо вс≥ впор€дкован≥ n-елементн≥ п≥дмножини множини. ќтже, њх число буде .

“≈ќ–≈ћј 1.7. „исло впор€дкованих k елементних п≥дмножин множини, що складаЇтьс€ з n елемент≥в, дор≥внюЇ

(1.4)

”пор€дкован≥ k-елементн≥ п≥дмножини множини з n елемент≥в називають розм≥щенн€ми з n по k. –≥зн≥ розм≥щенн€ з n по k в≥др≥зн€ютьс€ складом елемент≥в, або њх пор€дком.

ќтже, число р≥зних розм≥щень з n по k дор≥внюЇ

(1.5)

ѕриклад 1-16. —к≥лькома способами можна розсадити 4 учн≥в на 25 м≥сц€х?
Ўукане число дор≥внюЇ числу розм≥щень з 25 по 4





ѕоделитьс€ с друзь€ми:


ƒата добавлени€: 2015-02-12; ћы поможем в написании ваших работ!; просмотров: 708 | Ќарушение авторских прав


ѕоиск на сайте:

Ћучшие изречени€:

≈сть только один способ избежать критики: ничего не делайте, ничего не говорите и будьте никем. © јристотель
==> читать все изречени€...

2010 - | 1980 -


© 2015-2024 lektsii.org -  онтакты - ѕоследнее добавление

√ен: 0.011 с.