Для каких комбинаций важен порядок элементов. Комбинаторика - основные понятия и формулы

Перестановки. Формула для числа перестановок

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

Пусть множество Х состоит из n элементов.

Определение. Размещение без повторений из n элементов множества X по n называется перестановкой из n элементов.

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

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

Так как перестановки – это частный случай размещений без повторений при , то формулу для нахождения числа получим из формулы (2), подставляя в неё :

Таким образом,

(3)

Пример. Сколькими способами можно разместить на полке 5 книг?

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

Замечание. Формулы (1)-(3) запоминать не обязательно: задачи на их применение всегда можно решить с помощью правила произведения. Если у учащихся существуют проблемы с составлением комбинаторных моделей задач, то лучше сделать более узким множество используемых формул и правил (чтобы было меньше возможности ошибиться). Правда, задачи, в которых используются перестановки и формула (3), обычно решаются без особых проблем.

Задачи

1. Ф. Сколькими способами могут встать в очередь в билетную кассу: 1) 3 человека; 2) 5 человек?

Решение.

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

Три человека могут встать в очередь Р3 = 3! = 6 различными способами.

Ответ: 1) 6 способов; 2) 120 способов.

2. Т. Сколькими способами 4 человека могут разместиться на четырехместной скамейке?

Решение.

Количество человек равно количеству мест на скамейке, поэтому количество способов размещения равно числу перестановок из 4 элементов: Р4 = 4! = 24.

Можно рассуждать по правилу произведения: для первого человека можно выбрать любое из 4 мест, для второго - любое из 3 оставшихся, для третьего - любое из 2 оставшихся, последний займет 1 оставшееся место; всего есть = 24 разных способов Размещения 4 человек на четырехместной скамейке.

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

3. М. У Вовы на обед - первое, второе, третье блюда и пирожное. Он обязательно начнет с пирожного, а все остальное съест в произвольном порядке. Найдите число возможных вариантов обеда.

М- задачи из уч. пособия А.Г.Мордковича

Т- под ред. С.А.Теляковского

Ф- М.В.Ткачевой

Решение.

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

Ответ: 6.

4. Ф. Сколько различных правильных (с точки зрения русского языка) фраз можно составить, изменяя порядок слов в предложении: 1) «Я пошел гулять»; 2) «Во дворе гуляет кошка»?

Решение.

Во втором предложении предлог «во» должен всегда стоять перед существительным «дворе», к которому он относится. Поэтому, считая пару «во дворе» за одно слово, можно найти количество различных перестановок трех условных слов: Р3 = 3! = 6. Таким образом, и в этом случае можно составить 6 правильных предложений.

Ответ: 1) 6; 2) 6.

5. Сколькими способами можно с помощью букв К, L, М, Н обозначить вершины четырехугольника?

Решение.

Будем считать, что вершины четырехугольника пронумерованы, за каждой закреплен постоянный номер. Тогда задача сводится к подсчету числа разных способов расположения 4 букв на 4 местах (вершинах), т. е. к подсчету числа различных перестановок: Р4 = 4! =24 способа.

Ответ: 24 способа.

6. Ф. Четыре друга купили билеты в кино: на 1-е и 2-е места в первом ряду и на 1-е и 2-е места во втором ряду. Сколькими способами друзья могут занять эти 4 места в кинотеатре?

Решение.

Четыре друга могут занять 4 разных места Р4 = 4! = 24 различными способами.

Ответ: 24 способа.

7. Т. Курьер должен разнести пакеты в 7 различных учреждений. Сколько маршрутов может он выбрать?

Решение.

Под маршрутом следует понимать порядок посещения курьером учреждений. Пронумеруем учреждения номерами от 1 до 7, тогда маршрут будет представляться последовательностью из 7 Цифр, порядок которых может меняться. Количество маршрутов равно числу перестановок из 7 элементов: Р7= 7! = 5 040.

Ответ: 5 040 маршрутов.

8. Т. Сколько существует выражений, тождественно равных произведению abcde, которые получаются из него перестановкой множителей?

Решение.

Дано произведение пяти различных сомножителей abcde, порядок которых может меняться (при перестановке множителей произведение не меняется).

