Цель занятия: уметь применять основные формулы комбинаторики и знать условия применения этих формул; знать свойства биномиальных коэффициентов и уметь определять разложение бинома при конкретных значениях n.

План занятия:

1. Число размещений.

2. Число перестановок.

3. Число сочетаний.

4. Повторения.

5. Бином Ньютона. Треугольник Паскаля.

Методические указания по изучению темы

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

Комбинаторика – область математики, в которой изучаются вопросы о том, сколько различных комбинаций, подчиненных тем или иным условиям, можно составить из элементов, принадлежащих данному множеству. Термин «комбинаторика» происходит от латинского слова combina – сочетать, соединять.

Пусть есть некоторое множество из n элементов: x 1, x 2, x 3, …, x n .

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

Размещения

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

Число размещений из n элементов по m элементов обозначают (А – первая буква французского слова arrangement, что означает размещение, приведение в порядок) и вычисляют по формуле:

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

Произведение n натуральных чисел от 1 до n обозначается символом n ! (n факториал), то есть

Например, 2!=

5!=

Заметим, что удобно рассчитывать 0!, полагая по определению, 0!=1.

Примеры:

Из последних двух формул следует, что

Пример.

В однокруговом турнире по футболу участвуют 8 команд. Сколько существует вариантов призовой тройки?

Решение : Так как порядок команд в призовой тройке важен, то мы имеем дело с размещениями. Тогда

(вариантов).

Пример.

Сколькими способами можно выбрать три лица на три различные должности из десяти кандидатов?

Решение:

(способов).

Пример.

Сколько можно составить телефонных номеров из 5 цифр так, чтобы в каждом отдельно взятом номере все цифры были различными?

(телефонных номеров).

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

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

Число всех возможных перестановок из n элементов обозначают P n (P – первая буква французского слова permutation, что означает перестановка) и вычисляют по формуле:

Пример.

В финальном забеге на 100 метров участвуют 8 спортсменов. Сколько существует вариантов протокола забега?

Решение:

В данном случае речь идёт обо всех перестановках из 8 элементов. Тогда (вариантов)

Пример.

Сколькими различными способами могут разместиться на скамейке10 человек?

Решение:

(способов)

Пример.

Сколькими способами можно разместить 7 лиц за столом, на котором поставлено 7 столовых приборов?

Решение:

(способов).

Сочетания

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

Число сочетаний вычисляют по формуле: (С - первая буква французского слова combinasion).

Пример.

Сколькими способами можно выбрать три лица на три одинаковые должности из десяти кандидатов?

Решение :

(способов).

Пример.

Сколькими способами можно выбрать три детали из ящика, содержащего 15 деталей?

Решение:

(способов).

Другой вид формул числа размещений и числа сочетаний

; , то есть .

Свойства числа сочетаний:

5)

При решении задач комбинаторики используют следующие правила:

Правило суммы. Если некоторый объект А может быть выбран из совокупности объектов n способами, а другой объект В – k способами, то объект «либо А, либо В» можно выбрать n+k способами.

Правило произведения. Если некоторый объект А может быть выбран из совокупности объектов n способами и после каждого такого выбора другой объект В – k способами, то пара объектов (А, В) в указанном порядке может быть выбрана n×k способами.

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

Размещения с повторениями

Число размещений по m элементов с повторениями из n различных элементов равно n m ,то есть

Пример.

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

Перестановки с повторениями

Если среди n элементов есть n 1 элементов одного вида, n 2 элементов другого вида и т.д., то число перестановок с повторениями

где

Пример.

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

Решение:

Сочетания с повторениями

Число сочетаний с повторениями из n различных элементов по m элементов равно числу сочетаний без повторений из (n +m -1) различных элементов по m элементов:

Пример.

Найти число сочетаний с повторениями из четырех элементов a , b , c , d по 3 элемента.

Решение:

Искомое число будет

Бином Ньютона

Для произвольного положительного целого числа n справедлива следующая формула:

Это бином Ньютона. Коэффициенты называются биномиальными коэффициентами.

При n = 2 получим формулу ;

При n = 3 получим формулу .

Пример. Определить разложение при n=4.

Решение:

Биномиальные коэффициенты обладают рядом свойств:

2. ;

Рассмотрим следующий треугольник:

………………………….

Строка под номером n содержит биномиальные коэффициенты разложения . Воспользовавшись свойством , можно заметить, что каждый внутренний элемент треугольника равен сумме двух элементов, расположенных над ним, а боковые элементы треугольника – единицы:

……………………….

Это треугольник Паскаля. Он позволяет быстро найти значения биномиальных коэффициентов.

В русскоязычной литературе перестановки, составленные из n различных элементов выбором по m элементов, которые отличаются либо составом элементов, либо их порядком, обычно называют размещениями, а под перестановками понимают всю совокупность комбинаций, состоящих из одних и тех же n различных элементов и отличающихся только порядком их расположения. В этом смысле число всех возможных перестановок для множества из n различных элементов считается по формуле факториала Pn = n! или в Excel «=ФАКТР(N)» (см. рис. № 1)

Например, если ввести «=ПЕРЕСТ(3;2)», получим 6. Это 6 комбинации: (1,2), (2,1), (1,3), (3,1), (2,3), (3,2).

А вот встроенная функция «=ЧИСЛКОМБ(N;K)» выдает комбинаторную формулу, называемую у нас «Число сочетаний». В русскоязычной литературе так именуют перестановки, составленные из n различных элементов выбором по m элементов, которые отличаются только составом элементов, а порядок их выбора безразличен (см. рис, №4)

