Написать формулу числа перестановок из 4 элементов. Комбинаторика

Посвященный решению задач выбора и расположения элементов некоторого, обычно конечного, множества в соответствии с заданными правилами. Например, сколькими способами можно выбрать 6 карт из колоды, состоящей из 36 карт, или сколькими способами можно составить очередь, состоящей из10 человек и т.д. Каждое правило в комбинаторике определяет способ построения некоторой конструкции, составленной из элементов исходного множества и называемой комбинацией . Основная цель комбинаторики состоит в подсчете количества комбинаций, которые можно составить из элементов исходного множества в соответствии с заданным правилом. Простейшими примерами комбинаторных конструкций являются перестановки, размещения и сочетания.

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

Для определения мощности множества, которое соответствует тому или иному событию, полезно разобраться с двумя правилами комбинаторики: правило произведения и правило суммы (иногда их называют принципами умножения и сложения соответственно).

Правило nроизведения: пусть из некоторого конечного множества

1-й объект можно выбрать k 1 способами,

2-ой объект - k 2 способами,

n -ый объект - k n способами. (1.1)

Тогда произвольный набор, перечисленных n объектов из данного множества можно выбрать k 1 , k 2 , …, k n способами.

Пример 1. Сколько существует трехзначных чисел с разными цифрами?

Решение . В десятичной системе исчисления десять цифр: 0,1,2,3,4,5,6,7,8,9. На первом месте может стоять любая из девяти цифр (кроме нуля). На втором месте - любая из оставшихся 9 цифр, кроме выбранной. На последнем месте любая из оставшихся 8 цифр.

По правилу произведения 9·9·8 = 648 трёхзначных чисел имеют разные цифры.

Пример 2. Из пункта в пункт ведут 3 дороги, а из пункта в пункт - 4 дороги. Сколькими способами можно совершить поездку из в через ?

Решение . В пункте есть 3 способа выбора дороги в пункт , а в пункте есть 4 способа попасть в пункт . Согласно принципу умножения, существует 3×4 = 12 способов попасть из пункта в пункт .

Правило суммы: при выполнении условий (1.1), любой из объектов можно выбрать k 1 +k 2 +…+k n способами.

Пример 3. Сколько существует способов выбора одного карандаша из коробки, содержащей 5 красных, 7 синих, 3 зеленых карандаша.

Решение . Один карандаш, по правилу суммы, можно выбрать 5+7+3 = 15 способами.

Пример 4. Пусть из города в город можно добраться одним авиамаршрутом, двумя железнодорожными маршрутами и тремя автобусными маршрутами. Сколькими способами можно добраться из города в город ?

Решение . Все условия принципа сложения здесь выполнены, поэтому, в соответствии с этим принципом, получим 1+2+3 = 6 способов.

Рассмотрим пример, иллюстрирующий различие принципов умножения и сложения.

Пример 5. В магазине электроники продаются три марки телевизоров и два вида видеомагнитофонов. У покупателя есть возможности приобрести либо телевизор, либо видеомагнитофон. Сколькими способами он может совершить одну покупку? Сколько различных комплектов, содержащих телевизор и магнитофон, можно приобрести в этом магазине, если покупатель собирается приобрести в паре и телевизор, и видеомагнитофон?

Решение . Один телевизор можно выбрать тремя способами, а магнитофон - другими двумя способами. Тогда телевизор или магнитофон можно купить 3+2=5 способами.

Во втором случае один телевизор можно выбрать тремя способами, после этого видеомагнитофон можно выбрать двумя способами. Следовательно, в силу принципа умножения, купить телевизор и видеомагнитофон можно 3×2 = 6 способами.

Рассмотрим теперь примеры, в которых применяются оба правила комбинаторики: и принцип умножения, и принцип сложения.

Пример 6. В корзине лежат 12 яблок и 10 апельсинов. Ваня выбирает либо яблоко, либо апельсин. После чего Надя выбирает из оставшихся фруктов и яблоко и апельсин. Сколько возможно таких выборов?

Решение . Ваня может выбрать яблоко 12 способами, апельсин - 10 способами. Если Ваня выбирает яблоко, то Надя может выбрать яблоко 11 способами, а апельсин - 10 способами. Если Ваня выбирает апельсин, то Надя может выбрать яблоко 12 способами, а апельсин - 9 способами. Таким образом, Ваня и Надя могут сделать свой выбор способами.

Пример 7. Есть 3 письма, каждое из которых можно послать по 6 адресам. Сколькими способами это можно сделать?

Решение . В данной задаче мы должны рассмотреть три случая:

а) все письма рассылаются по разным адресам;

б) все письма посылаются по одному адресу;

в) только два письма посылаются по одному адресу.

Если все письма рассылаются по разным адресам, то число таких способов легко находится из принципа умножения: n 1 = 6×5×4 = 120 способов. Если все письма посылаются по одному адресу, то таких способов будет n 2 = 6. Таким образом, остается рассмотреть только третий случай, когда только 2 письма посылаются по одному адресу. Выбрать какое-либо письмо мы можем 3 способами, и послать его по какому-либо выбранному адресу можем 6 способами. Оставшиеся два письма мы можем послать по оставшимся адресам 5 способами. Следовательно, послать только два письма по одному адресу мы можем n 3 =3×6×5=90 способами. Таким образом, разослать 3 письма по 6 адресам в соответствие с принципом сложения можно

способами.

Обычно в комбинаторике рассматривается идеализированный эксперимент по выбору наудачу k элементов из n . При этом элементы: а) не возвращаются обратно (схема выбора без возвращений); б) возвращаются обратно (схема выбора с возвращением).

1. Схема выбора без возвращений

Размещением из n элементов по k называют любой упорядоченный набор из k элементов, принадлежащих n - элементному множеству. Различные размещения отличны друг от друга или порядком элементов, или составом.

Число размещений из n элементов по k обозначается и вычисляется по формуле

(1.2)

где n ! = 1×2×3×…×n , 1! = 1, 0! = 1.

Пример 8. В соревнованиях участвует 10 человек, трое из них займут 1, 2, 3 место. Сколько существует различных вариантов?

Решение . В этом случае важен порядок распределения мест. Число различных вариантов равно

