Элементы комбинаторики



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

Комбинаторика— это раздел математики, изучающий способы расположения объектов в соответствии со специальными правилами и методы подсчета числа всех возможных способов.Правило умножения. Если некоторый выбор 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.Замечание. Данные правила можно обобщить на большее число выборов.Вопрос. Сколько основных правил комбинаторики существует?

2

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

Определение 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 перестановок.Pn — число всех перестановок множества из n элементов.

Pn=n! (1), где

n!=1·2·3·…·n ( читается «н факториал»).Замечание. 0!=1; (n+1)!=n!·(n+1) .Пример 4.Сколько шестизначных чисел, кратных пяти, можно составить из цифр 0,1,2,3,4,5, при условии, что в числе нет одинаковых цифр?Решение. Числа, кратные пяти( делящиеся на пять), оканчиваются либо на 0, либо на 5. Если последняя цифра числа 0, то остальные цифры можно располагать в любом порядке, получим перестановки из пяти элементов, их P5=5!=120. Если на конце 5, то остальные можно расположить P5=120 способами, но среди них не подходят те, которые начинаются на 0, так как это будут не шестизначные числа. а пятизначные, данных чисел P4=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.Перестановки с повторениями — это перестановки из элементов данного множества, в которых элементы повторяются.Сочетания с повторениями примеры задач — число всех перестановок с повторениями.Число перестановок, не меняющих данную перестановку с повторениями равно Сочетания с повторениями примеры задач, а Сочетания с повторениями примеры задач чисел можно переставлять Сочетания с повторениями примеры задач способами, поэтому получаем следующую формулу для вычисления числа перестановок с повторениями:

Сочетания с повторениями примеры задач (2)

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

Сочетания.

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

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

Сочетания с повторениями примеры задач(3)

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

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

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

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

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

……………………………………………..

или

1

1 1

1 2 1

1 3 3 1

1 4 6 4 1

…………………..

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

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

Сочетания с повторениями примеры задач (4)



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

Сочетания с повторениями примеры задач(5)

Вопрос. Сочетания с повторениями примеры задач.

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

Пусть имеется множество, содержащее 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 способами, если воспользоваться правилом умножения, получим формулу для вычисления числа размещений с повторениями:

Сочетания с повторениями примеры задач (7)

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








sitemap
sitemap