Лекция на тему Основные формулы комбинаторики

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

Ст.преп Кыштообаева Ч.А.

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

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

Правило суммы и произведения

• Правило суммы . Если некоторый объект A можно выбрать способами n , а объект B можно выбрать способами m (не такими, как A) , то объект «либо A , либо B » можно выбрать n+m способами.
• Правило произведения . Если некоторый объект A можно выбрать n способами, а после каждого такого выбора объект B можно выбрать способами m (независимо от выбора объекта A ), то пару объектов « A и B » в указанном порядке можно выбрать n*m способами.

Пример

• В магазине бытовой техники имеется 8 видов электрических чайников и 10 видов микроволновых печей. Сколькими способами можно: а) совершить покупку, состоящую из одного электроприбора;

б) купить чайник и микроволновую печь?

• а) Электрический чайник можно выбрать 8 способами, а микроволновую печь – 10 способами. Число способов купить один электроприбор (то есть выбрать либо чайник, либо микроволновую печь), по правилу суммы, равно 8+10=18.
• б) Купить чайник и микроволновую печь (то есть выбрать пару объектов) можно, по правилу произведения, способами 8*10=80.

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

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

где

Пример

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

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

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

Пример

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

Сочетания

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

Пример

• Сколькими способами можно образовать стартовую пятерку из имеющихся в распоряжении тренера 12 баскетболистов?
• Поскольку в данном случае важен лишь состав стартовой пятерки, а порядок ее элементов не имеет значения, то число способов равно

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

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

где n 1 + n 2 + …+ n k =n.

Примеры

• Сколько различных четырехзначных чисел можно составить из цифр 5, 6, 7, если цифры в числе могут повторяться?
• По условию задачи, цифры в числе могут повторяться, значит речь идет о комбинациях с повторениями. Числа различаются не только составом цифр, но и порядком их расположения (например, числа 5567 и 6575 состоят из одних и тех цифр, записанных в разном порядке).

Примеры

• В продажу поступили открытки 15 разных видов. Сколькими способами можно образовать набор из 8 открыток, если в него могут войти одинаковые открытки?
• Так как виды открыток в наборе могут повторяться, а сами наборы отличаются один от другого только своим составом (очевидно, что расположение открыток в наборе не имеет значения), то число таких наборов равно

Примеры

• Сколько различных «слов» (не обязательно имеющих смысл) можно образовать, переставляя буквы в слове КОЛОКОЛ?
• В слове КОЛОКОЛ, состоящем из 7 букв, буква К встречается два раза, буква О – три раза, буква Л – два раза, то есть n=7, n 1 =2, n 2 =3, n 3 =2 . Следовательно, число «слов» равно

Задачи

• Имеется 3 вида конвертов без марок и 9 видов марок одинаковой стоимости. Сколькими способами можно выбрать конверт с маркой для посылки письма?
• На вершину горы ведут 5 тропинок. Сколькими способами турист может подняться в гору и потом спуститься с нее, если подъем и спуск: а) могут проходить по любым тропинкам; б) должны проходить по разным тропинкам?
• Сколькими способами из 25 членов научного общества учащихся можно выбрать его председателя, заместителя председателя, редактора газеты и секретаря?
• В отделе НИИ работают 22 человека. Сколькими способами можно выбрать 3 человек для участия в конференции?

Задачи

• Сколькими способами можно разместить на скамейке 9 человек?
• Сколько разных трехзначных чисел можно составить из цифр 1, 2, 3, 4, 5 при условии, что: а) ни одна цифра не повторяется; б) цифры могут повторяться; в) число оканчивается цифрой 3 и все цифры различны; г) число начинается с цифры 4 и цифры могут повторяться?
• Сколько различных восьмизначных чисел можно записать с помощью цифр 1, 1, 1, 2, 2, 2, 3, 3.
• Для несения почетного караула из 10 человек могут быть приглашены офицеры 6 родов войск. Сколькими способами можно назначить состав почетного караула?

Задачи

• Сколько различных «слов» можно образовать при перестановке букв слова МАТЕМАТИКА?
• Из 10 различных книг выбирают 4 для посылки. Сколькими способами это можно сделать?
• Сколько трехбуквенных «слов» можно составить из букв слова ИНТЕГРАЛ (буквы в «слове» могут повторяться)?
• Сколько различных «слов» (не обязательно имеющих смысл) можно образовать, переставляя буквы слова: а) ЗАМОК; б) САВАННА; в) ЗАМОК, если буква К должна стоять на первом месте?

Задачи

• Студентам надо сдать 4 экзамена за 12 дней. Сколькими способами можно составить расписание экзаменов, если в один день не должно быть двух экзаменов?
• Сколько различных вариантов хоккейной команды можно составить из 9 нападающих, 5 защитников и 3 вратарей, если в состав команды должны войти 3 нападающих, 2 защитника и 1 вратарь?
• Имеется 11 наименований товаров. Сколькими способами их можно развезти по трем магазинам следующим образом: 5 наименования – в первый магазин, 4 – во второй, 2 – в третий?
• Сколькими способами на шахматной доске можно указать: а) две клетки; б) две клетки одного цвета; в) две клетки разного цвета?

Задачи

• Из трех инженеров и девяти экономистов должна быть выбрана комиссия в составе семи человек. Сколькими способами может быть составлена комиссия, если в нее должен войти: а) ровно один инженер; б) хотя бы один инженер?
• Сколько четных пятизначных чисел можно составить из цифр 1, 2, 3, 4, 5, если цифры в числе не должны повторяться?
• Сколькими способами можно поставить в ряд 6 автомобилей так, чтобы два определенных автомобиля оказались рядом?
• Сколько автомобильных номеров формата Б ЦЦЦ ББ можно составить, если можно использовать все цифры и те буквы русского алфавита, которые имеют написание, подобное латинским буквам?

ОТВЕТЫ

• 1 . 27. 2 . а) 25; б) 20. 3 . 303600. 4 . 1540. 5 . 362880. 6 . а) 60; б) 125; в) 12; г) 25. 7 . 560. 8 . 3003. 9 . 151200. 10 . 210. 11 . 512. 12 . а) 120; б) 420; в) 24. 13 . 11880. 14 . 2520. 15 . 6930. 16 . а) 2016; б) 992; в) 1024. 17 . а) 252; б) 756. 18 . 48. 19 . 240. 20 . 1726272.