Комбинаторика — раздел математики, в котором изучаются вопросы о том, сколько различных комбинаций, подчинённых тем или иным условиям, можно составить из заданных объектов.
Комбинаторика возникла в XVI веке. Первые комбинаторные задачи касались азартных игр. Сегодня комбинаторные методы используются для решения транспортных задач, составления планов производства и реализации продукции. Установлены связи между комбинаторикой и задачами линейного программирования, статистики. Комбинаторика используется для составления и декодирования шифров, для решения других проблем теории информации.
Значительную роль комбинаторные методы играют и в чисто математических вопросах — теории групп и их представлений, изучении основ геометрии, неассоциативных алгебр и др.
Пример комбинаторной задачи. Сколько трёхзначных чисел можно составить из цифр 0, 2, 4, 6, 8, используя в записи числа каждую из них не более одного раза?
I способ. Постараемся выписать все такие числа. На первом месте может стоять любая цифра кроме 0. Например, 2. На втором месте любая цифра из 0, 4, 6 и 8. Пусть 0. Тогда в качестве третьей цифры можно выбрать любую из 4, 6, 8. Получаем три числа
Вместо 0 на второе место можно было поставить 4, тогда третье цифрой можно записать или 0, или 6, или 8:
Рассуждая аналогично, получаем ещё две тройки трёхзначных чисел с цифрой 2 на первом месте:
Других, кроме выписанных 12-ти, трёхзначных чисел с цифрой 2 на первом месте, и удовлетворяющих условию, нет.
Если на первом месте записать цифру 4, а остальные выбирать из цифр 0, 2, 6, 8, то получим ещё 12 чисел:
По столько же трёхзначных чисел можно составить с цифрой 6 на первом месте и цифрой 8 на первом месте. Значит, искомое количество:
Вот эти числа:
204, 206, 208, 240, 246, 248, 260, 264, 268, 280, 284, 286;
402, 406, 408, 420, 426, 428, 460, 462, 468, 480, 482, 486;
602, 604, 608, 620, 624, 628, 640, 642, 648, 680, 682, 684;
802, 804, 806, 820, 824, 826, 840, 842, 846, 860, 862, 864.
Ответ: 48. ◄
Метод рассуждения, которым мы воспользовались при решении предыдущей задачи, называется перебором возможных вариантов .
Правила сложения и умножения
Комбинаторное правило сложения (правило "или") — одно из основных правил комбинаторики, утверждающее, что, если имеется n элементов и элемент A 1 можно выбрать m 1 способами, элемент A 2 можно выбрать m 2 A n можно выбрать m n способами, то выбрать или A 1 , или A 2 , или, и так далее, A n можно
m 1 + m 2 + ... + m n
способами.
Например, выбрать подарок ребёнку из 9 машинок, 7 плюшевых медведей и 3 железных дорог можно
способами.
Ответ: 19. ◄
Правило умножения (правило "и") — ещё одно из важных правил комбинаторики. Согласно ему, если элемент A 1 можно выбрать m 1 способами, элемент A 2 можно выбрать m 2 способами и так далее, элемент A n можно выбрать m n способами, то набор элементов (A 1 , A 2 , ... , A n ) можно выбрать
m 1 · m 2 · ... · m n
способами.
Например.
1) Выбрать ребёнку в подарок машинку, плюшевого медведя и железную дорогу, выбирая из 9 машинок, 7 плюшевых медведей и 3 железных дорог, можно
9 · 7 · 3 = 189
способами.
Ответ: 189.
2) Воспользуемся правилом умножения для решения задачи, уже рассмотренной выше: Сколько трёхзначных чисел можно составить из цифр 0, 2, 4, 6, 8, используя в записи числа каждую из них не более одного раза?
II способ.
0 не может стоять первым, значит первую цифру нужно выбрать из 2, 4, 6, 8 — 4 способа;
второй цифрой может быть любая из четырёх оставшихся — 4 способа;
третью цифру можно выбрать среди трёх оставшихся — 3 способа.
Итак, искомое количество трёхзначных чисел:
4 · 4 · 3 = 48.
Ответ: 48. ◄
Перестановки
Множество из n элементов называется упорядоченным , если каждому его элементу поставлено в соответствие натуральное число от 1 до n .
Перестановкой из n элементов называется любое упорядоченное множество из n элементов.
Например, из 4 элементов ♦ ♣ ♠ можно составить следующие 24 перестановки:
| ♦
♣ ♠
| ♦
♣ ♠
| ♣
♦
♠
| ♠
♦
♣
|
| ♦
♠ ♣
| ♦
♠ ♣
| ♣
♦
♠
| ♠
♦
♣
|
| ♦
♣
♠
| ♣
♦
♠
| ♣
♦
♠
| ♠
♦
♣
|
| ♦
♣ ♠
| ♣ ♠ ♦
| ♣
♠ ♦
| ♠
♣
♦
|
| ♦
♠ ♣
| ♠ ♦
♣
| ♣
♠ ♦
| ♠
♣
♦
|
| ♦
♠ ♣
| ♠ ♣ ♦
| ♣
♠ ♦
| ♠
♣
♦
|
◄
Количество перестановок из n элементов принято обозначать P n . С помощью перебора возможных вариантов легко убедиться, в том что
P 1 = 1; P 2 = 2; P 3 = 6; P 4 = 24.
Вообще, число всевозможных перестановок из n элементов равно произведению всех натуральных чисел от 1 до n , то есть n ! (читается "эн факториал"):
P n = 1 · 2 · 3 · ... · (n - 1 ) · n = n !.
Для P n справедлива рекуррентная формула:
P n = n · P n - 1 .
Значение факториала определено не только для натуральных чисел, но и для 0:
0! = 1 .
| Таблица факториалов целых чисел от
0 до
10
|
|||||||||||
| n
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|
| n
!
| 1 | 1 | 2 | 6 | 24 | 120 | 720 | 5 040 | 40 320 | 362 880 | 3 628 800 |
Например, сколькими способами 5 мальчиков и 5 девочек могут занять в театре места в одном ряду с 1-го по 10-е место, если никакие два мальчика и никакие две девочки не сидят рядом?
Возможны два случая с одинаковым количеством способов: 1) мальчики — на нечётных местах, девочки на чётных и 2) наоборот.
Рассмотрим первый случай. Мальчики по нечётным местам могут сесть
P 5 = 120
способами. Столько способов и для девочек на чётных местах. Согласно правилу умножения, мальчики — на нечётных местах, девочки на чётных могут расположиться
120 · 120 = 14 400
способами. Значит, всего способов
14 400 + 14 400 = 28 800.
Ответ: 28 800. ◄
Перестановки с повторениями
Перестановкой с повторениями из n элементов, среди которых k разных, при этом насчитывается n 1 неразличимых элементов первого типа, n 2 неразличимых элементов второго типа и так далее, n k неразличимых элементов k -го типа (где n 1 + n 2 + … + n k = n ), называется любое расположение этих элементов по n различным местам.
Число перестановок с повторениями длины n из k разных элементов, взятых соответственно по n 1 , n 2 , …, n k раз каждый обозначается и вычисляется следующим образом:$$P_{n_1,n_2, ... , n_k}=\frac{n!}{n_1!n_2! ... n_k!}~.$$
Например, сколько различных десятизначных чисел можно составить из цифр: 1, 2, 2, 3, 3, 3, 4, 4, 4, 4?
В данном случае: n = 10, n 1 = 1, n 2 = 2, n 3 = 3, n 4 = 4,$$P_{1, 2, 3, 4}=\frac{10!}{1!2! 3! 4!}=\frac{10!}{1!2! 3! 4!}=12~600.$$
Ответ: 12 600. ◄
Размещения
Размещением из n элементов по m (m ≤ n) m элементов, взятых в определённом порядке из данных n элементов.
Два размещения из n элементов по m считаются различными, если они различаются самими элементами или порядком их расположения.
Например, составим все размещения из четырёх элементов A, B, C, D по два элемента:
A B; A C;A D;
B A; B C; B D;
C A; C В; C D;
D A; D В; D C.
◄
Число всех размещений из n элементов по m обозначают \(A_n^m\) (читается: "А из n по m ") и вычисляется по любой из формул:$$A_n^m=n\cdot (n-1)\cdot (n-2)\cdot ...\cdot (n-m+1)\\A_n^m=\frac{n!}{(n-m)!}$$
Примеры задач.
1) Воспользуемся понятием размещений из n элементов по m для решения задачи, уже дважды рассмотренной ранее: Сколько трёхзначных чисел можно составить из цифр 0, 2, 4, 6, 8, используя в записи числа каждую из них не более одного раза?
II I способ.
Первую цифру можно выбрать четырьмя способами из набора 2, 4, 6, 8. В каждом из этих случаев количество пар второй и третей цифры равно числу размещений из 4 оставшихся цифр по 2. Значит искомое количество трёхзначных чисел равно:$$4\cdot A_4^2=4\cdot \frac{4!}{(4-2)!}=4\cdot \frac{4!}{2!}=4\cdot (3\cdot 4)=48.$$Ответ: 48.
2) Для полёта в космос необходимо укомплектовать экипаж из шести человек. В него должны входить: командир корабля, первый и второй его помощники, два бортинженера, один из которых старший, и один врач. Командный состав выбирается из 20 лётчиков, бортинженеры — из 15 специалистов, а врач — из 5 медиков. Сколькими способами можно укомплектовать экипаж?
Поскольку в выборе командного состава важен порядок, то командира и двух его помощников можно выбрать \(A_{20}^3\) способами. Порядок бортинженеров тоже важен, значит, для их выбора существует \(A_{15}^2\) способов. Врач всего один, для его выбора существует 5 способов. Воспользуемся комбинаторным правилом умножения и найдём количество возможных экипажей корабля:$$A_{20}^3\cdot A_{15}^2\cdot 5=\frac{20!}{17!}\cdot \frac{15!}{13!}\cdot 5=(18\cdot 19\cdot 20)\cdot (14\cdot 15)\cdot 5=7~182~000.$$Ответ: 7 182 000. ◄
Понятно, что, если m = n , то$$A_n^m=A_n^n=P_n=n!.$$
Справедливо также, что, если m = n - 1 , то$$A_n^{n-1}=A_n^n=P_n=n!.$$
Размещения с повторениями
Помимо обычных размещений бывают и размещения с повторениями или выборки с возвращением .
Пусть имеется n различных объектов. Выберем из них m штук, действуя по следующему принципу. Возьмём любой, но не будем его устанавливать в какой-то ряд, а просто запишем под номером 1 его название, сам же объект после этого вернём к остальным. Затем опять из всех n объектов выберем один (в том числе, возможно, и тот, который был только что взят), запишем его название, пометив номером 2, и снова вернём объект обратно. И так далее, пока не получим m названий.
Размещения с повторениями обозначаются \(\overline{A}_n^m\) и, согласно правилу умножения, вычисляются по формуле$$\overline{A}_n^m=n^m.$$Заметим, что здесь допустим случай, когда m > n , то есть выбранных объектов больше, чем их всего имеется. Это неудивительно: каждый объект после "использования" возвращается обратно и может быть использован повторно.
Например, количество вариантов шестизначного пароля, в котором каждый знак является цифрой от 0 до 9 или буквой латинского алфавита (одна и та же строчная и прописная буква — один символ) и может повторяться, равно:$$\overline{A}_{10+26}^6=\overline{A}_{36}^6=36^6=2~176~782~336.$$Если же строчные и прописные буквы считаются различными символами (как это обычно и бывает), то количество возможных паролей становится ещё более колоссальным:$$\overline{A}_{10+26+26}^6=\overline{A}_{62}^6=62^6=56~800~235~584.$$
◄
Сочетания
Сочетанием из n элементов по m (m ≤ n) называется любое множество, состоящее из m элементов, выбранных из данных n элементов.
В отличии от размещений в сочетаниях не имеет значения, в каком порядке указаны элементы. Два сочетания из n элементов по m считаются различными, если они различаются хотя бы одним элементом.
Например, составим все сочетания из четырёх элементов A, B, C, D по два элемента:
A B; A C;A D;
B C; B D;
C D .
◄
Число всех сочетаний из n элементов по m обозначают \(C_n^m\) (читается: "C из n по m ") и вычисляется по любой из формул:$$C_n^m=\frac{A_n^m}{P_m}$$$$C_n^m=\frac{n\cdot (n-1)\cdot (n-2)~\cdot~ ...~\cdot~ (n-m+1)}{1\cdot2\cdot3~\cdot~...~\cdot ~m}$$$$C_n^m=\frac{n!}{m!\cdot (n-m)!}.$$
Примеры задач.
1) Бригада, занимающаяся ремонтом школы, состоит из 12 маляров и 5 плотников. Из них для ремонта физкультурного зала надо выделить 4 маляров и 2 плотников. Сколькими способами можно это сделать?
Так как порядок маляров в каждой выбранной четвёрке и порядок плотников в каждой выбранной паре не имеет значения, то, согласно комбинаторному правилу умножения, искомое количество способов равно:$$C_{12}^4 \cdot C_5^2 =\frac{12!}{4!\cdot 8!}\cdot \frac{5!}{2!\cdot 3!}=\frac{9\cdot10\cdot11\cdot12}{1\cdot2\cdot3\cdot4}\cdot \frac{4\cdot5}{1\cdot 2}=4~950.$$Ответ: 4 950. ◄
2) В классе обучаются 30 учащихся, среди которых 13 мальчиков и 17 девочек. Сколькими способами можно сформировать команду из 7 учащихся этого класса, если в неё должна входить хотя бы одна девочка?
Количество всех возможных команд по 7 человек из класса равно \(C_{30}^7\). Количество команд в которых только мальчики — \(C_{13}^7\). Значит, количество команд, в которых есть хотя бы одна девочка, равно:$$C_{30}^7 - C_{13}^7 =\frac{30!}{7!\cdot 23!} - \frac{13!}{7!\cdot 6!}=2~035~800-1~716=2~034~084.$$Ответ: 2 034 084. ◄
Сочетания с повторениями
Помимо обычных сочетаний рассматривают сочетания с повторениями .
Пусть в множестве имеется n объектов. Выберем из них m штук, действуя по следующему принципу. Возьмём любой, но не будем его устанавливать в какой-то ряд, а просто запишем, сам же объект после этого вернём к остальным. Затем опять из всех n объектов выберем один (в том числе, возможно, и тот, который был взят и записан ранее), запишем его название и снова вернём объект обратно. И так далее, пока не получим m названий.
Принципиальное отличие от размещений с повторениями заключается в том, что в данном случае элементы списка не нумеруются. Например, список "A, С, A, В" и список "А, А, В, С" считаются одинаковыми.
Сочетания с повторениями обозначаются \(\overline{C}_n^m\) и вычисляются по формуле$$\overline{C}_n^m=P_{m,~n-1}=\frac{(m+n-1)!}{m!\cdot (n-1)!}.$$И ещё один способ записи той же формулы:$$\overline{C}_n^m=C_{m+n-1}^m=\frac{(m+n-1)!}{m!\cdot (n-1)!}.$$Заметим, что подобно размещениям с повторениями, допустим случай, когда m > n , то есть выбранных объектов больше, чем их всего имеется. Действительно, каждый объект после "использования" возвращается обратно и может быть использован снова и снова.
Например, выясним сколькими способами можно купить 7 пирожных в кондитерском отделе, если в продаже 4 их сорта?
Естественно полагать, что количество пирожных каждого вида не меньше 7, и при желании можно купить только пирожные одного из них. Так как порядок в котором кладут купленные пирожные в коробку не важен, то имеем дело с сочетаниями с повторениями. Так как нужно выбрать 7 пирожных из 4 его видов, то искомое количество способов равно:$$\overline{C}_4^7=\frac{(7+4-1)!}{7!\cdot (4-1)!}=\frac{10!}{7!\cdot 3!}=\frac{8\cdot 9\cdot 10}{1\cdot 2\cdot 3}=120.$$
Ответ: 120. ◄
Бином Ньютона и биномиальные коэффициенты
Равенство$$(x+a)^n=C_n^0x^na^0+C_n^1x^{n-1}a^1+...+C_n^mx^{n-m}a^m+...+C_n^nx^0a^n$$называют биномом Ньютона или формулой Ньютона . Правая часть равенства называется биномиальным разложением в сумму , а коэффициенты \(C_n^0,~C_n^1,~...~,~C_n^n\) — биномиальными коэффициентами .
Свойства биномиальных коэффициентов:
\(~~~~~~~~1.~~C_n^0=C_n^n=1\\ ~~~~~~~~2.~~C_n^m=C_n^{n-m}\\ ~~~~~~~~3.~~C_n^m=C_{n-1}^{m-1}+C_{n-1}^{m}\\ ~~~~~~~~4.~~C_n^0+C_n^1+C_n^2+~...~+C_n^n=2^n\\ ~~~~~~~~5.~~C_n^0+C_n^2+C_n^4+~... =C_n^1+C_n^3+C_n^5+~...=2^{n-1}\\ ~~~~~~~~6.~~C_n^n+C_{n+1}^n+C_{n+2}^n+~...~+C_{n+m-1}^n=C_{n+m}^{n+1}\\ \)
Свойства биномиального разложения:
1. Число всех членов разложения на единицу больше показателя степени бинома,
то есть равно n + 1 .
2. Сумма показателей степеней x и a каждого члена разложения равна показателю степени бинома,
то есть (n - m) + m = n .
3. Общий член разложения (обозначается T n +1 ) имеет вид$$T_{n+1}=C_n^m x^{n-m}a^m,~~~~m=0,~1,~2,~...~,~n.$$
Треугольник Паскаля
Все возможные значения биномиальных коэффициентов (числа сочетаний) для каждого показателя степени бинома n можно записать в виде бесконечной треугольной таблицы. Такая таблица называется треугольником Паскаля:
| \(C_0^0\) | ||||||||||
| \(C_1^0\) | \(C_1^1\) | |||||||||
| \(C_2^0\) | \(C_2^1\) | \(C_2^2\) | ||||||||
| \(C_3^0\) | \(C_3^1\) | \(C_3^2\) | \(C_3^3\) | |||||||
| \(C_4^0\) | \(C_4^1\) | \(C_4^2\) | \(C_4^3\) | \(C_4^4\) | ||||||
| \(C_5^0\) | \(C_5^1\) | \(C_5^2\) | \(C_5^3\) | \(C_5^4\) | \(C_5^5\) |
|||||
| . . . | . . . | . . . |
В этом треугольнике крайние числа в каждой строке равны 1. Действительно, \(C_n^0=C_n^n=1\). А каждое не крайнее число равно сумме двух чисел предыдущей строки, стоящих над ним: \(C_n^m=C_{n-1}^{m-1}+C_{n-1}^{m}\).
Таким образом, этот треугольник предлагает ещё один (рекуррентный) способ вычисления чисел \(C_n^m\):
| n
= 0 | 1 | ||||||||||||||||
| n
= 1 | 1 | 1 | |||||||||||||||
| n
= 2 | 1 | 2 | 1 | ||||||||||||||
| n
= 3 | 1 | 3 | 3 | 1 | |||||||||||||
| n
= 4 | 1 | 4 | 6 | 4 | 1 | ||||||||||||
| n
= 5 | 1 | 5 | 10 | 10 | 5 | 1 | |||||||||||
| n
= 6 | 1 | 6 | 15 | 20 | 15 | 6 | 1 | ||||||||||
| n
= 7 | 1 | 7 | 21 | 35 | 35 | 21 | 7 | 1 | |||||||||
| n
= 8 | 1 | 8 | 28 | 56 | 70 | 56 | 28 | 8 | 1 |
||||||||
| ... | ... | ... | ... | ... |
Реферат на тему:
Выполнил ученик 10 класса «В»
средней школы №53
Глухов Михаил Александрович
г. Набережные Челны
2002 г.
Содержание
| Из истории комбинаторики_________________________________________ | 3 |
| Правило суммы___________________________________________________ | 4 |
| - | |
| Правило произведения_____________________________________________ | 4 |
| Примеры задач____________________________________________________ | - |
| Пересекающиеся множества________________________________________ | 5 |
| Примеры задач____________________________________________________ | - |
| Круги Эйлера_____________________________________________________ | - |
| Размещения без повторений________________________________________ | 6 |
| Примеры задач____________________________________________________ | - |
| Перестановки без повторений_______________________________________ | 7 |
| Примеры задач____________________________________________________ | - |
| Сочетания без повторений__________________________________________ | 8 |
| Примеры задач____________________________________________________ | - |
| Размещения и сочетания без повторений______________________________ | 9 |
| Примеры задач____________________________________________________ | - |
| Перестановки с повторениями_______________________________________ | 9 |
| Примеры задач____________________________________________________ | - |
| Задачи для самостоятельного решения________________________________ | 10 |
| Список используемой литературы___________________________________ | 11 |
Из истории комбинаторики
Комбинаторика занимается различного вида соединениями, которые можно образовать из элементов конечного множества. Некоторые элементы комбинаторики были известны в Индии еще во II в. до н. э. Нидийцы умели вычислять числа, которые сейчас называют "сочетания". В XII в. Бхаскара вычислял некоторые виды сочетаний и перестановок. Предполагают, что индийские ученые изучали соединения в связи с применением их в поэтике, науке о структуре стиха и поэтических произведениях. Например, в связи с подсчетом возможных сочетаний ударных (долгих) и безударных (кратких) слогов стопы из n слогов. Как научная дисциплина, комбинаторика сформировалась в XVII в. В книге "Теория и практика арифметики" (1656 г.) французский автор А. Также посвящает сочетаниям и перестановкам целую главу.
Б. Паскаль в "Трактате об арифметическом треугольнике" и в "Трактате о числовых порядках" (1665 г.) изложил учение о биномиальных коэффициентах. П. Ферма знал о связях математических квадратов и фигурных чисел с теорией соединений. Термин "комбинаторика" стал употребляться после опубликования Лейбницем в 1665 г. работы "Рассуждение о комбинаторном искусстве", в которой впервые дано научное обоснование теории сочетаний и перестановок. Изучением размещений впервые занимался Я. Бернулли во второй части своей книги "Ars conjectandi" (искусство предугадывания) в 1713 г. Современная символика сочетаний была предложена разными авторами учебных руководств только в XIX в.
Все разнообразие комбинаторных формул может быть выведено из двух основных утверждений, касающихся конечных множеств – правило суммы и правило произведения.
Правило суммы
Если конечные множества не пересекаются, то число элементов X U Y {или} равно сумме числа элементов множества X и числа элементов множества Y.
То есть, если на первой полке стоит X книг, а на второй Y, то выбрать книгу из первой или второй полки, можно X+Y способами.
Примеры задач
Ученик должен выполнить практическую работу по математике. Ему предложили на выбор 17 тем по алгебре и 13 тем по геометрии. Сколькими способами он может выбрать одну тему для практической работы?
Решение: X=17, Y=13
По правилу суммы X U Y=17+13=30 тем.
Имеется 5 билетов денежно-вещевой лотереи, 6 билетов спортлото и 10 билетов автомотолотереи. Сколькими способами можно выбрать один билет из спортлото или автомотолотереи?
Решение: Так как денежно-вещевая лотерея в выборе не участвует, то всего 6+10=16 вариантов.
Правило произведения
Если элемент X можно выбрать k способами, а элемент Y-m способами то пару (X,Y) можно выбрать k*m способами.
То есть, если на первой полке стоит 5 книг, а на второй 10, то выбрать одну книгу с первой полки и одну со второй можно 5*10=50 способами.
Примеры задач
Переплетчик должен переплести 12 различных книг в красный, зеленый и коричневые переплеты. Сколькими способами он может это сделать?
Решение: Имеется 12 книг и 3 цвета, значит по правилу произведения возможно 12*3=36 вариантов переплета.
Сколько существует пятизначных чисел, которые одинаково читаются слева направо и справа налево?
Решение: В таких числах последняя цифра будет такая же, как и первая, а предпоследняя - как и вторая. Третья цифра будет любой. Это можно представить в виде XYZYX , где Y и Z -любые цифры, а X - не ноль. Значит по правилу произведения количество цифр одинаково читающихся как слева направо, так и справа налево равно 9*10*10=900 вариантов.
Пересекающиеся множества
Но бывает, что множества X и Y пересекаются, тогда пользуются формулой
, где X и Y - множества, а - область пересечения. Примеры задач20 человекзнаютанглийскийи 10 - немецкий, изних 5 знаютианглийский, инемецкий. СколькоЧеловеквсего?
Ответ: 10+20-5=25 человек.
Также часто для наглядного решения задачи применяются круги Эйлера. Например:
Из 100 туристов, отправляющихся в заграничное путешествие, немецким языком владеют 30 человек, английским - 28, французским - 42. Английским и немецким одновременно владеют 8 человек, английским и французским - 10, немецким и французским - 5, всеми тремя языками - 3. Сколько туристов не владеют ни одним языком?Решение: Выразим условие этой задачи графически. Обозначим кругом тех, кто знает английский, другим кругом - тех, кто знает французский, и третьим кругом - тех, кто знают немецкий.
Всеми тремя языками владеют три туриста, значит, в общей части кругов вписываем число 3. Английским и французским языком владеют 10 человек, а 3 из них владеют еще и немецким. Следовательно, только английским и французским владеют 10-3=7 человек.Аналогично получаем, что только английским и немецким владеют 8-3=5 человек, а немецким и французским 5-3=2 туриста. Вносим эти данные в соответствующие части.
Определим теперь, сколько человек владеют только одним из перечисленных языков. Немецкий знают 30 человек, но 5+3+2=10 из них владеют и другими языками, следовательно, только немецкий знают 20 человек. Аналогично получаем, что одним английским владеют 13 человек, а одним французским - 30 человек.По условию задачи всего 100 туристов. 20+13+30+5+7+2+3=80 туристов знают хотя бы один язык, следовательно, 20 человек не владеют ни одним из данных языков.
Размещения без повторений.
Сколько можно составить телефонных номеров из 6 цифр каждый, так чтобы все цифры были различны?
Это пример задачи на размещение без повторений. Размещаются здесь 10 цифр по 6. А варианты, при которых одинаковые цифры стоят в разном порядке считаются разными.
Если X-множество, состоящие из n элементов, m≤n, то размещением без повторений из n элементов множества X по m называется упорядоченное множество X, содержащее m элементов называется упорядоченное множество X, содержащее m элементов.
Количество всех размещений из n элементов по m обозначают
n! - n-факториал (factorial анг. сомножитель) произведение чисел натурального ряда от 1 до какого либо числа nЗадача
Сколькими способами 4 юноши могут пригласить четырех из шести девушек на танец?
Решение : два юноши не могут одновременно пригласить одну и ту же девушку. И варианты, при которых одни и те же девушки танцуют с разными юношами считаются, разными, поэтому:
Возможно 360 вариантов.
Перестановки без повторений
В случае n=m (см. размещения без повторений) из n элементов по m называется перестановкой множества x.
Количество всех перестановок из n элементов обозначают P n.
Действительно при n=m:
Примеры задач
Сколько различных шестизначных чисел можно составить из цифр 0, 1, 2, 3, 4,5, если цифры в числе не повторяются?
1) Найдем количество всех перестановок из этих цифр: P 6 =6!=720
2) 0 не может стоять впереди числа, поэтому от этого числа необходимо отнять количество перестановок, при котором 0 стоит впереди. А это P 5 =5!=120.
P 6 -P 5 =720-120=600
Проказница Мартышка
Да косолапый Мишка
Затеяли играть квартет
Стой, братцы стой! –
Кричит Мартышка, - погодите!
Как музыке идти?
Ведь вы не так сидите…
И так, и этак пересаживались – опять музыка на лад не идет.
Правило сложения используется в том случае, если у нас есть два или более множеств, которые попарно не пересекаются, то есть не имеют общих элементов. И нам нужно найти сколько элементов содержится в объединении этих множеств. В этом случае мы складываем число элементов в каждом множестве. Простейший пример: если у нас есть две корзинки с фруктами: в одной 5 яблок, а в другой 7 груш. Если мы эти фрукты пересыпаем в одну корзинку (объединяем множества), тогда в новой корзинке окажется 5+7=12 фруктов.
Правило умножения
Правило умножения используется в том случае, если у нас есть два множества, и мы составляем всевозможные пары из элементов этих множеств. Например, если взять множество, состоящее из 5-ти яблок и множество, состоящее из 7-ми груш и составить всевозможные пары из этих фруктов, то мы получим всевозможных пар.
Действительно. Возьмем первое яблоко. Мы можем положить к нему любую из семи груш, то есть получаем 7 пар. Возьмем второе яблоко, и к нему мы также можем положить любую из 7-ми груш, получаем ещё 7 пар. И так далее. Всего получается пар.
Правило умножения легко понять, если попытаться ответить, например, на такой вопрос: "сколько существует двузначных чисел? "
Пусть двузначное чиcло имеет вид , где - число десятков, - число единиц. При этом цифра может принимать значения от 1 до 9 (цифра 0 не может стоять на первом месте, так как в этом случаем мы получим однозначное число), цифра может принимать значения от 0 до 9.
Пусть , и у нас есть 10 вариантов цифр, которые могут стоять на втором месте. Тогда мы имеем 10 двузначных чисел, содержащих 1 десяток.
Затем мы берем и так же получаем 10 двузначных чисел, у которых теперь уже 2 десятка.
Так как цифра может принимать 9 различных значений, то получаем двузначных чисел.
Зная, что на первом месте может стоять 9 различных цифр, а на втором - 10, мы получаем комбинаций этих цифр, то есть все возможные двузначные числа. Здесь важно понимать, что любая цифра, стоящая на первом месте, может сочетаться с любой цифрой, стоящей на втором месте.
В общем случае правило умножения звучит так:
Если элемент A можно выбрать n способами, и при любом выборе A элемент B можно выбрать m способами, то пару (A, B) можно выбрать n·m способами. Это правило распространяется на любое число независимо выбираемых элементов.
Если мы хотим ответить на вопрос, сколько существует трехзначных чисел, мы заметим, что в трехзначном числе первая цифра может принимать 9 значений, вторая - 10, и третья - 10 значений. И мы получаем трехзначных чисел.
Формула включений-исключений
используется в том случае, если нам нужно найти число элементов в объединении двух множеств, в том случае, если эти множества пересекаются.
Пусть множество А содержит n элементов, множество В содержит m элементов, и пересечение этих множеств содержит k элементов. То есть k элементов содержатся и в множестве А, и в множестве В. Тогда объединение множеств содержит m+n-k элементов.
Действительно, при объединении двух множеств мы k элементов посчитали два раза, и теперь один раз мы должны их вычесть.
Число элементов в множестве обозначается общепринятым значком #. Тогда формула для подсчета числа элементов в объединении трех множеств имеет вид:
#
#
#
#
#
#
#
#
Рассмотрим примеры задач.
1. Сколько трехзначных чисел содержит хотя бы одну цифру 3?
Если вопрос задачи содержит слова "хотя бы", то в большинстве случаев сначала надо ответить на противоположное утверждение.
Найдем, сколько трехзначных чисел НЕ содержит цифру 3. В этом случае на первом, втором и третьем месте в записи числа может стоять любая цифра кроме 3. То есть первая цифра может принимать 8 значений, вторая - 9, и третья - 9 значений. Тогда мы получаем трехзначных чисел, которые НЕ содержит цифру 3. Следовательно, остальные числа содержат хотя бы одну цифру 3.
2. Сколько четырехзначных чисел, кратных 5.
Мы знаем, что число делится на 5, если оно оканчивается на 0 или 5. Следовательно, в четырехзначном числе
последняя цифра может принимать только два значения: 0 и 5.
Первая цифра
может принимать 9 значений, вторая
- 10, и третья
- 10 значений, четвертая
- 2 значения.
Тогда мы получаем четырехзначных чисел, которые делятся на 5.
Перестановки
Воспользуемся правилом умножения чтобы ответить на вопрос, "сколькими способами можно построить 7 человек в шеренгу?" .
Человека, стоящего первым в шеренге можно выбрать семью способами, второго можно выбрать из оставшихся шести человек, то есть шестью способами. Третьего, соответственно, пятью. И так далее. Последнего можно выбрать единственным способом. Всего получаем способов построить 7 человек в шеренгу.
В общем случае, если мы имеем объектов, которые хотим расположить в определенном порядке (пронумеровать их), то мы получим
способов расположения этих объектов.
Факториалом натурального числа называется произведение всех натуральных чисел от 1 до :
По определению 0!=1; 1!=1.
Перестановкой из предметов называется любой способ нумерации этих предметов (способ расположения их в ряд).
Число перестановок предметов равно .
3. Имеется 10 компьютерных дисков и 10 коробок от них. Найдите вероятность того, что случайным образом уложив диски в коробки, мы обнаружим, что
1. Каждый диск лежит в своей коробке.
2. Хотя бы один диск лежит не в своей коробке.
3. Два определенных диска перепутаны местами, а остальные в своих коробках.
4. Ровно один лежит не в своей коробке, а остальные - в своих коробках.
1. Пронумеруем диски и коробки. Расположим коробки в определенной последовательности. Нам нужно, чтобы при случайном расположении дисков в ряд, их номера тоже оказались расположены в той же последовательности.
Расположить 10 чисел в определенной последовательности можно единственным способом, то есть мы имеем 1 благоприятный исход.
Расположить 10 чисел в произвольном порядке можно 10! способами.
Следовательно, вероятность того, что каждый диск окажется в своей коробке равна
2. Событие "хотя бы один диск лежит не в свой коробке " противоположно событию "", и его вероятность равна
3. Событие "два определенных диска перепутаны местами, а остальные в своих коробках", также как событие "каждый диск лежит в своей коробке ", имеет единственный благоприятный исход, поэтому вероятность этого события равна
4. Событие "ровно один лежит не в своей коробке, а остальные - в своих коробках " невозможно, так как если один диск лежит не своей коробке, то обязательно должен найтись ещё один, который так же лежит не в своей коробке. Поэтому вероятность этого события равна нулю.
4. Слово "МАТЕМАТИКА" написали на полоске картона и разрезали полоску на буквы. Найдите вероятность того, что составив все эти буквы случайным образом в ряд, мы снова получим слово "МАТЕМАТИКА".
МАТЕМАТИКА"?
Вероятность того, что на первом месте будет стоять буква М равна 2/10 - у нас две буквы М, и всего 10 букв.
Вероятность того, что на втором месте будет стоять буква А равна 3/9 - у нас осталось 9 букв, из которых 3 буквы А.
Вероятность того, что на втором месте будет стоять буква Т равна 2/8 - у нас осталось 8 букв, из которых 2 буквы Т.
Пронумеруем все буквы в слове "МАТЕМАТИКА". Найдем, сколькими способами мы можем их расположить в определенном порядке. В слове 10 букв, и мы можем их расположить 10!=3628800 различными способами.
Поскольку в слове есть одинаковые буквы, то при перестановке этих букв мы получим то же слово:
в слове "МАТЕМАТИКА" 2 буквы "М"; 3 буквы "А"; 2 буквы "Т", следовательно по правилу произведения это дает нам способов перестановки этих букв с сохранением слова "МАТЕМАТИКА".
Таким образом, вероятность снова получить слово "МАТЕМАТИКА" равна:
Сколько буквосочетаний можно составить из букв слова "МАТЕМАТИКА" ?
Из 10 букв слова "МАТЕМАТИКА" можно составить 10! буквосочетаний. Но некоторые из них будут одинаковыми, так как при перестановке одинаковых букв, мы будем получать те же буквосочетания. То есть в итоге мы получим
буквосочетаний.
Размещения
В задачах по теории вероятностей часто возникает необходимость определить, сколькими способами можно выбрать определенное число предметов и расположить их в определенном порядке.
5. Сколько существует различных вариантов выбора 4-х кандидатур из 9-ти специалистов для поездки в 4 различных страны?
Воспользуемся правилом умножения.
В первую страну мы выбираем из 9 специалистов, то есть у нас 9 вариантов выбора. После того, как специалист для поездки в первую страну выбран, у нас осталось 8 специалистов, и для поездки во вторую страну у нас 8 вариантов выбора. И так далее... в четвертую страну мы можем выбрать кандидата из 6 специалистов.
Таким образом, мы получаем вариантов выбора 4-х кандидатур из 9-ти специалистов для поездки в 4 различных страны.
Обобщим эту задачу на случай выбора k кандидатур из n специалистов для поездки в k различных стран.
Рассуждая аналогичным образом, мы получаем
вариантов.
Если умножить и разделить это выражение на , то получим следующую формулу:
В этой задаче из множества, состоящего из элементов мы выбрали упорядоченные подмножества (для нас был важен порядок расположения элементов в подмножестве) , состоящие из элементов. Задача сводилась к нахождению числа таких подмножеств.
Такие упорядоченные подмножества называются размещениями из n элементов по k.
Размещением (из n по k) называется упорядоченное подмножество из различных элементов из некоторого множества , состоящего из различных элементов.
Число размещений из элементов по обозначается и находится по формуле:
Размещения с повторениями
6. Игральную кость бросают трижды. Сколько различных комбинаций выпавших очков при этом получится?
При бросании кости первый раз мы получим 6 различных вариантов: 1 очко, 2, 3... или 6. Аналогично при бросании кости во второй и в третий раз мы получим также по 6 различных вариантов. По правилу умножения получим число различных комбинаций трех чисел, принимающих значения от 1 до 6:
В общем случае:
Пусть у нас есть множество , состоящее из элементов.
Любой упорядоченный набор элементов множества, состоящего из элементов называется размещением с повторением из элементов по . Число различных размещений с повторениями равно
Действительно. Представим ящик с пронумерованными шарами. Мы вынимаем шар, записываем его номер и возвращаем обратно, и так раз. Сколько комбинаций из номеров мы можем получить?
Поскольку шары каждый раз возвращаются, каждый раз, вынимая шар из коробки, в которой шаров, мы можем получить различных чисел. По правилу умножения имеем
Сочетания
Рассмотрим задачу, аналогичную задаче 5, но с существенным отличием.
7. Сколько существует различных вариантов выбора 4-х кандидатур из 9-ти специалистов?
В этой задаче нам нужно выбрать 4 кандидатуры, но при этом не важно, в каком порядке мы их выбираем, нас интересует только состав выбранных элементов, но не порядок их расположения.
Если бы нас интересовал порядок расположения элементов, как в задаче 5, то мы могли применили бы формулу для нахождения числа размещений из 9 по 4:
4 различных элемента можно расположить в определенном порядке 4! различными способами. Поскольку нас не интересует порядок расположения элементов, число способов, которыми мы можем выбрать 4 элемента, не располагая их в определенном порядке, уменьшается в 4! раза по сравнению с предыдущей задачей (так как для данной задачи различное расположение данных элементов считается одним способом), и мы получаем
способов.
В этой задаче появляется понятие сочетания .
Сочетаниями из n элементов по k элементов называются подмножества, состоящие из k элементов множества (множества, состоящего из n элементов).
Внимание! Одно сочетание от другого отличается только составом выбранных элементов (но не порядком их расположения, как у размещений).
Число сочетаний из n элементов по k элементов обозначается
и находится по формуле:
Число сочетаний из n по k показывает, сколькими способами мы можем выбрать k элементов из n элементов, или сколькими способами мы можем расположить k объектов по n местам.
Легко заметить, что
8. В коробке лежат 8 красных карандашей и 4 синих. Из коробки наугад вынимают 4 карандаша. Какова вероятность того, что среди них окажется 2 красных и 2 синих?
Всего в коробке 12 карандашей. Найдем, сколькими способами способами можно извлечь из коробки 4 карандаша. Так как нас не интересует порядок, в котором карандаши извлекаются из коробки, а только состав карандашей, это число равно числу сочетаний из 12 по 4:
Из 8 красных карандашей можно извлечь два карандаша 
способами.
Из 4 синих карандашей можно извлечь два карандаша 
способами.
По правилу произведения получаем, что извлечь 2 синих и 2 красных карандаша можно способами.
Таким образом, искомая вероятность равна:
Метод шаров и перегородок
9. Сколькими способами можно разложить 10 шаров в 4 коробки? Предполагается, что некоторые коробки могут оказаться пустыми.
Рассмотрим 10 шаров:
Будем "раскладывать шары по коробкам", ставя перегородки.
Например, так:
В этом примере в первой коробке 3 шара, во второй - 2, в третьей - 4, и в четвертой - 2. Переставляя шары и перегородки, мы получаем различные комбинации шаров в коробках. Например, переставив последний шар в первой коробке и первую внутреннюю перегородку, мы получим такую комбинацию:
Таким образом, мы получаем различное число шаров в коробках, комбинируя позиции 10-ти шаров и 3-х внутренних перегородок. Чтобы определить, сколько различных комбинаций мы можем получить, нам нужно найти число сочетаний из 13 по 3. (Или, что то же самое, что число сочетаний из 13 по 10.) Столько способов выбрать 3 места для перегородок из 13 возможных позиций. Или, что то же самое, 10 мест для шаров.
10. Сколько решений имеет уравнение в целых неотрицательных числах?
Так как переменные могут принимать только целые неотрицательные значения, следовательно, у нас есть 10 переменных, и они могут принимать значения 0, 1, 2, 3 и 4. Представим, что у нас есть 10 коробок (это переменные), и мы должны разложить по этим коробкам 4 шара. Сколько шаров попадет в коробку, таково значение соответствующей переменной. Если у нас 10 коробок, следовательно, 10-1=9 внутренних перегородки. И 4 шара. Всего 13 мест. Нам надо расположить на этих 13 местах 4 шара. Число таких возможностей:
В общем случае, если нам нужно разложить шаров в коробок, мы получаем комбинации из шаров и внутренней перегородки. И число таких комбинаций равно числу сочетаний из по .
В этой задаче мы имели дело с сочетаниями с повторениями.
Сочетания с повторениями
Сочетаниями из элементов по элементов с повторениями называются группы, содержащие элементов, причем каждый элемент принадлежит к одному из типов.
Что такое сочетания из элементов по элементов с повторениями можно понять с помощью такого мысленного эксперимента. Представим ящик с пронумерованными шарами. Мы вынимаем шар, записываем его номер и возвращаем обратно, и так раз. В отличие от размещений с повторениями нас не интересует порядок записанных чисел, а только их состав. Например, группы чисел {1,1,2,1,3,1,2} и {1,1,1,1,2,2,3} считаются одинаковыми. Сколько таких групп из номеров мы можем получить?
В конечном итоге нас интересует сколько элементов каждого типа (всего n типов элементов) содержится в каждой группе (из k элементов) , и сколько таких различных вариантов может быть. То есть мы находим, сколько в целых неотрицательных решений имеет уравнение уравнение - задача аналогична задаче по раскладыванию n шаров в k коробок.
Число сочетаний с повторениями находится по такой формуле:
Таким образом, число сочетаний с повторениями - это количество способов представить число k в виде суммы n слагаемых.
Элементы комбинаторики
Комбинаторика – это наука о расположении элементов в определенном порядке и о подсчете числа способов такого расположения.
Комбинаторный принцип умножения если одну часть действия можно выполнить способами, а другую - способами, то все действие можно выполнить числом способов.
Пример. Пусть требуется составить набор из ручки, карандаша и линейки. Имеется:
5 различных ручек,
7 различных карандашей,
10 различных линеек.
Сколькими способами можно составить требуемыйнабор?
Решение. Действием в данном случае является составление набора из ручки, карандаша и линейки; действие распадается на три этапа (части): выбрать ручку, выбрать линейку и выбрать карандаш. Первую часть действия – выбрать ручку – можно выполнить пятью способами, вторую часть действия – выбрать карандаш – можно выполнить семью способами, третью часть действия – выбрать линейку – можно выполнить десятью способами. Тогда все действие можно выполнить
Число способов. Т.е. возможно 350 вариантов такого набора.
Пример. Сколько существуетнаборов длиныиз нулей и единиц?
Решение. Действием в данном случае является составление набора длины из нулей и единиц.
Набор будет составлен, если все позиций (мест) будут заполнены нулями и единицами. Действие распадается на частей: заполнить первую позицию, вторую и т.д., заполнить - ю позицию. Первую часть действия – написать первую компоненту - можно двумя способами: можно написать 0, а можно написать 1, написать вторую компоненту тоже можно двумя способами, и так все мест в наборе: на каждом месте можно написать либо 0 либо 1:
Тогда все действие согласно комбинаторному принципу умножения можно выполнить числом способов:
Комбинаторный принцип сложения. Если два действия взаимно исключают друг друга, и одно из них можно выполнить способами, а другое - способами, то оба действия можно выполнить числом способов.
Пример.
Выборкой
объема из множества 
называется всякая
последовательность из элементов множества .
Если элементы в выборке не повторяются, то выборка называется бесповторной , иначе – выборкой с повторениями
При бесповторной выборке все равно, каким образом осуществляется выбор: берутся все элементы сразу,или же поочередно (по одному).
Расположение элементоввыборки в определенном порядке называется упорядочением , при этом выборка называется упорядоченной , в противном случае – неупорядоченной .
Рассмотрим бесповторную выборку
Расположение различных элементов в определенном порядке называется перестановкой без повторений из элементов.
Например, на множестве из трех элементов возможны следующие перестановки: .
Число различных перестановок без повторений из элементов обозначается и равно , т.е.
Сочетанием без повторений из элементов по называется неупорядоченное - элементное подмножество -элементного множества. Число сочетаний без повторений из элементов по равно :
Например, требуется подсчитать, сколькими способами можно составить бригаду из трех человек для дежурства вгруппе из 30 человек. Поскольку порядок расположения людей в бригаде не фиксируется и люди не повторяются , то мы имеем случай сочетаний из 30 элементов по 3 без повторений:
Таким образом, бригаду дежурных из трех человек в группе из 30 человек можно выбрать 4060 различными способами.
Размещением без повторений из элементов по называется упорядоченное - элементное подмножество -элементного множества.
Теорема.
Число размещений без повторений из элементов по равно:
Доказательство . Чтобы получить упорядоченное - элементное подмножество -элементного множества, нужно выполнить два этапа: выбрать элементов из (это можно выполнить числом способов) и затем упорядочить выбранные элементы (это можно сделать числом способов). Согласно комбинаторному принципу умножения, все действие -получить упорядоченное - элементное подмножество -элементного множества – можно числом способов.
Свойства сочетаний без повторений :
Доказательство.
Поскольку 
и
, то
утверждаемое очевидно.
2)
(без доказательства).
Значения могут быть найдены не расчетом по формуле количества сочетаний, а с помощью так называемого треугольника Паскаля. (Блез Паскаль (1623 – 1662) – французский математик).
Этот треугольник имеет вид:
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
Закономерность его построения такова: складывая две рядом стоящие числа, получаем число, стоящее ниже между ними. Первая строчка – значения числа сочетаний из 1 (), вторая – из 2 ( - слева направо), и т.д.
Рассмотрим выборку с повторениями
Пусть имеется выборка из элементов, причем элементов из них - одинаковые.
1. Число различных перестановок на элементах такой выборки равно:
- число перестановок с повторениями на множестве из элементов
2. Сочетание с повторениями из элементов по - неупорядоченная выборка элементов с возвращением из множества, содержащегоэлементов:
- число различных сочетанийс повторениями из элементов по
3. Размещения с повторениями из элементов по - расположение различных шаров по различным ячейкам
- число различных размещений с повторениями
Пример . Сколько различных 4-буквенных слов можно составить из символов ?
Решение. Другими словами, требуется найти число перестановок с повторениями на4 элементах выборки, в которойдва элемента одинаковы:
Пример . Сколько различных перестановок можно составить избукв словаАБАКАН?
Решение. Требуется найти число перестановок на множестве из 6 элементов, среди которых три элемента одинаковы:
.
Верно обобщение рассматриваемой формулы: число различных перестановок на множестве из элементов, среди которых имеется
Элементов первого вида,
Элементов второго вида,
Элементов - го вида
равно:
Пример. Сколько перестановок можно получить из букв слова КОЛОКОЛА?
Решение. Требуется найти число перестановок с повторениями на множестве из 8 букв, среди которых:
буква К повторяется 2 раза;
буква О повторяется 3 раза;
буква Л повторяется 2 раза
буква А повторяется 1 раз.
Таким образом, .
Пример. Сколькими способами можно составить набор из 5 шоколадок, если имеются шоколадки трех сортов в количестве по 10 штук каждого вида?
Решение. Поскольку при составлении шоколадного набора порядок расположения шоколадок не важен, то используем для подсчета формулу сочетаний с повторениями:
Пример. Сколькими способами можно рассадить 7 человек по 9 вагонам?
Решение. Поскольку по условию задачи в один вагон могут сесть несколько человек, и поскольку рассадка зависит от того кто в каком вагоне находится, то используем формулу размещения с повторениями:
Пример. Сколькими способами можно рассадить 7 человек по 9 вагонам по одному в вагон?
Решение. Поскольку по условию задачи в один вагон могут сесть только один человек, и поскольку рассадка зависит от того кто в каком вагоне находится, то используем формулу размещений без повторений:
Эту же задачу можно решить, применяя комбинаторный принцип умножения: действие – рассадить 7 человек распадается на 7 этапов: разместить первого пассажира, разместить второго пассажира, …, разместить седьмого пассажира. Первый этап – размещение первого пассажира можно выполнить 9 способами, второго пассажира тоже можно разместить9 способами, и т.д. :
Пример. Сколько различных сигналов можно составить из четырех флажков различных цветов, если каждый сигнал должен состоять не менее чем из двух флажков?
Решение. Составить сигнал можно из двух флажков, из трех или из четырех. Перечисленные ситуации взаимно исключают друг друга (два флажка – это не три и не четыре),поэтому вычислим, сколькими способами можно составить сигнал в каждой из перечисленных ситуаций,и сложим полученные результаты.
Действие – составить сигнал – означает выбрать флажки из четырех и расположить их в определенном порядке. Таким образом, в каждом случае нужно выполнить два этапа: первый - выбрать флажки, второй – расположить выбранные флажки в определенном порядке.
Составляем сигналы из двух флажков: выбрать два
флажка из четырех можно 
различными способами,
и расположить выбранные два флажка в определенном порядке можно числом способов. Таким
образом, согласно комбинаторному принципу умножения, можно составить различных сигналов из двух флажков.
способами. Значит,
можно составить различных сигнала из
четырех флажков.
Применим теперь комбинаторный принцип сложения:
всего существует 
сигналов из не менее,
чем двух флажков.
Пример. Номер автомобиля состоит из трех букв и трех цифр. Сколько различных номеров можно составить, используя 10 цифр и алфавит в 30 букв.
Очевидно, что количество всех возможных комбинаций из 10 цифр по 4 равно 10.000.
Число всех возможных комбинаций из 30 букв по две равно
.
Если учесть возможность того, что буквы могут повторяться, то число повторяющихся комбинаций равно 30 (одна возможность повтора для каждой буквы). Итого, полное количество комбинаций по две буквы равно 900.
Если к номеру добавляется еще одна буква из алфавита в 30 букв, то количество комбинаций увеличивается в 30 раз, т.е. достигает 27.000 комбинаций.
Окончательно, т.к. каждой буквенной комбинации можно поставить в соответствие числовую комбинацию, то полное количество автомобильных номеров равно 270.000.000.
Е.Г. Hикифорова
Конспект урока по теме «Элементы комбинаторики»
Цели:
О бучающие:
Формирование основных понятий комбинаторики: размещения из mэлементов по n, сочетания из m элементов по n, перестановки из nэлементов;
Формирование умений и навыков вычисления значений комбинаторных выражений по формулам, решения простейших комбинаторных задач;
Развивающие:
Развитие умения анализировать, обобщать изучаемые факты, выделять и сравнивать существенные признаки, выбирать наиболее эффективные способы решения задач в зависимости от конкретных условий; рефлексия способов и условий действия; контроль и оценка процесса и результатов деятельности;
Воспитательные:
Воспитание интереса к дисциплине, честности, аккуратности, эстетического отношения к оформлению математических решений, воспитание умения слушать и вступать в диалог, участвовать в коллективном обсуждении проблем, интегрироваться в группу сверстников и строить продуктивное взаимодействие, настойчивости в достижении цели и заинтересованности в конечном результате труда; прививать чувство патриотизма.
Обучающийся должен:
знать:
Определения трех важнейших понятий комбинаторики:
Размещения из n элементов по m;
Сочетания из n элементов по m;
Перестановки из n элементов, а также, формулы вычисления их количества.
уметь:
Отличать задачи на «перестановки», «сочетания», «размещения» друг от друга;
Применять основные комбинаторные формулы при решении простейших комбинаторных задач.
ХОД УРОКА
1. Организационный момент.
Ребята, каждая группа в течении года дежурит по техникуму.
Являются ли бригады дежурных в группах постоянными? Скажите, а сколько всего существует способов назначить из n студентов группы mдежурных. В математике есть раздел, который занимается решением подобных задач. Этот раздел называется комбинаторикой.
2. Сообщение темы, целей урока.
Тема сегодняшнего урока «Основные понятия комбинаторики». Давайте вместе попробуем сформулировать цели урока
Ознакомиться с основными понятиями комбинаторики (размещения, сочетания, перестановки)
Научиться решать простейшие комбинаторные задачи
3. Актуализация опорных знаний.
Прежде чем перейти к изучению нового материала, повторим то, что имеет к нему непосредственное отношение. Это уже известное вам понятие «факториал». Итак, кто помнит, что называют «n-факториалом»? Запишите формулу.
Чему, к примеру, равны 2!, 3!, 4!, 5!, 6! ? А кто сможет показать вычисления на доске? А чему равен 1! ? 0! ? Какие значения в данном случае может принимать n?
4. Изложение нового материала.
4.1. Введение общих понятий
Комбинаторикой называют область математики, которая изучает вопросы о числе различных комбинаций (удовлетворяющих тем или иным условиям), которые можно составить из данных элементов.
Комбинаторика – раздел математики, в котором исследуются и решаются задачи выбора элементов из исходного множества и расположения их в некоторой комбинации, составляемой по заданным правилам.
Группы, составленные из каких-либо элементов, называются соединениями .
Различают три вида соединений: размещения , перестановки и сочетания .
Задачи, в которых производится подсчет возможных различных соединений, составленных из конечного числа элементов по некоторому правилу, называются комбинаторными , а раздел математики, занимающийся их решением, - комбинаторикой . Рассмотрим три основных вида соединений и формулы вычисления их количества. Для этого сначала рассмотрим 2 задачи, которые помогут нам сосредоточиться на сути новых понятий.
4.2. Создание проблемной ситуации.
Тексты двух задач на слайде:
Задача 1. В некотором учреждении имеются две различные вакантные должности, на каждую из которых претендуют три сотрудника: A, B, C. Сколькими способами из этих трех кандидатов можно выбрать два лица на эти должности?
Задача 2. Для участия в соревнованиях требуется выбрать двоих спортсменов из трех кандидатов: A, B, C. Сколькими способами можно осуществить этот выбор?
Студентам предлагается два проблемных задания: 1) установить различие между этими двумя внешне схожими задачами и 2) предположить, в какой задаче результат будет больше, и почему. После этого предлагается решить эти задачи методом перебора всевозможных вариантов.
Р ешение задачи 1. AB, BA, BC, CB, AC, CA (всего шесть способов).
Решение задачи 2. AB, BC, AC (всего три способа).
Преподаватель обращает внимание студентов на то, что эти задачи оказались похожими только внешне, из-за того, что в обеих присутствуют два числа: m=3 – общее количество элементов и n=2 – количество выбранных элементов. Но в первой задаче составляются упорядоченные соединения, тогда как во второй задаче порядок следования элементов в соединении не имеет значения.
А если вместо чисел 3 и 2 будут например числа 8 и 3. Подойдет ли этот метод для решения этих задач? Поэтому существуют комбинаторные выражения (формулы) для этих соединений
5.3. Лекция «Основные комбинаторные понятия и формулы».
1) Размещения.
Определение. Размещениями из m элементов по n элементов (n ≤ m) называются такие соединения, каждое из которых содержит n элементов, взятых из m данных разных элементов, и которые отличаются одно от другого либо самими элементами, либо порядком их расположения.
Число размещений из m элементов по n обозначают (от французского «arrangement» - «размещение») и вычисляют по формуле:
Пример 1. Решим задачу 1 с помощью этой формулы:
2) Перестановки.
Определение. Перестановкой из n элементов называют размещение из n элементов по n.
Число перестановок из n элементов обозначается
и вычисляется по формуле:
Задача. Сколькими способами можно расположить в столбик три детали конструктора, различающиеся по цвету?
Ответ:6.
3) Сочетания.
Определение.
Сочетаниями из m элементов по n элементов (n ≤ m) называются такие соединения, каждое из которых содержит n элементов, взятых из m данных элементов, и которые отличаются друг от друга по крайней мере одним элементом.
Число сочетаний из n элементов по m обозначают
(от французского «combination» - «сочетание») и вычисляют по формуле:
Пример 2. Решим задачу 2 с помощью этой формулы:
А теперь решим ту же задачу для случая m=8, n=3:
Снова, как и ожидалось, результат в первой задаче оказался больше, чем во второй.
Мы рассмотрели теоретические основы комбинаторики. Теперь перейдем к этапу закрепления новых знаний при решении задач.
6. Закрепление материала
6.1. Игра «Математическое лото»
Студентам раздаются наборы раздаточных материалов «Математического лото» (по одному на парту). Каждый комплект состоит из 16 математических заданий по основам комбинаторики, картонного листа в виде матрицы размерности 4 на 4 с написанными в ячейках числами-ответами и цветной фотографии, разрезанной на 16 равных прямоугольника. Все части фотографии пронумерованы в соответствии с порядком заданий и перемешаны. Задача студентов – решить 16 заданий, соответствующие частям разрезанной фотографии, и в соответствии с полученными числовыми ответами отыскать их место на картонной матрице, сложив в итоге фото. Задание выполняется как соревнование между малыми группами По 3-4 человека. Определяются три пары, которые не только сложат картинку раньше всех, но и представят в письменном виде все подробные решения.
Перед началом игры преподаватель мотивирует студентов на активное участие в ней, сообщая, что это упражнение позволит наилучшим образом сформировать навыки комбинаторных вычислений, что значительно упростит выполнение домашнего задания. Кроме того, выполняя это упражнение, можно совместить полезное с приятным, так как результат вызовет эстетические чувства.
Задания.
Вычислите.
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
.
Решения:
В завершении игры объявляются и поощряются победители.
6.2. Решение комбинаторных задач.
При решении комбинаторных задач важно научиться различать виды соединений.
Чтобы отличать задачи на подсчёт числа размещений от задач на подсчёт числа сочетаний, определим, важен или нет порядок в следующих выборках:
а) судья хоккейного матча и его помощник;
б) три ноты в аккорде;
в) «Шесть человек останутся убирать класс!»
г) две серии для просмотра из многосерийного фильма.
Ответ: а)да; б)нет; в)нет; г)да.
Задача 1. Сколькими способами могут занять I, II, III места 8 участниц финального забега на дистанции 100 м?
Ответ: 366.
Задача 2. Из 30 обучающихся группы надо выбрать старосту и помощника старосты. Сколькими способами это можно сделать?
Ответ: 870.
Задача 3. Сколькими способами можно составить букет из трёх цветков, выбирая цветы из девяти имеющихся?
Ответ: 84.
Задача 4. В группе 7 человек успешно занимаются математикой. Сколькими способами можно выбрать из них двоих для участия в математической олимпиаде?
Ответ:21
6.3 Самостоятельная работа
Проверь себя
1 .Определите вид соединений:
а) Соединения из n элементов, отличающиеся друг от друга только порядком расположения в них элементов, называются __________ перестановки
б) Соединения из m элементов по n , отличающихся друг от друга только составом элементов, называются _______________ сочетания
в) Соединения из m элементов по n , отличающихся друг от друга составом элементом и порядком их расположения, называются _________ размещения
2 .Восстановите соответствие типов соединений и формул для их подсчёта
А.сочетания Ответ:
Подведение итогов самостоятельной работы
7. Подведение итогов урока
Обобщаются новые знания, делаются выводы о достигнутых целях урока. Поощряются активные студенты, выставляются обоснованные преподавателем оценки.
8. Домашнее задание
Подготовка сообщений по темам: «Истории комбинаторики», «Комбинаторика и ее применение в реальной жизни».