Всего существует Р5 = 5! = 120 различных способов расположения пяти множителей; один из них (abcde) считаем исходным, остальные 119 выражений тождественно равны данному.

Ответ: 119 выражений.

9. Т. Ольга помнит, что телефон подруги оканчивается цифрами 5, 7, 8, но забыла, в каком порядке эти цифры следуют. Укажите наибольшее число вариантов, которые ей придется перебрать, чтобы дозвониться подруге.

Решение.

Три последних цифры телефонного номера могут быть расположены в одном из Р3 =3! =6 возможных порядков, из которых только один верный. Ольга может сразу набрать верный вариант, может набрать его третьим, и т. д. Наибольшее число вариантов ей придется набрать, если правильный вариант окажется последним, т. е. шестым.

Ответ: 6 вариантов.

10. Т. Сколько шестизначных чисел (без повторения цифр) можно составить из цифр: а) 1,2, 5, 6, 7, 8; б) 0, 2, 5, 6, 7, 8? Решение.

а) Дано 6 цифр: 1, 2, 5, 6, 7, 8, из них можно составлять разные шестизначные числа, только переставляя эти цифры местами. Количество различных шестизначных чисел при этом равно Р6 = 6! = 720.

б) Дано 6 цифр: 0, 2, 5, 6, 7, 8, из них нужно составлять различные шестизначные числа. Отличие от предыдущей задачи состоит в том, что ноль не может стоять на первом месте.

Можно напрямую применить правило произведения: на первое место можно выбрать любую из 5 цифр (кроме нуля); на второе место - любую из 5 оставшихся цифр (4 «ненулевые» и теперь считаем ноль); на третье место - любую из 4 оставшихся после первых двух выборов цифр, и т. д. Общее количество вариантов равно: = 600.

Можно применить метод исключения лишних вариантов. 6 цифр можно переставить Р6 = 6! = 720 различными способами. Среди этих способов будут такие, в которых на первом месте стоит ноль, что недопустимо. Подсчитаем количество этих недопустимых вариантов. Если на первом месте стоит ноль (он фиксирован), то на последующих пяти местах могут стоять в произвольном порядке «ненулевые» цифры 2, 5, 6, 7, 8. Количество различных способов, которыми можно разместить 5 цифр на 5 местах, равно Р5 = 5! = 120, т. е. количество перестановок чисел, начинающихся с нуля, равно 120. Искомое количество различных шестизначных чисел в этом случае равно: Р6 - Р5 = 720 - 120 = 600.

Ответ: а) 720; б) 600 чисел.

11. Т. Сколько среди четырехзначных чисел (без повторения цифр), составленных из цифр 3, 5, 7, 9, таких, которые: а) начинаются с цифры 3;

б) кратны 15?

Решение.

а) Из цифр 3, 5, 7, 9 составляем четырехзначные числа, начинающиеся с цифры 3.

Фиксируем цифру 3 на первом месте; тогда на трех оставшихся местах в произвольном порядке могут располагаться цифры 5, 7 9 Общее количество вариантов их расположения равно Р 3 = 3!=6. Столько и будет разных четырехзначных чисел, составленных из данных цифр и начинающихся с цифры 3.

б) Заметим, что сумма данных цифр 3 + 5 + 7 + 9 = 24 делится на 3, следовательно, любое четырехзначное число, составленное из этих цифр, делится на 3. Для того, чтобы некоторые из этих чисел делились на 15, необходимо, чтобы они заканчивались цифрой 5.

Фиксируем цифру 5 на последнем месте; остальные 3 цифры можно разместить на трех местах перед 5 Рз = 3! = 6 различными способами. Столько и будет разных четырехзначных чисел, составленных из данных цифр, которые делятся на 15.

Ответ: а) 6 чисел; б) 6 чисел.

12. Т. Найдите сумму цифр всех четырехзначных чисел, которые можно составить из цифр 1, 3, 5, 7 (без их повторения).

Решение.

Каждое четырехзначное число, составленное из цифр 1, 3, 5, 7 (без повторения), имеет сумму цифр, равную 1+3 + 5 + 7=16.

Из этих цифр можно составить Р4 = 4! = 24 различных числа, отличающихся только порядком цифр. Сумма цифр всех этих чисел будет равна

16 = 384.

Ответ: 384.

