18. Комбинаторика. Размещения, перестановки, сочетания

В комбинаторике изучают вопросы о том, сколько комбинаций определенного типа можно составить из данных предметов (элементов).

Рождение комбинаторики как раздела математики связано с трудами Б. Паскаля и П. Ферма по теории азартных игр. Большой вклад в развитие комбинаторных методов внесли Г.В. Лейбниц, Я. Бернулли и Л. Эйлер.

Французский философ, писатель, математик и физик Блез Паскаль (1623–1662) рано проявил свои выдающиеся математические способности. Круг математических интересов Паскаля был весьма разнообразен. Паскаль доказал одну
из основных теорем проективной геометрии (теорема Паскаля), сконструировал суммирующую машину (арифмометр Паскаля), дал способ вычисления биномиальных коэффициентов (треугольник Паскаля), впервые точно определил и применил для доказательства метод математической индукции, сделал существенный шаг в развитии анализа бесконечно малых, сыграл важную роль в зарождении теории вероятности. В гидростатике Паскаль установил ее основной закон (закон Паскаля). “Письма к провинциалу” Паскаля явились шедевром французской классической прозы.

Готфрид Вильгельм Лейбниц (1646–1716) — немецкий философ, математик, физик и изобретатель, юрист, историк, языковед. В математике наряду с И. Ньютоном разработал дифференциальное и интегральное исчисление. Важный вклад внес в комбинаторику. С его именем, в частности, связаны теоретико-числовые задачи.

Готфрид Вильгельм Лейбниц имел мало внушительную внешность и поэтому производил впечатление довольно невзрачного человека. Однажды в Париже он зашел в книжную лавку в надежде приобрести книгу своего знакомого философа. На вопрос посетителя об этой книге книготорговец, осмотрев его с головы до ног, насмешливо бросил: “Зачем она вам? Неужели вы способны читать такие книги?” Не успел ученый ответить, как в лавку вошел сам автор книги со словами: “Великому Лейбницу привет и уважение!” Продавец никак не мог взять втолк, что перед ним действительно знаменитый Лейбниц, книги которого пользовались большим спросом среди ученых.

В дальнейшем важную роль будет играть следующая

Лемма. Пусть в множестве A m элементов, а в множестве Bn элементов. Тогда число всех различных пар (a,b), где a\in A,b\in B будет равно mn.

Доказательство. Действительно, с одним элементом из множества A мы можем составить n таких различных пар, а всего в множестве A m элементов.

Размещения, перестановки, сочетания

Пусть у нас есть множество из трех элементов \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 мест. Сколькими способами можно их рассадить так, чтобы все девочки сидели рядом?

