Элементы комбинаторики сочетание примеры. Задачи по комбинаторике

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

Перестановками называют комбинации, состоящие из одних и тех же 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 способами, то пара объектов (А,В) в указанном порядке может быть выбрана способами.

Чтобы в материале было легче ориентироваться, добавлю содержание данной темы:

Введение. Множества и выборки.

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

Для работы нам понадобятся кое-какие вспомогательные сведения. Начнём с такого фундаментального математического понятия как множество. Подробно понятие множества было раскрыто в теме "Понятие множества. Способы задания множеств" .

Очень краткий рассказ про множества : показать\скрыть

Если вкратце: множеством именуют некую совокупность объектов. Записывают множества в фигурных скобках. Порядок записи элементов роли не играет; повторения элементов не допускаются. Например, множество цифр числа 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$. Количество размещений без повторений из $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)$-выборка с повторениями.

Количество размещений с повторениями из $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)$-выборка без повторений.

По сути, перестановка без повторений есть частный случай размещения без повторений, когда объём выборки равен мощности исходного множества. Количество перестановок без повторений из $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)$-выборка без повторений.

Общее количество сочетаний без повторений из $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)$-выборка с повторениями.

Общее количество сочетаний с повторениями из $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 разных элементов взятых в определенном порядке. В перестановке важен порядок следования элементов, и в перестановке должны быть задействованы все N элементов.

Задача : Найти все возможные перестановки для последовательности чисел 1, 2, 3.
Существуют следующие перестановки:

1: 1 2 3
2: 1 3 2
3: 2 1 3
4: 2 3 1
5: 3 1 2
6: 3 2 1

Перестановки без повторений

Количество перестановок для N различных элементов составляет N! . Действительно:

на первое место может быть помещен любой из N элементов (всего вариантов N ),
на вторую позицию может быть помещен любой из оставшихся (N-1) элементов (итого вариантов N·(N-1) ),
если продолжить данную последовательность для всех N мест, то получим: N·(N-1)·(N-2)· … ·1 , то есть всего N! перестановок.

Рассмотрим задачу получения всех перестановок чисел 1…N (то есть последовательности длины N ), где каждое из чисел входит ровно по 1 разу. Существует множество вариантов порядка получения перестановок. Однако наиболее часто решается задача генерации перестановок в лексикографическом порядке (см. пример выше). При этом все перестановки сортируются сначала по первому числу, затем по второму и т.д. в порядке возрастания. Таким образом, первой будет перестановка 1 2 … N , а последней — N N-1 … 1 .

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

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

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

Реализация на С++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

#include
using namespace std;