13. Т. Семь мальчиков, в число которых входят Олег и Игорь, становятся в ряд. Найдите число возможных комбинаций, если:

а) Олег должен находиться в конце ряда;

б) Олег должен находиться в начале ряда, а Игорь - в конце ряда;

в) Олег и Игорь должны стоять рядом.
Решение.

а) Всего 7 мальчиков на 7 местах, но один элемент фиксирован, не переставляется (Олег находится в конце ряда). Число возможных комбинаций при этом равно числу перестановок 6 мальчиков, стоящих перед Олегом: Р6=6!=720.

пару как единый элемент, переставляемый с другими пятью элементами. Число возможных комбинаций тогда будет Р6 = 6! = 720.

Пусть теперь Олег и Игорь стоят рядом в порядке ИО. Тогда получим еще Р6 = 6! = 720 других комбинаций.

Общее число комбинаций, в которых Олег и Игорь стоят рядом (в любом порядке) равно 720 + 720 = 1 440.

Ответ: а) 720; б) 120; в) 1 440 комбинаций.

14. М. Одиннадцать футболистов строятся перед началом матча. Первым становится капитан, вторым - вратарь, а остальные - случайным образом. Сколько существует способов построения?

Решение.

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

1 =362 880, или Р 9 = 9! = 362 880.

Ответ: 362 880.

15. М. Сколькими способами можно обозначить вершины куба буквами А, В, С, D, E, F, G, K?

Решение.

Для первой вершины можно выбрать любую из 8 букв, для второй - любую из 7 оставшихся, и т. д. Общее число способов по правилу произведения равно =40 320, или Р8 = 8!

Ответ: 40 320.

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

Решение.

Всего 6 уроков, из них два урока математики должны стоять рядом.

«Склеиваем» два элемента (алгебра и геометрия) сначала в порядке АГ, затем в порядке ГА. При каждом варианте «склеивания» получаем Р5 = 5! = 120 вариантов расписания. Общее число способов составить расписание равно120 (AГ) +120 (ГА) = 240.

Ответ: 240 способов.

17. Т. Сколько существует перестановок букв слова «конус», в которых буквы К, О, Н стоят рядом?

Решение.

Дано 5 букв, из которых три буквы должны стоять рядом. Три буквы К, О, Н могут стоять рядом одним из Р3 = 3! = 6 способов. Для каждого способа «склеивания» букв К, О, Н получаем Р3 = 3! = 6 способов перестановки букв, «склейка», У, С. Общее число различных перестановок букв слова «конус», в которых буквы К, О, Н стоят рядом, равно 6 6 = 36 перестановок- анаграмм.

Ответ: 36 анаграмм.

18. Т. Сколькими способами 5 мальчиков и 5 девочек могут занять в театре в одном ряду места с 1 по 10? Сколькими способами они могут это сделать, если мальчики будут сидеть на нечетных местах, а девочки - на четных?

Решение.

Каждый вариант расположения мальчиков может сочетаться с каждым из вариантов расположения девочек, поэтому по правилу произведения общее число способов рассадить детей в этом случае равно 120 20= 14400.

Ответ: 3 628 800 способов; 14 400 способов.

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

Решение.

По условию задачи мальчики и девочки должны чередоваться, т. е. девочки могут сидеть только на четных местах, а мальчики -только на нечетных. Поэтому меняться местами девочки могут только с девочками, а мальчики - только с мальчиками. Четырех девочек можно рассадить на четырех четных местах Р4 = 4! = 24 способами, а пятерых мальчиков на пяти нечетных местах Р5 = 5! = 120 способами.

Каждый способ размещения девочек может сочетаться с каждым способом размещения мальчиков, поэтому по правилу произведения общее число способов равно: Р4 20 = 2 880 способов.

Ответ: 2 880 способов.

20. Ф. Разложить на простые множители числа 30 и 210. Сколькими способами можно записать в виде произведения продых множителей число: 1) 30; 2) 210?

Решение.

Разложим данные числа на простые множители:

30 = 2 ; 210 = 2 .

Число 30 можно записать в виде произведения простых множителей

Р 3 = 3! = 6 разными способами (переставляя множители).

Число 210 можно записать в виде произведения простых
множителей Р 4 = 4! = 24 разными способами.

