пользователей: 30398
предметов: 12406
вопросов: 234839
Конспект-online
РЕГИСТРАЦИЯ ЭКСКУРСИЯ

I семестр:
» Дискретка

0сновний принцип комбінаторики. Приклади.

У будь-якій комбінаторній задачі в тій чи іншій мірі фігурує так зване правило множення.

Приклад

З міста А до міста В веде п різних доріг, з міста В до міста С веде т різних шляхів. Скількома способами можна здійснити подорож з міста А в місто С?

Відповідь очевидна: n • m, бо обравши один з n можливих шляхів з міста А в місто B, ми матимемо т різних продовжень подорожі з В в С.

Міркування, які були проведені при розв’язанні задачі, доводять справедливість такого простого правила, яке називають правилом множення або основним принципом комбінаторики.

Якщо деякий вибір А можна здійснити N способами, а для кож­ного з цих способів другий вибір В можна здійснити т способами, то вибір А і В (у вказаному порядку) можна здійснити n - т спо­собами

Задача 1. На вершину гори веде 8 доріг.

а)  Скількома способами турист може піднятися на гору і спусти­тися вниз?

б) Скількома способами турист може піднятися на гору і спусти­тися вниз, якщо підйом і спуск здійснюються різними шляхами?

а)  Відповідь: 8 х 8 = 64. б)Відповідь: 8 х 7 = 56.

Сформулюємо тепер правило множення в загальному вигляді. Не­хай треба виконати одна за одною "к" дій. Якщо першу дію можна здійснити п способами, другу дію (після того, як здійснена перша)

— n2 способами, третю дію (після того, як здійснені попередні дві) — n3 способами, і так до k-тої дії, яку можна здійснити nk, способами, то загальне число способів здійснення дій дорівнює

n1 x n2 x...x nk

 


хиты: 826
рейтинг:+1
Точные науки
математика
для добавления комментариев необходимо авторизироваться.
  Copyright © 2013-2024. All Rights Reserved. помощь