Перестановкой из n элементов называют размещение из n элементов по n. Число перестановок из n элементов обозначают P n и вычисляют по формуле

(1.3)

Пример 9. Сколько существует способов расстановки 10 книг на полке?

Решение . Общее число способов расстановки определяется как число перестановок (1.3) из 10 элементов и равно Р 10 = 10! = 3628 800.

2. Схема выбора с возвращениями

Если при выборе k элементов из n , элементы возвращаются обратно и упорядочиваются, то говорят, что это размещения с nовторениями .

Число размещений с повторениями:

Пример 11. В гостинице 10 комнат, каждая из которых может разместить четырех человек. Сколько существует вариантов размещения, прибывших четырех гостей?

Решение . Каждый следующий гость из 4 может быть помещён в любую из 10 комнат, так как рассматривается идеализированный опыт, поэтому общее число размещений, по формуле размещений с повторениями (1.5), равно

.

Если при выборе k элементов из n элементы возвращаются обратно без последующего упорядочивания, то говорят, что это сочетания с nовторениями. Число сочетаний с повторениями из n элементов по k определяется:

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

Решение . Число равновозможных заказов по формуле (1.6) равно

.

Комбинаторика - это раздел математики, в котором изучаются вопросы о том, сколько различных комбинаций, подчиненных тем или иным условиям, можно составить из заданных объектов. Основы комбинаторики очень важны для оценки вероятностей случайных событий, т.к. именно они позволяют подсчитать принципиальновозможное количество различных вариантов развития событий.

Основная формула комбинаторики

Пусть имеется k групп элементов, причем i-я группа состоит из n i элементов. Выберем по одному элементу из каждой группы. Тогда общее число N способов, которыми можно произвести такой выбор, определяется соотношением N=n 1 *n 2 *n 3 *...*n k .

Пример 1. Поясним это правило на простом примере. Пусть имеется две группы элементов, причем первая группа состоит из n 1 элементов, а вторая - из n 2 элементов. Сколько различных пар элементов можно составить из этих двух групп, таким образом, чтобы в паре было по одному элементу от каждой группы? Допустим, мы взяли первый элемент из первой группы и, не меняя его, перебрали все возможные пары, меняя только элементы из второй группы. Таких пар для этого элемента можно составить n 2 . Затем мы берем второй элемент из первой группы и также составляем для него все возможные пары. Таких пар тоже будет n 2 . Так как в первой группе всего n 1 элемент, всего возможных вариантов будет n 1 *n 2 .

Пример 2. Сколько трехзначных четных чисел можно составить из цифр 0, 1, 2, 3, 4, 5, 6, если цифры могут повторяться?
Решение: n 1 =6 (т.к. в качестве первой цифры можно взять любую цифру из 1, 2, 3, 4, 5, 6), n 2 =7 (т.к. в качестве второй цифры можно взять любую цифру из 0, 1, 2, 3, 4, 5, 6), n 3 =4 (т.к. в качестве третьей цифры можно взять любую цифру из 0, 2, 4, 6).
Итак, N=n 1 *n 2 *n 3 =6*7*4=168.

В том случае, когда все группы состоят из одинакового числа элементов, т.е. n 1 =n 2 =...n k =n можно считать, что каждый выбор производится из одной и той же группы, причем элемент после выбора снова возвращается в группу. Тогда число всех способов выбора равно n k . Такой способ выбора в комбинаторики носит название выборки с возвращением.

Пример 3. Сколько всех четырехзначных чисел можно составить из цифр 1, 5, 6, 7, 8?
Решение. Для каждого разряда четырехзначного числа имеется пять возможностей, значит N=5*5*5*5=5 4 =625.

Рассмотрим множество, состоящие из n элементов. Это множество в комбинаторике называется генеральной совокупностью .

Число размещений из n элементов по m

Определение 1. Размещением из n элементов по m в комбинаторике называется любой упорядоченный набор из m различных элементов, выбранных из генеральной совокупности в n элементов.

Пример 4. Различными размещениями из трех элементов {1, 2, 3} по два будут наборы (1, 2), (2, 1), (1, 3), (3, 1), (2, 3),(3, 2). Размещения могут отличаться друг от друга как элементами, так и их порядком.

Число размещений в комбинаторике обозначается A n m и вычисляется по формуле:

Замечание: n!=1*2*3*...*n (читается: "эн факториал"), кроме того полагают, что 0!=1.

Пример 5 . Сколько существует двузначных чисел, в которых цифра десятков и цифра единиц различные и нечетные?
Решение: т.к. нечетных цифр пять, а именно 1, 3, 5, 7, 9, то эта задача сводится к выбору и размещению на две разные позиции двух из пяти различных цифр, т.е. указанных чисел будет:

Определение 2. Сочетанием из n элементов по m в комбинаторике называется любой неупорядоченный набор из m различных элементов, выбранных из генеральной совокупности в n элементов.

Пример 6 . Для множества {1, 2, 3}сочетаниями являются {1, 2}, {1, 3}, {2, 3}.

Число сочетаний из n элементов по m

Число сочетаний обозначается C n m и вычисляется по формуле:

Пример 7. Сколькими способами читатель может выбрать две книжки из шести имеющихся?

Решение: Число способов равно числу сочетаний из шести книжек по две, т.е. равно:

Перестановки из n элементов

Определение 3. Перестановкой из n элементов называется любой упорядоченный набор этих элементов.

Пример 7a. Всевозможными перестановками множества, состоящего из трех элементов {1, 2, 3} являются: (1, 2, 3), (1, 3, 2), (2, 3, 1), (2, 1, 3), (3, 2, 1), (3, 1, 2).

Число различных перестановок из n элементов обозначается P n и вычисляется по формуле P n =n!.

Пример 8. Сколькими способами семь книг разных авторов можно расставить на полке в один ряд?

Решение: эта задача о числе перестановок семи разных книг. Имеется P 7 =7!=1*2*3*4*5*6*7=5040 способов осуществить расстановку книг.

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

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

Во-вторых, результат зависит от того, какой величины наборы элементов нам нужны.

И последнее, важно знать, является ли для нас существенным порядок элементов в наборе. Поясним последний фактор на следующем примере.