Ответ: 1) 6 способов; 2) 24 способа.

21. Ф. Сколько различных четных четырехзначных чисел с неповторяющимися цифрами можно записать, используя цифры 1, 2, 3, 5?

Решение.

Чтобы число было четным, оно должно заканчиваться четной цифрой, т. е. 2. Зафиксируем двойку на последнем месте, остальные три цифры должны стоять перед ней в произвольном порядке. Количество различных перестановок из 3 цифр равно P3 = 3! = 6; следовательно, различных четных четырехзначных чисел будет также 6 (к каждой перестановке из трех цифр добавляется цифра 2).

Ответ: 6 чисел.

22. Ф. Сколько различных нечетных пятизначных чисел, в которых нет одинаковых цифр, можно записать с помощью Цифр 1,2, 4, 6, 8?

Решение.

Чтобы составленное число было нечетным, необходимо, чтобы оно оканчивалось нечетной цифрой, т. е. единицей. Остальные 4 Цифры можно переставлять местами, располагая каждую перестановку перед единицей.

Общее число нечетных пятизначных чисел равно числу перестановок: Р4 = 4! =24.

23. Ф. Сколько различных шестизначных чисел с неповторяющимися цифрами можно записать с помощью цифр 1; 2 3, 4, 5, 6, если: 1) число должно начинаться с 56; 2) цифры 5 и 6 в числе должны стоять рядом?

Решение.

Две цифры 5 и 6 фиксируем в начале числа и дописываем к ним различные перестановки из 4 оставшихся цифр; количество различных шестизначных чисел равно: Р4 = 4! = 24.

Общее количество различных шестизначных чисел, в которых цифры 5 и 6 стоят рядом (в любом порядке), равно 120 + 120 = 240 чисел. (Варианты 56 и 65 несовместны, не могут реализоваться одновременно; применяем комбинаторное правило суммы.)

Ответ: 1) 24 числа; 2) 240 чисел.

24. Ф. Сколько различных четных четырехзначных чисел, в записи которых нет одинаковых цифр, можно составить из цифр 1,2,3,4?

Решение.

Четное число должно оканчиваться четной цифрой. Фиксируем на последнем месте цифру 2, тогда 3 предшествующие цифры можно переставить Р3 = 3! = 6 различными способами; получим 6 чисел с двойкой на конце. Фиксируем на последнем месте цифру 4, получим Р3 = 3! = 6 различных перестановок трех предшествующих цифр и 6 чисел, оканчивающихся цифрой 4.

Общее количество четных четырехзначных чисел будет 6 + 6 = 12 различных чисел.

Ответ: 12 чисел.

Замечание. Общее количество вариантов мы находим, пользуясь комбинаторным правилом суммы (6 вариантов чисел, оканчивающихся двойкой, 6 вариантов чисел, оканчивающихся четверкой; способы построения чисел с двойкой и с четверкой на конце являются взаимоисключающими, несовместными, поэтому общее количество вариантов равно сумме числа вариантов с двойкой на конце и числа вариантов с 4 на конце). Запись 6 + 6 = 12 лучше отражает основания наших действий, чем запись Р .

25. Ф. Сколькими способами можно записать в виде произведения простых множителей число 1) 12; 2) 24; 3) 120?

Решение.

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

1) Число 12 разлагается на три простых множителя, два из которых одинаковы: 12 = .

Если бы все множители были различны, то их можно было бы переставить в произведении Р3 = 3! = 6 различными способами. Чтобы перечислить эти способы, условно «различим» две двойки, подчеркнем одну из них: 12 = 2 .

Тогда возможны следующие 6 вариантов разложения на жители:

Но на самом деле подчеркивание цифр не имеет в математике никакого значения, поэтому полученные 6 перестановок в обычной записи имеют вид:

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

Обозначим Р х искомое число перестановок из трех элементов среди которых два одинаковых; тогда полученный нами результат можно записать так: Рз = Р х Но 2 - это количество разных перестановок из двух элементов, т. е. 2 = = 2! = Р 2 , поэтому Р3, = Р х Р 2 , отсюда Р х = . (это формула для числа перестановок с повторениями).

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