При использовании встроенных функций пользуйтесь «Справкой по этой функции». Например:

Задачи для самостоятельного решения

1. Вычислить:

2. Вычислить:

3. Вычислить:

4. Найти n , если 5С n 3 =

5. Найти n , если

6. Найти n , если

7. Найти n , если

8. Найти n , если , k n

9. Решить уравнение

10. Решить систему

11. Сколько можно составить сигналов из 6 флажков различного цвета, взятых по 2?

12. Сколькими способами можно выбрать четыре лица на четыре различные должности из девяти кандидатов?

13. Сколько можно составить телефонных номеров из 6 цифр так, чтобы в каждом отдельно взятом номере все цифры были различны?

14. В классе 10 учебных предметов и 5 разных уроков в день. Сколькими способами могут быть распределены уроки в один день?

15. Сколько можно записать четырёхзначных чисел, используя без повторения все 10 цифр?

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

17. В восьмом классе изучается 15 предметов. Сколькими способами можно составить расписание на среду, если известно, что в этот день должно быть 6 уроков?

18. В высшей лиге чемпионата страны по футболу 16 команд. Борьба идет за золотые, серебряные и бронзовые медали. Сколькими способами медали могут быть распределены между командами?

19. Сколькими способами можно разместить 9 лиц за столом, на котором поставлено 9 приборов?

20. На собрании выступят 6 ораторов. Сколькими способами их фамилии можно расположить в списке?

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

22. Сколькими различными способами можно расставить 10 различных книг на полке, чтобы определённые 4 книги стояли рядом?

23. В однокруговом турнире по футболу участвуют 8 команд. Сколько всего матчей будет сыграно?

24. Из 25 студентов нужно выбрать трех делегатов на конференцию. Сколькими способами это можно сделать?

25. Сколькими способами можно выбрать две детали из ящика, содержащего 10 деталей?

26. В колоде 36 карт, из них 4 туза. Сколькими способами можно извлечь 6 карт так, чтобы среди них было 2 туза?

27. Комплексная бригада состоит из двух маляров, трёх штукатуров и одного столяра. Сколько различных бригад можно создать из рабочего коллектива, в котором 15 маляров, 10 штукатуров и 5 столяров?

28. В отборочном турнире за 3 путёвки на чемпионат мира участвуют 10 команд. Сколько существует вариантов «счастливой тройки»?

29. Из 12 человек выбирают четверых для назначения на 4 одинаковые должности. Сколькими способами можно сделать такой выбор?

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

31. На плоскости дано n точек, из которых никакие три не лежат на одной прямой. Найти число прямых, которые можно получить, соединяя точки попарно.

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

33. Сколько существует различных семизначных телефонных номеров?

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

35. При игре в бридж между четырьмя игроками распределяется колода карт в 52 листа по 13 карт каждому игроку. Сколько существует различных способов раздать карты?

36. В почтовом отделении продаются открытки пяти видов. Определить число способов покупки семи открыток.

37. Два коллекционера обмениваются марками. Найти число способов обмена, если первый коллекционер обменивает 3 марки, а второй – 6 марок. (Обмен происходит по одной марке).

38. У одного студента 6 книг по математике, а у другого – 5. Сколькими способами они могут обменять 2 книги одного на 2 книги другого?

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

40. Сколькими различными способами можно разместить в 9 клетках следующие 9 букв: а, а, а, б, б, б, в, в, в?

41. В автомашине 6 мест. Сколькими способами 6 человек могут сесть в эту машину, если занять место водителя могут только двое из них?

42. Сколькими способами из колоды в 52 карты можно извлечь 6 карт, содержащих туза и короля одной масти?

43. Определить разложение при n=5.

44. Определить разложение при n=8.

45. Найти член разложения , не содержащий x (то есть содержащий x в нулевой степени).

46. Найти шестой член разложения , если биномиальный коэффициент третьего от конца члена равен 45.

47. В разложении коэффициент третьего члена на 44 больше коэффициента второго члена. Найти свободный член, то есть член разложения, не зависящий от x (членом, не зависящим от x, будет тот, который содержит x в нулевой степени).

48. В разложении бинома найти члены, не содержащие иррациональности.

49. Найти номер того члена разложения , который содержит a и b в одинаковых степенях.

Практическое занятие №2

(интерактивное занятие в малых группах)

Булевы функции

Цель занятия: уметь строить различные булевы функции, проверять эквивалентность булевых формул (используя таблицу истинности), определять существенные и фиктивные переменные.

План занятия:

1. Основные операции

2. Булевы функции от n переменных

3. Основные эквивалентности

Основные правила комбинаторики.