Пример 9. На родительском собрании присутствует 20 человек. Сколько существует различных вариантов состава родительского комитета, если в него должны войти 5 человек?
Решение: В этом примере нас не интересует порядок фамилий в списке комитета. Если в результате в его составе окажутся одни и те же люди, то по смыслу для нас это один и тот же вариант. Поэтому мы можем воспользоваться формулой для подсчета числа сочетаний из 20 элементов по 5.

Иначе будут обстоять дела, если каждый член комитета изначально отвечает за определенное направление работы. Тогда при одном и том же списочном составе комитета, внутри него возможно 5! вариантов перестановок , которые имеют значение. Количество разных (и по составу, и по сфере ответственности) вариантов определяется в этом случае числом размещений из 20 элементов по 5.

Задачи для самопроверки
1. Сколько трехзначных четных чисел можно составить из цифр 0, 1, 2, 3, 4, 5, 6, если цифры могут повторяться?

2. Сколько существует пятизначных чисел, которые одинаково читаются слева направо и справа налево?

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

4. Сколькими способами можно выбрать 4 делегата на конференцию, если в группе 20 человек?

5. Сколькими способами можно разложить восемь различных писем по восьми различным конвертам, если в каждый конверт кладется только одно письмо?

6. Из трех математиков и десяти экономистов надо составить комиссию, состоящую из двух математиков и шести экономистов. Сколькими способами это можно сделать?

Чтобы в материале было легче ориентироваться, добавлю содержание данной темы:

Введение. Множества и выборки.

В этой теме рассмотрим основные понятия комбинаторики: перестановки, сочетания и размещения. Выясним их суть и формулы, по которым можно найти их количество.

Для работы нам понадобятся кое-какие вспомогательные сведения. Начнём с такого фундаментального математического понятия как множество. Подробно понятие множества было раскрыто в теме "Понятие множества. Способы задания множеств" .

Очень краткий рассказ про множества : показать\скрыть

Если вкратце: множеством именуют некую совокупность объектов. Записывают множества в фигурных скобках. Порядок записи элементов роли не играет; повторения элементов не допускаются. Например, множество цифр числа 11115555999 будет таким: $\{1,5,9 \}$. Множество согласных букв в слове "тигрёнок" таково: $\{т, г, р, н, к\}$. Запись $5\in A$ означает, что элемент 5 принадлежит множеству $A=\{1,5,9 \}$. Количество элементов в конечном множестве называют мощностью этого множества и обозначают $|A|$. Например, для множества $A=\{1,5,9 \}$, содержащего 3 элемента, имеем: $|A|=3$.

Рассмотрим некое непустое конечное множество $U$, мощность которого равна $n$, $|U|=n$ (т.е. в множестве $U$ имеется $n$ элементов). Введём такое понятие, как выборка (некоторые авторы именуют её кортежем). Под выборкой объема $k$ из $n$ элементов (сокращённо $(n,k)$-выборкой) будем понимать набор элементов $(a_1, a_2,\ldots, a_k)$, где $a_i\in U$. Выборка называется упорядоченной, если в ней задан порядок следования элементов. Две упорядоченные выборки, различающиеся лишь порядком элементов, являются различными. Если порядок следования элементов выборки не является существенным, то выборку именуют неупорядоченной.

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

Для примера рассмотрим множество $U=\{a,b,c,d,e\}$. Множество $U$ содержит 5 элементов, т.е. $|U|=5$. Выборка без повторений может быть такой: $(a,b,c)$. Данная выборка содержит 3 элемента, т.е. объём этой выборки равен 3. Иными словами, это $(5,3)$-выборка.

Выборка с повторениями может быть такой: $(a,a,a,a,a,c,c,d)$. Она содержит 8 элементов, т.е. объём её равен 8. Иными словами, это $(5,8)$-выборка.

Рассмотрим ещё две $(5,3)$-выборки: $(a,b,b)$ и $(b,a,b)$. Если мы полагаем наши выборки неупорядоченными, то выборка $(a,b,b)$ равна выборке $(b,a,b)$, т.е. $(a,b,b)=(b,a,b)$. Если мы полагаем наши выборки упорядоченными, то $(a,b,b)\neq(b,a,b)$.

Рассмотрим ещё один пример, немного менее абстрактный:) Предположим, в корзине лежат шесть конфет, причём все они различны. Если первой конфете поставить в соответствие цифру 1, второй конфете - цифру 2 и так далее, то с конфетами в корзине можно сопоставить такое множество: $U=\{1,2,3,4,5,6\}$. Представьте, что мы наугад запускаем руку в корзинку с целью вытащить три конфеты. Вытащенные конфеты - это и есть выборка. Так как мы вытаскиваем 3 конфеты из 6, то получаем (6,3)-выборку. Порядок расположения конфет в ладони совершенно несущественен, поэтому эта выборка является неупорядоченной. Ну, и так как все конфеты различны, то выборка без повторений. Итак, в данной ситуации говорим о неупорядоченной (6,3)-выборке без повторений.

Теперь подойдём с иной стороны. Представим себе, что мы находимся на фабрике по производству конфет, и на этой фабрике производятся конфеты четырёх сортов. Множество $U$ в этой ситуации таково: $U=\{1,2,3,4 \}$ (каждая цифра отвечает за свой сорт конфет). Теперь вообразим, что все конфеты ссыпаются в единый жёлоб, около которого мы и стоим. И, подставив ладони, из этого потока отбираем 20 конфет. Конфеты в горсти – это и есть выборка. Играет ли роль порядок расположения конфет в горсти? Естественно, нет, поэтому выборка неупорядоченная. Всего 4 сорта конфет, а мы отбираем двадцать штук из общего потока - повторения сортов неизбежны. При этом выборки могут быть самыми различными: у нас даже могут оказаться все конфеты одного сорта. Следовательно, в этой ситуации мы имеем дело с неупорядоченной (4,20)-выборкой с повторениями.

