Раздаточный материал по тем: "Комбинаторика"

ОСНОВНЫЕ ПОНЯТИЯ КОМБИНАТОРИКИ

1. Понятие факториала

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

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

4. Сочетания

В разделе математики, который называется комбинаторикой, решаются некоторые задачи, связанные с рассмотрением множеств и составлением различных комбинаций из элементов этих множеств. Например, если взять 10 различных цифр 0, 1, 2, 3, …, 9 и составлять из них комбинации, то будем получать различные числа, например, 345, 534, 1036, 5671, 45 и т.п.

Мы видим, что некоторые из таких комбинаций отличаются только порядком цифр (например, 345 и 534), другие – входящими в них цифрами (например, 1036 и 5671), третьи – количеством цифр (например, 345 и 45).

Таким образом, полученные комбинации удовлетворяют различным условиям. В зависимости от правил составления можно выделить три типа комбинаций: перестановки, размещения, сочетания. Рассмотрим их отдельно. Однако предварительно познакомимся с понятием факториала.

1. ПОНЯТИЕ ФАКТОРИАЛА

Произведение всех натуральных чисел от 1 до n включительно называют n-факториалом и пишут

1. Вычислите: а) 3!; б) 7!-5!; в)

Решение.

а) 3!=1·2·3=6.

б) Так как 7!=1·2·3·4·5·6·7 и 5!=1·2·3·4·5, то можно вынести за скобки 5!. Тогда получим

5!(6·7-1)=5! ·41=1·2·3·4·5·41=120·41=4920.

в)

1. Упростите:

а) б) в)

Решение

а) Учитывая, что (n+1)!=1·2·3·…·n(n+1), a n!=1·2·3·…·n, сократим дробь:

б) Так как (n+1)!=1·2·3·…·(n-1)n(n+1), то после сокращения получим

в) Имеем (n+1)!=1·2·3·…·n(n+1), n!= 1·2·3·…·n. Приведем дробь к общему знаменателю, тогда получим

3-5. Вычислите:

3. 4. 5.

6-11. Упростите выражение:

6. 7. 8. 9.

10. 11.

1. ПЕРЕСТАНОВКИ

Пусть даны три буквы А, В и С. Составим все возможные комбинации из этих букв: АВС, АСВ, ВСА, САВ, СВА, Вас. Мы видим, что они отличаются друг от друга только порядком расположения букв и таких комбинаций 6.

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

Перестановки обозначаются символом Р_n, где n – число элементов, входящих в каждую перестановку.

Число перестановок можно вычислить по формуле

(1)

которую можно записать так:

(2)

Число перестановок из трех элементов по формуле (2) равно Р₃=3!=6, что совпадает с рассмотренным примером.

Действительно, на первое место в комбинации (перестановке) можно уже можно поставить только одну из двух букв (одна заняла первое место), а на третьем окажется только одна из оставшихся. Значит,

3·2·1=6=Р₃.

12. Сколько различных пятизначных чисел можно составить из цифр 1, 2, 3, 4 и 5 при условии, что ни одна цифра в числе не повторяется?

13. В соревнованиях участвовали четыре команды. Сколько вариантов распределения мест между ними возможно?

14-16. Вычислите:

14. 15. 16.

1. РАЗМЕЩЕНИЯ

Пусть имеются четыре буквы А, В, С и D. Составив все комбинации только из двух букв, получим:

АВ, АС, АD;

BA, BC, BD;

CA, CB, CD;

DA, DB, DC.

Мы видим, что все полученные комбинации отличаются или буквами, или их порядком (комбинации ВА и АВ различны).

Комбинации из m элементов по n элементов, которые отличаются друг от друга или самими элементами или порядком элементов, называются размещениями.

Размещения обозначаются символом , где m – число всех имеющихся элементов, n – число элементов в каждой комбинации. При этом полагают n≤m. Число размещений можно вычислить по формуле

, (3)

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

Так, что совпадает с результатом приведенного примера: поскольку число строк соответствует числу всех имеющихся букв, то есть m=4, а число столбцов равно 3, всего имеется 12 различных комбинаций.

17. Вычислите: а) б)

Решение.

а)

б) Так как

то

18. Сколько двухзначных чисел можно составить из пяти цифр 1, 2, 3, 4 и 5 при условии, что ни одна из них не повторяется?

Решение. Так как двухзначные числа отличаются друг от друга или самими цифрами, или их порядковым, то искомое количество равно числу размещений из пяти элементов по два: Итак, можно составить 20 различных двузначных чисел.

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

Поэтому формулу числа размещений можно записать в виде

Отсюда, учитывая, что числитель равен m!, а знаменатель равен (m-n)!, запишем эту формулу в другой форме:

(4)

19. Вычислите по формуле 4.

Решение.

20-25. Вычислите:

20. 21. 22.

23. 24. 25.

26. Сколько существует вариантов распределения трех призовых мест, если в соревновании участвуют 7 команд?

27. Сколько различных четырехзначных чисел можно составить из цифр 0, 1, 2, ..., 8 и 9?

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

29. Сколько вариантов распределения трех путевок в санатории различного профиля можно составить для пяти претендентов?

4. СОЧЕТАНИЯ

Сочетаниями называются все возможные комбинации из m элементов по n, которые отличаются друг от друга по крайней мере хотя бы одним элементов (здесь m и n – натуральные числа, причем n≤m).

Так, из четырех различных букв А, В, С и D можно составить следующие комбинации, отличающиеся друг от друга хотя бы одним элементом: АВ, АС, АD, ВС, ВD, CD. Значит, число сочетаний из четырех элементов по два равно 6. Это кратко записывают так:

В каждой комбинации сделаем перестановки элементов:

АВ, АС, AD, BC, BD, CD;

BA, CA, DA, CB, DB, DC.

В результате мы получили размещения из четырех элементов по два. Следовательно, откуда

В общем случае число из m элементов по n равно числу размещений из m элементов по n, деленному на число перестановок из n элементов:

(5)

Используя формулы и получим формулу числа размещений в виде

(6)

30. Вычислить: а) б)

Решение. а) Применяя формулу (6) при m=8, n=3, находим

б)

Отметим основное свойство сочетаний:

(7)

Действительно,

Мы видим, что правые части этих равенств равны; следовательно, равны и левые части.

Это свойство числа сочетаний позволяет упростить нахождение числа сочетаний из m элементов по n, когда n превосходит

31. Сколькими способами можно выбрать трех дежурных, если в классе 30 учащихся?

32. Сколькими способами можно выбрать двух человек в президиум, если на собрании присутствует 78 человек?

33. Найти х, если известно, что

34. Найти х, если

35. Сколькими способами можно заполнить лотерейный билет «5 из 36»?

36. Сколькими способами можно составить дозор из трех солдат и одного офицера, если имеется 80 солдат и 3 офицера?

МАОУ «СОШ № 57 г. Улан-Удэ имени А. Цыденжапова» Страница 7