Чтобы составить произведение из трех множителей, сначала выберем место для множителя 3; это можно сделать одним из трех способов. После этого оба оставшихся места заполняем двойками; это можно сделать 1 способом. По правилу произведения общее число способов равно: 3-1 =3. , Р х =20.

Второй способ. Составляя произведение из пяти множителей, сначала выберем место для пятерки (5 способов), затем для тройки (4 способа), а оставшиеся 3 места заполним двойками (1 способ); по правилу произведения 5 4 1 = 20.

Ответ: 1) 3; 2) 4; 3) 20.

26. Ф. Сколькими способами можно закрасить 6 клеток таким образом, чтобы 3 клетки были красными, а 3 оставшиеся были закрашены (каждая своим цветом) белым, черным или зеленым?

Решение.

Перестановки из 6 элементов, среди которых три - одинаковые:

Иначе: для закраски белым цветом можно выбрать одну из 6 клеток, черным - из 5, зеленым - из 4; три оставшиеся клетки закрашиваем красным цветом. Общее число способов: 6 5 4 1 = 120.

Ответ: 120 способов.

27.Т. Пешеход должен пройти один квартал на север и три квартала на запад. Выпишите все возможные маршруты пешехода. = 4.

Ответ: 4 маршрута.

28. М. а) На дверях четырех одинаковых кабинетов надо повесить таблички с фамилиями четырех заместителей директора. Сколькими способами это можно сделать?

б) В 9 «А» классе в среду 5 уроков: алгебра, геометрия, физкультура, русский язык, английский язык. Сколько можно составить вариантов расписания на этот день?

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

г) Адъютант должен развезти пять копий приказа генерала пяти полкам. Сколькими способами он может выбрать маршрут доставки копий приказа?

Решение.

а) Для первой таблички можно выбрать любой из 4 кабинетов,
Для второй - любой из трех оставшихся, для третьей - любой из двух оставшихся, для четвертой - один оставшийся; по правилу
произведения общее число способов равно: 4 3 2 1 = 24, или Р4 = 4! = 24. = 120, или Р5 = 5! = 120.

Ответ: а) 24; б) 120; в) 24; г) 120.

Литература

Афанасьев В.В. Теория вероятностей в примерах и задачах, - Ярославль: ЯГПУ, 1994.

Баврин И. И. Высшая математика: Учебник для студентов химико-математических специальностей педагогических вузов-2-е издание, переработанное. - М.:Просвещение, 1993.

Бунимович Е. А., Булычёв В.А. Вероятность и статистика. 5-9 классы: Пособие для общеобразовательных учебных заведений, - М.:Дрофа, 2005.

Виленкин Н. Я. и другие. Алгебра и математический анализ для 10 класса: Учебное пособие для учащихся школ и классов с углублённым изучением математики. - М.:Просвещение,1992.

Виленкин Н. Я. и другие. Алгебра и математический анализ для 11 класса: Учебное пособие для учащихся школ и классов с углублённым изучением математики - М.:Просвещение, 1990.

Глейзер Г.И. История математики в школе: 9-10 класс. Пособие для учителей. - М.: Просвещение 1983.

Дорофеев Г.В., Суворова С.Б., Бунимович Е.А. Математика 9:Алгебра. Функции. Анализ данных - М.: Дрофа, 2000.

Колягин и другие. Алгебра и начала анализа 11 класс. Математика в школе - 2002 - №4 - с.43,44,46.

Люпшкас В.С. Факультативные курсы по математике: теория вероятностей: Учебное пособие для 9-11 классов.- М.,1991.

Макарычев Ю.Н., Миндюк Н.Г. Элементы статистики и теории вероятностей: Учебное пособие для учащихся 7-9 классов.- М.: Просвещение, 2005.

Мордкович А.Г., Семенов П.В. Алгебра и начала анализа 10 класс: Учебник для общеобразовательных учреждений (профильный уровень) – М.: Мнемозина, 2005.

Ткачева М.В., Федорова Н.Е. Элементы статистики и вероятность: Учебное пособие для учащихся 7-9 классов.- М.: Просвещение, 2005.

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

Правило умножения (основная формула комбинаторики)

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

Пример 1

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

Решение

Первая монета имеет альтернативы – либо орел, либо решка. Для второй монеты также есть альтернативы и т.д., т.е. .

Искомое количество способов:

Правило сложения