Рассмотрим ещё пару примеров. Пусть на кубиках написаны различные 7 букв: к, о, н, ф, е, т, а. Эти буквы образуют множество $U=\{к,о,н,ф,е,т,а\}$. Допустим, из данных кубиков мы хотим составить "слова" из 5 букв. Буквы этих слов (к примеру, «конфе», «тенко» и так далее) образуют (7,5)-выборки: $(к,о,н,ф,е)$, $(т,е,н,к,о)$ и т.д. Очевидно, что порядок следования букв в такой выборке важен. Например, слова «нокфт» и «кфтон» различны (хотя состоят из одних и тех же букв), ибо в них не совпадает порядок букв. Повторений букв в таких «словах» нет, ибо в наличии только семь кубиков. Итак, набор букв каждого слова представляет собой упорядоченную (7,5)-выборку без повторений.

Еще один пример: мы составляем всевозможные восьмизначные числа из четырёх цифр 1, 5, 7, 8. Например, 11111111, 15518877, 88881111 и так далее. Множество $U$ таково: $U=\{1,5,7,8\}$. Цифры каждого составленного числа образуют (4,8)-выборку. Порядок следования цифр в числе важен, т.е. выборка упорядоченная. Повторения допускаются, поэтому здесь мы имеем дело с упорядоченной (4,8)-выборкой с повторениями.

Размещения без повторений из $n$ элементов по $k$

Размещение без повторений из $n$ элементов по $k$ - упорядоченная $(n,k)$-выборка без повторений.

Так как элементы в рассматриваемой выборке повторяться не могут, то мы не можем отобрать в выборку больше элементов, чем есть в исходном множестве. Следовательно, для таких выборок верно неравенство: $n≥ k$. Количество размещений без повторений из $n$ элементов по $k$ определяется следующей формулой:

\begin{equation}A_{n}^{k}=\frac{n!}{(n-k)!} \end{equation}

Что обозначает знак "!"? : показать\скрыть

Запись "n!" (читается "эн факториал") обозначает произведение всех чисел от 1 до n, т.е.

$$ n!=1\cdot2\cdot 3\cdot \ldots\cdot n $$

По определению полагается, что $0!=1!=1$. Для примера найдём 5!:

$$ 5!=1\cdot 2\cdot 3\cdot 4\cdot 5=120. $$

Пример №1

Алфавит состоит из множества символов $E=\{+,*,0,1,f\}$. Определим количество таких трёхсимвольных слов в этом алфавите, которые не содержат повторяющихся букв.

Под трёхсимвольными словами будем понимать выражения вида "+*0" или "0f1". В множестве $E$ пять элементов, поэтому буквы трехсимвольных слов образуют (5,3)-выборки. Первый вопрос: эти выборки упорядочены или нет? Слова, которые отличаются лишь порядком букв, полагаются различными, поэтому порядок элементов в выборке важен. Значит, выборка является упорядоченной. Второй вопрос: допускаются повторения или нет? Ответ на этот вопрос даёт условие: слова не должны содержать повторяющихся букв. Подводим итоги: буквы каждого слова, удовлетворяющего условию задачи, образуют упорядоченную (5,3)-выборку без повторений. Иными словами, буквы каждого слова образуют размещение без повторений из 5 элементов по 3. Вот примеры таких размещений:

$$ (+,*,f), \; (*,+,f), \; (1,+,0) $$

Нас же интересует общее количество этих размещений. Согласно формуле (1) количество размещений без повторений из 5 элементов по 3 будет таким:

$$ A_{5}^{3}=\frac{5!}{(5-3)!}=\frac{5!}{2!}=60. $$

Т.е. можно составить 60 трёхсимвольных слов, буквы которых не будут повторяться.

Ответ : 60.

Размещения с повторениями из $n$ элементов по $k$

Размещение с повторениями из $n$ элементов по $k$ - упорядоченная $(n,k)$-выборка с повторениями.

Количество размещений с повторениями из $n$ элементов по $k$ определяется следующей формулой:

\begin{equation}\bar{A}_{n}^{k}=n^k \end{equation}

Пример №2

Сколько пятизначных чисел можно составить из множества цифр $\{5,7,2\}$?

Из данного набора цифр можно составить пятизначные числа 55555, 75222 и так далее. Цифры каждого такого числа образуют (3,5)-выборку: $(5,5,5,5,5)$, $(7,5,2,2,2)$. Зададимся вопросом: что это за выборки? Во-первых, цифры в числах могут повторяться, поэтому мы имеем дело с выборками с повторениями. Во-вторых, порядок расположения цифр в числе важен. Например, 27755 и 77255 - разные числа. Следовательно, мы имеем дело с упорядоченными (3,5)-выборками с повторениями. Общее количество таких выборок (т.е. общее количество искомых пятизначных чисел) найдём с помощью формулы (2):

$$ \bar{A}_{3}^{5}=3^5=243. $$

Следовательно, из заданных цифр можно составить 243 пятизначных числа.

Ответ : 243.

Перестановки без повторений из $n$ элементов

Перестановка без повторений из $n$ элементов - упорядоченная $(n,n)$-выборка без повторений.

По сути, перестановка без повторений есть частный случай размещения без повторений, когда объём выборки равен мощности исходного множества. Количество перестановок без повторений из $n$ элементов определяется следующей формулой:

\begin{equation}P_{n}=n! \end{equation}

Эту формулу, кстати, легко получить, если учесть, что $P_n=A_{n}^{n}$. Тогда получим:

$$ P_n=A_{n}^{n}=\frac{n!}{(n-n)!}=\frac{n!}{0!}=\frac{n!}{1}=n! $$

Пример №3

В морозилке лежат пять порций мороженого от различных фирм. Сколькими способами можно выбрать порядок их съедения?

Пусть первому мороженому соответствует цифра 1, второму - цифра 2 и так далее. Мы получим множество $U=\{1,2,3,4,5\}$, которое будет представлять содержимое морозилки. Порядок съедения может быть таким: $(2,1,3,5,4)$ или таким: $(5,4,3,1,2)$. Каждый подобный набор есть (5,5)-выборка. Она будет упорядоченной и без повторений. Иными словами, каждая такая выборка есть перестановка из 5 элементов исходного множества. Согласно формуле (3) общее количество этих перестановок таково:

$$ P_5=5!=120. $$

Следовательно, существует 120 порядков выбора очередности съедения.

