2015-01-30
2393
Пусть у нас есть множество из трех элементов \left\{ a,b,c\right\}. Какими способами мы можем выбрать из этих элементов два? ab,ac,bc,ba,ca,cb.
Определение. Размещениями множества из n различных элементов по m элементов (m\le n) называются комбинации, которые составлены из данных n элементов по m элементов и отличаются либо самими элементами, либо порядком элементов.
Число всех размещений множества из n элементов по m элементов обозначается через {\sf A}_m^n (от начальной буквы французского слова “arrangement”, что означает размещение), где n=1,2,\dots и m=\overline{1,n}.
Теорема. Число размещений множества из n элементов по m элементов равно
{\sf A}_n^m=n(n-1)\dots(n-m+1).
Доказательство. Пусть у нас есть элементы a_1,a_2,\ldots,a_n. Пусть a_{i_1},a_{i_2},\ldots,a_{im} — возможные размещения. Будем строить эти размещения последовательно. Сначала определим a_{i_1} — первый элемент размещения. Из данной совокупности n элементов его можно выбрать n различными способами. После выбора первого элемента a_{i_1} для второго элемента a_{i_2} остается n-1 способов выбора и т.д. Так как каждый такой выбор дает новое размещение, то все эти выборы можно свободно комбинировать между собой. Поэтому имеем:
|
|
|
{\sf A}_n^m=n(n-1)\cdot\dots\cdot(n-m+1).
Пример. Сколькими способами можно составить флаг, состоящий из трех горизонтальных полос различных цветов, если имеется материал пяти цветов?
Решение. Искомое число трехполосных флагов:
{\sf A}_5^3=5\cdot4\cdot3=60.
Определение. Перестановкой множества из n элементов называется расположение элементов в определенном порядке.
Так, все различные перестановки множества из трех элементов \{ a,b,c\} — это
abc,acb,bac,bca,cab,cba.
Очевидно, перестановки можно считать частным случаем размещений при m=n.
Число всех перестановок из n элементов обозначается {\sf P}_n (от начальной буквы французского слова “permutation”, что значит “перестановка”, “перемещение”). Следовательно, число всех различных перестановок вычисляется по формуле
{\sf P}_n=n(n-1)\cdot\ldots\cdot2\cdot1=n!
Пример. Сколькими способами можно расставить 8 ладей на шахматной доске так, чтобы они не били друг друга?
Решение. Искомое число расстановки 8 ладей
{\sf P}_8=8!=40320.
\begin{tabular}{|c|c|c|c|}<br />
\hline<br />
$n$&$n!$&$n$&$n!$\\<br />
\hline<br />
0&1&6&720\\<br />
\hline<br />
1&1&7&5040\\<br />
\hline<br />
2&2&8&40320\\<br />
\hline<br />
3&6&9&362880\\<br />
\hline<br />
4&24&10&3628800\\<br />
\hline<br />
5&120&&\\<br />
\hline<br />
\end{tabular}
0!=1 по определению!
Определение. Сочетаниями из n различных элементов по k элементов называются комбинации, которые составлены из данных n элементов по k элементов и отличаются хотя бы одним элементом (иначе говоря, k-элементные подмножества данного множества из n элементов).
|
|
|
Как видим, в сочетаниях в отличие от размещений не учитывается порядок элементов. Число всех сочетаний из n элементов по k элементов в каждом обозначается {\sf C}_n^k (от начальной буквы французского слова “combinasion”, что значит “сочетание”).
Числа {\sf C}_n^k
{\sf C}_5^{2}=10
Все сочетания из множества \{ a,b,c,d,e\} по два — ab,ac,ad,ae,bc,bd,be,cd,ce,de.
{\sf C}_n^0=1,{\sf C}_n^n=1,{\sf C}_n^1=n.
Свойства чисел {\sf C}_n^k
1. {\sf C}_n^k={\sf C}_n^{n-k}.
Действительно, каждому k-элементному подмножеству данного n элементного множества соответствует одно и только одно n-k-элементное подмножество того же множества.
2. {\sf C}_n^k={\sf C}_{n-1}^k+{\sf C}_{n-1}^{k-1}.
Действительно, мы можем выбирать подмножества из k элементов следующим образом: фиксируем один элемент; число k-элементных подмножеств, содержащих этот элемент, равно {\sf C}_{n-1}^{k-1}; число k-элементных подмножеств, не содержащих этот элемент, равно {\sf C}_{n-1}^k.
Треугольник Паскаля
<br />
\begin{tabular}{ccccccccc}<br />
&&&&${\sf C}_0^0$&&&&\\<br />
&&&${\sf C}_1^0$&&${\sf C}_1^1$&&&\\<br />
&&${\sf C}_2^0$&&${\sf C}_2^1$&&${\sf C}_2^2$&&\\<br />
&${\sf C}_3^0$&&${\sf C}_3^1$&&${\sf C}_3^2$&&${\sf C}_3^3$&\\<br />
${\sf C}_4^0$&&${\sf C}_4^1$&&${\sf C}_4^2$&&${\sf C}_4^3$&&${\sf C}_4^4$\\<br />
\dots&&&&&&&&<br />
\end{tabular}
В этом треугольнике крайние числа в каждой строке равны 1, а каждое не крайнее число равно сумме двух чисел предыдущей строки, стоящих над ним. Таким образом, этот треугольник позволяет вычислять числа {\sf C}_n^k.
<br />
\begin{tabular}{ccccccccccccccccc}<br />
&&&&&&&&1&&&&&&&&\\<br />
&&&&&&&1&&1&&&&&&&\\<br />
&&&&&&1&&2&&1&&&&&&\\<br />
&&&&&1&&3&&3&&1&&&&&\\<br />
&&&&1&&4&&6&&4&&1&&&&\\<br />
&&&1&&5&&10&&10&&5&&1&&&\\<br />
&&1&&6&&15&&20&&15&&6&&1&&\\<br />
&1&&7&&21&&35&&35&&21&&7&&1&\\<br />
1&&8&&28&&56&&70&&56&&28&&8&&1\\<br />
\dots&&&&&&&&&&&&&&&&<br />
\end{tabular}
{\sf C}_7^3=35;{\sf C}_8^6=28.
Теорема. <br />
{\sf C}_n^k={n!\over k!(n-k)!}\qquad (0\le k\le n)<br />
Доказательство. Рассмотрим множество из n элементов и решим двумя способами следующую задачу: сколько можно составить последовательностей из k элементов данного
множества, в каждой из которых никакой элемент не встречается дважды?
1 способ. Выбираем первый член последовательности, затем второй, третий и т.д. член
<br />
n(n-1)(n-2)\ldots(n-k+1).<br />
2 способ. Выберем сначала k элементов из данного множества, а затем расположим их в некотором порядке
<br />
{\sf C}_n^k\cdot k!,<br />
{\sf C}_n^k\cdot k!=n(n-1)\dots(n-k+1),
\displaystyle{\sf C}_n^k={n(n-1)(n-2)\dots(n-k+1)\over k!}.
Домножим числитель и знаменатель этой дроби на (n-k)!:
\displaystyle<br />
{\sf C}_n^k={n!\over k!(n-k)!}.<br />
\displaystyle<br />
{\sf C}_{20}^8={20\cdot19\cdot18\cdot17\cdot16\cdot15\cdot14\cdot13\over<br />
1\cdot2\cdot3\cdot4\cdot5\cdot6\cdot7\cdot8}=323\cdot390=125970.<br />
Пример. Сколькими способами можно в игре “Спортлото” выбрать 5 номеров из 36?
Искомое число способов
\displaystyle<br />
{\sf C}_{36}^5={36!\over 5!31!}={36\cdot35\cdot34\cdot33\cdot32\over<br />
1\cdot2\cdot3\cdot4\cdot5}=376992.<br />
Задачи.
1. Номера машин состоят из 3 букв русского алфавита (33 буквы) и 4 цифр. Сколько существует различных номеров автомашин?
2. На рояле 88 клавиш. Сколькими способами можно извлечь последовательно 6 звуков?
3. Сколько есть шестизначных чисел, делящихся на 5?
4. Сколькими способами можно разложить 7 разных монет в три кармана?
5. Сколько можно составить пятизначных чисел, в десятичной записи которых хотя бы один раз встречается цифра 5?
6. Сколькими способами можно усадить 20 человек за круглым столом, считая способы одинаковыми, если их можно получить один из другого движением по кругу?
|
|
|
7. Сколько есть пятизначных чисел, делящихся на 5, в записи которых нет одинаковых цифр?
8. На клетчатой бумаге со стороной клетки 1 см нарисована окружность радиуса 100 см, не проходящая через вершины клеток и не касающаяся сторон клеток. Сколько клеток может пересекать эта окружность?
9. Сколькими способами можно расставить в ряд числа 1, 2, \ldots, n так, чтобы числа 1, 2, 3 стояли рядом и притом шли в порядке возрастания?
10. Сколько пятизначных чисел можно составить из цифр 1, 2, 3, 5, 7, 8, если каждую цифру можно использовать только один раз?
11. Из слова РОТ перестановкой букв можно получить еще такие слова: ТОР, ОРТ, ОТР, ТРО, РТО. Их называют анаграммами. Сколько анаграмм можно составить из слова ЛОГАРИФМ?
12. Назовем разбиением натурального числа представление его в виде суммы натуральных чисел. Вот, например, все разбиения числа 4:
<br />
4;3+1;1+3;2+2;2+1+1;1+2+1;1+1+2;1+1+1+1.<br />
Разбиения считаются разными, если они отличаются либо числами, либо порядком слагаемых.
Сколько существует различных разбиений числа 11 на 4 слагаемых?
13. Сколько существует трехзначных чисел с невозрастающим порядком цифр?
14. Сколько существует четырехзначных чисел с невозрастающим порядком цифр?
15. Сколькими способами можно рассадить в ряд 17 человек, чтобы A и B оказались рядом?
16. n девочек и n мальчиков рассаживаются произвольным образом в ряду из 2n мест. Сколькими способами можно их рассадить так, чтобы никакие две девочки не сидели рядом?
17. n девочек и n мальчиков рассаживаются произвольным образом в ряду из 2n мест. Сколькими способами можно их рассадить так, чтобы все девочки сидели рядом?
