Формула числа перестановок с повторениями
Понравилось? Добавьте в закладки
Чтобы прийти к нужной формуле, используют одну из общеизвестных постановок задач:
1. Пусть имеется $n$ различных шаров и $k$ ящиков. Сколькими способами можно разложить шары по ящикам так, чтобы $n_1$ шаров оказались в первом ящике, $n_2$ шаров — во втором, …, $n_k$ шаров — в $k$-ом ящике. $n=n_1+n_2+…+n_k$.
2. Пусть имеется $n$ объектов различных типов: $n_1$ объектов первого типа, $n_2$ объектов второго типа,… $n_k$ объектов $k$-го типа. Сколькими способами можно переставить все объекты между собой?
Будем переставлять $n$ объектов всеми возможными способами (их будет $n!$). Но так как некоторые объекты совпадают, итоговое число будет меньше. В частности, $n_1$ объектов первого типа можно переставлять между собой $n_1!$ способами, но они не меняют итоговую перестановку. Аналогично для всех остальных объектов, поэтому число перестановок с повторениями есть
$$ P_n (n_1,n_2,…,n_k)=frac{n!}{n_1! cdot n_2!cdot … cdot n_k!}. $$
Напомним, что символ $n!$ называется факториалом, калькулятор и описание смотрите тут
Заметим, что для случая двух типов объектов $(n=n_1+n_2)$ формула перестановок с повторениями дает как частный случай формулу сочетаний без повторений.
Примеры решений
Рассмотрим решение типовых задач.
Пример 1. Сколькими способами можно собрать гирлянду из 4 красных, 4 синих и 8 желтых флажков?
Решение. У нас имеется $n_1=4$ объекта первого типа (красные флажки), $n_2=4$ объекта второго типа (синие флажки) и $n_3=8$ объектов третьего типа (желтые флажки). Все эти $n=4+4+8=16$ флажков нужно развесить на веревке всеми возможными способами. Применяем формулу числа перестановок с повторенями:
$$ P_{16} (4,4,8)=frac{16!}{4! cdot 4!cdot 8!}=900900.$$
Пример 2. Сколькими способами можно разбить группу 10 друзей на команды из 2 бандитов, 2 полицейских, 1 сыщика и 5 прохожих для игры?
Решение. В самой задаче объекты (люди) уже разбиты по типам: $n_1=2$, $n_2=2$, $n_3=1$, $n_4=5$. Осталось лишь применить формулу. Тогда искомое число способов разбиться на персонажи равно:
$$ P_{10} (2,2,1,5)=frac{10!}{2! cdot 2!cdot 1!cdot 5!}=7560.$$
Калькулятор перестановок с повторениями онлайн
Введите число типов объектов $K$ и затем количество объектов каждого типа $n_1$, …, $n_K$.
Видеоролик о перестановках с повторениями в Excel
Посмотрите наш видеообзор для формулы перестановок с повторениями: как использовать Excel, как решать типовые задачи.
Расчетный файл из видео можно бесплатно скачать
Полезные ссылки
- Как решать задачи по теории вероятностей
- Основные формулы комбинаторики
- Решенные примеры по теории вероятностей
- Заказать контрольную по ТВ
Понравилось? Добавьте в закладки
Решебник по комбинаторике и теории вероятностей:
Перестановки
- Выборки
- Перестановка без повторений
- Перестановка с повторениями
- Примеры
п.1. Выборки
Рассмотрим некоторое непустое конечное множество A мощностью |A| = n (т.е. состоящее из n элементов). Из этого множества всегда можно выбрать k элементов.
Выборка (кортеж) – набор из k элементов из некоторого множества n элементов. Назовём её ⟨n,k⟩ – выборка.
Важной характеристикой выборки является её упорядоченность.
Выборка называется упорядоченной, если в ней задан порядок следования элементов. Две упорядоченные выборки с одинаковым набором элементов, но разными порядками следования, являются различными.
Если порядок следования не задан (не важен), выборка называется неупорядоченной.
Второй важной характеристикой выборки является повторение элементов.
Если элементы в выборке не повторяются, она называется выборкой без повторений.
В отличие от множества, элементы в выборке могут повторяться; в этом случае она называется выборкой с повторениями. При этом может оказаться, что k > n – количество элекментов выборки больше мощности исходного множества.
Например:
Пусть задано множество A={a,b,c,d,e,f,g}. Его мощность |A|=7.
(a,c,d) – это ⟨7,3⟩– выборка без повторений
Если мы работаем с неупорядоченными выборками, то
(a,c,d) = (c,d,a) = (d,a,c) = …
Если мы определяем наши выборки как упорядоченные, то
(a,c,d) ≠ (c,d,a) ≠ (d,a,c) ≠ …
(a,a,a,g,c,d,e,e,g) – это ⟨7,9⟩– выборка с повторениями. Она также может быть упорядоченной или неупорядоченной, в зависимости от задачи.
п.2. Перестановка без повторений
Перестановка без повторений – это упорядоченная ⟨n,n⟩– выборка без повторений.
Общее количество перестановок без повторений:
$P_n=n!$
Лексикографический порядок – способ упорядочения перестановок, основанный на сравнении. Меньшей считается та перестановка, у которой на первом месте стоит меньший элемент. Если оба первых элементов равны, сравниваются вторые элементы; и т.д. Отношение лексикографического «меньше» обозначается ≺
Читается «меньше» или «предшествует».
Например:
1) Пусть задано множество A={a,b}, n=2
Его перестановки без повторений: (a,b) и (b,a) – итого два варианта (2!=2)
2) Для A={a,b,c}, n=3
Все перестановки без повторений:
(a,b,c),(b,c,a),(c,a,b),(b,a,c),(a,c,b),(c,b,a) – итого шесть вариантов (3!=6)
В лексикографическом порядке:
(a,b,c)≺(a,c,b)≺(b,a,c)≺(b,c,a)≺(c,a,b)≺(c,b,a)
п.3. Перестановка с повторениями
Перестановка с повторениями – это упорядоченная⟨n,k⟩ – выборка с повторениями, в которой элемент a1 повторяется k1 раз, элемент a2 повторяется k2 раз, и так далее, до последнего элемента as, который повторяется ks раз (s ≤ n). При этом
k = k1 + k2 + … + ks.
Общее количество перестановок с повторениями: $$ mathrm{ P_k(k_1,k_2,…,k_s)=frac{k!}{k_1!k_2!…k_s!} } $$
Например:
Сколько различных 6-тибуквенных слов можно написать из 3 букв {a,b,c}, если буква a должна повторяться 3 раза, буква b – 2 раза, буква c – 1 раз.
Пример такого слова: (a,b,a,a,b,c) – это ⟨3,6⟩ – выборка с повторениями.
По условию k1=3, k2=2, k3=1, k=3+2+1=6 $$ mathrm{ P_6(3,2,1)=frac{6!}{3! 2! 1!}=frac{720}{6cdot 2cdot 1}=60 } $$ Всего – 60 слов.
п.4. Примеры
Пример 1. Сколько 4-значных чисел можно составить из 4-х карточек с цифрами 0,1,3,5?
У нас только 4 карточки – значит, исследуем перестановки без повторений для ⟨4,4⟩-выборки. Таких перестановок P4 = 4! = 24.
Кроме того, нужно учесть, что число не может начинаться с 0. Отложим карточку «0» в сторону, и посчитаем, сколько перестановок без повторений у выборки (1,3,5), т.е. у ⟨3,3⟩- выборки: P3 = 3! = 6.
Получаем искомое число вариантов: N = P4 – P3 = 24 – 6 = 18
Ответ: 18.
Пример 2. У Маши четыре вазы. Сколькими способами Маша может расставить их по углам комнаты, если вазы разноцветные: белая, голубая, розовая и красная? Сколько способов останется, если все вазы — совершенно одинаковые?
1) Для разноцветных ваз рассматриваем ⟨4,4⟩-выборку вида (a,b,c,d). Количество перестановок без повторений P4 = 4! = 24.
2) Для одинаковых ваз рассматриваем ⟨4,4⟩-выборку вида (a,a,a,a). В выборке один элемент, который повторяется 4 раза. Количество перестановок с повторениями: (mathrm{P_4(4)=frac{4!}{4!}}). Для одинаковых ваз есть только 1 вариант.
Ответ: 24; 1.
Пример 3. Сколькими способами можно разместить на полке 7 книг? Если среди книг – один трёхтомник, тома которого нужно ставить рядом (в любом порядке), сколько способов размещения останется?
1) Для 7 книг рассматриваем ⟨7,7⟩-выборку. Количество перестановок без повторений P7 = 7! = 5040.
2) Для трёхтомника рассматриваем ⟨3,3⟩-выборку. Расставить 3 тома можно P3 = 3! = 6 способами. Теперь рассматриваем трёхтомник как одно целое: получатся, что нужно расставить 5 книг, т.е. посчитать перестановки без повторений для ⟨5,5⟩-выборки: P5 = 5! = 120 вариантов. Общее количество расстановок ищем по правилу произведения: N = P3 · P5 = 720.
Ответ: 5040; 720.
Пример 4. Сколько различных слов можно составить, переставляя буквы слова «МАТЕМАТИКА»? Сколько слов останется, если потребовать, чтобы три буквы «А» не стояли рядом?
1) По условию рассматриваем перестановки с повторениями.
a1=M, k1=2, a2=A, k2=3, a3=T, k3=2,
a4=E, k4=1, a5=И, k5=1, a6=K, k6=1,
k = k1 + k2 + … + k6 = 2+3+2+1+1+1 = 10
$$ mathrm{ P_{10}(2;3;2;1;1;1)=frac{10!}{2! cdot 3! cdot 2!}=frac{3628800}{2 cdot 6 cdot 2}=151200 } $$ 2) Найдем количество слов с тремя «А» подряд. Условие для перестановок с повторениями изменится так:
a1=M, k1=2, a2=»AAA», k2=1, a3=T, k3=2,
a4=E, k4=1, a5=И, k5=1, a6=K, k6=1,
k = k1 + k2 + … + k6 = 2+1+2+1+1+1 = 8
$$ mathrm{ P_{8}(2;1;2;1;1;1)=frac{8!}{2! cdot 2!}=frac{40320}{2 cdot 2}=10080 } $$ Исключим слова с тремя «А» подряд из общего набора.
Останется N = 151200 – 10080 = 141120 слов.
Ответ: 151200 слов; 141120 слов.
При перестановке букв в слове «толпа» получается P5 = 5! = 120 «слов». Если же переставлять буквы в слове «топот», то получится меньше различных «слов», потому что ни перестановка двух букв «т», ни перестановка двух букв «о» не изменяют «слова»; всего перестановок в данном случае будет 
. Мы имеем здесь дело с перестановками с повторениями.
Общую задачу сформулируем следующим образом.
Имеется n элементов k различных типов: n1 элементов первого типа, n2 элементов второго типа, …, nk элементов k-го типа, 
. Сколько можно составить различных перестановок из этих элементов?
Число перестановок c повторениями обозначают 
. Сколько же их? Если бы все элементы были различны, то число перестановок равнялось бы n!. Но из-за того, что некоторые элементы совпадают, получится меньшее число перестановок. В первой группе элементы (первого типа) можно переставлять друг с другом n1! способами. Но так как все эти элементы одинаковы, то перестановки ничего не меняют. Точно также ничего не меняют n2! перестановок элементов во второй группе и т. д. Перестановки элементов в разных группах можно делать независимо друг от друга. Поэтому (из принципы умножения) элементы можно переставлять друг с другом 
способами так, что она остаётся неизменной.
Число различных перестановок с повторениями, которые можно составить из данных элементов, равно
, (11.1) где 
.
Замечание. Отметим, что формула числа сочетаний из n элементов по k элементов совпадает с формулой для числа перестановок с повторениями из k элементов одного типа и n–k элементов другого типа:
.
Пример 11.1. Сколькими способами можно нанизать на нить 4 зеленых, 5 синих и 6 красных бус?
Решение. Речь идет об отыскании числа перестановок с повторениями, которые можно сделать из k1=4 элементов первого типа (зеленых бус), k2=5 элементов второго типа (синих бус) и k3=6 элементов третьего типа (красных бус). По формуле (6) получаем
.
Пример 11.2. У мамы было 2 одинаковых яблока, 3 одинаковых груши и 4 одинаковых апельсина. Каждый день она давала ребенку по одному фрукту. Сколькими способами она могла это сделать?
Решение. Данная задача есть задача на отыскание числа перестановок с повторениями:
.
Пример 11.3. Сколько различных браслетов можно сделать из пять одинаковых изумрудов, шести одинаковых рубинов и семи одинаковых сапфиров (в браслет входят все 18 камней)?
Решение. Камни можно переставлять P(5, 6, 7) способами. При циклических перестановках и при зеркальном отражении браслет остается неизменным. В результате получаем
.
Пример 11.4. Сколько способами можно переставлять буквы слова «огород» так, чтобы: а) три буквы «о» не стояли рядом? б) если запрещается, чтобы две буквы «о» стояли рядом?
Решение. а) Буквы данного слова можно переставлять P(3,1,1,1) способами. Если три буквы «о» стоят рядом, то их можно считать за одну букву. Тогда буквы можно переставлять 4! Способами. Вычитая этот результат из предыдущего, получим
.
Б) Сначала расставляем согласные (3! способов). Для трёх букв «о» остаётся 4 места, и их можно расставить 
способами. Всего получаем 
способа.
Упражнения
11.1. Сколькими способами можно расположить в ряд две зелёные и четыре красные лампочки?
Ответ: 
.
11.2. Десять человек надо разбить на три группы соответственно по 2, 3, 5 человек в группе. Сколькими способами можно это сделать?
Ответ: 
.
11.3. Сколькими способами можно упаковать девять различных книг в трёх бандеролях соответственно по два три, четыре книги в каждой бандероли?
Ответ: 
.
11.4. Группу командировочных из восьми человек требуется расселить в три комнаты, из которых две трёхместные и одна двухместная. Сколько вариантов расселения возможно?
Ответ: 
.
11.5. Сколько различных слов можно получить, переставляя буквы в следующих исходных словах: а) академия, б) электротехника, в) молокопродукт?
Ответ: 
.
11.6. Сколькими способами можно разделить 12 предметов между тремя студентами, чтобы каждому досталось ровно по четыре предмета?
Ответ: 
.
11.7. Для премий на математической олимпиаде выделено 3 экземпляра одной книги, 4 экземпляра другой и 8 экземпляров третьей. Сколькими способами могут быть распределены эти премии между 30 участниками олимпиады, если каждому вручается не более одной книги?
Ответ: 
.
11.8. Сколькими способами можно переставить буквы слова «обороноспособность» так, чтобы две буквы «о» не шли подряд?
Ответ: 
.
11.9. Сколькими способами можно переставить буквы слова «каракули» так, чтобы никакие две гласные не стояли рядом?
Ответ: Гласные можно переставлять P(2,1,1)=12 способами, Аналогично, P(2,1,1)=12 способами можно расставить согласные буквы. Если согласные уже расставлены, то для гласных останется 5 мест. Поэтому места для них можно выбрать 
способами. Всего 
способов.
| < Предыдущая | Следующая > |
|---|
Перестановки с повторениями
Определение.
Перестановкой
с повторениями из m
элементов состава k1,
k2,…,km
называют кортеж длины суммы k1+k2+…+km,
где k1
– число повторений одного элемента
множества, k2
– число повторений другого элемента
множества и т.д., km
– количество повторений оставшегося
элемента множества.
Обозначают:
.
Теорема
10. Число
различных перестановок с повторениями
данного состава (n1,
n
,
…,n
)
вычисляют по формуле
,
где
n
=n1
+n
+…+
nт.
Рассмотрим
одну перестановку и заменим в ней все
одинаковые элементы разными. Тогда
число различных перестановок, которые
можно составить из рассматриваемой
нами перестановки, по правилу произведения
равно n1,
n
,…,
n
.
Проделав это для каждой перестановки,
получим n!
перестановок.
Следовательно,
∙n1!∙n2∙…∙nm!
= n!.
Теорема
доказана.
Задача. Сколькими
способами можно расставить белые фигуры:
2 коня, 2 слона, 2 ладьи, ферзя и короля на
первой линии шахматной доски?
Решение.
В
этой задаче надо найти число кортежей
длины 8, имеющих заданный состав (2, 2, 2,
1, 1). Число таких кортежей, то есть
перестановок с повторениями, равно
5040.
.
Ответ:
5 040
способами.
Общую
задачу о перестановках с повторениями
можно сформулировать следующим образом:
имеются предметы m
различных
типов. Сколько перестановок можно
сделать, взяв n1
элементов первого типа, n2
типа, …, nm
элементов m-го
типа?
Задача. Сколько
различных буквенных комбинаций (не
обязательно имеющих смысл) можно
получить, переставляя буквы слова
«кишмиш»?
Решение.
В данном
слове одна буква «к», две буквы «и», две
буквы «ш», одна буква «м», всего 1+2+2+1=6
(букв).
Значит,
Р(1,2,2,1)=
(слов).
Ответ:
180 слов.
Задачи для самостоятельного решения
-
Сколько слов,
состоящих из восьми букв, можно образовать
из 6 букв алфавита? -
В магазине имеется
7 видов тетрадей в клеточку. Сколькими
способами можно купить 12 тетрадей? -
Сколькими
способами можно расставить белые
фигуры: два коня, две ладьи, ферзя и
четыре пешки – на одной линии шахматной
доски? -
Сколько будет
костей геометрического домино, если
использовать в их образовании следующие
геометрические фигуры: квадрат,
треугольник, круг, ромб? -
Сколько
различных буквенных комбинаций (не
обязательно имеющих смысл) можно
получить, переставляя буквы слова
«комбинаторика»? Переставляя буквы
слова «математика»? -
Сколькими
способами можно обить 12 стульев, если
имеется 5 сортов обивочного материала?
Бином Ньютона
В
алгебре довольно часто приходится
возводить в степень двучлен (a+b).
Недаром каждый школьник заучивает
наизусть формулы квадрата и куба суммы
двух чисел. Аналогичная формула, но уже
для произвольного натурального числа
п≥1
называютбиномом
Ньютона, хотя и была известна задолго
до того времени, когда жил Ньютон.
Слово «бином» в переводе с латыни
означает «двучлен».
Теорема
11. Для
любого целого неотрицательного n
справедливо тождество:
.
Левая
часть равенства является произведением
n
одинаковых сомножителей:
.
Если раскрыть скобки, не приводя подобных
и не группируя одинаковые сомножители
в степени, получится сумма, в которой
каждое слагаемое является произведениемn переменных,
по одной из каждого сомножителя. Например,
.
Каждое
слагаемое в этой сумме имеет вид слова
в алфавите {x,y},
в котором i–тую
позицию занимает переменная, выбираемая
из i–того
сомножителя. Нетрудно видеть, что каждое
слово длины n
появится в этом выражении в точности
один раз. После группировки сомножителей
каждое слово, в котором буква x
встречается k
раз, превращается в слагаемое вида
.
Таких слов имеется ровноC
,
поэтому после приведения подобных
получается правая часть равенства.
Ранее
были приведены следующие свойства
биномиальных коэффициентов:
1)
;
4)
;
2)
;
5)
;
3)
;
6)
.
Особенно
важным свойством является последнее.
Оно позволяет с помощью одних только
операций сложения найти все числа
сочетаний из n
элементов,
если известны числа сочетаний из (
)
элемента. Это же свойство лежит в основе
построения таблицы биномиальных
коэффициентов, называемой треугольником
Паскаля.
Треугольник
Паскаля является, пожалуй, одной из
наиболее известных и изящных числовых
схем во всей математике. Блез Паскаль,
французский математик и философ, посвятил
ей специальный «Трактат об арифметическом
треугольнике». Впрочем, эта треугольная
таблица была известна задолго до 1665
года – даты выхода в свет трактата.
Так,
в 1529 году треугольник Паскаля был
воспроизведен на титульном листе
учебника арифметики, написанного
астрономом Петром Апианом.
Изображен
треугольник и на иллюстрации книги
«Яшмовое зеркало четырех элементов»
китайского математика Чжу Шицзе,
выпущенной в 1303 году. Омар Хайям, бывший
не только философом и поэтом, но и
математиком, знал о существовании
треугольника в 1110 году, в свою очередь,
заимствовав его из более ранних китайских
или индийских источников.
В
треугольнике Паскаля биномиальные
коэффициенты располагаются следующим
образом:
C
.
. . . . . . . .
В
этой бесконечной таблице строка с
номером n
(n=0,1,2,…)
образована числами C
,
k
пробегает все значения от 0 до n.
При этом каждая следующая строчка
сдвинута относительно предыдущей таким
образом, что непосредственно над числом
C
левее и правее его оказываются расположены
числа
и
,
сумма которых, по свойству 6), как раз и
равнаC
.
Таким образом, если строка с номером
(
)
заполнена, то легко заполняется строка
с номером n:
первый и последний элементы всегда
равны 1, а каждый из остальных получается
сложением двух расположенных над ним
элементов предыдущей строки.
В
треугольнике Паскаля прослеживаются
следующие закономерности.
1.
Члены
всякой строки треугольника Паскаля
сначала возрастают (до середины строки),
а затем − убывают.
Например, 1<4<6,
6>4>1 (четвертая строка); 1<5<10, 10>5>1
(пятая строка).
2.
Всякая строка треугольника Паскаля
симметрична относительно своей середины
(то есть члены всякой строки треугольника
Паскаля, равноудаленные от ее краев,
равны между собой).
Формально
это свойство записывается в виде
упоминавшегося нами равенства
.
3.
Сумма
членов n-й
строки треугольника Паскаля равна 2
.
То
есть
.Это
можно рассматривать как следствие
формулы бинома Ньютона,
если положить
.Важно,
однако, разобраться в теоретико-множественной
интерпретации данного свойства. Число
равно
количеству m-элементных
подмножеств n—элементного
множества. Поэтому левую часть формулы
бинома Ньютона можно рассматривать как
число всех подмножеств n—элементного
множества (включая пустое подмножество
и само n-элементное
множество).
4.
Всякое
непустое множество имеет столько
подмножеств с четным числом элементов,
сколько и подмножеств с нечетным числом
элементов; иными словами, при
n≤1
C
+ C
+ C
+ …=C
+ C
+ C
+ …
Данное
соотношение получается применением
формулы бинома Ньютона к левой части
тождества (1
–
1)п=0.
С
помощью утверждения 3 можно конкретизировать:
C
+ C
+ C
+ … = C
+ C
+ C
+ …=2
.
Приведем
комбинаторное доказательство этого
утверждения.
С
каждым подмножеством X
данного
непустого множества
А={а1,
а2,
… , ап}
свяжем
подмножество Y,
определяемое
следующим образом: Y
получается
из X
путем
исключения или, наоборот, путем добавления
к нему элемента аi
в зависимости от того, содержит X
элемент
аi
или не содержит.
Все
подмножества множества А
можно
таким образом разбить на пары подмножеств
(X,
У),
причем в каждой такой паре одно из
подмножеств содержит четное, а другое
–
нечетное число элементов. Следовательно,
подмножеств с четным числом элементов
столько же, сколько и подмножеств с
нечетным числом элементов.
5.
Крайние
члены треугольника Паскаля равны 1.
Каждый же из остальных членов равен
сумме двух смежных с ним членов, стоящих
в предыдущей строке.
Например
(см. строку с номером п=4),
4=1
+ 3; 6=3 + 3; 4=3 + 1.
В
общем случае (при 1≤m≤п)
C
=C
+ C
.
Последняя
формула интересна и тем, что несет в
себе правило построения каждой последующей
строки треугольника Паскаля по предыдущей
строке.
Доказать
это равенство можно непосредственными
вычислениями с помощью формулы
.
Однако гораздо
интересней обратиться к ее комбинаторной
трактовке: тех сочетаний из элементов
{ а1,
а2,
… , ап,
an+1}
по т,
которые не
содержат ап+1,
будет, очевидно, С
;
тех же сочетаний, которые содержатan+1,
будет C
.
6.
.
Это
получается при
.
7.
.
Получается
применением формул
и
.
Рассмотрим
примеры использования формулы бинома.
Пример.
Разложить
по формуле бинома Ньютона двучлен
Решение.
Пример.
Разложить
по формуле бинома Ньютона двучлен
Решение.
Пример.
Запишите
формулу Бинома Ньютона для (х–2у)
.
=
.
Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]
- #
- #
- #
- #
- #
- #
- #
- #
- #
- #
- #
План урока:
Комбинаторика и ее основные принципы
Перестановки
Перестановки с повторениями
Размещения
Сочетания
Комбинаторика и ее основные принципы
Очень часто приходится решать задачи, в которых надо посчитать количество возможных вариантов для той или иной ситуации. Например, сколько позиций может возникнуть на шахматной доске после первого хода обоих игроков? Сколько разных паролей длиною в десять символов можно записать, если ни один символ не использовать дважды? Сколько разнообразных комбинаций чисел может выпасть при игре в лотерею «6 из 49»? На все эти вопросы помогает ответить специальный раздел математики, называемый комбинаторикой. Почти всегда комбинаторную задачу можно сформулировать так, чтобы ее вопрос начинался словами «сколькими способами…».
Очевидно, что если в конечном множестве содержится n элементов, то есть ровно n способов выбрать один из них.
Пример. В классе 15 человек. Сколькими способами учитель может назначить одного из них ответственным за чистоту доски?
Ответ. Таких способов ровно 15.
В комбинаторике существует два основных правила. Первое из них называется правилом сложения.
Несмотря на формулировку, по сути это очень простое правило.
Пример. В магазине продается 14 телевизоров Panasonic и 17 телевизоров Sony. Петя хочет купить один телевизор. Сколько у него вариантов покупки?
Решение. По правилу сложения Петя может выбрать один из 14 + 17 = 31 телевизоров.
Ответ: 31 телевизор.
Особое значение имеет второе правило, которое называют правилом умножения.
Проиллюстрируем это правило.
Пример. В секции бадминтона 15 мальчиков и 20 девочек. Тренер должен отправить на соревнования смешанную пару. Сколько вариантов действий у него?
Решение. Тренер может составить 15•20= 300 разнополых пар из своих воспитанников.
Ответ: 300
Пример. Пете нужно купить технику для компьютера. В магазине продается 20 различных клавиатур, 25 моделей геймпадов и 30 компьютерных мышей. Купить надо по одному экземпляру каждого из этих устройств. Сколько вариантов покупки есть у него?
Решение. Сначала подсчитаем число возможных пар «клавиатура-геймпад». Их количество равно 20•25 = 500. Теперь составим «тройку» из одной из 500 пар и одной из 30 мышей. Число троек равно 500•30 = 15000.
Ответ: 15000
Правила сложения и умножения можно комбинировать.
Пример. Сколько слов не более чем из трех букв можно составить, используя алфавит, содержащий ровно 30 букв?
Решение. Очевидно, что слов из одной буквы можно составить ровно 30. Количество двухбуквенных слов равно количеству пар, которые можно составить из этих букв, то есть 30•30 = 900. Трехбуквенных слов можно составить 30•30•30 = 27000. Всего же слов длиною не более 3 букв будет
30 + 900 + 27000 = 27930
Ответ: 27930
Далее мы изучим основные понятия комбинаторики – перестановки, размещения, сочетания.
Перестановки
Рассмотрим простейшую комбинаторную задачу. На полке расставляют по порядку книги. Их ставят вертикально друг за другом. Сколькими способами можно расставить на полке 2 книги? Очевидно, что двумя:
Либо синяя книжка будет первой слева, либо она будет находиться в конце полки, третьего варианта здесь нет. Здесь условно считается, что варианты, когда между книгами есть зазоры, идентичны вариантам без зазоров:
То есть нас интересует исключительно порядок, в котором стоят книги. Каждый из найденных вариантов называется перестановкой книг. Перестановкой называют любое конечное множество, для элементов которого указан порядок элементов.В комбинаторике перестановки являются одними из основных объектов изучения.
Например, если в забеге на 100 метров стартует 8 спортсменов, то они образуют множество участников забега. После финиша становится известно, кто занял 1-ое место, кто оказался вторым или третьим, а кто стал последним. Результат забега будет перестановкой, ведь он представляет собой список спортсменов с указанием их мест, то есть он определяет порядок между ними.
Вернемся к примеру с книгами. Обозначим количество возможных перестановок n элементов как Рn. Две книжки можно расставить двумя разными способами, поэтому Р2 = 2. Обозначим эти перестановки как АБ и БА. Сколько способов расстановки есть в случае трех книжек? Их все можно получить из вариантов с 2 книжками, добавляя между ними книгами ещё один том:
Видно, что между 2 книгами есть три позиции, на которые можно поставить 3-ий том. Общее количество вариантов равно произведению числа этих позиций и количества вариантов для 2 книг, то есть Р3 = 3•Р2 = 3•2 = 6:
Итак, мы имеем 6 перестановок для 3 книг:
ВАБ
АВБ
АБВ
ВБА
ВБА
БАВ
А сколько перестановок существует для 4 книг? Снова-таки, между тремя книгами 4-ый том можно поставить четырьмя способами:
То есть из перестановки трех книг АБВ можно получить 4 перестановки:
ГАБВ
АГБВ
АБГВ
АБВГ
Всего существует 6 перестановок для 3 книг (Р3 = 6), и для каждой из них можно построить 4 перестановки из 4 книг. Получается, что общее количество перестановок 4 книг равно
Р4 = 4Р3 = 4•6 = 24.
Продолжая подобные рассуждения, можно убедиться, что количество перестановок 5 предметов в 5 раз больше, чем перестановок для 4 объектов:
Р5 = 5Р4
И вообще, если число перестановок n объектов равно Рn, то количество перестановок (n + 1)объекта равно в (n + 1)раз больше:
Рn+1 = (n + 1)Рn
При этом отметим, что 1 книгу можно расставить на полке только одним способом:
То есть Р1 = 1. Теперь выпишем значения чисел Р при разном количестве переставляемых предметов, используя формулуРn+1 = (n + 1)Рn
Р1 = 1
Р2 = 2•Р1= 2•1 = 2
Р3 = 3Р2 = 3•2•1 = 6
Р4 = 4Р3 = 4•3•2•1 = 24
Р5 = 5Р4 = 5•4•3•2•1 = 120
Видно, что количество перестановок n объектов равно произведению всех натуральных чисел от 1 до n. В математике есть специальная функция для вычисления значения этого произведения. Она называется факториалом и обозначается восклицательным знаком.
Например, факториал 6 вычисляется так:
6! = 1•2•3•4•5•6 = 720
Мы убедились на примере с книгами, что количество перестановок из n различных объектов, которое обозначается как Рn, равно n!.
Относительно факториала надо заметить несколько важных моментов. Во-первых, очевидно, что факториал единицы равен 1:
1! = 1
Во-вторых, иногда в комбинаторных задачах приходится вычислять факториал нуля. По ряду соображений эта величина также принимается равной единице
0! = 1
Объяснить это можно так. Факториал числа можно представить как произведение этого числа и факториала предыдущего числа, например:
5! = 1•2•3•4•5 = (1•2•3•4)•5 = 4!•5
7! = 1•2•3•4•5•6•7 = (1•2•3•4•5•6)•7 = 6!•7
В общем случае формула выглядит так:
n! = (n– 1)!•n
Из неё несложно получить, что
(n– 1)! = n!/n
Например: 5! = 4!•5
Подставив в эту формулу единицу, получим
(1 – 1)! = 1!/1
0! = 1/1
0! = 1
Пример. Сколькими способами тренер может расставить 4 участников эстафеты 4х400 м по этапам эстафеты?
Решение. Количество таких способов равно числу перестановок 4 различных объектов Р4:
Р4 = 4! = 1•2•3•4 = 24
Ответ: 24
Пример. Вася решил изучать сразу 7 иностранных языков, причем на занятия по каждому из них он собирается выделить ровно один день в неделе. Сколько вариантов расписаний занятий может составить себе Вася?
Решение. В данном случае расписание занятий – это порядок, в котором Вася в течение недели будет изучать иностранные языки, например:
Такое расписание можно описать последовательностью символов:
Ф, Ан, И, К, Я, Ар, П
Создавая расписание, Вася переставляет 7 языков, поэтому общее количество расписаний равно 7!:
Р7 = 1•2•3•4•5•6•7 = 5040
Ответ: 5040
Пример. Сколько пятизначных цифр можно записать, используя цифры 0, 1, 2, 3, 4, причем каждую не более одного раза?
Решение. Общее количество перестановок 5 цифр составляет Р5. Однако нельзя начинать запись числа с нуля. Так как, перестановка 12340 – это пятизначное число (двенадцать тысяч триста сорок), а перестановка 03241 – не является пятизначным числом.
Расстановок, начинающихся с нуля, ровно Р4, поэтому общее количество допустимых цифр равно Р5 – Р4:
Р5 – Р4 = 5! – 4! = 120 – 24 = 96
Ответ: 96
Пример. На полке расставляют 7 книг, однако 3 из них образуют трехтомник. Тома трехтомника должны стоять друг за другом и в определенном порядке. Сколько существует способов расстановки книг?
Решение. Будем считать трехтомник одной книгой. Тогда нам надо расставить 5 книг
Р5 = 5! = 120
Ответ: 120
Пример. Необходимо расставить 7 книг на полке, но три из них принадлежат одному автору. Их надо поставить друг с другом, но они могут стоять в любом порядке. Сколько возможно перестановок книг.
Решение. Снова будем считать три книги как один трехтомник. Получается, что существует 5! = 120 вариантов. Однако каждому из них соответствует 3! = 6 расстановок книг внутри трехтомника, например:
В итоге на каждую из 120 расстановок приходится 6 вариантов расстановки трехтомника, а общее число расстановок равно, согласно правилу умножения, произведению этих чисел:
120•6 = 720
Ответ: 720
Перестановки с повторениями
До этого мы рассматривали случаи, когда все переставляемые объекты были различными. Однако порою некоторые из них не отличаются друг от друга. Пусть на полке надо расставить 3 книги, но две из них одинаковые. Сколько тогда существует перестановок? Общее число перестановок 3 книг составляет 3! = 6:
Здесь одинаковые книги отмечены как А и А1. Очевидно, что 1-ый и 2-ой варианты (А1АБ) и (АА1Б) на самом деле не отличаются друг от друга. В них отличается лишь порядок одинаковых книг А и А1. В первом случае за А1 следует А, а во втором, наоборот, за А следует А1. Тоже самое можно сказать про варианты 3 и 4, 5 и 6. Получается, что все возможные перестановки можно разбить на группы, в которых находятся «перестановки-дубликаты»:
А1АБ и АА1Б
А1БА и АБА1
БА1А и БАА1
В каждой группе находится ровно по два «дубликата». Почему именно по два? Это число равно количеству перестановок одинаковых книг. Так как одинаковых томов 2, а Р2 = 2, то в каждой группе по 2 «дубликата». Действительно, если бы мы «убрали» с полки все книги, кроме повторяющихся, то там осталось бы только 2 одинаковых тома, которые можно переставить двумя способами.
Для того чтобы найти количество «оригинальных» перестановок, надо их общее количество поделить на число дубликатов в каждой группе.
6:2 = 3
Пусть теперь надо расставить 4 книги, из которых 3 одинаковы. Обозначим тома как А, А1, А2 и Б. Всего можно записать 4! = 24 перестановки. Однако каждые 6 из них будут дублировать друг друга. То есть их можно разбить на группы, в каждой из которых будет 6 идентичных «дубликатов»:
1-ая группа: БАА1А2, БАА2А1, БА1АА2, БА1А2А, БА2АА1, БА2А1А
2-ая группа: АБА1А2, АБА2А1, А1БАА2, А1БА2А, А2БАА1, А2БА1А
3-ая группа: АА1БА2, АА2БА1, А1АБА2, А1А2БА, А2АБА1, А2А1БА
4-ая группа: АА1А2Б, АА2А1Б, А1АА2Б, А1А2АБ, А2АА1Б, А2А1АБ
И снова для подсчета числа оригинальных перестановок надо из общее число расстановок поделить на количество дубликатов в каждой группе:
Р4/Р3 = 4!/3! = 24/6 = 4
Для обозначения перестановок с повторениями используется запись
Рn(n1, n2, n3,… nk)
где n – общее количество объектов, а n1, n2, n3,… nk – количество одинаковых элементов. Например, в задаче с 4 книгами мы искали величину Р4(3, 1), потому что всего книг было 4, но они были разбиты на две группы, в одной из которых находилось 3 одинаковых тома (буквы А, А1, А2), а ещё одна книга (Б) составляла вторую группу. Мы заметили, что для вычисления числа перестановок с повторениями надо общее число перестановок делить на количество дублирующих перестановок. Формула в общем случае выглядит так:
Пример. Вася решил, что ему стоит изучать только два иностранных языка. Он решил 4 дня в неделю тратить на английский, а оставшиеся три дня – на испанский. Сколько расписаний занятий он может себе составить.
Решение. Вася должен расставить 3 урока испанского и 4 урока английского, тогда n1 = 3, а n2 = 4. Общее количество уроков равно 3 + 4 = 7. Тогда
Ответ: 35
Обратите внимание, что для удобства при делении факториалов мы не вычисляли их сразу, а пытались сократить множители. Так как в ответе любой комбинаторной задачи получается целое число, то весь знаменатель дроби обязательно сократится с какими-нибудь множителями в числителе.
Пример. У мамы есть 3 яблока, 2 банана и 1 апельсин. Эти фрукты она распределяет между 6 детьми. Сколькими способами она может это сделать, если каждый должен получить по фрукту?
Решение. Всего есть три группы фруктов. В первой находится 3 яблока, поэтому n1 = 3. Во второй группе 2 банана, поэтому n2 = 2. В третьей группе только 1 апельсин, поэтому nk = 1. Общее число фруктов равно 6. Используем формулу:
Ответ: 60
В знаменателе формулы для перестановок с повторениями мы записываем число объектов в каждой группе одинаковых предметов. Так, если переставляются 3 яблока, 2 банана и 1 апельсин, то в знаменателе мы пишем 3!•2!•1!. Но что будет, если в каждой группе будет находиться ровно один уникальный объект? Тогда мы запишем в знаменателе произведение единиц:
В итоге мы получили ту же формулу, что и для перестановок без повторов. Другими словами, перестановки без повтора могут рассматриваться просто как частный случай перестановок с повторами.
Размещения
Пусть в футбольном турнире участвуют 6 команд. Нам предлагают угадать те команды, которые займут призовые места (то есть первые три места). Сколько вариантов таких троек существует?
Сначала запишем ту команду, которая выиграет турнир. Здесь есть шесть вариантов, по количеству участвующих команд. Запишем эти варианты:
Далее выберем один из вариантов и для него укажем серебряного призера соревнований. Здесь есть только 5 вариантов, ведь 1 из 6 команд уже записана на 1-ом месте:
Такую пятерку можно записать для каждого из шести вариантов того, кто станет чемпионом. Получается, что всего есть 6•5 = 30 пар «чемпион – серебряный призер». Наконец, для одной такой пары можно записать 4 варианта того, кто окажется третьим (две команды писать нельзя, так как они уже записаны на первых двух строчках):
Для каждой пары можно записать 4 тройки призеров. Так как число пар «чемпион – вице-чемпион» равно 6•5 = 30, то число троек составит 6•5•4 = 120.
В данном случае из некоторого множества команд мы выбрали несколько и расположили их в каком-то порядке. То есть мы выбрали упорядоченное множество. В комбинаторике оно называется размещением.
Если общее число команд обозначить как n (в этом примере n = 6), а количество упорядочиваемых команд равно k, то количество таких размещений в комбинаторике обозначается как
В примере с командами количество размещений равнялось 120:
Читается эта запись как «число размещений из 6 по 3 равно 120».
Для нахождения этого числа мы перемножили k (3)множителей. Первый из них был равен n(6), так как каждая из n команд могла занять первая место. Второй множитель был равен (n– 1), так как после определения чемпиона мы могли поставить на вторую позицию одну из (n– 1) команд. Третий множитель был равен (n– 2). По этой логике каждый следующий множитель будет меньше предыдущего на единицу. Например, чтобы вычислить число размещений из 7 по 4, надо перемножить 4 множителя, первый из которых равен 7, а каждый следующий меньше на 1:
Однако математически удобнее представлять это произведение как отношение двух факториалов. Для этого умножим количество размещений на дробь 3!/3!, равную единице. Естественно, число размещений из-за умножения на единицу не меняется:
Число 3 в данном случае можно получить, если из 7 вычесть 4. В общем случае из числа n надо вычесть число k. Тогда формула для вычисления количества размещений примет вид:
Пример. В программе 8 «А» класса 12 различных предметов. В понедельник проводится 5 занятий подряд. Сколько существует вариантов расписаний для класса, если в течение понедельника нельзя проводить два одинаковых урока?
Решение. Для составления расписания нужно выбрать 5 предметов и расставить их по порядку. Поэтому нам необходимо найти размещение из 12 по 5:
Ответ: 95040
Пример. В вагоне 10 свободных мест. В него зашло 6 пассажиров. Сколькими способами они могут расположиться в вагоне?
Решение. Из десяти мест надо выбрать шесть и указать для каждого, какому пассажиру оно соответствует. То есть каждый вариант рассадки пассажиров – это размещение из 10 по 6. Найдем их количество:
Ответ: 151200
Заметим, что перестановка – это частный случай размещения, когда k = n. Действительно, если нам надо указать тройку призеров турнира, в котором участвуют 6 команд, то мы указываем размещение из 6 по 3. Но если мы указываем для каждой из 6 команд, какое место она займет в чемпионате, то это размещение из 6 по 6. С другой стороны, это расстановка одновременно является и перестановкой 6 команд. Убедимся, что в этом частном случае формула для подсчета количества размещений покажет тот же результат, что и формула для перестановок
Для примера с 6 командами это будет выглядеть так:
Здесь мы использовали тот факт, что факториал нуля принимается равным единице. Данное рассуждение можно, наоборот, использовать для того, чтобы доказать, что факториал нуля – это единица.
Сочетания
Выбирая размещение, мы должны были выбрать из множества несколько объектов и упорядочить их. В частности, мы выбирали три команды из шести и указывали, какая из них будет первой, какая второй, а какая третьей. Поэтому размещения «Локомотив, Зенит, Краснодар» и «Локомотив, Краснодар, Зенит» отличались друг от друга.
Однако порою этот порядок не имеет значения. Так, существует известная лотерея, где предлагается угадать 7 чисел из 49, которые выпадут во время розыгрыша из барабана. При этом порядок их выпадения не играет никакой роли. Игрок, выбирая эти 7 чисел, с точки зрения математики формирует сочетание из 49 по 7.
Количество возможных сочетаний из n по k обозначается буквой С:
Для вычисления количеств сочетаний из n по k сначала найдем количество аналогичных размещений. Оно вычисляется по формуле:
Однако ясно, что, как и в случае с перестановками с повторениями, некоторые сочетания мы посчитали несколько раз. Вернемся к примеру с командами. Если мы выбрали команды Л (Локомотив) , З (Зенит) и К (Краснодар), то мы можем составить ровно 3! = 6 размещений из них:
ЛЗК
ЛКЗ
ЗЛК
ЗКЛ
КЛЗ
КЗЛ
Однако все они соответствуют только одному сочетании – ЛКЗ. Таким образом, считая количество размещений, мы посчитали каждое сочетание не один, а 3! раз. Поэтому для нахождения количества сочетаний в комбинаторике надо поделить число размещений на число перестановок k элементов:
Эта формула связывает важнейшие понятия комбинаторики – перестановки, сочетания и размещения. Подставим в неё формулы для размещений и перестановок и получим:
Пример. Сколько троек призеров турнира можно составить, выбирая три футбольные команды из шести?
Решение. Посчитаем число сочетаний из 6 по 3:
Ответ: 20
Пример. Сколько комбинаций чисел может составить игрок, играющий в лотереи «5 из 36», «6 из 45», «7 из 49»?
Решение. В каждом из этих случаев игрок выбирает сочетание нескольких чисел. Посчитаем их число:
Ответ: 376992; 8145060; 85900584
Пример. На плоскости отмечены 8 точек, причем никакие три из них не лежат на одной прямой. Сколько различных прямых можно провести через них? Сколько треугольников и четырехугольников можно построить с вершинами в этих точках?
Решение. Для того чтобы провести прямую, достаточно выбрать любые 2 точки из 8. Общее количество прямых будет равно числу сочетаний из 8 по 2:
Заметим принципиальную важность того условия, что никакие три точки не лежат на одной прямой. Оно гарантирует, что при выборе двух различных точек мы будем получать различные прямые. Если бы, например, точки АВС лежали бы на одной прямой, то при выборе сочетаний АВ, ВС и АС мы получали бы одну и ту же прямую:
Это же условие гарантирует, что, выбрав любые 3 и 8 точек, мы сможем построить треугольник с вершинами в этих точках, а выбрав 4 точки, получим четырехугольник. Поэтому для подсчета количества треугольников и четырехугольников следует искать число сочетаний по 3 и 4:
Ответ: 28 прямых, 56 треугольников и 70 четырехугольников.
Пример. В одной урне находится 10 различных шаров с номерами от 0 до 9, а в другой – 8 различных шаров с первыми восемью буквами алфавита. По условиям лотереи ведущий вытаскивает из первой урны два шара с числами, а из второй – три шара с буквами. Для победы в лотерее надо угадать выпавшие шары. Сколько комбинаций шаров может выпасть в игре?
Решение. Посчитаем отдельно, сколькими способами можно выбрать 2 шара с цифрами из 10 и 3 шара с буквами из 8:
По правилу умножения мы должны перемножить эти числа, чтобы найти общее количество возможных вариантов:
56•45 = 2520
Ответ: 2520
Заметим, что выбирая, например, сочетание из 49 по 7, мы одновременно выбираем и сочетание из 49 по 49 – 7 = 42. Действительно, игрок, обводящий в кружок в лотерейном билете свои 7 счастливых чисел, одновременно и определяет остальные 42 числа, какие числа он НЕ считает счастливыми. Для наглядности запишем число сочетаний в обоих случаях:
Получили одну и ту же дробь, в которой отличается лишь последовательность множителей в знаменателе. Можно показать, что и в общем случае число сочетаний из n по k совпадает с количеством сочетаний из n по (n– k):
