Чтобы в материале было легче ориентироваться, добавлю содержание данной темы:
В этой теме рассмотрим основные понятия комбинаторики: перестановки, сочетания и размещения. Выясним их суть и формулы, по которым можно найти их количество.
Для работы нам понадобятся кое-какие вспомогательные сведения. Начнём с такого фундаментального математического понятия как множество. Подробно понятие множества было раскрыто в теме "Понятие множества. Способы задания множеств" .
Очень краткий рассказ про множества : показать\скрыть
Если вкратце: множеством именуют некую совокупность объектов. Записывают множества в фигурных скобках. Порядок записи элементов роли не играет; повторения элементов не допускаются. Например, множество цифр числа 11115555999 будет таким: $\{1,5,9 \}$. Множество согласных букв в слове "тигрёнок" таково: $\{т, г, р, н, к\}$. Запись $5\in A$ означает, что элемент 5 принадлежит множеству $A=\{1,5,9 \}$. Количество элементов в конечном множестве называют мощностью этого множества и обозначают $|A|$. Например, для множества $A=\{1,5,9 \}$, содержащего 3 элемента, имеем: $|A|=3$.
Рассмотрим некое непустое конечное множество $U$, мощность которого равна $n$, $|U|=n$ (т.е. в множестве $U$ имеется $n$ элементов). Введём такое понятие, как выборка (некоторые авторы именуют её кортежем). Под выборкой объема $k$ из $n$ элементов (сокращённо $(n,k)$-выборкой) будем понимать набор элементов $(a_1, a_2,\ldots, a_k)$, где $a_i\in U$. Выборка называется упорядоченной, если в ней задан порядок следования элементов. Две упорядоченные выборки, различающиеся лишь порядком элементов, являются различными. Если порядок следования элементов выборки не является существенным, то выборку именуют неупорядоченной.
Заметьте, что в определении выборки ничего не сказано про повторения элементов. В отличие от элементов множеств, элементы выборки могут повторяться.
Для примера рассмотрим множество $U=\{a,b,c,d,e\}$. Множество $U$ содержит 5 элементов, т.е. $|U|=5$. Выборка без повторений может быть такой: $(a,b,c)$. Данная выборка содержит 3 элемента, т.е. объём этой выборки равен 3. Иными словами, это $(5,3)$-выборка.
Выборка с повторениями может быть такой: $(a,a,a,a,a,c,c,d)$. Она содержит 8 элементов, т.е. объём её равен 8. Иными словами, это $(5,8)$-выборка.
Рассмотрим ещё две $(5,3)$-выборки: $(a,b,b)$ и $(b,a,b)$. Если мы полагаем наши выборки неупорядоченными, то выборка $(a,b,b)$ равна выборке $(b,a,b)$, т.е. $(a,b,b)=(b,a,b)$. Если мы полагаем наши выборки упорядоченными, то $(a,b,b)\neq(b,a,b)$.
Рассмотрим ещё один пример, немного менее абстрактный:) Предположим, в корзине лежат шесть конфет, причём все они различны. Если первой конфете поставить в соответствие цифру 1, второй конфете - цифру 2 и так далее, то с конфетами в корзине можно сопоставить такое множество: $U=\{1,2,3,4,5,6\}$. Представьте, что мы наугад запускаем руку в корзинку с целью вытащить три конфеты. Вытащенные конфеты - это и есть выборка. Так как мы вытаскиваем 3 конфеты из 6, то получаем (6,3)-выборку. Порядок расположения конфет в ладони совершенно несущественен, поэтому эта выборка является неупорядоченной. Ну, и так как все конфеты различны, то выборка без повторений. Итак, в данной ситуации говорим о неупорядоченной (6,3)-выборке без повторений.
Теперь подойдём с иной стороны. Представим себе, что мы находимся на фабрике по производству конфет, и на этой фабрике производятся конфеты четырёх сортов. Множество $U$ в этой ситуации таково: $U=\{1,2,3,4 \}$ (каждая цифра отвечает за свой сорт конфет). Теперь вообразим, что все конфеты ссыпаются в единый жёлоб, около которого мы и стоим. И, подставив ладони, из этого потока отбираем 20 конфет. Конфеты в горсти – это и есть выборка. Играет ли роль порядок расположения конфет в горсти? Естественно, нет, поэтому выборка неупорядоченная. Всего 4 сорта конфет, а мы отбираем двадцать штук из общего потока - повторения сортов неизбежны. При этом выборки могут быть самыми различными: у нас даже могут оказаться все конфеты одного сорта. Следовательно, в этой ситуации мы имеем дело с неупорядоченной (4,20)-выборкой с повторениями.
Рассмотрим ещё пару примеров. Пусть на кубиках написаны различные 7 букв: к, о, н, ф, е, т, а. Эти буквы образуют множество $U=\{к,о,н,ф,е,т,а\}$. Допустим, из данных кубиков мы хотим составить "слова" из 5 букв. Буквы этих слов (к примеру, «конфе», «тенко» и так далее) образуют (7,5)-выборки: $(к,о,н,ф,е)$, $(т,е,н,к,о)$ и т.д. Очевидно, что порядок следования букв в такой выборке важен. Например, слова «нокфт» и «кфтон» различны (хотя состоят из одних и тех же букв), ибо в них не совпадает порядок букв. Повторений букв в таких «словах» нет, ибо в наличии только семь кубиков. Итак, набор букв каждого слова представляет собой упорядоченную (7,5)-выборку без повторений.
Еще один пример: мы составляем всевозможные восьмизначные числа из четырёх цифр 1, 5, 7, 8. Например, 11111111, 15518877, 88881111 и так далее. Множество $U$ таково: $U=\{1,5,7,8\}$. Цифры каждого составленного числа образуют (4,8)-выборку. Порядок следования цифр в числе важен, т.е. выборка упорядоченная. Повторения допускаются, поэтому здесь мы имеем дело с упорядоченной (4,8)-выборкой с повторениями.
Размещение без повторений из $n$ элементов по $k$ - упорядоченная $(n,k)$-выборка без повторений.
Так как элементы в рассматриваемой выборке повторяться не могут, то мы не можем отобрать в выборку больше элементов, чем есть в исходном множестве. Следовательно, для таких выборок верно неравенство: $n≥ k$. Количество размещений без повторений из $n$ элементов по $k$ определяется следующей формулой:
\begin{equation}A_{n}^{k}=\frac{n!}{(n-k)!} \end{equation}
Что обозначает знак "!"? : показать\скрыть
Запись "n!" (читается "эн факториал") обозначает произведение всех чисел от 1 до n, т.е.
$$ n!=1\cdot2\cdot 3\cdot \ldots\cdot n $$
По определению полагается, что $0!=1!=1$. Для примера найдём 5!:
$$ 5!=1\cdot 2\cdot 3\cdot 4\cdot 5=120. $$
Пример №1
Алфавит состоит из множества символов $E=\{+,*,0,1,f\}$. Определим количество таких трёхсимвольных слов в этом алфавите, которые не содержат повторяющихся букв.
Под трёхсимвольными словами будем понимать выражения вида "+*0" или "0f1". В множестве $E$ пять элементов, поэтому буквы трехсимвольных слов образуют (5,3)-выборки. Первый вопрос: эти выборки упорядочены или нет? Слова, которые отличаются лишь порядком букв, полагаются различными, поэтому порядок элементов в выборке важен. Значит, выборка является упорядоченной. Второй вопрос: допускаются повторения или нет? Ответ на этот вопрос даёт условие: слова не должны содержать повторяющихся букв. Подводим итоги: буквы каждого слова, удовлетворяющего условию задачи, образуют упорядоченную (5,3)-выборку без повторений. Иными словами, буквы каждого слова образуют размещение без повторений из 5 элементов по 3. Вот примеры таких размещений:
$$ (+,*,f), \; (*,+,f), \; (1,+,0) $$
Нас же интересует общее количество этих размещений. Согласно формуле (1) количество размещений без повторений из 5 элементов по 3 будет таким:
$$ A_{5}^{3}=\frac{5!}{(5-3)!}=\frac{5!}{2!}=60. $$
Т.е. можно составить 60 трёхсимвольных слов, буквы которых не будут повторяться.
Ответ : 60.
Размещение с повторениями из $n$ элементов по $k$ - упорядоченная $(n,k)$-выборка с повторениями.
Количество размещений с повторениями из $n$ элементов по $k$ определяется следующей формулой:
\begin{equation}\bar{A}_{n}^{k}=n^k \end{equation}
Пример №2
Сколько пятизначных чисел можно составить из множества цифр $\{5,7,2\}$?
Из данного набора цифр можно составить пятизначные числа 55555, 75222 и так далее. Цифры каждого такого числа образуют (3,5)-выборку: $(5,5,5,5,5)$, $(7,5,2,2,2)$. Зададимся вопросом: что это за выборки? Во-первых, цифры в числах могут повторяться, поэтому мы имеем дело с выборками с повторениями. Во-вторых, порядок расположения цифр в числе важен. Например, 27755 и 77255 - разные числа. Следовательно, мы имеем дело с упорядоченными (3,5)-выборками с повторениями. Общее количество таких выборок (т.е. общее количество искомых пятизначных чисел) найдём с помощью формулы (2):
$$ \bar{A}_{3}^{5}=3^5=243. $$
Следовательно, из заданных цифр можно составить 243 пятизначных числа.
Ответ : 243.
Перестановка без повторений из $n$ элементов - упорядоченная $(n,n)$-выборка без повторений.
По сути, перестановка без повторений есть частный случай размещения без повторений, когда объём выборки равен мощности исходного множества. Количество перестановок без повторений из $n$ элементов определяется следующей формулой:
\begin{equation}P_{n}=n! \end{equation}
Эту формулу, кстати, легко получить, если учесть, что $P_n=A_{n}^{n}$. Тогда получим:
$$ P_n=A_{n}^{n}=\frac{n!}{(n-n)!}=\frac{n!}{0!}=\frac{n!}{1}=n! $$
Пример №3
В морозилке лежат пять порций мороженого от различных фирм. Сколькими способами можно выбрать порядок их съедения?
Пусть первому мороженому соответствует цифра 1, второму - цифра 2 и так далее. Мы получим множество $U=\{1,2,3,4,5\}$, которое будет представлять содержимое морозилки. Порядок съедения может быть таким: $(2,1,3,5,4)$ или таким: $(5,4,3,1,2)$. Каждый подобный набор есть (5,5)-выборка. Она будет упорядоченной и без повторений. Иными словами, каждая такая выборка есть перестановка из 5 элементов исходного множества. Согласно формуле (3) общее количество этих перестановок таково:
$$ P_5=5!=120. $$
Следовательно, существует 120 порядков выбора очередности съедения.
Ответ : 120.
Перестановка с повторениями – упорядоченная $(n,k)$-выборка с повторениями, в которой элемент $a_1$ повторяется $k_1$ раз, $a_2$ повторяется $k_2$ раза так далее, до последнего элемента $a_r$, который повторяется $k_r$ раз. При этом $k_1+k_2+\ldots+k_r=k$.
Общее количество перестановок с повторениями определяется формулой:
\begin{equation}P_{k}(k_1,k_2,\ldots,k_r)=\frac{k!}{k_1!\cdot k_2!\cdot \ldots \cdot k_r!} \end{equation}
Пример №4
Слова составляются на основе алфавита $U=\{a,b,d\}$. Сколько различных слов из семи символов может быть составлено, если в этих словах буква "a" должна повторяться 2 раза; буква "b" - 1 раз, а буква "d" - 4 раза?
Вот примеры искомых слов: "aabdddd", "daddabd" и так далее. Буквы каждого слова образуют (3,7)-выборку с повторениями: $(a,a,b,d,d,d,d)$, $(d,a,d,d,a,b,d)$ и т.д. Каждая такая выборка состоит из двух элементов "a", одного элемента "b" и четырёх элементов "d". Иными словами, $k_1=2$, $k_2=1$, $k_3=4$. Общее количество повторений всех символов, естественно, равно объёму выборки, т.е. $k=k_1+k_2+k_3=7$. Подставляя эти данные в формулу (4), будем иметь:
$$ P_7(2,1,4)=\frac{7!}{2!\cdot 1!\cdot 4!}=105. $$
Следовательно, общее количество искомых слов равно 105.
Ответ : 105.
Сочетание без повторений из $n$ элементов по $k$ – неупорядоченная $(n,k)$-выборка без повторений.
Общее количество сочетаний без повторений из $n$ элементов по $k$ определяется формулой:
\begin{equation}C_{n}^{k}=\frac{n!}{(n-k)!\cdot k!} \end{equation}
Пример №5
В корзине размещены карточки, на которых написаны целые числа от 1 до 10. Из корзины вынимают 4 карточки и суммируют числа, написанные на них. Сколько различных наборов карточек можно вытащить из корзины?
Итак, в данной задаче исходное множество таково: $U=\{1,2,3,4,5,6,7,8,9,10\}$. Из этого множества мы выбираем четыре элемента (т.е., четыре карточки из корзины). Номера вытащенных элементов образуют (10,4)-выборку. Повторения в этой выборке не допускаются, так как номера всех карточек различны. Вопрос вот в чём: порядок выбора карточек играет роль или нет? Т.е., к примеру, равны ли выборки $(1,2,7,10)$ и $(10,2,1,7)$ или не равны? Тут нужно обратиться к условию задачи. Карточки вынимаются для того, чтобы потом найти сумму элементов. А это значит, что порядок карточек не важен, так как от перемены мест слагаемых сумма не изменится. Например, выборке $(1,2,7,10)$ и выборке $(10,2,1,7)$ будет соответствовать одно и то же число $1+2+7+10=10+2+1+7=20$. Вывод: из условия задачи следует, что мы имеем дело с неупорядоченными выборками. Т.е. нам нужно найти общее количество неупорядоченных (10,4)-выборок без повторений. Иными словами, нам нужно найти количество сочетаний из 10 элементов по 4. Используем для этого формулу (5):
$$ C_{10}^{4}=\frac{10!}{(10-4)!\cdot 4!}=\frac{10!}{6!\cdot 4!}=210. $$
Следовательно, общее количество искомых наборов равно 210.
Ответ : 210.
Сочетание с повторениями из $n$ элементов по $k$ – неупорядоченная $(n,k)$-выборка с повторениями.
Общее количество сочетаний с повторениями из $n$ элементов по $k$ определяется формулой:
\begin{equation}\bar{C}_{n}^{k}=\frac{(n+k-1)!}{(n-1)!\cdot k!} \end{equation}
Пример №6
Представьте себе, что мы находимся на конфетном заводе, - прямо возле конвейера, по которому движутся конфеты четырёх сортов. Мы запускаем руки в этот поток и вытаскиваем двадцать штук. Сколько всего различных "конфетных комбинаций" может оказаться в горсти?
Если принять, что первому сорту соответствует число 1, второму сорту - число 2 и так далее, то исходное множество в нашей задаче таково: $U=\{1,2,3,4\}$. Из этого множества мы выбираем 20 элементов (т.е., те самые 20 конфет с конвейера). Пригоршня конфет образует (4,20)-выборку. Естественно, повторения сортов будут. Вопрос в том, играет роль порядок расположения элементов в выборке или нет? Из условия задачи следует, что порядок расположения элементов роли не играет. Нам нет разницы, будут ли в горсти располагаться сначала 15 леденцов, а потом 4 шоколадных конфеты, или сначала 4 шоколадных конфеты, а уж потом 15 леденцов. Итак, мы имеем дело с неупорядоченной (4,20) выборкой с повторениями. Чтобы найти общее количество этих выборок используем формулу (6):
$$ \bar{C}_{4}^{20}=\frac{(4+20-1)!}{(4-1)!\cdot 20!}=\frac{23!}{3!\cdot 20!}=1771. $$
Следовательно, общее количество искомых комбинаций равно 1771.
Перестановками называют комбинации, состоящие из одних и тех же 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 способами, то пара объектов (А,В) в указанном порядке может быть выбрана способами.
Элементы комбинаторики: перестановки, сочетания, размещения.
“Число, положение и комбинация – три
взаимно пересекающиеся, но различные
сферы мысли, к которым можно
отнести все математические идеи”.
Джозеф Сильвестр (1844 г.)
Цели занятия.
Образовательные:
Развивающие:
Воспитывающая:
Оборудование: компьютеры, проектор, экран, презентация, электронные и на бумажных носителях тесты, задачи “Судоку”, кубики Рубика, папки для ВСР (внеаудиторная самостоятельная работа), рабочие тетради, чистые ватманы, калькуляторы, цветная бумага, клей, ножницы, фломастеры.
Ход занятия
I. Организационный момент
Перекличка
Сообщение целей и задач занятия: В связи с тем, что по дисциплине “Математика” на 2 курсе специальности “Технология деревообработки” на тему “Основные понятия комбинаторика: перестановки, размещения, сочетания” отводится 2 часа, а рассмотреть нужно много материала, решать задачи, создать проект, вам было выдано задание на внеаудиторную самостоятельную работу следующее: в литературе по истории математики, в энциклопедиях, в учебниках и в интернете найти материал о разделе математики, имеющем звучное название “комбинаторика”. Слайды № 1–2. Презентация
В календарно-тематическом плане по дисциплине “Математика” на 2 курсе специальности “Технология деревообработки” на тему “Основные понятия комбинаторика: перестановки, размещения, сочетания” отводится 2 часа. Изучить теоретический материал, решить задачи разных видов за такой временной промежуток невозможно. Для достижения глубокого изучения материала было выдано задание на внеаудиторную самостоятельную работу: в литературе по истории математики, в энциклопедиях, в учебниках и в интернете найти материал о разделе математики, имеющем звучное название “комбинаторика”. Слайды № 1–2.
Вопросов для внеаудиторной самостоятельной работы выделено было три:
Запись даты, темы урока.
II. Работа над темой занятия
Вступление:
Из глубокой древности до современного человечества дошли сведения о том, что уже тогда люди занимались выбором объектов и расположения их в том или ином порядке и увлекались составлением различных комбинаций. Так, например, в Древнем Китае увлекались составлением квадратов, в которых заданные числа располагали так, что их сумма по всем горизонталям, вертикалям и главным диагоналям была одной и той же (современная игра – задача “Судоку”). Такие задачи вы могли встречать в журналах и газетах. В частности, наша Мариинская газета “Вперед” довольно часто предлагает читателям такие задачи. В Древней Греции подобные задачи возникали в связи c такими играми, как шашки, шахматы, домино, карты и т.д.
Комбинаторика ставится самостоятельным разделом математики, по сути – самостоятельной наукой лишь во второй половине XVII века, - в период, когда возникла теория вероятностей.
Таким образом, - комбинаторика – это самостоятельный раздел математики, в котором изучаются вопросы о том, сколько различных комбинаций, подчинённых тем или условиям, можно составить из заданных объектов.
Комбинаторика – самостоятельная ветвь математической науки. Cлайд № 3
Термин “КОМБИНАТОРИКА” происходит от латинского слова “combina”, что в переводе на русский означает – “сочетать”, “соединять” - слайд № 4.
Как трактует это слово Большой Энциклопедический Словарь?
Комбинаторика – это раздел математики, в котором изучаются простейшие “соединения”: перестановки, размещения, сочетания. Этот раздел иначе называют “комбинаторный анализ”.
Сегодня мы будем рассматривать перестановки, размещения, сочетания, как соединения, как комбинаторные конфигурации.
Разделы комбинаторики: перечислительная, структурная, вероятностная, топологическая – слайд № 5.
Давайте вспомним известное вам из детства сказание о том, как богатырь или другой добрый молодец, доехав до развилки трех дорог, читает на камне: “Вперед поедешь – голову сложишь, направо поедешь – коня потеряешь, налево поедешь – меча лишишься”. А дальше уже говорится, как он выходит из того положения, в которое попал в результате выбора. Но выбирать разные пути или варианты приходится и современному человеку. Эти пути и варианты складываются в самые разнообразные комбинации. И целый раздел математики, именуемый КОМБИНАТОРИКОЙ, занят поисками ответов на вопросы: сколько всего есть комбинаций в том или ином случае, как из всех этих комбинаций выбрать наилучшую – слайд № 6.
Итак, комбинаторика – раздел математики, в котором изучается, сколько различных комбинаций, подчиненных тем или иным условиям, можно составить из заданных объектов.
Перестановки-соединения, которые можно составить из n предметов, меняя всеми возможными способами их порядок; число их
Количество всех перестановок из n элементов обозначают
Число n при этом называется порядком перестановки – слайд № 7–10.
Произведение всех натуральных чисел от n до единицы, обозначают символом n! (Читается “эн - факториал”). Используя знак факториала, можно, например, записать:
3! = 3 2 1 = 6,
4! = 4 3 2 1 = 24,
5! = 5 4 3 2 1 = 120.
Необходимо знать, что 0!=1
Термин “перестановки” употребил впервые Якоб Бернулли в книге “Искусство предположений”.
Примеры решения задач:
Задача №1. Сколькими способами 7 книг разных авторов можно расставить на полке в один ряд?
Перестановками называют комбинации, состоящие из одних и тех же п различных элементов и отличающиеся только порядком их расположения. Число всех возможных перестановок обозначается Рп и оно равно п !, т.е. Рп = п !, где п ! = 1 * 2 * 3 * … п .
Решение: Р7 = 7!, где 7! = 1 * 2 * 3 * 4 * 5 * 6 * 7 =5040, значит существует 5040 способов осуществить расстановку книг.
Ответ: 5040 способов.
Задача № 2 (о квартете)
В знаменитой басне Крылова “Квартет” “Проказница мартышка, Осел, Козел да косолапый Мишка” исследовали влияние взаимного расположения музыкантов на качество исполнения.
Зададим вопрос: Сколько существует способов, чтобы рассадить четырех музыкантов?
Решение: на слайде
Размещения – соединения, содержащие по m предметов из числа n данных, различающихся либо порядком предметов, либо самими предметами; число их.
Cлайды № 11–13.
В комбинаторике размещением называется расположение “предметов” на некоторых “местах” при условии, что каждое место занято в точности одним предметом и все предметы различны.
В отличие от сочетаний размещения учитывают порядок следования предметов. Так, например, наборы < 2,1,3 > и < 3,2,1 > являются различными, хотя состоят из одних и тех же элементов {1,2,3} (то есть, совпадают как сочетания).
Термин “Размещение” употребил впервые Якоб Бернулли в книге “Искусство предположений”.
Примеры решения задач:
Задача № 1. Сколько можно составить телефонных номеров из 6 цифр каждый, так чтобы все цифры были различны? Это пример задачи на размещение без повторений.
Размещаются здесь десять цифр по 6. Значит,
ответ на выше поставленную задачу будет: 
Ответ :151200 способов
Задача № 2. В группе ТД – 21 обучается 24 студентов. Сколькими способами можно составить график дежурства по техникуму, если группа дежурных состоит из трех студентов?
Решение: число способов равно числу размещений из 24 элементов по 3, т.е. равно А 24 3 . По формуле находим
Ответ: 12144 способа
Сочетания-соединения, содержащие по m предметов
из n, различающиеся друг от друга, по крайней мере,
одним предметом; число их 
.
Таким образом, количество вариантов при сочетании будет меньше количества размещений. Cлайды № 14–16.
В комбинаторике сочетанием из n по m называется набор m элементов, выбранных из данных n элементов. Наборы, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми, этим сочетания отличаются от размещений.
Термин “сочетание” впервые встречается у Блеза Паскаля в 1665 году.
Примеры решения задач:
Задача №1. Сколько трехкнопочных комбинаций существует на кодовом замке (все три кнопки нажимаются одновременно), если на нем всего 10 цифр?
Решение: Так как кнопки нажимаются одновременно, то выбор этих кнопок – сочетание. Отсюда возможно
Ответ: 120 вариантов.
Задача № 2. Сколько экзаменационных комиссий, состоящих из 3 членов, можно образовать из 10 преподавателей?
Решение: По формуле находим:
комиссий
Ответ: 120 комиссий.
Библиографическая справка – слайд № 17.
Общее у всех этих задач то, что их решением занимается отдельная область математики, называемая комбинаторикой. “Особая примета” комбинаторных задач – вопрос, который всегда можно сформулировать так, чтобы он начинался словами: “Сколькими способами…?”. Cлайд № 18.
3. Решение задач: тексты задач с решениями в приложении 1 – начало на слайде № 19.
4. Исторические сведения о комбинаторике на слайдах № 20–21 (частично даны сведения при изучении темы, остальные данные для проекта студенты возьмут из материалов для ВСР).
5. Связи комбинаторики на слайдах № 22–31 (частично даны сведения при изучении темы, остальные данные для проекта студенты возьмут из материалов для ВСР).
6. Выдвижение гипотезы. Гипотеза – это научное предположение, выдвигаемое для объяснения каких-нибудь явлений, вообще – предположение, требующее подтверждения.
Выдвигается гипотеза: Комбинаторика интересна и имеет широкий спектр практической направленности - слайд № 32.
7. Метод проектов: три группы студентов и группа преподавателей выполняют проект
Посвященный решению задач выбора и расположения элементов некоторого, обычно конечного, множества в соответствии с заданными правилами. Например, сколькими способами можно выбрать 6 карт из колоды, состоящей из 36 карт, или сколькими способами можно составить очередь, состоящей из10 человек и т.д. Каждое правило в комбинаторике определяет способ построения некоторой конструкции, составленной из элементов исходного множества и называемой комбинацией . Основная цель комбинаторики состоит в подсчете количества комбинаций, которые можно составить из элементов исходного множества в соответствии с заданным правилом. Простейшими примерами комбинаторных конструкций являются перестановки, размещения и сочетания.
Рождение комбинаторики связано с работами Б. Паскаля и П. Ферма по поводу азартных игр, большой вклад внесли Лейбниц, Бернулли, Эйлер. В настоящее время интерес к комбинаторике связан с развитием компьютеров. Нас в комбинаторике будет интересовать возможность определения количественно различных подмножеств конечных множеств для вычисления вероятности классическим способом.
Для определения мощности множества, которое соответствует тому или иному событию, полезно разобраться с двумя правилами комбинаторики: правило произведения и правило суммы (иногда их называют принципами умножения и сложения соответственно).
Правило nроизведения: пусть из некоторого конечного множества
1-й объект можно выбрать k 1 способами,
2-ой объект - k 2 способами,
n -ый объект - k n способами. (1.1)
Тогда произвольный набор, перечисленных n объектов из данного множества можно выбрать k 1 , k 2 , …, k n способами.
Пример 1. Сколько существует трехзначных чисел с разными цифрами?
Решение . В десятичной системе исчисления десять цифр: 0,1,2,3,4,5,6,7,8,9. На первом месте может стоять любая из девяти цифр (кроме нуля). На втором месте - любая из оставшихся 9 цифр, кроме выбранной. На последнем месте любая из оставшихся 8 цифр.
По правилу произведения 9·9·8 = 648 трёхзначных чисел имеют разные цифры.
Пример 2. Из пункта в пункт ведут 3 дороги, а из пункта в пункт - 4 дороги. Сколькими способами можно совершить поездку из в через ?
Решение . В пункте есть 3 способа выбора дороги в пункт , а в пункте есть 4 способа попасть в пункт . Согласно принципу умножения, существует 3×4 = 12 способов попасть из пункта в пункт .
Правило суммы: при выполнении условий (1.1), любой из объектов можно выбрать k 1 +k 2 +…+k n способами.
Пример 3. Сколько существует способов выбора одного карандаша из коробки, содержащей 5 красных, 7 синих, 3 зеленых карандаша.
Решение . Один карандаш, по правилу суммы, можно выбрать 5+7+3 = 15 способами.
Пример 4. Пусть из города в город можно добраться одним авиамаршрутом, двумя железнодорожными маршрутами и тремя автобусными маршрутами. Сколькими способами можно добраться из города в город ?
Решение . Все условия принципа сложения здесь выполнены, поэтому, в соответствии с этим принципом, получим 1+2+3 = 6 способов.
Рассмотрим пример, иллюстрирующий различие принципов умножения и сложения.
Пример 5. В магазине электроники продаются три марки телевизоров и два вида видеомагнитофонов. У покупателя есть возможности приобрести либо телевизор, либо видеомагнитофон. Сколькими способами он может совершить одну покупку? Сколько различных комплектов, содержащих телевизор и магнитофон, можно приобрести в этом магазине, если покупатель собирается приобрести в паре и телевизор, и видеомагнитофон?
Решение . Один телевизор можно выбрать тремя способами, а магнитофон - другими двумя способами. Тогда телевизор или магнитофон можно купить 3+2=5 способами.
Во втором случае один телевизор можно выбрать тремя способами, после этого видеомагнитофон можно выбрать двумя способами. Следовательно, в силу принципа умножения, купить телевизор и видеомагнитофон можно 3×2 = 6 способами.
Рассмотрим теперь примеры, в которых применяются оба правила комбинаторики: и принцип умножения, и принцип сложения.
Пример 6. В корзине лежат 12 яблок и 10 апельсинов. Ваня выбирает либо яблоко, либо апельсин. После чего Надя выбирает из оставшихся фруктов и яблоко и апельсин. Сколько возможно таких выборов?
Решение . Ваня может выбрать яблоко 12 способами, апельсин - 10 способами. Если Ваня выбирает яблоко, то Надя может выбрать яблоко 11 способами, а апельсин - 10 способами. Если Ваня выбирает апельсин, то Надя может выбрать яблоко 12 способами, а апельсин - 9 способами. Таким образом, Ваня и Надя могут сделать свой выбор способами.
Пример 7. Есть 3 письма, каждое из которых можно послать по 6 адресам. Сколькими способами это можно сделать?
Решение . В данной задаче мы должны рассмотреть три случая:
а) все письма рассылаются по разным адресам;
б) все письма посылаются по одному адресу;
в) только два письма посылаются по одному адресу.
Если все письма рассылаются по разным адресам, то число таких способов легко находится из принципа умножения: n 1 = 6×5×4 = 120 способов. Если все письма посылаются по одному адресу, то таких способов будет n 2 = 6. Таким образом, остается рассмотреть только третий случай, когда только 2 письма посылаются по одному адресу. Выбрать какое-либо письмо мы можем 3 способами, и послать его по какому-либо выбранному адресу можем 6 способами. Оставшиеся два письма мы можем послать по оставшимся адресам 5 способами. Следовательно, послать только два письма по одному адресу мы можем n 3 =3×6×5=90 способами. Таким образом, разослать 3 письма по 6 адресам в соответствие с принципом сложения можно
способами.
Обычно в комбинаторике рассматривается идеализированный эксперимент по выбору наудачу k элементов из n . При этом элементы: а) не возвращаются обратно (схема выбора без возвращений); б) возвращаются обратно (схема выбора с возвращением).
1. Схема выбора без возвращений
Размещением из n элементов по k называют любой упорядоченный набор из k элементов, принадлежащих n - элементному множеству. Различные размещения отличны друг от друга или порядком элементов, или составом.
Число размещений из n элементов по k обозначается и вычисляется по формуле
(1.2)
где n ! = 1×2×3×…×n , 1! = 1, 0! = 1.
Пример 8. В соревнованиях участвует 10 человек, трое из них займут 1, 2, 3 место. Сколько существует различных вариантов?
Решение . В этом случае важен порядок распределения мест. Число различных вариантов равно
Перестановкой из n элементов называют размещение из n элементов по n. Число перестановок из n элементов обозначают P n и вычисляют по формуле
(1.3)
Пример 9. Сколько существует способов расстановки 10 книг на полке?
Решение . Общее число способов расстановки определяется как число перестановок (1.3) из 10 элементов и равно Р 10 = 10! = 3628 800.
2. Схема выбора с возвращениями
Если при выборе k элементов из n , элементы возвращаются обратно и упорядочиваются, то говорят, что это размещения с nовторениями .
Число размещений с повторениями:
Пример 11. В гостинице 10 комнат, каждая из которых может разместить четырех человек. Сколько существует вариантов размещения, прибывших четырех гостей?
Решение . Каждый следующий гость из 4 может быть помещён в любую из 10 комнат, так как рассматривается идеализированный опыт, поэтому общее число размещений, по формуле размещений с повторениями (1.5), равно
.
Если при выборе k элементов из n элементы возвращаются обратно без последующего упорядочивания, то говорят, что это сочетания с nовторениями. Число сочетаний с повторениями из n элементов по k определяется:
Пример 12. В магазине продается 10 видов тортов. Очередной покупатель выбил чек на три торта. Считая, что любой набор товаров равновозможен, определить число возможных заказов.
Решение . Число равновозможных заказов по формуле (1.6) равно
.
В комбинаторике изучают вопросы о том, сколько комбинаций определенного типа можно составить из данных предметов (элементов).
Рождение комбинаторики как раздела математикисвязано с трудами Б. Паскаля и П. Ферма по теории азартных игр. Большой вклад в развитие комбинаторных методов внесли Г.В. Лейбниц, Я. Бернулли и Л. Эйлер.
Французский философ, писатель, математик и физик Блез Паскаль (1623–1662) рано проявил свои выдающиеся математические способности. Круг математических интересов Паскаля был весьма разнообразен. Паскаль доказал одну из основных теорем проективной геометрии (теорема Паскаля), сконструировал суммирующую машину (арифмометр Паскаля), дал способ вычисления биномиальных коэффициентов (треугольник Паскаля), впервые точно определил и применил для доказательства метод математической индукции, сделал существенный шаг в развитии анализа бесконечно малых, сыграл важную роль в зарождении теории вероятности. В гидростатике Паскаль установил ее основной закон (закон Паскаля). “Письма к провинциалу” Паскаля явились шедевром французской классической прозы.
Готфрид Вильгельм Лейбниц (1646–1716) - немецкий философ, математик, физик и изобретатель, юрист, историк, языковед. В математике наряду с И. Ньютоном разработал дифференциальное и интегральное исчисление. Важный вклад внес в комбинаторику. С его именем, в частности, связаны теоретико-числовые задачи.
Готфрид Вильгельм Лейбниц имел мало внушительную внешность и поэтому производил впечатление довольно невзрачного человека. Однажды в Париже он зашел в книжную лавку в надежде приобрести книгу своего знакомого философа. На вопрос посетителя об этой книге книготорговец, осмотрев его с головы до ног, насмешливо бросил: “Зачем она вам? Неужели вы способны читать такие книги?” Не успел ученый ответить, как в лавку вошел сам автор книги со словами: “Великому Лейбницу привет и уважение!” Продавец никак не мог взять втолк, что перед ним действительно знаменитый Лейбниц, книги которого пользовались большим спросом среди ученых.
В дальнейшем важную роль будет играть следующая
Лемма. Пусть в множестве элементов, а в множестве-элементов. Тогда число всех различных пар, гдебудет равно.
Доказательство. Действительно, с одним элементом из множества мы можем составитьтаких различных пар, а всего в множествеэлементов.
Пусть у нас есть множество из трех элементов . Какими способами мы можем выбрать из этих элементов два?.
Определение. Размещениями множества из различных элементов поэлементовназываются комбинации, которые составлены из данныхэлементов поэлементов и отличаются либо самими элементами, либо порядком элементов.
Число всех размещений множества из элементов поэлементов обозначается через(от начальной буквы французского слова “arrangement”, что означает размещение), гдеи.
Теорема. Число размещений множества из элементов поэлементов равно
Доказательство. Пусть у нас есть элементы . Пусть- возможные размещения. Будем строить эти размещения последовательно. Сначала определим- первый элемент размещения. Из данной совокупностиэлементов его можно выбратьразличными способами. После выбора первого элементадля второго элементаостаетсяспособов выбора и т.д. Так как каждый такой выбор дает новое размещение, то все эти выборы можно свободно комбинировать между собой. Поэтому имеем:
Пример. Сколькими способами можно составить флаг, состоящий из трех горизонтальных полос различных цветов, если имеется материал пяти цветов?
Решение. Искомое число трехполосных флагов:
Определение. Перестановкой множества из элементов называется расположение элементов в определенном порядке.
Так, все различные перестановки множества из трех элементов - это
Число всех перестановок из элементов обозначается(от начальной буквы французского слова “permutation”, что значит “перестановка”, “перемещение”). Следовательно, число всех различных перестановок вычисляется по формуле
Пример. Сколькими способами можно расставить 8 ладей на шахматной доске так, чтобы они не били друг друга?