Ответ : 120.

Перестановки с повторениями

Перестановка с повторениями – упорядоченная $(n,k)$-выборка с повторениями, в которой элемент $a_1$ повторяется $k_1$ раз, $a_2$ повторяется $k_2$ раза так далее, до последнего элемента $a_r$, который повторяется $k_r$ раз. При этом $k_1+k_2+\ldots+k_r=k$.

Общее количество перестановок с повторениями определяется формулой:

\begin{equation}P_{k}(k_1,k_2,\ldots,k_r)=\frac{k!}{k_1!\cdot k_2!\cdot \ldots \cdot k_r!} \end{equation}

Пример №4

Слова составляются на основе алфавита $U=\{a,b,d\}$. Сколько различных слов из семи символов может быть составлено, если в этих словах буква "a" должна повторяться 2 раза; буква "b" - 1 раз, а буква "d" - 4 раза?

Вот примеры искомых слов: "aabdddd", "daddabd" и так далее. Буквы каждого слова образуют (3,7)-выборку с повторениями: $(a,a,b,d,d,d,d)$, $(d,a,d,d,a,b,d)$ и т.д. Каждая такая выборка состоит из двух элементов "a", одного элемента "b" и четырёх элементов "d". Иными словами, $k_1=2$, $k_2=1$, $k_3=4$. Общее количество повторений всех символов, естественно, равно объёму выборки, т.е. $k=k_1+k_2+k_3=7$. Подставляя эти данные в формулу (4), будем иметь:

$$ P_7(2,1,4)=\frac{7!}{2!\cdot 1!\cdot 4!}=105. $$

Следовательно, общее количество искомых слов равно 105.

Ответ : 105.

Сочетания без повторений из $n$ элементов по $k$

Сочетание без повторений из $n$ элементов по $k$ – неупорядоченная $(n,k)$-выборка без повторений.

Общее количество сочетаний без повторений из $n$ элементов по $k$ определяется формулой:

\begin{equation}C_{n}^{k}=\frac{n!}{(n-k)!\cdot k!} \end{equation}

Пример №5

В корзине размещены карточки, на которых написаны целые числа от 1 до 10. Из корзины вынимают 4 карточки и суммируют числа, написанные на них. Сколько различных наборов карточек можно вытащить из корзины?

Итак, в данной задаче исходное множество таково: $U=\{1,2,3,4,5,6,7,8,9,10\}$. Из этого множества мы выбираем четыре элемента (т.е., четыре карточки из корзины). Номера вытащенных элементов образуют (10,4)-выборку. Повторения в этой выборке не допускаются, так как номера всех карточек различны. Вопрос вот в чём: порядок выбора карточек играет роль или нет? Т.е., к примеру, равны ли выборки $(1,2,7,10)$ и $(10,2,1,7)$ или не равны? Тут нужно обратиться к условию задачи. Карточки вынимаются для того, чтобы потом найти сумму элементов. А это значит, что порядок карточек не важен, так как от перемены мест слагаемых сумма не изменится. Например, выборке $(1,2,7,10)$ и выборке $(10,2,1,7)$ будет соответствовать одно и то же число $1+2+7+10=10+2+1+7=20$. Вывод: из условия задачи следует, что мы имеем дело с неупорядоченными выборками. Т.е. нам нужно найти общее количество неупорядоченных (10,4)-выборок без повторений. Иными словами, нам нужно найти количество сочетаний из 10 элементов по 4. Используем для этого формулу (5):

$$ C_{10}^{4}=\frac{10!}{(10-4)!\cdot 4!}=\frac{10!}{6!\cdot 4!}=210. $$

Следовательно, общее количество искомых наборов равно 210.

Ответ : 210.

Сочетания с повторениями из $n$ элементов по $k$

Сочетание с повторениями из $n$ элементов по $k$ – неупорядоченная $(n,k)$-выборка с повторениями.

Общее количество сочетаний с повторениями из $n$ элементов по $k$ определяется формулой:

\begin{equation}\bar{C}_{n}^{k}=\frac{(n+k-1)!}{(n-1)!\cdot k!} \end{equation}

Пример №6

Представьте себе, что мы находимся на конфетном заводе, - прямо возле конвейера, по которому движутся конфеты четырёх сортов. Мы запускаем руки в этот поток и вытаскиваем двадцать штук. Сколько всего различных "конфетных комбинаций" может оказаться в горсти?

Если принять, что первому сорту соответствует число 1, второму сорту - число 2 и так далее, то исходное множество в нашей задаче таково: $U=\{1,2,3,4\}$. Из этого множества мы выбираем 20 элементов (т.е., те самые 20 конфет с конвейера). Пригоршня конфет образует (4,20)-выборку. Естественно, повторения сортов будут. Вопрос в том, играет роль порядок расположения элементов в выборке или нет? Из условия задачи следует, что порядок расположения элементов роли не играет. Нам нет разницы, будут ли в горсти располагаться сначала 15 леденцов, а потом 4 шоколадных конфеты, или сначала 4 шоколадных конфеты, а уж потом 15 леденцов. Итак, мы имеем дело с неупорядоченной (4,20) выборкой с повторениями. Чтобы найти общее количество этих выборок используем формулу (6):

$$ \bar{C}_{4}^{20}=\frac{(4+20-1)!}{(4-1)!\cdot 20!}=\frac{23!}{3!\cdot 20!}=1771. $$

Следовательно, общее количество искомых комбинаций равно 1771.

Следует отметить, что комбинаторика является самостоятельным разделом высшей математики (а не частью тервера) и по данной дисциплине написаны увесистые учебники, содержание которых, порой, ничуть не легче абстрактной алгебры. Однако нам будет достаточно небольшой доли теоретических знаний, и в данной статье я постараюсь в доступной форме разобрать основы темы с типовыми комбинаторными задачами. А многие из вас мне помогут;-)

Чем будем заниматься? В узком смысле комбинаторика - это подсчёт различных комбинаций, которые можно составить из некоторого множества дискретных объектов. Под объектами понимаются какие-либо обособленные предметы или живые существа - люди, звери, грибы, растения, насекомые и т.д. При этом комбинаторику совершенно не волнует, что множество состоит из тарелки манной каши, паяльника и болотной лягушки. Принципиально важно, что эти объекты поддаются перечислению - их три (дискретность) и существенно то, что среди них нет одинаковых.