Комбинаторика - это раздел математики, изучающий способы расположения объектов в соответствии со специальными правилами и методы подсчета числа всех возможных способов. Правило умножения. Если некоторый выбор A можно осуществить m способами, а для каждого из них некоторый другой выбор B можно осуществить n способами, то выбор A и B (в указанном порядке) можно осуществить m×n способами. Пример 1. На гору ведут 6 дорог. Сколькими способами можно подняться на гору и спуститься с горы, если подъем и спуск должен быть по разным дорогам? Решение. Дорогу на гору можно выбрать 6-ю способами, так как подъем и спуск должны быть по разным дорогам, то выбрать дорогу для спуска можно 5-ю способами. Тогда по правилу умножения число способов выбора дороги для подъема и спуска равно 6×5=30. Правило сложения. Если некоторый выбор A можно осуществить m способами, а выбор B можно осуществить n способами, то выбор A или B можно осуществить m+n способами. Пример 2. В ящике имеется 6 красных карандашей, 5 синих и 3 простых карандаша. Сколькими способами можно выбрать цветной карандаш? Решение. Цветной карандаш - это красный или синий, следовательно, по правилу сложения число способов выбора цветного карандаша равно 6+5=11. Замечание. Данные правила можно обобщить на большее число выборов. Вопрос. Сколько основных правил комбинаторики существует?

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

Определение 1. Множество называется упорядоченным, если каждому элементу этого множества поставлено в соответствие некоторое натуральное число от 1 до n, где n - это число элементов данного множества, причем разным элементам поставлены в соответствие разные числа.

Упорядоченные множества считаются различными, если они отличаются либо своими элементами, либо их порядком. Определение 2. Различные упорядоченные множества, составленные из элементов данного множества, отличающиеся лишь порядком элементов, называются его перестановками. Пример 3. Рассмотрим множество M={a,b,c}. Это множество из трех элементов. Составим его различные перестановки: (a,b,c),(a,c,b),(b,a,c),(b,c,a),(c,a,b),(c,b,a). Получили 6 перестановок. P n - число всех перестановок множества из n элементов.

P n =n! (1), где

n!=1·2·3·...·n (читается "н факториал"). Замечание. 0!=1; (n+1)!=n!·(n+1) . Пример 4. Сколько шестизначных чисел, кратных пяти, можно составить из цифр 0,1,2,3,4,5, при условии, что в числе нет одинаковых цифр? Решение. Числа, кратные пяти(делящиеся на пять), оканчиваются либо на 0, либо на 5. Если последняя цифра числа 0, то остальные цифры можно располагать в любом порядке, получим перестановки из пяти элементов, их P 5 =5!=120. Если на конце 5, то остальные можно расположить P 5 =120 способами, но среди них не подходят те, которые начинаются на 0, так как это будут не шестизначные числа. а пятизначные, данных чисел P 4 =4!=24.Тогда требуемых чисел будет 120+120-24=216.

Вопрос. Сколько существует перестановок из шести элементов?

Ваш ответ : 720

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

Если взять цифры 1, 2, 3, 4, то из них можно составить 24 перестановки. Но если взять четыре цифры 1, 1, 2, 2, то можно получить только следующие различные перестановки: (1,1,2,2),(1,2,1,2),(1,2,2,1),((2,2,1,1),(2,1,2,1),(2,1,1,2), то есть шесть перестановок, их в 4 раза меньше, чем перестановок из четырех различных чисел, так как перестановки, в которых меняются местами одинаковые числа - это не новые перестановки, их 2!·2!=4. Рассмотрим задачу в общем виде:пусть имеется множество из элементов, в котором элементывстречаютсяраз, элементывстречаютсяраз,..., элементывстречаютсяраз, причем.

Определение 3. Перестановки с повторениями - это перестановки из элементов данного множества, в которых элементы повторяются. - число всех перестановок с повторениями. Число перестановок, не меняющих данную перестановку с повторениями равно, ачисел можно переставлятьспособами, поэтому получаем следующую формулу для вычисления числа перестановок с повторениями:

Пример 4. Сколькими способами можно расселить 8 студентов по трем комнатам: одноместной, трехместной и четырехместной? Решение. Различныеспособы расселения студентов по комнатам являются перестановками с повторениями, так как внутри, например, трехместной комнаты выбранные студенты могут занимать спальные места по-разному, но эти варианты не будут являться новыми перестановками, поэтому получаем: То есть всего 280 способов расселения студентов.Вопрос. Вычислить

Сочетания.

Пусть некоторое множество содержит n элементов.

Определение 4. Всякое m- элементное подмножество n- элементного множества называется сочетанием из n элементов по m. - число всех сочетаний.

(3)

Пример 5. Для соревнований из 30 спортсменов надо выбрать трех человек. Сколькими способами это можно сделать? Решение. Команда из 3 спортсменов - это подмножество из трех элементов, то есть сочетание из 30 по 3, поэтому количество способов выбора таких команд вычисляется по формуле (3): .

Свойства сочетаний.

1. 2.. Из данных свойств следует, что, тогда, далее,,и так далее. Можно расположить эти числа в виде таблицы:

.....................................................

.......................

Эта таблица в виде треугольника называется треугольником Паскаля.

Определение 5. Выражение a+b называется биномом.

Формула (4) называется биномиальной формулой Ньютона, а коэффициенты называются биномиальными коэффициентами. Из данной формулы вытекает следующее свойство числа сочетаний

Вопрос. .

Сочетания с повторениями

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

(5)

Пример 6. В кондитерском магазине продаются пирожные четырех видов: наполеоны, эклеры, песочные и бисквитные. Сколькими способами можно купить 7 пирожных? Решение. Любая покупка - это подмножество, в котором могут быть одинаковые элементы, поэтому это сочетание с повторениями. Число всех возможных покупок находим по формуле (5): .Вопрос. В формуле (5) m может быть больше n.

Размещения

Определение 7. Упорядоченное m - элементное подмножество n- элементного множества называется размещением. - число всех размещений из n элементов по m. Число всех размещений из n по m больше числа всех сочетаний из n по m, так как из каждого подмножества из m элементов с помощью перестановок можно получить m! упорядоченных подмножеств, получаем формулу для числа размещений

(6)

Пример 7. В группе 25 человек. Нужно выбрать актив группы: старосту, заместителя старосты и профорга. Сколькими способами это можно сделать? Решение. Актив группы - это упорядоченное подмножество из трех элементов, так как надо выбрать не только трех человек, но и распределить между ними должности, значит актив группы - это размещение, число всех размещений вычисляем по формуле (6): .Вопрос. Во сколько раз число сочетаний из 20 по 4 меньше числа размещений из 20 по 4?

Размещения с повторениями

Пусть дано множество из n элементов, в котором есть одинаковые элементы, тогда его подмножества тоже могут содержать одинаковые элементы. Определение 8. Упорядоченные m- элементные подмножества n- элементного множества, в которых элементы могут повторяться, называются размещениями с повторениями. - число всех размещений из n по m. В подмножестве из m элементов первый элемент можно выбрать n способами(то есть любой элемент множества) , так как элементы могут повторяться, то второй элемент тоже можно выбрать n способами, аналогично остальные элементы подмножества можно выбрать n способами, если воспользоваться правилом умножения, получим формулу для вычисления числа размещений с повторениями:

Пример 8. В лифт десятиэтажного дома вошли 5 человек. Каждый из них может выйти на любом этаже, начиная со второго. Сколькими способами они могут это сделать? Решение. Так как каждый человек может выйти на любом этаже, начиная со второго, то этажей для выхода 9. Надо выбрать этажи для возможности выхода каждого человека: для первого человека - можно выбрать любой из девяти этажей, аналогично для остальных пассажиров, тогда по формуле (7): способов.Вопрос. Вычислить .

Следует отметить, что комбинаторика является самостоятельным разделом высшей математики (а не частью тервера) и по данной дисциплине написаны увесистые учебники, содержание которых, порой, ничуть не легче абстрактной алгебры. Однако нам будет достаточно небольшой доли теоретических знаний, и в данной статье я постараюсь в доступной форме разобрать основы темы с типовыми комбинаторными задачами. А многие из вас мне помогут;-)

