Пособие по терверу
Комбинаторика область математики, в которой изучаются вопросы о том, сколько различных комбинаций, подчиненных тем или иным условиям, можно составить из заданных объектов.
Два основных принципа комбинаторики правило суммы и правило произведения.
Правило суммы. Если некоторый объект A можно выбрать m способами, а другой объект B можно выбрать n способами, то выбор \либо A, либо B” можно осуществить m + n способами.
Пример. В первой вазе лежит 6 яблок, во второй 5 груш, в третьей 4 персика. Сколькими способами можно выбрать один из фруктов?
B По правилу суммы, число способов: 6 + 5 + 4 = 15: C
Правило произведения. Если объект A можно выбрать m способами и если после каждого такого выбора объект B можно выбрать n способами, то выбор пары (A; B) в указанном порядке можно осуществить m n способами.
Пример. У одного студента 5 книг, у другого 9. Все книги различные. Сколькими способами студенты могут произвести обмен одной книги на книгу?
B Любую из 5 книг первого студента можно обменять на любую из 9 книг второго студента. Общее число способов обмена: 5 9 = 45. C
Пример. Имеется набор чисел: f1; 2; 3; 4g. Сколькими способами можно расположить числа из этого набора так, что крайние числа имеют одинаковую четность?
B Если крайние числа четные, то имеется два варианта для их расположения (первое число 2, или первое число 4), при этом оставшиеся
нечетные числа можно также расположить двумя способами (первым идет 1 или первым идет 3). Всего здесь вариантов, по правилу произведения, 2 2 = 4. Аналогично имеется 4 варианта в том случае, если крайними стоят нечетные числа. Общее число вариантов находится по правилу суммы: 4 + 4 = 8. C
1.2 Основные формулы
При подсчете числа возможных исходов опыта рассматривают упорядоченные и неупорядоченные комбинации элементов. Набор элементов некоторого множества называется упорядоченным, если в нем задан порядок следования элементов.
Пример. Множество состоит из двух элементов, чисел 1 и 2. Тогда имеется один неупорядоченный набор этих элементов: (1; 2) и два упорядоченных набора: (1; 2) и (2; 1).
На упорядоченных множествах рассматривают перестановки и размещения.
Перестановками называются комбинации, состоящие из одних и тех же n различных элементов, отличающихся только порядком их расположения.
Пример. Перестановками трех чисел 1; 2 и 3 являются шесть комбинаций: (1; 2; 3); (1; 3; 2); (2; 1; 3); (2; 3; 1); (3; 1; 2); (3; 2; 1).
Число перестановок из n элементов вычисляется по формуле
P n = n! = 1 2 3 (n 1) n:
Пример. В аудитории 10 мест. Сколькими способами можно разместить в ней 10 студентов?
B Искомое количество дает число перестановок из 10 элементов:
P 10 = 10! = 3 628 800. C
Размещением из n элементов по m называется любой упорядоченный набор из m различных элементов, выбранный из общей совокупности в n элементов.
Пример. Размещением из 3 элементов по 2, взятых из набора f1; 2; 3g, являются шесть комбинаций: (1; 2); (2; 1); (1; 3); (3; 1); (2; 3); (3; 2).
Число размещений из n элементов по m вычисляется по формуле
A m n = n (n 1) (n 2) (n m + 1):
Пример. Студенту необходимо сдать 4 экзамена в течение 7 дней. Сколькими способами можно составить расписание экзаменов, если учитывать, что в один день он может сдавать только один экзамен?
B Четыре экзамена нужно разместить среди имеющихся семи дней, причем важно, в каком порядке идут экзамены. Количество способов дает число размещений из 7 элементов по 4: A 4 7 = 7 6 5 4 = 840. C
На неупорядоченных множествах рассматривают сочетания. Сочетанием из n элементов по m называется любой неупорядоченный набор из m различных элементов, выбранных из общей совокупности в n элементов.
Пример. Сочетанием из 3 элементов по 2, взятых из набора f1; 2; 3g, являются три комбинации: (1; 2); (1; 3); (2; 3).
Число сочетаний из n элементов по m вычисляется по формуле
Пример. В шахматном турнире участвуют 10 человек, причем турнир проходит по круговой системе, т.е. каждый встречается с каждым. Сколько партий надо запланировать организаторам турнира?
B Нужно всевозможными способами выбирать пары участников из имеющихся 10 человек, причем, в выбранной паре не важен порядок участников, важен только состав. Искомое количество дает число сочетаний из 10 по 2:
комбинаторика — Сколько существует семизначных чисел, в которых ровно две четные цифры.
Сколько существует семизначных чисел, в которых ровно две четные цифры, и перед каждой четной цифрой обязательно стоит нечётная?
задан 3 Ноя ’19 18:20
1 ответ
Выделим «слоги» НЧ как отдельные «буквы», и кроме них ещё будут три цифры типа Н. Итого 5 мест, на двух из них мы ставим НЧ; это можно сделать 10 способами. Заметим, что с нуля такие числа не начинаются. Выбрать каждую из цифр заданной чётности можно 5 способами. Итого получится 10*5^7 чисел.
Школа олимпийского резерва. Математика
Решение. Выберем любой из 15 комплектов предыдущей задачи. его можно дополнить ложкой четырьмя различными способами. Поэтому общее число возможных комплктов равно 60 (60 = 15 • 4 = 5 • 3 • 4).
Задача 3. В Стране Чудес есть три города: А, Б и В. Из города А в город Б ведёт 6 дорог, а из города Б в город В — 4 дороги. Сколькими способами можно проехать от А до В?
Cколько существует разных пятизначных чисел, все цифры которых чётные?
Нам предстоит расставить пять чётных цифр по пяти позициям в пятизначном числе.
Цифры: 0, 2, 4, 6, 8.
Модель числа: __ __ __ __ __.
Сколько вариантов цифр можно поставить на первую позицию _?_ __ __ __ __?
Только четыре, так как 0 не может стоять в начале (число станет четырехзначным).
На 2-ой, 3-ей, 4-ой и 5-ой позициях — по пяти вариантов, подходят любые цифры из заданных.
По комбинаторному правилу, число всех вариантов ищется произведением (4 и 5 и 5 и 5 и 5 вариантов — союз «и» = умножение).