С множеством разобрались, теперь о комбинациях. Самыми распространёнными видами комбинаций являются перестановки объектов, их выборка из множества (сочетание) и распределение (размещение). Давайте прямо сейчас посмотрим, как это происходит:

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

Не пугайтесь малопонятных терминов, тем более, некоторые из них действительно не очень удачны. Начнём с хвоста заголовка - что значит «без повторений »? Это значит, что в данном параграфе будут рассматриваться множества, которые состоят из различных объектов. Например, … нет, кашу с паяльником и лягушкой предлагать не буду, лучше что-нибудь повкуснее =) Представьте, что перед вами на столе материализовалось яблоко, груша и банан (при наличии таковых ситуацию можно смоделировать и реально). Выкладываем фрукты слева направо в следующем порядке:

яблоко / груша / банан

Вопрос первый : сколькими способами их можно переставить?

Одна комбинация уже записана выше и с остальными проблем не возникает:

яблоко / банан / груша
груша / яблоко / банан
груша / банан / яблоко
банан / яблоко / груша
банан / груша / яблоко

Итого : 6 комбинаций или 6 перестановок .

Хорошо, здесь не составило особого труда перечислить все возможные случаи, но как быть, если предметов больше? Уже с четырьмя различными фруктами количество комбинаций значительно возрастёт!

Никаких мучений - 3 объекта можно переставить способами.

Вопрос второй : сколькими способами можно выбрать а) один фрукт, б) два фрукта, в) три фрукта, г) хотя бы один фрукт?

Зачем выбирать? Так нагуляли же аппетит в предыдущем пункте - для того, чтобы съесть! а) Один фрукт можно выбрать, очевидно, тремя способами - взять либо яблоко, либо грушу, либо банан.

Формальный подсчёт проводится по формуле количества сочетаний :

Запись в данном случае следует понимать так: «сколькими способами можно выбрать 1 фрукт из трёх?»

б) Перечислим все возможные сочетания двух фруктов:

яблоко и груша;
яблоко и банан;
груша и банан.

Количество комбинаций легко проверить по той же формуле:

Запись понимается аналогично: «сколькими способами можно выбрать 2 фрукта из трёх?».

в) И, наконец, три фрукта можно выбрать единственным способом:

Кстати, формула количества сочетаний сохраняет смысл и для пустой выборки:
способом можно выбрать ни одного фрукта - собственно, ничего не взять и всё.

г) Сколькими способами можно взять хотя бы один фрукт? Условие «хотя бы один» подразумевает, что нас устраивает 1 фрукт (любой) или 2 любых фрукта или все 3 фрукта:
способами можно выбрать хотя бы один фрукт.

Для ответа на следующий вопрос мне требуется два добровольца… …Ну что же, раз никто не хочет, тогда буду вызывать к доске =)

Вопрос третий : сколькими способами можно раздать по одному фрукту Даше и Наташе?

Для того чтобы раздать два фрукта, сначала нужно их выбрать. Согласно пункту «бэ» предыдущего вопроса, сделать это можно способами, перепишу их заново:

яблоко и груша;
яблоко и банан;
груша и банан.

Но комбинаций сейчас будет в два раза больше. Рассмотрим, например, первую пару фруктов:
яблоком можно угостить Дашу, а грушей - Наташу;
либо наоборот - груша достанется Даше, а яблоко - Наташе.

И такая перестановка возможна для каждой пары фруктов.

В данном случае работает формула количества размещений :

Она отличается от формулы тем, что учитывает не только количество способов, которым можно выбрать несколько объектов, но и все перестановки объектов в каждой возможной выборке. Так, в рассмотренном примере, важно не только то, что можно просто выбрать, например, грушу и банан, но и то, как они будут распределены (размещены) между Дашей и Наташей.

Постарайтесь хорошо уяснить разницу между перестановками, сочетаниями и размещениями. В простейших случаях можно пересчитать все возможные комбинации вручную, но чаще всего это становится неподъемной задачей, именно поэтому и нужно понимать смысл формул.

Также напоминаю, что сейчас речь идёт о множестве с различными объектами, и если яблоко/грушу/банан заменить на 3 яблока или даже на 3 очень похожих яблока, то в контексте рассмотренной задачи они всё равно будут считаться различными .

Остановимся на каждом виде комбинаций подробнее:

Перестановки

Перестановками называют комбинации, состоящие из одних и тех же различных объектов и отличающиеся только порядком их расположения. Количество всех возможных перестановок выражается формулой

Отличительной особенностью перестановок является то, что в каждой из них участвует ВСЁ множество, то есть, все объектов. Например, дружная семья:

Задача 1

Сколькими способами можно рассадить 5 человек за столом?

Решение : используем формулу количества перестановок:

Ответ : 120 способами

Невероятно, но факт. Обратите внимание, что здесь не имеет значения круглый ли стол, квадратный, или вообще все люди сели на скамейку вдоль одной стены - важно лишь количество объектов и их взаимное расположение. Помимо перестановок людей, часто встречается задача о перестановках различных книг на полке, но это было бы слишком просто даже для чайника:

Задача 2

Сколько четырёхзначных чисел можно составить из четырёх карточек с цифрами 0, 5, 7, 9?

Для того чтобы составить четырёхзначное число нужно задействовать все четыре карточки (цифры на которых различны! ) , и это очень важная предпосылка для применения формулы Очевидно, что, переставляя карточки, мы будем получать различные четырёхзначные числа, … стоп, а всё ли тут в порядке? ;-)

Хорошенько подумайте над задачей! Вообще, это характерная черта комбинаторных и вероятностных задач - в них НУЖНО ДУМАТЬ. И зачастую думать по-житейски, как, например, в разборе вступительного примера с фруктами. Нет, конечно, я не призываю тупо прорабатывать другие разделы математики, однако должен заметить, что те же интегралы можно научиться решать чисто механически.

Решение и ответ в конце урока.

Увеличиваем обороты:

Сочетания