Чем будем заниматься? В узком смысле комбинаторика – это подсчёт различных комбинаций, которые можно составить из некоторого множества дискретных объектов. Под объектами понимаются какие-либо обособленные предметы или живые существа – люди, звери, грибы, растения, насекомые и т.д. При этом комбинаторику совершенно не волнует, что множество состоит из тарелки манной каши, паяльника и болотной лягушки. Принципиально важно, что эти объекты поддаются перечислению – их три (дискретность) и существенно то, что среди них нет одинаковых.

С множеством разобрались, теперь о комбинациях. Самыми распространёнными видами комбинаций являются перестановки объектов, их выборка из множества (сочетание) и распределение (размещение). Давайте прямо сейчас посмотрим, как это происходит:

Перестановки, сочетания и размещения без повторений

Не пугайтесь малопонятных терминов, тем более, некоторые из них действительно не очень удачны. Начнём с хвоста заголовка – что значит «без повторений »? Это значит, что в данном параграфе будут рассматриваться множества, которые состоят из различных объектов. Например, … нет, кашу с паяльником и лягушкой предлагать не буду, лучше что-нибудь повкуснее =) Представьте, что перед вами на столе материализовалось яблоко, груша и банан (при наличии таковых ситуацию можно смоделировать и реально). Выкладываем фрукты слева направо в следующем порядке:

яблоко / груша / банан

Вопрос первый : сколькими способами их можно переставить?

Одна комбинация уже записана выше и с остальными проблем не возникает:

яблоко / банан / груша
груша / яблоко / банан
груша / банан / яблоко
банан / яблоко / груша
банан / груша / яблоко

Итого : 6 комбинаций или 6 перестановок .

Хорошо, здесь не составило особого труда перечислить все возможные случаи, но как быть, если предметов больше? Уже с четырьмя различными фруктами количество комбинаций значительно возрастёт!

Пожалуйста, откройте справочный материал (методичку удобно распечатать) и в пункте № 2 найдите формулу количества перестановок.

Никаких мучений – 3 объекта можно переставить способами.

Вопрос второй : сколькими способами можно выбрать а) один фрукт, б) два фрукта, в) три фрукта, г) хотя бы один фрукт?

Зачем выбирать? Так нагуляли же аппетит в предыдущем пункте – для того, чтобы съесть! =)

а) Один фрукт можно выбрать, очевидно, тремя способами – взять либо яблоко, либо грушу, либо банан. Формальный подсчёт проводится по формуле количества сочетаний :

Запись в данном случае следует понимать так: «сколькими способами можно выбрать 1 фрукт из трёх?»

б) Перечислим все возможные сочетания двух фруктов:

яблоко и груша;
яблоко и банан;
груша и банан.

Количество комбинаций легко проверить по той же формуле:

Запись понимается аналогично: «сколькими способами можно выбрать 2 фрукта из трёх?».

в) И, наконец, три фрукта можно выбрать единственным способом:

Кстати, формула количества сочетаний сохраняет смысл и для пустой выборки:
способом можно выбрать ни одного фрукта – собственно, ничего не взять и всё.

г) Сколькими способами можно взять хотя бы один фрукт? Условие «хотя бы один» подразумевает, что нас устраивает 1 фрукт (любой) или 2 любых фрукта или все 3 фрукта:
способами можно выбрать хотя бы один фрукт.

