Рассмотрим задачу подсчета числа выборок из данного множества в общем виде. Пусть имеется некоторое множество N , состоящее из n элементов. Любое подмножество, состоящее из m элементов можно рассматривать без учета их порядка, так и с его учетом, т.е. при изменении порядка переходим к другой m – выборке.
Сформулируем следующие определения:
Размещения без повторения
Размещением без повторения из n элементов по m N , содержащее m различных элементов .
Из определения следует, что два размещения отличаются друг от друга, как элементами, так и их порядком, даже если элементы одинаковы.
Теорема 3 . Число размещений без повторения равно произведению m сомножителей, наибольшим из которых является число n . Записывают:
Перестановки без повторений
Перестановками из n элементов называются различные упорядочения множества N .
Из этого определения следует, что две перестановки отличаются только порядком элементов и их можно рассматривать как частный случай размещений.
Теорема 4 . Число различных перестановок без повторений вычисляется по формуле
Сочетания без повторений
Сочетанием без повторения из n элементов по m называется любое неупорядоченное подмножество множества N , содержащее m различных элементов.
Из определения следует, что два сочетания различаются только элементами, порядок не важен.
Теорема 5 . Число сочетаний без повторений вычисляют по одной из следующих формул:
Пример 1 . В комнате 5 стульев. Сколькими способами можно разместить на них
а) 7 человек; б) 5 человек; в) 3 человека?
Решение:
а) Прежде всего надо выбрать 5 человек
из 7 для посадки на стулья. Это можно
сделать
способом. С каждым выбором конкретной
пятерки можно произвести
перестановок местами. Согласно теореме
умножения искомое число способов посадки
равно.
Замечание: Задачу можно решать, используя только теорему произведения, рассуждая следующим образом: для посадки на 1-й стул имеется 7 вариантов, на 2-й стул-6 вариантов, на 3-й -5, на 4-й -4 и на 5-й -3. Тогда число способов посадки 7 человек на 5 стульев равно . Решения обоими способами согласуются, так как
б) Решение очевидно
-
в)
- число выборов занимаемых стульев.
- число размещений
трех человек на трех выбранных стульях.
Общее число выборов равно .
Не трудно проверить
формулы
;
;
Число всех подмножеств множества, состоящего из n элементов.
Размещения с повторением
Размещением с повторением из n элементов по m называется всякое упорядоченное подмножество множества N , состоящее из m элементов так, что любой элемент ожжет входить в это подмножество от 1 до m раз, либо вообще в нем отсутствовать .
Число
размещений с повторением обозначают
и вычисляют по формуле, представляющей
собой следствие из теоремы умножения:
Пример 2
.
Пусть дано множество из трех букв N
= {a,
b,
c}.
Назовем словом любой набор из букв,
входящих в это множество. Найдем
количество слов длиной 2, которые можно
составить из этих букв:
.
Замечание:
Очевидно, размещения с повторением
можно рассматривать и при
.
Пример 3 . Требуется из букв {a, b}, составить всевозможные слова длиной 3. Сколькими способами это можно сделать?
Ответ
:
Комбинаторика — раздел математики, в котором изучаются вопросы о том, сколько различных комбинаций, подчинённых тем или иным условиям, можно составить из заданных объектов.
Комбинаторика возникла в 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 |
||||||||
| ... | ... | ... | ... | ... |
КОМБИНАТОРИКА
Комбинаторика - раздел математики, который изучает задачи выбора и расположения элементов из некоторого основного множества в соответствии с заданными правилами. Формулы и принципы комбинаторики используются в теории вероятностей для подсчета вероятности случайных событий и, соответственно, получения законов распределения случайных величин. Это, в свою очередь, позволяет исследовать закономерности массовых случайных явлений, что является весьма важным для правильного понимания статистических закономерностей, проявляющихся в природе и технике.
Правила сложения и умножения в комбинаторике
Правило суммы. Если два действия А и В взаимно исключают друг друга, причем действие А можно выполнить 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), т. е. есть одинаковые предметы.
Пример 8.
Сколько разных буквосочетаний можно сделать из букв слова «Миссисипи»?
Решение
Здесь 1 буква «м», 4 буквы «и», 3 буквы «c» и 1 буква «п», всего 9 букв. Следовательно, число перестановок с повторениями равно
ОПОРНЫЙ КОНСПЕКТ ПО РАЗДЕЛУ "КОМБИНАТОРИКА"
В комбинаторике изучают вопросы о том, сколько комбинаций определенного типа можно составить из данных предметов (элементов).
Рождение комбинаторики как раздела математикисвязано с трудами Б. Паскаля и П. Ферма по теории азартных игр. Большой вклад в развитие комбинаторных методов внесли Г.В. Лейбниц, Я. Бернулли и Л. Эйлер.
Французский философ, писатель, математик и физик Блез Паскаль (1623–1662) рано проявил свои выдающиеся математические способности. Круг математических интересов Паскаля был весьма разнообразен. Паскаль доказал одну из основных теорем проективной геометрии (теорема Паскаля), сконструировал суммирующую машину (арифмометр Паскаля), дал способ вычисления биномиальных коэффициентов (треугольник Паскаля), впервые точно определил и применил для доказательства метод математической индукции, сделал существенный шаг в развитии анализа бесконечно малых, сыграл важную роль в зарождении теории вероятности. В гидростатике Паскаль установил ее основной закон (закон Паскаля). “Письма к провинциалу” Паскаля явились шедевром французской классической прозы.
Готфрид Вильгельм Лейбниц (1646–1716) - немецкий философ, математик, физик и изобретатель, юрист, историк, языковед. В математике наряду с И. Ньютоном разработал дифференциальное и интегральное исчисление. Важный вклад внес в комбинаторику. С его именем, в частности, связаны теоретико-числовые задачи.
Готфрид Вильгельм Лейбниц имел мало внушительную внешность и поэтому производил впечатление довольно невзрачного человека. Однажды в Париже он зашел в книжную лавку в надежде приобрести книгу своего знакомого философа. На вопрос посетителя об этой книге книготорговец, осмотрев его с головы до ног, насмешливо бросил: “Зачем она вам? Неужели вы способны читать такие книги?” Не успел ученый ответить, как в лавку вошел сам автор книги со словами: “Великому Лейбницу привет и уважение!” Продавец никак не мог взять втолк, что перед ним действительно знаменитый Лейбниц, книги которого пользовались большим спросом среди ученых.
В дальнейшем важную роль будет играть следующая
Лемма. Пусть в множестве элементов, а в множестве-элементов. Тогда число всех различных пар, гдебудет равно.
Доказательство. Действительно, с одним элементом из множества мы можем составитьтаких различных пар, а всего в множествеэлементов.
Размещения, перестановки, сочетания
Пусть у нас есть множество из трех элементов . Какими способами мы можем выбрать из этих элементов два?.
Определение. Размещениями множества из различных элементов поэлементовназываются комбинации, которые составлены из данныхэлементов поэлементов и отличаются либо самими элементами, либо порядком элементов.
Число всех размещений множества из элементов поэлементов обозначается через(от начальной буквы французского слова “arrangement”, что означает размещение), гдеи.
Теорема. Число размещений множества из элементов поэлементов равно
Доказательство. Пусть у нас есть элементы . Пусть- возможные размещения. Будем строить эти размещения последовательно. Сначала определим- первый элемент размещения. Из данной совокупностиэлементов его можно выбратьразличными способами. После выбора первого элементадля второго элементаостаетсяспособов выбора и т.д. Так как каждый такой выбор дает новое размещение, то все эти выборы можно свободно комбинировать между собой. Поэтому имеем:
Пример. Сколькими способами можно составить флаг, состоящий из трех горизонтальных полос различных цветов, если имеется материал пяти цветов?
Решение. Искомое число трехполосных флагов:
Определение. Перестановкой множества из элементов называется расположение элементов в определенном порядке.
Так, все различные перестановки множества из трех элементов - это
Число всех перестановок из элементов обозначается(от начальной буквы французского слова “permutation”, что значит “перестановка”, “перемещение”). Следовательно, число всех различных перестановок вычисляется по формуле
Пример. Сколькими способами можно расставить 8 ладей на шахматной доске так, чтобы они не били друг друга?
Цель занятия: уметь применять основные формулы комбинаторики и знать условия применения этих формул; знать свойства биномиальных коэффициентов и уметь определять разложение бинома при конкретных значениях n.
План занятия:
1. Число размещений.
2. Число перестановок.
3. Число сочетаний.
4. Повторения.
5. Бином Ньютона. Треугольник Паскаля.
Методические указания по изучению темы
Во многих практических случаях возникает необходимость подсчитать количество возможных комбинаций объектов, удовлетворяющих определенным условиям. Такие задачи называются комбинаторными. Разнообразие комбинаторных задач не поддается исчерпывающему описанию, но среди них есть целый ряд особенно часто встречающихся, для которых известны способы подсчета.
Комбинаторика – область математики, в которой изучаются вопросы о том, сколько различных комбинаций, подчиненных тем или иным условиям, можно составить из элементов, принадлежащих данному множеству. Термин «комбинаторика» происходит от латинского слова combina – сочетать, соединять.
Пусть есть некоторое множество из n элементов: x 1, x 2, x 3, …, x n .
Из этого множества можно образовать различные подмножества, то есть выборки, каждая из которых содержит m элементов (0 ≤ m ≤ n). Различают упорядоченные выборки (размещения), перестановки и неупорядоченные выборки (сочетания).
Размещения
Размещениями n различных элементов по m элементов, которые отличаются либо составом элементов, либо их порядком.
Число размещений из n элементов по m элементов обозначают (А – первая буква французского слова arrangement, что означает размещение, приведение в порядок) и вычисляют по формуле:
Понятие факториала
Произведение n натуральных чисел от 1 до n обозначается символом n ! (n факториал), то есть
Например, 2!=
5!= 
Заметим, что удобно рассчитывать 0!, полагая по определению, 0!=1.
Примеры:
Из последних двух формул следует, что
Пример.
В однокруговом турнире по футболу участвуют 8 команд. Сколько существует вариантов призовой тройки?
Решение : Так как порядок команд в призовой тройке важен, то мы имеем дело с размещениями. Тогда
(вариантов).
Пример.
Сколькими способами можно выбрать три лица на три различные должности из десяти кандидатов?
Решение:
(способов).
Пример.
Сколько можно составить телефонных номеров из 5 цифр так, чтобы в каждом отдельно взятом номере все цифры были различными?
(телефонных номеров).
Перестановки
Перестановками называют комбинации, состоящие из одних и тех же n различных элементов и отличающиеся только порядком их расположения.
Число всех возможных перестановок из n элементов обозначают P n (P – первая буква французского слова permutation, что означает перестановка) и вычисляют по формуле:
Пример.
В финальном забеге на 100 метров участвуют 8 спортсменов. Сколько существует вариантов протокола забега?
Решение:
В данном случае речь идёт обо всех перестановках из 8 элементов. Тогда (вариантов)
Пример.
Сколькими различными способами могут разместиться на скамейке10 человек?
Решение:
(способов)
Пример.
Сколькими способами можно разместить 7 лиц за столом, на котором поставлено 7 столовых приборов?
Решение:
(способов).
Сочетания
Сочетаниями называют комбинации, составленные из n различных элементов по m элементов, которые отличаются хотя бы одним элементом.
Число сочетаний вычисляют по формуле: 
(С - первая буква французского слова combinasion).
Пример.
Сколькими способами можно выбрать три лица на три одинаковые должности из десяти кандидатов?
Решение :
(способов).
Пример.
Сколькими способами можно выбрать три детали из ящика, содержащего 15 деталей?
Решение:
(способов).
Другой вид формул числа размещений и числа сочетаний
; 
, то есть 
.
Свойства числа сочетаний:
5) 
При решении задач комбинаторики используют следующие правила:
Правило суммы. Если некоторый объект А может быть выбран из совокупности объектов n способами, а другой объект В – k способами, то объект «либо А, либо В» можно выбрать n+k способами.
Правило произведения. Если некоторый объект А может быть выбран из совокупности объектов n способами и после каждого такого выбора другой объект В – k способами, то пара объектов (А, В) в указанном порядке может быть выбрана n×k способами.
Если некоторые элементы повторяются, то в этом случае комбинации с повторениями вычисляют по другим формулам.
Размещения с повторениями
Число размещений по m
элементов с повторениями из n
различных элементов равно n m
,то есть 
Пример.
Из цифр 1,2,3,4,5 можно составить 5 3 =125 трехзначных чисел, если в одном и том же числе могут попадаться и одинаковые цифры.
Перестановки с повторениями
Если среди n элементов есть n 1 элементов одного вида, n 2 элементов другого вида и т.д., то число перестановок с повторениями
где 
Пример.
Сколько различных перестановок букв можно сделать в слове «математика»?
Решение:
Сочетания с повторениями
Число сочетаний с повторениями из n различных элементов по m элементов равно числу сочетаний без повторений из (n +m -1) различных элементов по m элементов:
Пример.
Найти число сочетаний с повторениями из четырех элементов a , b , c , d по 3 элемента.
Решение:
Искомое число будет 
Бином Ньютона
Для произвольного положительного целого числа n справедлива следующая формула:
Это бином Ньютона. Коэффициенты называются биномиальными коэффициентами.
При n = 2 получим формулу ;
При n = 3 получим формулу .
Пример. Определить разложение при n=4.
Решение:
Биномиальные коэффициенты обладают рядом свойств:
2. 
;
Рассмотрим следующий треугольник:
………………………….
Строка под номером n содержит биномиальные коэффициенты разложения . Воспользовавшись свойством , можно заметить, что каждый внутренний элемент треугольника равен сумме двух элементов, расположенных над ним, а боковые элементы треугольника – единицы:
……………………….
Это треугольник Паскаля. Он позволяет быстро найти значения биномиальных коэффициентов.
В русскоязычной литературе перестановки, составленные из n различных элементов выбором по m элементов, которые отличаются либо составом элементов, либо их порядком, обычно называют размещениями, а под перестановками понимают всю совокупность комбинаций, состоящих из одних и тех же n различных элементов и отличающихся только порядком их расположения. В этом смысле число всех возможных перестановок для множества из n различных элементов считается по формуле факториала Pn = n! или в Excel «=ФАКТР(N)» (см. рис. № 1)
Например, если ввести «=ПЕРЕСТ(3;2)», получим 6. Это 6 комбинации: (1,2), (2,1), (1,3), (3,1), (2,3), (3,2).
А вот встроенная функция «=ЧИСЛКОМБ(N;K)» выдает комбинаторную формулу, называемую у нас «Число сочетаний». В русскоязычной литературе так именуют перестановки, составленные из n различных элементов выбором по m элементов, которые отличаются только составом элементов, а порядок их выбора безразличен (см. рис, №4)
При использовании встроенных функций пользуйтесь «Справкой по этой функции». Например:
Задачи для самостоятельного решения
1. Вычислить: 
2. Вычислить:
3. Вычислить: 
4. Найти n , если 5С n 3 =
5. Найти n , если
6. Найти n , если
7. Найти n
, если 
8. Найти n
, если 
, k n
9. Решить уравнение 
10. Решить систему
11. Сколько можно составить сигналов из 6 флажков различного цвета, взятых по 2?
12. Сколькими способами можно выбрать четыре лица на четыре различные должности из девяти кандидатов?
13. Сколько можно составить телефонных номеров из 6 цифр так, чтобы в каждом отдельно взятом номере все цифры были различны?
14. В классе 10 учебных предметов и 5 разных уроков в день. Сколькими способами могут быть распределены уроки в один день?
15. Сколько можно записать четырёхзначных чисел, используя без повторения все 10 цифр?
16. Фирма производит выбор из девяти кандидатов на три различные должности. Сколько существует способов такого выбора?
17. В восьмом классе изучается 15 предметов. Сколькими способами можно составить расписание на среду, если известно, что в этот день должно быть 6 уроков?
18. В высшей лиге чемпионата страны по футболу 16 команд. Борьба идет за золотые, серебряные и бронзовые медали. Сколькими способами медали могут быть распределены между командами?
19. Сколькими способами можно разместить 9 лиц за столом, на котором поставлено 9 приборов?
20. На собрании выступят 6 ораторов. Сколькими способами их фамилии можно расположить в списке?
21. Сколько трехзначных чисел можно составить из цифр 1, 2, 3, если каждая цифра входит в изображение числа только один раз?
22. Сколькими различными способами можно расставить 10 различных книг на полке, чтобы определённые 4 книги стояли рядом?
23. В однокруговом турнире по футболу участвуют 8 команд. Сколько всего матчей будет сыграно?
24. Из 25 студентов нужно выбрать трех делегатов на конференцию. Сколькими способами это можно сделать?
25. Сколькими способами можно выбрать две детали из ящика, содержащего 10 деталей?
26. В колоде 36 карт, из них 4 туза. Сколькими способами можно извлечь 6 карт так, чтобы среди них было 2 туза?
27. Комплексная бригада состоит из двух маляров, трёх штукатуров и одного столяра. Сколько различных бригад можно создать из рабочего коллектива, в котором 15 маляров, 10 штукатуров и 5 столяров?
28. В отборочном турнире за 3 путёвки на чемпионат мира участвуют 10 команд. Сколько существует вариантов «счастливой тройки»?
29. Из 12 человек выбирают четверых для назначения на 4 одинаковые должности. Сколькими способами можно сделать такой выбор?
30. Сколькими различными способами можно составить разведывательную группу из 3-х солдат и одного командира, если имеется 12 солдат и 3 командира?
31. На плоскости дано n точек, из которых никакие три не лежат на одной прямой. Найти число прямых, которые можно получить, соединяя точки попарно.
32. Буквы азбуки Морзе образуются как последовательность точек и тире. Сколько различных букв можно образовать, если использовать 5 символов?
33. Сколько существует различных семизначных телефонных номеров?
34. Пусть буквы некоторой азбуки образуются как последовательность точек, тире и пробелов. Сколько различных букв можно образовать, если использовать 5 символов?
35. При игре в бридж между четырьмя игроками распределяется колода карт в 52 листа по 13 карт каждому игроку. Сколько существует различных способов раздать карты?
36. В почтовом отделении продаются открытки пяти видов. Определить число способов покупки семи открыток.
37. Два коллекционера обмениваются марками. Найти число способов обмена, если первый коллекционер обменивает 3 марки, а второй – 6 марок. (Обмен происходит по одной марке).
38. У одного студента 6 книг по математике, а у другого – 5. Сколькими способами они могут обменять 2 книги одного на 2 книги другого?
39. Сколько различных перестановок букв можно сделать в словах: «замок», «ротор», «обороноспособность», «колокол», «семинар»?
40. Сколькими различными способами можно разместить в 9 клетках следующие 9 букв: а, а, а, б, б, б, в, в, в?
41. В автомашине 6 мест. Сколькими способами 6 человек могут сесть в эту машину, если занять место водителя могут только двое из них?
42. Сколькими способами из колоды в 52 карты можно извлечь 6 карт, содержащих туза и короля одной масти?
43. Определить разложение при n=5.
44. Определить разложение при n=8.
45. Найти член разложения , не содержащий x (то есть содержащий x в нулевой степени).
46. Найти шестой член разложения 
, если биномиальный коэффициент третьего от конца члена равен 45.
47. В разложении 
коэффициент третьего члена на 44 больше коэффициента второго члена. Найти свободный член, то есть член разложения, не зависящий от x (членом, не зависящим от x, будет тот, который содержит x в нулевой степени).
48. В разложении бинома 
найти члены, не содержащие иррациональности.
49. Найти номер того члена разложения 
, который содержит a и b в одинаковых степенях.
Практическое занятие №2
(интерактивное занятие в малых группах)
Булевы функции
Цель занятия: уметь строить различные булевы функции, проверять эквивалентность булевых формул (используя таблицу истинности), определять существенные и фиктивные переменные.
План занятия:
1. Основные операции
2. Булевы функции от n переменных
3. Основные эквивалентности