В учебниках обычно даётся лаконичное и не очень понятное определение сочетаний, поэтому, в моих устах формулировка будет не особо рациональной, но, надеюсь, доходчивой:

Сочетаниями называют различные комбинации из объектов, которые выбраны из множества различных объектов, и которые отличаются друг от друга хотя бы одним объектом. Иными словами, отдельно взятое сочетание - это уникальная выборка из элементов, в которой не важен их порядок (расположение). Общее же количество таких уникальных сочетаний рассчитывается по формуле .

Задача 3

В ящике находится 15 деталей. Сколькими способами можно взять 4 детали?

Решение : прежде всего, снова обращаю внимание на то, что по логике условия, детали считаются различными - даже если они на самом деле однотипны и визуально одинаковы (в этом случае их можно, например, пронумеровать) .

В задаче речь идёт о выборке из 4-х деталей, в которой не имеет значения их «дальнейшая судьба» - грубо говоря, «просто выбрали 4 штуки и всё». Таким образом, у нас имеют место сочетания деталей. Считаем их количество:

Здесь, конечно же, не нужно ворочать огромные числа .
В похожей ситуации я советую использовать следующий приём: в знаменателе выбираем наибольший факториал (в данном случае ) и сокращаем на него дробь. Для этого числитель следует представить в виде . Распишу очень подробно:

Способами можно взять 4 детали из ящика.

Ещё раз: что это значит? Это значит, что из набора 15-ти различных деталей можно составить одну тысячу триста шестьдесят пять уникальных сочетания 4-х деталей. То есть, каждая такая комбинация из 4-х деталей будет отличаться от других комбинаций хотя бы одной деталью.

Ответ : 1365 способами

Формуле необходимо уделить самое пристальное внимание, поскольку она является «хитом» комбинаторики. При этом полезно понимать и без всяких вычислений записывать «крайние» значения: . Применительно к разобранной задаче:

Единственным способом можно взять ни одной детали;
способами можно взять 1 деталь (любую из 15-ти);
способами можно взять 14 деталей (при этом какая-то одна из 15-ти останется в ящике);
- единственным способом можно взять все пятнадцать деталей.

Рекомендую внимательно ознакомиться с биномом Ньютона и треугольником Паскаля , по которому, к слову, очень удобно выполнять проверку вычислений при небольших значениях «эн».

Задача 4

Сколькими способами из колоды в 36 карт можно выбрать 3 карты?

Это пример для самостоятельного решения. Чем приятны многие комбинаторные задачи, так это краткостью - главное, разобраться в сути. И суть, бывает, открывается с различных сторон. Разберём весьма поучительный пример:

Задача 4

В шахматном турнире участвует человек и каждый с каждым играет по 1-й партии. Сколько всего партий сыграно в турнире?

Поскольку я сам играю в шахматы и неоднократно принимал участие в круговых турнирах, то сразу же сориентировался по турнирной таблице размером клеток, в которой результат каждой партии учитывается дважды и, кроме того, затушёвываются клетки «главной диагонали» (т.к. участники не играют сами с собой) . Исходя из проведённых рассуждений, общее количество сыгранных партий рассчитывается по формуле . Такое решение полностью корректно (см. соответствующий файл банка готовых решений ) и на долгое время я забыл о нём по принципу «решено, да и ладно».

Однако один из посетителей сайта заметил, что на самом деле здесь можно руководствоваться самыми что ни на есть банальными сочетаниями:
различных пар можно составить из соперников (кто играет белыми, кто чёрными - не важно) .

Эквивалентной является задача о рукопожатиях: в отделе работает мужчин и каждый с каждым здоровается за руку, сколько рукопожатий они совершают? К слову, шахматисты тоже пожимают друг другу руку перед каждой партией.

Ну а вывода тут два:

Во-первых, не всё очевидное - очевидно;

И во-вторых, не бойтесь решать задачи «нестандартно»!

Большое спасибо за ваши письма, они помогают улучшить качество учебных материалов!

Размещения

Или «продвинутые» сочетания. Размещениями называют различные комбинации из объектов, которые выбраны из множества различных объектов, и которые отличаются друг от друга как составом объектов в выборке, так и их порядком . Количество размещений рассчитывается по формуле

Что наша жизнь? Игра:

Задача 5

Боря, Дима и Володя сели играть в «очко». Сколькими способами им можно сдать по одной карте? (колода содержит 36 карт)

Решение : ситуация похожа на Задачу 4, но отличается тем, что здесь важно не только то, какие три карты будут извлечены из колоды, но и то, КАК они будут распределены между игроками. По формуле размещений:

Способами можно раздать 3 карты игрокам.

Есть и другая схема решения, которая, с моей точки зрения, даже понятнее:

способами можно извлечь 3 карты из колоды.

Теперь давайте рассмотрим, какую-нибудь одну из семи тысяч ста сорока комбинаций, например: король пик, 9 червей, 7 червей. Выражаясь комбинаторной терминологией, эти 3 карты можно «переставить» между Борей, Димой и Володей способами:

КП, 9Ч, 7Ч;
КП, 7Ч, 9Ч;
9Ч, КП, 7Ч;
9Ч, 7Ч, КП;
7Ч, КП, 9Ч;
7Ч, 9Ч, КП.

И аналогичный факт справедлив для любого уникального набора из 3-х карт. А таких наборов, не забываем, мы насчитали . Не нужно быть профессором, чтобы понять, что найденное количество сочетаний следует умножить на шесть:

Способами можно сдать по одной карте 3-м игрокам.

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

Ответ : 42840

Возможно, у вас остался вопрос, а кто же раздавал карты? …Наверное, преподаватель =)
И чтобы никому не было обидно, в следующей задаче примет участие вся студенческая группа:

Задача 6

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

Задача о «размещении» должностей в коллективе встречается очень часто и является самым настоящим баяном. Краткое решение и ответ в конце урока.

Реферат на тему:

Выполнил ученик 10 класса «В»

средней школы №53

Глухов Михаил Александрович

г. Набережные Челны

2002 г.
Содержание

Из истории комбинаторики