Читатели, внимательно изучившие вводный урок по теории вероятностей , уже кое о чём догадались. Но о смысле знака «плюс» позже.

Для ответа на следующий вопрос мне требуется два добровольца… …Ну что же, раз никто не хочет, тогда буду вызывать к доске =)

Вопрос третий : сколькими способами можно раздать по одному фрукту Даше и Наташе?

Для того чтобы раздать два фрукта, сначала нужно их выбрать. Согласно пункту «бэ» предыдущего вопроса, сделать это можно способами, перепишу их заново:

яблоко и груша;
яблоко и банан;
груша и банан.

Но комбинаций сейчас будет в два раза больше. Рассмотрим, например, первую пару фруктов:
яблоком можно угостить Дашу, а грушей – Наташу;
либо наоборот – груша достанется Даше, а яблоко – Наташе.

И такая перестановка возможна для каждой пары фруктов.

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

Способами можно выбрать 1 юношу;
способами можно выбрать 1 девушку.

Таким образом, одного юношу и одну девушку можно выбрать: способами.

Когда из каждого множества выбирается по 1 объекту, то справедлив следующий принцип подсчёта комбинаций: «каждый объект из одного множества может составить пару с каждым объектом другого множества».

То есть, Олег может пригласить на танец любую из 13 девушек, Евгений – тоже любую из тринадцати, и аналогичный выбор есть у остальных молодых людей. Итого: возможных пар.

Следует отметить, что в данном примере не имеет значения «история» образования пары; однако если принять во внимание инициативу, то количество комбинаций нужно удвоить, поскольку каждая из 13 девушек тоже может пригласить на танец любого юношу. Всё зависит от условия той или иной задачи!

Похожий принцип справедлив и для более сложных комбинаций, например: сколькими способами можно выбрать двух юношей и двух девушек для участия в сценке КВН?

Союз И недвусмысленно намекает, что комбинации необходимо перемножить:

Возможных групп артистов.

Иными словами, каждая пара юношей (45 уникальных пар) может выступать с любой парой девушек (78 уникальных пар). А если рассмотреть распределение ролей между участниками, то комбинаций будет ещё больше. …Очень хочется, но всё-таки воздержусь от продолжения, чтобы не привить вам отвращение к студенческой жизни =).

Правило умножения комбинаций распространяется и на бОльшее количество множителей:

Задача 8

Сколько существует трёхзначных чисел, которые делятся на 5?

Решение : для наглядности обозначим данное число тремя звёздочками: ***

В разряд сотен можно записать любую из цифр (1, 2, 3, 4, 5, 6, 7, 8 или 9). Ноль не годится, так как в этом случае число перестаёт быть трёхзначным.

А вот в разряд десятков («посерединке») можно выбрать любую из 10 цифр: .

По условию, число должно делиться на 5. Число делится на 5, если оно заканчивается на 5 либо на 0. Таким образом, в младшем разряде нас устраивают 2 цифры.

Итого, существует : трёхзначных чисел, которые делятся на 5.

При этом произведение расшифровывается так: «9 способами можно выбрать цифру в разряд сотен и 10 способами выбрать цифру в разряд десятков и 2 способами в разряд единиц »

Или ещё проще: «каждая из 9 цифр в разряде сотен комбинируется с каждой из 10 цифр разряда десятков и с каждой из двух цифр в разряде единиц ».

Ответ : 180

А теперь…

Да, чуть не забыл об обещанном комментарии к задаче № 5, в которой Боре, Диме и Володе можно сдать по одной карте способами. Умножение здесь имеет тот же смысл: способами можно извлечь 3 карты из колоды И в каждой выборке переставить их способами.

А теперь задача для самостоятельного решения… сейчас придумаю что-нибудь поинтереснее, …пусть будет про ту же русскую версию блэкджека:

Задача 9

Сколько существует выигрышных комбинаций из 2 карт при игре в «очко»?

Для тех, кто не знает: выигрывает комбинация 10 + ТУЗ (11 очков) = 21 очко и, давайте будем считать выигрышной комбинацию из двух тузов.

(порядок карт в любой паре не имеет значения)

Краткое решение и ответ в конце урока.

Кстати, не надо считать пример примитивным. Блэкджек – это чуть ли не единственная игра, для которой существует математически обоснованный алгоритм, позволяющий выигрывать у казино. Желающие могут легко найти массу информации об оптимальной стратегии и тактике. Правда, такие мастера довольно быстро попадают в чёрный список всех заведений =)

Пришло время закрепить пройденный материал парой солидных задач:

Задача 10

У Васи дома живут 4 кота.

а) сколькими способами можно рассадить котов по углам комнаты?
б) сколькими способами можно отпустить гулять котов?
в) сколькими способами Вася может взять на руки двух котов (одного на левую, другого – на правую)?

Решаем : во-первых, вновь следует обратить внимание на то, что в задаче речь идёт о разных объектах (даже если коты – однояйцовые близнецы). Это очень важное условие!

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

Повторюсь, что при перестановках имеет значение лишь количество различных объектов и их взаимное расположение. В зависимости от настроения Вася может рассаживать животных полукругом на диване, в ряд на подоконнике и т.д. – перестановок во всех случаях будет 24. Желающие могут для удобства представить, что коты разноцветные (например, белый, чёрный, рыжий и полосатый) и перечислить все возможные комбинации.

