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

1. Комбинаторика

Задачи

2. Введение

Комбинаторика
–
раздел
математики, в котором изучаются
вопросы о том, сколько различных
комбинаций, подчиненных тем или
иным условиям, можно составить из
заданных объектов.
Слово
«комбинаторика»
от
латинского слова «combinare», что в
переводе на русский означает –
«сочетать», «соединять».
Термин "комбинаторика" был
введён
знаменитым
Готфридом
Вильгельмом Лейбницем, - всемирно
известным немецким учёным.

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

Если некоторый объект A можно выбрать m
способами, а другой объект В можно выбрать n
способами, то выбор «либо А, либо В» можно
осуществить (m+n) способами.
• При использовании правила суммы надо следить,
чтобы ни один из способов выбора объекта А не
совпадал с каким-либо способом выбора объекта В.
• Если такие совпадения есть, правило суммы
утрачивает силу, и мы получаем лишь (m + n - k)
способов выбора, где k—число совпадений.

4. Образец решения

В коробке находится 10 шаров: 3 белых,
2 черных, 1 синий и 4 красных.
Сколькими способами можно взять из
ящика цветной шар?
Решение:
Цветной шар – это синий или красный,
поэтому применим правило суммы:

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

Если объект А можно выбрать m
способами и если после каждого такого
выбора объект В можно выбрать n
способами, то выбор пары (А,В) в указанном
порядке можно осуществить mn способами.
• При этом число способов выбора второго
элемента не зависит от того, как именно
выбран первый элемент.
• Правила суммы и произведения верны для
любого количества объектов.

6. Образец решения

Сколько может быть различных комбинаций выпавших
граней при бросании двух игральных костей?
Решение:
На первой кости может быть: 1,2,3,4,5 и 6 очков, т.е. 6
вариантов.
На второй – 6 вариантов.
Всего: 6*6=36 вариантов.

7. Выберите правило

№1. Из города А а город В ведут 5 дорог, а из города В в
город С – 3 дороги. Сколькими способами можно
проехать из города А в город С?
№2. На книжной полке стоят 3 книги по алгебре, 4 по
геометрии и 5 по литературе. Сколькими способами
можно взять с полки одну книгу по математике?
№3. В меню имеется 4 первых блюда, 3 – вторых, 2 –
десерта. Сколько различных обедов можно из них
составить?

8. Факториал

Читаем:
n!
n (эн) - факториал
Произведение всех последовательных
натуральных чисел от 1 до n обозначается n!
n! = 1 · 2 · 3 · ... · n.
5! = 1*2*3*4*5 = 120
7! = 1*2*3*4*5*6*7 =5040
2! = 1*2= 2
(англ.) factorial –
делающий
(англ.) factor –
множитель

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

Перестановками из n элементов
называются размещения из n
элементов по n.
Р=п!
1. В упорядоченную выборку входят все n
элементов;
2. Отличаться выборки могут только порядком;
3. Все перестановки имеют один и тот же состав
и отличаются только порядком элементов.

10. Образец решения

Сколькими способами можно развесить 5
цветных шаров на гирлянде?
Решение:
Каждая расстановка будет отличаться
от предыдущей порядком следования
шаров (элементов). Поэтому это будет
перестановка из 5 элементов.
Р5 = 5! = 1·2·3·4·5= 120

11. Образец решения

«Проказница-Мартышка,
Осел, Козел
Сколькими различными
Да косолапый Мишка
способами
могутКвартет.
сесть
Затеяли сыграть
музыканты?
Достали нот,
баса, альта, две скрипки
И сели
на лужок
под липки,Любой
из четырех
зверей
Пленять своим искусством свет.
Ударили в смычки, дерут, а толку нет.
Любой из трех других зверей
"Стой, братцы, стой! - кричит Мартышка. Погодите!
- из вы
двух
оставшихся
Как музыкеЛюбой
идти? Ведь
не так
сидите.
*** *** *** *** ***
Единственный
Послушались
Осла: уселись оставшийся
чинно в ряд;
А все-таки Квартет зверь
нейдет на лад.
Вот пуще прежнего пошли у них разборы
Р4 = 4! = 4 *И3споры,
* 2 * 1 = 24
Кому и как сидеть…»
И.А. Крылов «Квартет»

12. Размещения

Размещениями из n элементов по m (m≤n)
называются упорядоченные m -элементные выборки
из данных n элементов.
Читаем:
Число размещений из n по m.
Это - формула для вычисления числа размещений.
Здесь n – число объектов «из которых выбирали», а
m – число объектов «по сколько составляли».
Запишите и вычислите:
1. Число размещений из 7 по 3
2. Число размещений из 5 по 2
3. Число размещений из 8 по 4

13. Решите задачи:

1.
Сколько слов можно образовать из букв слова
фрагмент, если слова должны состоять: из 8
букв; из 7 букв; из 3 букв?
2. Студенту необходимо сдать 4 экзамена в
течение десяти дней. Сколькими способами
можно составить ему расписание экзаменов?
3. Доказать, что число трехбуквенных слов,
которые можно образовать из букв,
составляющих слово «гипотенуза», равно числу
всех возможных перестановок букв,
составляющих слово «призма».

14. Сочетания

Сочетаниями из n элементов по m (m≤n) называются
неупорядоченные m-элементные выборки из данных
n элементов.
1. Все сочетания отличаются друг от друга хотя бы
одним элементом;
2. Порядок элементов здесь не существенен
Читаем:
Число сочетаний элементов из n по m.
Найдите:
Число сочетаний из 6 по 3:
Число сочетаний из 4 по 4:

15. Образец решения

Из 20 учащихся надо выбрать двух дежурных.
Сколькими способами это можно сделать?
Решение:
Надо выбрать двух человек из 20.
Ясно, что от порядка выбора ничего не зависит, то есть
Иванов
- Петров
или Петров
- Иванов
- это одна
и та же пара дежурных. Следовательно, это будут сочетания
из 20 по 2.

16. Решите задачи:

1. Сколькими способами из восьми человек можно
избрать комиссию, состоящую из пяти членов?
2. Подрядчику нужны 4 плотника, а к нему с
предложением своих услуг обратились 10.
Сколькими способами он может выбрать среди
них четверых?
3. Сколькими способами можно отобрать несколько
фруктов из семи яблок, четырех лимонов и
девяти апельсинов? (Фрукты одного вида
считаем неразличимыми.)