Если любые две группы и не имеют общих элементов, то выбор одного элемента или из , или из , …или из можно осуществить способами.

Пример 2

На полке 30 книг, из них 20 математических, 6 технических и 4 экономических. Сколько существует способов выбора одной математической или одной экономической книги.

Решение

Математическая книга может быть выбрана способами, экономическая - способами.

По правилу суммы существует способа выбора математической или экономической книги.

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

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

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

Число различных способов, которыми можно произвести последовательный выбор без возвращения элементов из генеральной совокупности объема , равно:

Пример 3

Расписание дня состоит из 5 различных уроков. Определите число вариантов расписания при выборе из 11 дисциплин.

Решение

Каждый вариант расписания представляет набор 5 дисциплин из 11, отличающихся от других вариантов как составом, так и порядком следования. поэтому:

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

Пример 4

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

Решение

Каждый вариант рассадки отличается только порядком участников, то есть является перестановкой из 4 элементов:

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

Общее число различных способов, которыми можно произвести выбор с возвращением элементов из генеральной совокупности объема , равно

Пример 5

Лифт останавливается на 7 этажах. Сколькими способами могут выйти на этих этажах 6 пассажиров, находящихся в кабине лифта?

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

Решение

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

Сочетания

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

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

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

Пример 6

В ящике 9 яблок. Сколькими способами можно выбрать 3 яблока из ящика?

Решение

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

Количество способов, которыми можно выбрать 3 яблока из 9:

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

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

Пример 7

На почте продают открытки 3 видов. Сколькими способами можно купить 6 открыток?

Это задача на отыскание числа сочетаний с повторениями из 3 по 6:

Разбиение множества на группы

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

Число разбиений на групп, когда в первую попадают элементов, во вторую - элементов, в k-ю группу - элементов, равно:

Пример 8

Группу из 16 человек требуется разбить на три подгруппы, в первой из которых должно быть 5 человек, во второй – 7 человек, в третьей – 4 человека. Сколькими способами это можно сделать?

Решение

Здесь

Число разбиений на 3 подгруппы:

Излагается понятие геометрического закона распределения дискретной случайной величины и рассматривается пример решения задачи. Приведены формулы математического ожидания и дисперсии случайной величины, распределенной по геометрическому закону.

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

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

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

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

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

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

Лемма. Пусть в множестве элементов, а в множестве-элементов. Тогда число всех различных пар, гдебудет равно.

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

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

Пусть у нас есть множество из трех элементов . Какими способами мы можем выбрать из этих элементов два?.

Определение. Размещениями множества из различных элементов поэлементовназываются комбинации, которые составлены из данныхэлементов поэлементов и отличаются либо самими элементами, либо порядком элементов.

Число всех размещений множества из элементов поэлементов обозначается через(от начальной буквы французского слова “arrangement”, что означает размещение), гдеи.

Теорема. Число размещений множества из элементов поэлементов равно

Доказательство. Пусть у нас есть элементы . Пусть- возможные размещения. Будем строить эти размещения последовательно. Сначала определим- первый элемент размещения. Из данной совокупностиэлементов его можно выбратьразличными способами. После выбора первого элементадля второго элементаостаетсяспособов выбора и т.д. Так как каждый такой выбор дает новое размещение, то все эти выборы можно свободно комбинировать между собой. Поэтому имеем:

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

Решение. Искомое число трехполосных флагов:

Определение. Перестановкой множества из элементов называется расположение элементов в определенном порядке.

Так, все различные перестановки множества из трех элементов - это

Число всех перестановок из элементов обозначается(от начальной буквы французского слова “permutation”, что значит “перестановка”, “перемещение”). Следовательно, число всех различных перестановок вычисляется по формуле

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

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

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

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

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

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

Комбинаторные конфигурации

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

• размещение;
• перестановка;
• сочетание;
• композиция числа;
• разбиение числа.

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

Разделы

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

• перечислительная;
• структурная;
• экстремальная;
• теория Рамсея;
• вероятностная;
• топологическая;
• инфинитарная.