б) Сколькими способами можно отпустить гулять котов?

Предполагается, что коты ходят гулять только через дверь, при этом вопрос подразумевает безразличие по поводу количества животных – на прогулку могут выйти 1, 2, 3 или все 4 кота.

Считаем все возможные комбинации:

Способами можно отпустить гулять одного кота (любого из четырёх);
способами можно отпустить гулять двух котов (варианты перечислите самостоятельно);
способами можно отпустить гулять трёх котов (какой-то один из четырёх сидит дома);
способом можно выпустить всех котов.

Наверное, вы догадались, что полученные значения следует просуммировать:
способами можно отпустить гулять котов.

Энтузиастам предлагаю усложнённую версию задачи – когда любой кот в любой выборке случайным образом может выйти на улицу, как через дверь, так и через окно 10 этажа. Комбинаций заметно прибавится!

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

Ситуация предполагает не только выбор 2 животных, но и их размещение по рукам:
способами можно взять на руки 2 котов.

Второй вариант решения: способами можно выбрать двух котов и способами посадить каждую пару на руки:

Ответ : а) 24, б) 15, в) 12

Ну и для очистки совести что-нибудь поконкретнее на умножение комбинаций…. Пусть у Васи дополнительно живёт 5 кошек =) Сколькими способами можно отпустить гулять 2 котов и 1 кошку?

То есть, с каждой парой котов можно выпустить каждую кошку.

Ещё один баян для самостоятельного решения:

Задача 11

В лифт 12-этажного дома сели 3 пассажира. Каждый независимо от других с одинаковой вероятностью может выйти на любом (начиная со 2-го) этаже. Сколькими способами:

1) пассажиры могут выйти на одном и том же этаже (порядок выхода не имеет значения) ;
2) два человека могут выйти на одном этаже, а третий – на другом;
3) люди могут выйти на разных этажах;
4) пассажиры могут выйти из лифта?

И тут часто переспрашивают, уточняю: если 2 или 3 человека выходят на одном этаже, то очерёдность выхода не имеет значения. ДУМАЙТЕ, используйте формулы и правила сложения/умножения комбинаций. В случае затруднений пассажирам полезно дать имена и порассуждать, в каких комбинациях они могут выйти из лифта. Не нужно огорчаться, если что-то не получится, так, например, пункт № 2 достаточно коварен.

Полное решение с подробными комментариями в конце урока.

Заключительный параграф посвящён комбинациям, которые тоже встречаются достаточно часто – по моей субъективной оценке, примерно в 20-30% комбинаторных задач:

Перестановки, сочетания и размещения с повторениями

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

Перестановки с повторениями

В перестановках с повторениями, как и в «обычных» перестановках, участвует сразу всё множество объектов , но есть одно но: в данном множестве один или бОльшее количество элементов (объектов) повторяются. Встречайте очередной стандарт:

Задача 12

Сколько различных буквосочетаний можно получить перестановкой карточек со следующими буквами: К, О, Л, О, К, О, Л, Ь, Ч, И, К?

Решение : в том случае, если бы все буквы были различны, то следовало бы применить тривиальную формулу , однако совершенно понятно, что для предложенного набора карточек некоторые манипуляции будут срабатывать «вхолостую», так, например, если поменять местами любые две карточки с буквами «К» в любом слове, то получится то же самое слово. Причём, физически карточки могут сильно отличаться: одна быть круглой с напечатанной буквой «К», другая – квадратной с нарисованной буквой «К». Но по смыслу задачи даже такие карточки считаются одинаковыми , поскольку в условии спрашивается о буквосочетаниях.

Всё предельно просто – всего: 11 карточек, среди которых буква:

К – повторяется 3 раза;
О – повторяется 3 раза;
Л – повторяется 2 раза;
Ь – повторяется 1 раз;
Ч – повторяется 1 раз;
И – повторяется 1 раз.

Проверка: 3 + 3 + 2 + 1 + 1 + 1 = 11, что и требовалось проверить.

По формуле количества перестановок с повторениями :
различных буквосочетаний можно получить. Больше полумиллиона!

Для быстрого расчёта большого факториального значения удобно использовать стандартную функцию Экселя: забиваем в любую ячейку =ФАКТР(11) и жмём Enter .

На практике вполне допустимо не записывать общую формулу и, кроме того, опускать единичные факториалы:

Но предварительные комментарии о повторяющихся буквах обязательны!

Ответ : 554400

Другой типовой пример перестановок с повторениями встречается в задаче о расстановке шахматных фигур, которую можно найти на складе готовых решений в соответствующей pdf-ке. А для самостоятельного решения я придумал менее шаблонное задание:

Задача 13

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

Формула здесь не годится, поскольку учитывает совпадающие перестановки (например, когда меняются местами силовые упражнения в среду с силовыми упражнениями в четверг). И опять – по факту те же 2 силовые тренировки могут сильно отличаться друг от друга, но по контексту задачи (с точки зрения расписания) они считаются одинаковыми элементами.

Двухстрочное решение и ответ в конце урока.

Сочетания с повторениями

Характерная особенность этого вида комбинаций состоит в том, что выборка проводится из нескольких групп, каждая из которых состоит из одинаковых объектов.

Сегодня все хорошо потрудились, поэтому настало время подкрепиться:

Задача 14

В студенческой столовой продают сосиски в тесте, ватрушки и пончики. Сколькими способами можно приобрести пять пирожков?

