Основные комбинаторные конфигурации.

Основные комбинаторные конфигурации.

1. Выборки (сочетания);

2. Перестановки;

3. Подстановки;

4. Размещения;

5. Разбиения;

6. Перестановки с повторением;

7. Выборки с повторением.

 

Выборки (сочетания).

Классической задачей КА является задача о числе выборок (сочетаний), содержание которой можно выразить следующим образом: сколькими способами можно выбрать m из n различных предметов?

Пример 1.  Сколькими способами можно выбрать 2 монеты из трех монет в 1, 2 и 3 копейки?                                                                 

Решение: {1,2}; {1,3}; {2,3}.                      

Число всех возможных выборок из n предметов по m в каждой выборке обозначается

Оно выражается формулой:

Правило симметрии по выборкам:

Доказательство:

Правило Паскаля:

Доказательство:

что и требовалось доказать.

Пример 2. Есть шахматная доска 3 x 3

Сколькими способами можно выбрать пару клеток: белую и черную?

I вариант: 4 способа для белой пары * 5 способов для чёрной пары = 20 способов.

II вариант: Всего квадратов – 9. Тогда:

   способов выбрать пару клеток.

       способов выбрать 2 белых.

   способов выбрать 2 черных.

Тогда решение:                          

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

Решение: Выбираем 3 семьи:     способа.

Из каждой семьи берем по 1 человеку:     способа на семью.

Всего способов: 4*2*2*2=32.