В первом случае речь идет об исчисляющей комбинаторике, задачи рассматривают перечисление или подсчет разных конфигураций, которые образованы элементами множеств. На данные множества, как правило, накладываются какие-либо ограничения (различимость, неразличимость, возможность повтора и так далее). А количество этих конфигураций подсчитывается при помощи правила сложения или умножения, о которых мы поговорим немного позже. К структурной комбинаторике относятся теории графов и матроидов. Пример задачи экстремальной комбинаторики - какова наибольшая размерность графа, который удовлетворяет следующим свойствам… В четвертом пункте мы упомянули теорию Рамсея, которая изучает в случайных конфигурациях наличие регулярных структур. Вероятностная комбинаторика способна нам ответить на вопрос - какова вероятность того, что у заданного множества присутствует определенное свойство. Как нетрудно догадаться, топологическая комбинаторика применяет методы в топологии. И, наконец, седьмой пункт - инфинитарная комбинаторика изучает применение методов комбинаторики к бесконечным множествам.

Правило сложения

Среди формул комбинаторики можно найти и довольно простые, с которыми мы достаточно давно знакомы. Примером является правило суммы. Предположим, что нам даны два действия (С и Е), если они взаимоисключаемы, действие С выполнимо несколькими способами (например а), а действие Е выполнимо b-способами, то выполнить любое из них (С или Е) можно а+b способами.

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

Правило умножения

К основным формулам комбинаторики относится и правило умножения. Начнем с теории. Допустим, нам необходимо выполнить несколько действий (а): первое действие выполняется с1 способами, второе - с2 способами, третье - с3 способами и так далее до последнего а-действия, выполняемого са способами. Тогда все эти действия (которых всего у нас а) могут быть выполнены N способами. Как высчитать неизвестную N? В этом нам поможет формула: N = с1 * с2 * с3 *…* са.

Опять же, в теории ничего не понятно, переходим к рассмотрению простого примера на применение правила умножения. Возьмем все тот же класс из двадцати пяти человек, в котором учится пятнадцать девочек и десять мальчиков. Только на этот раз нам необходимо выбрать двух дежурных. Ими могут быть как только мальчики или девочки, так и мальчик с девочкой. Переходим к элементарному решению задачи. Выбираем первого дежурного, как мы решили в прошлом пункте, у нас получается двадцать пять возможных вариантов. Вторым дежурным может быть любой из оставшихся человек. У нас было двадцать пять учеников, одного мы выбрали, значит вторым дежурным может быть любой из оставшихся двадцати четырех человек. Наконец, применяем правило умножения и получаем, что двоих дежурных можно избрать шестью сотнями способов. Мы данное число получили умножением двадцати пяти и двадцати четырех.

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

Сейчас мы рассмотрим еще одну формулу комбинаторики. В данном разделе статьи мы поговорим о перестановках. Рассмотреть проблему предлагаем сразу же на примере. Возьмем бильярдные шары у нас их n-ое количество. Нам нужно подсчитать: сколько есть вариантов расставить их в ряд, то есть составить упорядоченный набор.

Начнем, если у нас нет шаров, то и вариантов расстановки у нас так же ноль. А если у нас шар один, то и расстановка тоже одна (математически это можно записать следующим образом: Р1 = 1). Два шара можно расставить двумя разными способами: 1,2 и 2,1. Следовательно, Р2 = 2. Три шара можно расставить уже шестью способами (Р3=6): 1,2,3; 1,3,2; 2,1,3; 2,3,1; 3,2,1; 3,1,2. А если таких шаров не три, а десять или пятнадцать? Перечислять все возможные варианты очень долго, тогда нам на помощь приходит комбинаторика. Формула перестановки поможет нам найти ответ на интересующий нас вопрос. Pn = n *P (n-1). Если попытаться упростить формулу, то получаем: Pn = n* (n - 1) *…* 2 * 1. А это и есть произведение первых натуральных чисел. Такое число называется факториалом, а обозначается как n!