Решение : сразу обратите внимание на типичный критерий сочетаний с повторениями – по условию на выбор предложено не множество объектов как таковое, а различные виды объектов; при этом предполагается, что в продаже есть не менее пяти хот-догов, 5 ватрушек и 5 пончиков. Пирожки в каждой группе, разумеется, отличаются – ибо абсолютно идентичные пончики можно смоделировать разве что на компьютере =) Однако физические характеристики пирожков по смыслу задачи не существенны, и хот-доги / ватрушки / пончики в своих группах считаются одинаковыми.

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

Как и при «обычных» сочетаниях, порядок выбора и размещение пирожков в выборке не имеет значения – просто выбрали 5 штук и всё.

Используем формулу количества сочетаний с повторениями:
способом можно приобрести 5 пирожков.

Приятного аппетита!

Ответ : 21

Какой вывод можно сделать из многих комбинаторных задач?

Порой, самое трудное – это разобраться в условии.

Аналогичный пример для самостоятельного решения:

Задача 15

В кошельке находится достаточно большое количество 1-, 2-, 5- и 10-рублёвых монет. Сколькими способами можно извлечь три монеты из кошелька?

В целях самоконтроля ответьте на пару простых вопросов:

1) Могут ли в выборке все монеты быть разными?
2) Назовите самую «дешевую» и самую «дорогую» комбинацию монет.

Решение и ответы в конце урока.

Из моего личного опыта, могу сказать, что сочетания с повторениями – наиболее редкий гость на практике, чего не скажешь о следующем виде комбинаций:

Размещения с повторениями

Из множества, состоящего из элементов, выбирается элементов, при этом важен порядок элементов в каждой выборке. И всё бы было ничего, но довольно неожиданный прикол заключается в том, что любой объект исходного множества мы можем выбирать сколько угодно раз. Образно говоря, от «множества не убудет».

Когда так бывает? Типовым примером является кодовый замок с несколькими дисками, но по причине развития технологий актуальнее рассмотреть его цифрового потомка:

Задача 16

Сколько существует четырёхзначных пин-кодов?

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

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

Ответ : 10000

Что тут приходит на ум… …если банкомат «съедает» карточку после третьей неудачной попытки ввода пин-кода, то шансы подобрать его наугад весьма призрачны.

И кто сказал, что в комбинаторике нет никакого практического смысла? Познавательная задача для всех читателей сайт:

Задача 17

Согласно государственному стандарту, автомобильный номерной знак состоит из 3 цифр и 3 букв. При этом недопустим номер с тремя нулями, а буквы выбираются из набора А, В, Е, К, М, Н, О, Р, С, Т, У, Х (используются только те буквы кириллицы, написание которых совпадает с латинскими буквами) .

Сколько различных номерных знаков можно составить для региона?

Не так их, кстати, и много. В крупных регионах такого количества не хватает, и поэтому для них существуют по несколько кодов к надписи RUS.

Решение и ответ в конце урока. Не забываем использовать правила комбинаторики;-) …Хотел похвастаться эксклюзивом, да оказалось не эксклюзивом =) Заглянул в Википедию – там есть расчёты, правда, без комментариев. Хотя в учебных целях, наверное, мало кто прорешивал.

Наше увлекательное занятие подошло к концу, и напоследок я хочу сказать, что вы не зря потратили время – по той причине, что формулы комбинаторики находят ещё одно насущное практическое применение: они встречаются в различных задачах по теории вероятностей ,
и в задачах на классическое определение вероятности – особенно часто =)

Всем спасибо за активное участие и до скорых встреч!

Решения и ответы :

Задача 2: Решение : найдём количество всех возможных перестановок 4 карточек:

Когда карточка с нулём располагается на 1-м месте, то число становится трёхзначным, поэтому данные комбинации следует исключить. Пусть ноль находится на 1-м месте, тогда оставшиеся 3 цифры в младших разрядах можно переставить способами.

Примечание : т.к. карточек немного, то здесь несложно перечислить все такие варианты:
0579
0597
0759
0795
0957
0975

Таким образом, из предложенного набора можно составить:
24 – 6 = 18 четырёхзначных чисел
Ответ : 18

Задача 4: Решение : способами можно выбрать 3 карты из 36.
Ответ : 7140

Задача 6: Решение : способами.
Другой вариант решения : способами можно выбрать двух человек из группы и и
2) Самый «дешёвый» набор содержит 3 рублёвые монеты, а самый «дорогой» – 3 десятирублёвые.

Задача 17: Решение : способами можно составить цифровую комбинацию автомобильного номера, при этом одну из них (000) следует исключить: .
способами можно составить буквенную комбинацию автомобильного номера.
По правилу умножения комбинаций, всего можно составить:
автомобильных номера
(каждая цифровая комбинация сочетается с каждой буквенной комбинацией).
Ответ : 1726272

Сочетания. Размещения. Перестановки

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

Рассмотрим пример : сколько трехзначных чисел можно составить из цифр 1,2,3, если каждая цифра входит в изображение числа только один раз?

Решение:

Или такой пример . Порядок выступления семи участников на студенческой конференции определяется жребием. Сколько различных вариантов жеребьевки при этом возможно?

Решение: каждый вариант жеребьевки отличается только порядком участников, то есть является перестановкой из 7 элементов. Их число находится

Пример. К кассе за получением денег подошли одновременно 4 человека. Сколькими способами они могут выстроиться в очередь?