Комбинаторика занимается различного вида соединениями, которые можно образовать из элементов конечного множества. Некоторые элементы комбинаторики были известны в Индии еще во II в. до н. э. Нидийцы умели вычислять числа, которые сейчас называют "сочетания". В XII в. Бхаскара вычислял некоторые виды сочетаний и перестановок. Предполагают, что индийские ученые изучали соединения в связи с применением их в поэтике, науке о структуре стиха и поэтических произведениях. Например, в связи с подсчетом возможных сочетаний ударных (долгих) и безударных (кратких) слогов стопы из n слогов. Как научная дисциплина, комбинаторика сформировалась в XVII в. В книге "Теория и практика арифметики" (1656 г.) французский автор А. Также посвящает сочетаниям и перестановкам целую главу.
Б. Паскаль в "Трактате об арифметическом треугольнике" и в "Трактате о числовых порядках" (1665 г.) изложил учение о биномиальных коэффициентах. П. Ферма знал о связях математических квадратов и фигурных чисел с теорией соединений. Термин "комбинаторика" стал употребляться после опубликования Лейбницем в 1665 г. работы "Рассуждение о комбинаторном искусстве", в которой впервые дано научное обоснование теории сочетаний и перестановок. Изучением размещений впервые занимался Я. Бернулли во второй части своей книги "Ars conjectandi" (искусство предугадывания) в 1713 г. Современная символика сочетаний была предложена разными авторами учебных руководств только в XIX в.

Все разнообразие комбинаторных формул может быть выведено из двух основных утверждений, касающихся конечных множеств – правило суммы и правило произведения.

Правило суммы

Если конечные множества не пересекаются, то число элементов X U Y {или} равно сумме числа элементов множества X и числа элементов множества Y.

То есть, если на первой полке стоит X книг, а на второй Y, то выбрать книгу из первой или второй полки, можно X+Y способами.

Примеры задач

Ученик должен выполнить практическую работу по математике. Ему предложили на выбор 17 тем по алгебре и 13 тем по геометрии. Сколькими способами он может выбрать одну тему для практической работы?

Решение: X=17, Y=13

По правилу суммы X U Y=17+13=30 тем.

Имеется 5 билетов денежно-вещевой лотереи, 6 билетов спортлото и 10 билетов автомотолотереи. Сколькими способами можно выбрать один билет из спортлото или автомотолотереи?

Решение: Так как денежно-вещевая лотерея в выборе не участвует, то всего 6+10=16 вариантов.

Правило произведения

Если элемент X можно выбрать k способами, а элемент Y-m способами то пару (X,Y) можно выбрать k*m способами.

То есть, если на первой полке стоит 5 книг, а на второй 10, то выбрать одну книгу с первой полки и одну со второй можно 5*10=50 способами.

Примеры задач

Переплетчик должен переплести 12 различных книг в красный, зеленый и коричневые переплеты. Сколькими способами он может это сделать?

Решение: Имеется 12 книг и 3 цвета, значит по правилу произведения возможно 12*3=36 вариантов переплета.

Сколько существует пятизначных чисел, которые одинаково читаются слева направо и справа налево?

Решение: В таких числах последняя цифра будет такая же, как и первая, а предпоследняя - как и вторая. Третья цифра будет любой. Это можно представить в виде XYZYX , где Y и Z -любые цифры, а X - не ноль. Значит по правилу произведения количество цифр одинаково читающихся как слева направо, так и справа налево равно 9*10*10=900 вариантов.

Пересекающиеся множества

Но бывает, что множества X и Y пересекаются, тогда пользуются формулой

20 человекзнаютанглийскийи 10 - немецкий, изних 5 знаютианглийский, инемецкий. СколькоЧеловеквсего?

Ответ: 10+20-5=25 человек.

Также часто для наглядного решения задачи применяются круги Эйлера. Например:

Решение: Выразим условие этой задачи графически. Обозначим кругом тех, кто знает английский, другим кругом - тех, кто знает французский, и третьим кругом - тех, кто знают немецкий.

Аналогично получаем, что только английским и немецким владеют 8-3=5 человек, а немецким и французским 5-3=2 туриста. Вносим эти данные в соответствующие части.

По условию задачи всего 100 туристов. 20+13+30+5+7+2+3=80 туристов знают хотя бы один язык, следовательно, 20 человек не владеют ни одним из данных языков.

Размещения без повторений.

Сколько можно составить телефонных номеров из 6 цифр каждый, так чтобы все цифры были различны?

Это пример задачи на размещение без повторений. Размещаются здесь 10 цифр по 6. А варианты, при которых одинаковые цифры стоят в разном порядке считаются разными.

Если X-множество, состоящие из n элементов, m≤n, то размещением без повторений из n элементов множества X по m называется упорядоченное множество X, содержащее m элементов называется упорядоченное множество X, содержащее m элементов.

Количество всех размещений из n элементов по m обозначают

n! - n-факториал (factorial анг. сомножитель) произведение чисел натурального ряда от 1 до какого либо числа n

n!=1*2*3*...*n 0!=1

Значит, ответ на вышепоставленную задачу будет

Задача

Сколькими способами 4 юноши могут пригласить четырех из шести девушек на танец?

Решение : два юноши не могут одновременно пригласить одну и ту же девушку. И варианты, при которых одни и те же девушки танцуют с разными юношами считаются, разными, поэтому:

Возможно 360 вариантов.

Перестановки без повторений

В случае n=m (см. размещения без повторений) из n элементов по m называется перестановкой множества x.

Количество всех перестановок из n элементов обозначают P n.

Действительно при n=m:

Примеры задач

Сколько различных шестизначных чисел можно составить из цифр 0, 1, 2, 3, 4,5, если цифры в числе не повторяются?

1) Найдем количество всех перестановок из этих цифр: P 6 =6!=720

2) 0 не может стоять впереди числа, поэтому от этого числа необходимо отнять количество перестановок, при котором 0 стоит впереди. А это P 5 =5!=120.

P 6 -P 5 =720-120=600

Проказница Мартышка

Да косолапый Мишка

Затеяли играть квартет

Стой, братцы стой! –

Кричит Мартышка, - погодите!

Как музыке идти?

Ведь вы не так сидите…

И так, и этак пересаживались – опять музыка на лад не идет.