Рассмотрим задачу. Вожатый каждое утро выстраивает свой отряд в шеренгу (двадцать человек). В отряде есть три лучших друга - Костя, Саша и Леша. Какова вероятность того, что они будут стоять рядом? Чтобы найти ответ на вопрос, нужно вероятность «хорошего» исхода поделить на общее количество исходов. Общее число перестановок составляет 20! = 2,5 квинтиллиона. Как посчитать количество «хороших» исходов? Предположим, что Костя, Саши и Леша - это один сверхчеловек. Тогда мы имеем всего восемнадцать субъектов. Число перестановок в данном случае равняется 18 = 6,5 квадриллионов. При всем этом, Костя, Саша и Леша могут произвольно перемещаться между собой в своей неделимой тройке, а это еще 3! = 6 вариантов. Значит всего «хороших» расстановок у нас 18! * 3! Нам остается только найти искомую вероятность: (18! * 3!) / 20! Что равняется примерно 0,016. Если перевести в проценты, то это получается всего 1,6%.

Размещение

Сейчас мы рассмотрим еще одну очень важную и необходимую формулу комбинаторики. Размещение - это наш следующий вопрос, который предлагаем вам рассмотреть в данном разделе статьи. Мы идем на усложнение. Предположим, что мы хотим рассмотреть возможные перестановки, только не из всего множества (n), а из меньшего (m). То есть мы рассматриваем перестановки из n предметов по m.

Основные формулы комбинаторики стоит не просто заучивать, а понимать их. Даже несмотря на то, что они усложняются, так как у нас не один параметр, а два. Предположим, что m = 1, то и А = 1, m = 2, то А = n * (n - 1). Если далее упрощать формулу и перейти на запись при помощи факториалов, то получится вполне лаконичная формула: А = n! / (n - m)!

Сочетание

Мы рассмотрели практически все основные формулы комбинаторики с примерами. Теперь перейдем к заключительному этапу рассмотрения базового курса комбинаторики - знакомство с сочетанием. Сейчас мы будем выбирать m предметов из имеющихся у нас n, при этом всем мы будем выбирать всеми возможными способами. Чем же тогда это отличается от размещения? Мы не будем учитывать порядок. Этот неупорядоченный набор и будет являться сочетанием.

Сразу введем обозначение: С. Берем размещения m шариков из n. Мы перестаем обращать внимание на порядок и получаем повторяющиеся сочетания. Чтобы получить число сочетаний нам надо поделить число размещений на m! (m факториал). То есть С = А / m! Таким образом, способов выбрать из n шаров немножко, равняется примерно столько, сколько выбрать почти все. Этому есть логическое выражение: выбрать немножко все равно, что выкинуть почти все. Еще в данном пункте важно упомянуть и то, что максимальное число сочетаний можно достигнуть при попытке выбрать половину предметов.

Как выбрать формулу для решения задачи?

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

1. Задайте себе вопрос: порядок размещения элементов учитывается в тексте задачи?
2. Если ответ нет, то воспользуйтесь формулой сочетания (С = n! / (m! * (n - m)!)).
3. Если ответ нет, то необходимо ответить на еще один вопрос: все ли элементы входят в комбинацию?
4. Если ответ да, то воспользуйтесь формулой перестановки (Р = n!).
5. Если ответ нет, то воспользуйтесь формулой размещения (А = n! / (n - m)!).

Пример

Мы рассмотрели элементы комбинаторики, формулы и некоторые другие вопросы. Теперь перейдем к рассмотрению реальной задачи. Представьте, что перед вами лежат киви, апельсин и банан.

Вопрос первый: сколькими способами их можно переставить? Для этого воспользуемся формулой перестановок: Р = 3! = 6 способов.

Вопрос второй: сколькими способами можно выбрать один фрукт? Это очевидно, у нас всего три варианта - выбрать киви, апельсин или банан, но применим формулу сочетаний: С = 3! / (2! * 1!) = 3.

Вопрос третий: сколькими способами можно выбрать два фрукта? Какие есть у нас вообще варианты? Киви и апельсин; киви и банан; апельсин и банан. То есть три варианта, но это легко проверить при помощи формулы сочетания: С = 3! / (1! * 2!) = 3

Вопрос четвертый: сколькими способами можно выбрать три фрукта? Как видно, выбрать три фрукта можно одним-единственным способом: взять киви, апельсин и банан. С = 3! / (0! * 3!) = 1.

Вопрос пятый: сколькими способами можно выбрать хотя бы один фрукт? Это условие подразумевает, что мы можем взять один, два или все три фрукта. Следовательно, мы складываем С1 + С2 + С3 =3 + 3 + 1 = 7. То есть у нас есть семь способов взять со стола хотя бы один фрукт.