Решение: очередь состоит из 4 различных лиц, поэтому в каждом способе составления очереди учитывается порядок их расположения. Таким образом, имеют место перестановки из четырех человек, их число равно

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

Число всех возможных размещений рассчитывается

Пример: сколько можно составить сигналов из 6 флажков различного цвета, взятых по два?

Решение:

Пример: расписание одного дня состоит из пяти уроков. Определить число вариантов расписания при выборе из 11 дисциплин.

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

Сочетаниями называют комбинации, составленные из n различных элементов по m элементов, которые отличаются хотя бы одним элементом. Число сочетаний

Пример: сколькими способами можно выбрать 2 детали из ящика, содержащего 10 деталей?

Решение:

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

Решение: каждая партия играется двумя участниками из 16 и отличается только составом пар участников, то есть представляет собой сочетание из 16 элементов по два

Пример: имеется 6 штаммов бактерий. Для определения скорости их роста необходимо выбрать три штамма. Сколькими способами можно это сделать?

Решение: способы отбора считаются различными, если каждый отобранный штамм различается хотя бы одним элементом. Это число

То есть имеется 20 способов.

Подчеркнем, что числа размещений, перестановок и сочетаний связаны равенством

При решении задач комбинаторики используют следующие правила.

Правило суммы: если некоторый объект A может быть выбран из совокупности объектов m способами, а другой объект В может быть выбран n способами, то выбрать либо А , либо В можно способами.

Правило произведения: если объект А можно выбрать из совокупности объектов m способами и после каждого такого выбора объект В можно выбрать n способами, то пара объектов (А,В) в указанном порядке может быть выбрана способами.

Подсчитаем в MS EXCEL количество перестановок из n элементов. С помощью формул выведем на лист все варианты перестановок (английский перевод термина: permutation).

Перестановкой множества из n элементов называется расположение элементов в определенном порядке.

Элементами множества могут быть числа, буквы и вообще любые объекты. Главное, чтобы эти элементы были различными. Т.к. любому объекту можно сопоставить число, то для Перестановок обычно используют конечное множество целых чисел, например, {1; 2; 3; 4; 5}. Хотя множества из букв также можно часто встретить в литературе. Например, все различные Перестановки множества из трех элементов {a, b, c} – это abc , acb , bac , bca , cab , cba .

Число Перестановок n элементов равно n! (факториал).

Для вычисления факториала в MS EXCEL есть функция =ФАКТР() , английский вариант FACT(). Понятно, что число перестановок растет очень быстро с ростом n: для n=7 число перестановок равно 5040. Справедливости ради, нужно отметить, что зачастую сами варианты перестановок находить не требуется, главное – найти их количество.

Примечание : Перестановки можно считать частным случаем размещений при n=k (см. статью ). Поэтому для вычисления количества перестановок можно использовать функцию ПЕРЕСТ() . Для n=7 число Перестановок вычисляется по формуле =ПЕРЕСТ(7;7)

Примечание : О Перестановках с повторениями (с возвращением элементов обратно во множество, из которого они берутся, после выборки каждого элемента) можно прочитать в статье .

В файле примера создана универсальная формула для вывода всех Перестановок для заданного n. Например, для n=3.

Задача

6 машин разных марок участвуют в гонках на выживание: LADA Granta, Hyundai Solaris, KIA Rio, Renault Duster, Lada Kalina, Volkswagen Polo. Определить число возможных вариантов распределения мест между всеми участниками.

Нам нужно определить число перестановок 6 машин на 6-и местах. Т.е. n=6. Оказывается, что таких перестановок 720: =ПЕРЕСТ(6;6) или 6! =ФАКТР(6)

Воспользуемся файлом примера , чтобы найти все варианты перестановок.

Произвольным образом сопоставим маркам машин числовые значения и сделаем сокращения названий марок: LADA Granta (LG=1), Hyundai Solaris (HS=2), …

Введя в ячейке В5 значение 6, определим все варианты расстановок машин на занятых ими в гонке местах.

Примечание : О Размещениях можно прочитать в статье , а о Сочетаниях в статье .

Перебор всех возможных перестановок может потребоваться для решения различных задач (см. статью и ).

Инверсии перестановок

Для каждой перестановки a 1, a 2, a 3,..., a n из n целых чисел 1, 2, 3, ..., n , инверсией называется пара (a i, a j) если для i < j выполняется a i > a j. Число инверсией в перестановке показывает насколько перестановка является "несортированной" по возрастанию.

Например, число инверсий в перестановке 1, 2, 3, 4 равно 0 (перестановка из 4-х целых чисел отсортирована по возрастанию от 1 до 4), а число инверсий в перестановке 4, 3, 1, 2 равно 5, т.к.:

• первый элемент (i=1) равен 4 и он больше 3-х чисел (с j=2, 3, 4), которые расположены правее (4>3, 4>1, 4>2), т.е. мы имеем 3 инверсии;
• второй элемент (i=2) равен 3 и он больше2-х чисел (с j=3, 4), которые расположены правее (3>1, 3>2), т.е. мы имеем еще 2 инверсии;
• так третий элемент (i=3) равен 1 и он меньше числа с j=4, которое расположено правее (1<2), то эта пара не является инверсией. Т.е. у перестановки 4, 3, 1, 2 число инверсий равно 3+2+0=5.

В файле примера для каждой Перестановки подсчитывается число инверсией.