Комментариев: 22

  1. 1 Числовой треугольник | Математика, которая мне нравится:

    [...] числовой треугольник чем-то напоминает треугольник Паскаля. Однако он перевернут основанием вверх, и числа в нем [...]

  2. 2 Теорема Холла, или теорема о свадьбах | Математика, которая мне нравится:

    [...] доказанная им в 1935 году, является одним из основных комбинаторных принципов. Возможно, самый важный его вклад в [...]

  3. 3 Саидчалол:

    У лото-спорт 20 ячейка, которое 10-правилна а 10-непрвилно как можно утачнит правилни ячейку

    [Ответить]

  4. 4 Елизавета Александровна Калинина:

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

    [Ответить]

    Андрей Reply:

    У меня к вам вопрос если сможете ответе пожалуйста. Вот вопрос 16 клеток в 8 клетках нарисованы нолики а в других 8 клетках нарисованы звёздочки какой формулой можно изменять конбинации чтоб они постоянно изменялись

    [Ответить]

    Елизавета Александровна Калинина Reply:

    Андрей, если я правильно понимаю, что нужно, то сделала бы так: сначала в первую клетку ставим нолик, а второй нолик ставим поочередно во вторую, третью и т.д. клетки. Когда второй нолик дошел до 16-й клетки, первый нолик ставим во вторую клетку, второй – в третью, и опять двигаем второй нолик до последней клетки. Далее снова на одну клетку сдвигаем первый нолик, а второй ставим справа от него в соседней клетке и двигаем вправо и т.д.

    [Ответить]

  5. 5 Саидчалол:

    У лото-спорт 18 ячейка 9-правильно а 9-неправильно, нам нужна вибират 9-правильный ячейку.Как вибираем скажите пожалуста.

    [Ответить]

  6. 6 Елизавета Александровна Калинина:

    Если выбираем правильную ячейку, то выбрать правильную можно всего 9 различными способами. Всего различных способов выбора одной ячейки – 18. Это если все ячейки различны. Или условие задачи неполное, или я просто не понимаю, что нужно ( .

    [Ответить]

  7. 7 Саидчалол:

    [1200] [1208] [605] [600] [300] [350] [150] [155] [ 80] [88] [45] [40] [23] [20] [15] [10] [5] [6] вот такой система, в каждом строку состоит из двух ячейку, те которое 5.10.20.40.80.150.300600.1200 они правилний а остальние неправильна.Сверху ячейк наклейна никельний свет, что снизу невидна.Поэтому нам нужин стират 9- правильное ячейку.

    [Ответить]

  8. 8 Саидчалол:

    [1200] [1208] [605] [600] [300] [350] [150] [155] [ 80] [88] [45] [40] [23] [20] [15] [10] [5] [6] вот такой система, в каждом строку состоит из двух ячейку, те которое 5.10.20.40.80.150.300600.1200 они правилний а остальние неправильна.Сверху ячейк наклейна никельний свет, что снизу невидна.Поэтому нам нужин стират 9- правильное ячейку.Как угадаем 9 правильни ответ.Если ишо непонили отправти свой номер, ми будем звонит вам

    [Ответить]

  9. 9 Елизавета Александровна Калинина:

    Саидчалол, это к математике не имеет отношения. Увы, помочь Вам не могу, никак :(

    [Ответить]

  10. 10 О треугольнике Паскаля | Математика, которая мне нравится:

    [...] интересные треугольники являются частями треугольника Паскаля. Все числа, из которых они состоят, делятся на одно и то [...]

  11. 11 Трюк с биномиальными коэффициентами | Математика, которая мне нравится:

    [...] биномиальными коэффициентами проще иметь дело, когда их аргументами являются целые [...]

  12. 12 SV:

    Добрый день.
    Подскажите решение задачи, пожалуйста:
    Сколькими способами можно составить четырехзначное число, все цифры которого различны?
    Сам решал так: А 4 10 – А 3 10 = 4320.
    С уважением SV.

    [Ответить]

    Елизавета Александровна Калинина Reply:

    Сначала найдем количество различных последовательностей 4 цифр, выбранных из 10 – это у Вас сделано: A_{10}^4. А дальше нужно вычесть количество таких последовательностей, в которых на первом месте стоит цифра 0 – и это Вы догадались сделать. Только их будет A_{9}^3 – мы нуль ставим на первое место, а далее выбираем упорядоченные последовательности из трех цифр из оставшихся 9 цифр (нуль уже взяли). Итого 9\cdot9\cdot8\cdot7=4536.

    [Ответить]

    zbl Reply:

    Не надо так рассуждать. Иначе, когда попадётся задача, решение которой не выражается через A или C, вы будете беспомощны пред ней. Первой цифрой числа не может быть ноль, поэтому её можно выбрать 9-ю способами (1,2,3…9). Для каждой выбранной первой цифры вторую можно выбрать 9-ю способами, а не 10-ю, потому что одна цифра занята первой и нельзя её повторять, третью можно выбрать 8-ю способами, потому что две уже заняты, четвёртую — 7-ю. Итого 9\times 9\times 8 \times 7. А такие формулы, как A или C, — это только готовый результат для часто встречающихся значений. На практике эти формулы с факториалами для C даже не используются, потому что вычислять несколько факториалов дольше, чем одно рекуррентное соотношение по треугольнику Паскаля-отца, который к тому же раскрывает смысл биномиальных коэффициентов, что отсутствует напрочь в отношении факториалов.

    [Ответить]

    Елизавета Александровна Калинина Reply:

    Рассуждать можно по-разному :)

    [Ответить]

    zbl Reply:

    Всё можно делать по-разному. Но, делая выбор, нужно понимать разницу. В данном случае я эту разницу обозначил. И, не смотря на наличие такого выбора, мы должны обучать стоматологов удалять зубы только через правильное отверстие, ибо иное нам самим чревато страданием.

    [Ответить]

    Никки Reply:

    “Не смотря” в употребленном Вами контексте пишется слитно – “несмотря”. Не нужно задаваться: на всякого задаваку довольно простоты.

    [Ответить]

    zbl Reply:

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

    [Ответить]

  13. 13 SV:

    Большое спасибо, только начал изучать сию науку, сам бы до этого решения никогда бы не догадался.
    С уважением SV.

    [Ответить]

  14. 14 Теорема (звезда Давида) | Математика, которая мне нравится:

    [...] Эта теорема представляет собой одно из арифметических свойств биномиальных коэффициентов, или чисел . [...]

Оставьте свой отзыв

Добавить изображение


Warning: Illegal string offset 'solo_subscribe' in /home2/ekalinin/public_html/wp-content/plugins/subscribe-to-comments.php on line 304

Подписаться, не комментируя