{
int s = a[i];
a[i] = a[j];
a[j] = s;
}
bool NextSet(int *a, int n)
{
int j = n - 2;
while (j != -1 && a[j] >= a) j--;
if (j == -1)
return false; // больше перестановок нет
int k = n - 1;
while (a[j] >= a[k]) k--;
swap(a, j, k);
int l = j + 1, r = n - 1;
while (l swap(a, l++, r--);
return true;
}
void Print(int *a, int n) // вывод перестановки
{
static int num = 1; // номер перестановки
cout.width(3);
cout << num++ << ": " ;
for (int i = 0; i < n; i++)
cout << a[i] << " " ;
cout << endl;
}
int main()
{
int n, *a;
cout << "N = " ;
cin >> n;
a = new int [n];
for (int i = 0; i < n; i++)
a[i] = i + 1;
Print(a, n);
while (NextSet(a, n))
Print(a, n);
cin.get(); cin.get();
return 0;
}

Результат выполнения

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

Особого внимания заслуживает задача генерации перестановок N элементов в случае если элементы последовательности могут повторяться. Допустим, исходная последовательность состоит из элементов n 1 , n 2 ... n k , где элемент n 1 повторяется r 1 раз, n 2 повторяется r 2 раз и т.д. При этом n 1 +n 2 +...+n k =N . Если мы будем считать все n 1 +n 2 +...+n k элементов перестановки с повторениями различными, то всего различных вариантов перестановок (n 1 +n 2 +...+n k)! . Однако среди этих перестановок не все различны. В самом деле, все r 1 элементов n 1 мы можем переставлять местами друг с другом, и от этого перестановка не изменится. Точно так же, можем переставлять элементы n 2 , n 3 и т. д. В итоге имеем r 1 ! вариантов записи одной и той же перестановки с различным расположением повторяющихся элементов n 1 . Таким образом, всякая перестановка может быть записана r 1 !·r 2 !·...·r k ! способами. Следовательно, число различных перестановок с повторениями равно

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

#include
using namespace std;
void swap(int *a, int i, int j)
{
int s = a[i];
a[i] = a[j];
a[j] = s;
}
bool NextSet(int *a, int n)
{
int j = n - 2;
while (j != -1 && a[j] >= a) j--;
if (j == -1)
return false; // больше перестановок нет
int k = n - 1;
while (a[j] >= a[k]) k--;
swap(a, j, k);
int l = j + 1, r = n - 1; // сортируем оставшуюся часть последовательности
while (l swap(a, l++, r--);
return true;
}
void Print(int *a, int n) // вывод перестановки
{
static int num = 1; // номер перестановки
cout.width(3); // ширина поля вывода номера перестановки
cout << num++ << ": " ;
for (int i = 0; i < n; i++)
cout << a[i] << " " ;
cout << endl;
}
int main()
{
int n, *a;
cout << "N = " ;
cin >> n;
a = new int [n];
for (int i = 0; i < n; i++)
a[i] = i + 1;
a = 1; // повторяющийся элемент
Print(a, n);
while (NextSet(a, n))
Print(a, n);
cin.get(); cin.get();
return 0;
}

Результат работы приведенного выше алгоритма:

Элементы комбинаторики: перестановки, сочетания, размещения.

“Число, положение и комбинация – три
взаимно пересекающиеся, но различные
сферы мысли, к которым можно
отнести все математические идеи”.
Джозеф Сильвестр (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. Метод проектов: три группы студентов и группа преподавателей выполняют проект

КОМБИНАТОРИКА

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

Правила сложения и умножения в комбинаторике

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

Пример 1.

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

Решение

Дежурным можно назначить либо мальчика, либо девочку, т.е. дежурным может быть любой из 16 мальчиков, либо любая из 10 девочек.

По правилу суммы получаем, что одного дежурного можно назначить 16+10=26 способами.

Правило произведения. Пусть требуется выполнить последовательно k действий. Если первое действие можно выполнить n 1 способами, второе действие n 2 способами, третье - n 3 способами и так до k-го действия, которое можно выполнить n k способами, то все k действий вместе могут быть выполнены:

способами.

Пример 2.

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

Решение

Первым дежурным можно назначить либо мальчика, либо девочку. Т.к. в классе учится 16 мальчиков и 10 девочек, то назначить первого дежурного можно 16+10=26 способами.

После того, как мы выбрали первого дежурного, второго мы можем выбрать из оставшихся 25 человек, т.е. 25-ю способами.

По теореме умножения двое дежурных могут быть выбраны 26*25=650 способами.

Сочетания без повторений. Сочетания с повторениями

Классической задачей комбинаторики является задача о числе сочетаний без повторений, содержание которой можно выразить вопросом: сколькими способами можно выбрать m из n различных предметов ?

Пример 3.

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

Решение

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

Рассмотрим задачу о числе сочетаний с повторениями: имеется по r одинаковых предметов каждого из n различных типов; сколькими способами можно выбрать m () из этих (n*r) предметов?

Пример 4.

В кондитерском магазине продавались 4 сорта пирожных: наполеоны, эклеры, песочные и слоеные. Сколькими способами можно купить 7 пирожных?

Решение

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

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

Классической задачей комбинаторики является задача о числе размещений без повторений, содержание которой можно выразить вопросом: сколькими способами можно выбрать и разместить по m различным местам m из n различных предметов?

Пример 5.

В некоторой газете 12 страниц. Необходимо на страницах этой газеты поместить четыре фотографии. Сколькими способами можно это сделать, если ни одна страница газеты не должна содержать более одной фотографии?

Решение.

В данной задаче мы не просто выбираем фотографии, а размещаем их на определенных страницах газеты, причем каждая страница газеты должна содержать не более одной фотографии. Таким образом, задача сводится к классической задаче об определении числа размещений без повторений из 12 элементов по 4 элемента:

Таким образом, 4 фотографии на 12 страницах можно расположить 11880 способами.

Также классической задачей комбинаторики является задача о числе размещений с повторениями, содержание которой можно выразить вопросом: сколькими способами можно вы б рать и разместить по m различным местам m из n предметов, с реди которых есть одинаковые?

Пример 6.

У мальчика остались от набора для настольной игры штампы с цифрами 1, 3 и 7. Он решил с помощью этих штампов нанести на все книги пятизначные номера- составить каталог. Сколько различных пятизначных номеров может составить мальчик?

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

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

Пример 7.

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

Решение

Генеральной совокупностью являются 4 буквы слова «брак» (б, р, а, к). Число «слов» определяется перестановками этих 4 букв, т. е.

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