Основные виды комбинаторных соединений

Общие правила комбинаторики

ПРАВИЛО СУММЫ.

Если некоторый объект А можно выбрать m способами, а объект В – k способами, то объект «А или В» можно выбрать (m + k) способами.

Пр.1. В магазине продаются торты: 5 бисквитных и 3 песочных. Сколькими способами можно выбрать один из этих тортов (бисквитный или песочный)?

5 + 3 = 8 способов

ПРАВИЛО ПРОИЗВЕДЕНИЯ.

Если некоторый объект А можно выбрать m  способами, а после каждого такого выбора другой объект В можно выбрать k способами, то объект «А и В» можно выбрать (m * k) способами.

Пр.2. В магазине продаются торты: 5 бисквитных и 3 песочных. Сколькими способами можно выбрать два торта (бисквитный и песочный)?

5 * 3 = 15 способов

Пр.3   Пять товарищей решили обменяться фотографиями. Сколько потребуется фотографий?

Решение. Каждый из пяти товарищей должен подарить 4 фотографии. Значит, всего потребуется  фотокарточек.

 

 

ОСНОВНЫЕ ВИДЫ КОМБИНАТОРНЫХ СОЕДИНЕНИЙ

1. ПЕРЕСТАНОВКИ из n элементов:  

2. РАЗМЕЩЕНИЯ из n элементов по m:

3. СОЧЕТАНИЯ из n элементов по m:  

1. ПЕРЕСТАНОВКИ из n  элементов:

 

 ???      Сколько  различных  комбинаций  можно  получить,

 переставляя  n элементов  множества в различном  порядке?

 

!! Каждая перестановка содержит все n элементов множества.

!! Различные перестановки отличаются друг от друга только порядком следования элементов.

 

      Число всех возможных перестановок из n элементов обозначают P_n: 

 

    n                     (1)   

 

   !!     Знак n!  читается: "эн - факториал".

 

= n(n -1)(n -2)…3*2*1

 

   !!     Оказывается удобным рассматривать также 0!

       В математике полагают, что   0! = 1.

 

Пр. 1.  Сколькими способами можно расставить 5 различных книг на одной полке?

Решение.  Искомое число способов равно P₅ = 5!= 1*2*3*4*5 = 120.

 

Пр. 2. Лингвисты расшифровывают надписи на незнакомом языке. Текст содержит 26 знаков, которые соответствуют 26 различным звукам. Сколькими способами можно сопоставить звуки знакам письма? (26!)

ПР. 3. Сколькими способами могут сесть в ряд музыканты из квартета в басне И.А.Крылова (проказница Мартышка, Осел, Козел да косолапый Мишка)?......

 

ПР. 4. Вычислите , , ........

 

Пр. 5. Сколько существует различных перестановок из 52 игральных карт?

       

Ответ: 52! (52 факториал), то есть

 

80658175170943878571660636856403766975289505440883277824000000000000

 или примерно 8.0658 × 10⁶⁷.

 

2. РАЗМЕЩЕНИЯ  из  n  элементов  по  m:

Читается: « А из n по m »

 ???  Сколько  различных  комбинаций  можно  получить, выбирая

 m элементов из n без повторения (без возвращения)

и размещая их определенным образом?

 

!! Каждый отобранный элемент не может быть выбран снова.

!! Важен порядок выбора.

!! Комбинации могут отличаться не только набором, но и порядком элементов.

Пр. 6. Сколькими способами можно выбрать старосту и его заместителя в студенческой группе из 16 человек?

Решение:  старосту можно выбрать из 16 человек, т.е. … способами, а его заместителя уже из 15 оставшихся студентов, т.е. … способами, тогда количество способов выбрать данную пару с учетом порядка вычислим по правилу произведения: 16 *15,    т.е. = 16*15 = 240 (сп.)

 

Пр. 7. Сколькими способами можно составить трехцветный полосатый флаг, если имеются ткани 5 различных цветов?

  Решение:  = 5*4*3=60 (сп.).            Или  иначе: 5*(5-1)*(5-2)

 

Число всех возможных размещений из n по m вычисляется по формуле:

 = n(n -1)…(n – (m-1)) =  n(n -1)…(n - m+1)           (2)

Число  представляется как произведение последовательно уменьшающихся на единицу множителей, первый из которых равен n, а число всех сомножителей равно m.

Или иначе:                          (3)

 

 

Пр. 8. (а) В соревновании участвуют 10 команд. Сколько существует различных возможностей среди этих команд занять призовые (I, II, III) места?

     

  Решение: Выбираем претендентов на 1, 2, 3 места:

на 1-е место - 10 вариантов, при любом выборе первой команды на 2-е место претендуют 9 остающихся, и на 3-е – 8 команд, т.е. выбираются 3 команды из 10 с учётом порядка: = 10*9*8 = 720.     

                       Иначе: =  = = 10*9*8 = 720.     

Пр. 8. (б) В соревновании участвуют 5 команд. Сколько существует различных возможностей распределения мест среди этих команд:

Ø  первых трех мест?.......

Ø всех 5 мест?........