Слайд 2
Размещения
Определение 1
Размещением из n элементов по
k называется всякая перестановка из k элементов, выбранных каким-либо
способом из данных n.
Пример
Дано множество . Составим все 2-размещения этого множества.
Слайд 3
Число размещений
Теорема 1 Число всех размещений из n
элементов по k вычисляется по формуле
Доказательство. Каждое размещение можно
получить с помощью k действий:
1) выбор первого элемента n способами;
2) выбор второго элемента (n-1) способами;
и т. д.
k) выбор k –го элемента (n-(k-1))=(n-k+1) способами.
По правилу умножения число всех размещений будет
n(n-1)(n-2)…(n-k+1). Теорема доказана.
Слайд 4
Число размещений
Замечание. Формулу для числа размещений можно записать
в виде
Действительно
Слайд 5
Пример
Абонент забыл последние 3 цифры номера телефона. Какое
максимальное число номеров ему нужно перебрать, если он вспомнил,
что эти последние цифры разные?
Решение.
Задача сводится к поиску различных перестановок 3 элементов из 10 ( так как всего цифр 10). Применим формулу для числа перестановок.
Слайд 6
Размещения с повторениями
Определение 2
Размещением с повторением из n
элементов по k называется всякая перестановка из k элементов,
выбранных каким-либо способом из данных n элементов возможно с повторениями.
Пример
Дано множество
Составим 2- размещения с повторениями:
Слайд 7
Число размещений с повторениями
Теорема 2. Число k- размещений
с повторениями из
n элементов вычисляется по формуле
Доказательство.
Каждый элемент размещения
можно выбрать n способами. По правилу
умножения число всех размещений с повторениями
равно
Слайд 8
Пример
Сколько существует номеров машин?
Решение. Считаем, что в трех
буквах номера машины не используются буквы «й», «ы», «ь»,
«ъ», тогда число перестановок букв равно .
Число перестановок цифр равно .
По правилу умножения получим число номеров машин
Слайд 9
Перестановки
Определение 1
Перестановкой из n элементов называется всякий способ
нумерации этих элементов
Пример 1
Дано множество
. Составить все перестановки этого множества.
Решение.
Слайд 10
Число перестановок
Теорема 1. Число всех различных перестановок из
n элементов равно n!
Замечание.
Например,
Считают, что 0!=1
читается «n
факториал» и вычисляется по формуле
Слайд 11
Число перестановок
Доказательство теоремы 1.
Любую перестановку из n элементов
можно получить с помощью n действий:
выбор первого элемента n
различными способами,
выбор второго элемента из оставшихся (n-1) элементов, т.е. (n-1) способом,
выбор третьего элемента (n-2) способами,
……
n) выбор n-го элемента 1 способом.
По правилу умножения число всех способов выполнения действий, т.е. число перестановок, равно
Теорема доказана.
Слайд 12
Перестановки
Число всех перестановок обозначается
Итак,
Пример
В команде 6
человек. Сколькими способами они могут построиться для приветствия?
Решение
Число способов
построения равно числу перестановок 6 элементов, т.е.
Слайд 13
Перестановки с повторениями
Теорема 2
Число перестановок n – элементов,
в котором есть одинаковые элементы, а именно
элементов i –того типа ( ) вычисляется по формуле
где
Доказательство. Так как перестановки между одинаковыми элементами не изменяют вид перестановки в целом, количество перестановок всех элементов множества нужно разделить на число перестановок одинаковых элементов.
Слайд 14
Пример
Задача: Сколько слов можно составить, переставив буквы в
слове «экзамен», а в слове «математика»?
Решение: В слове «экзамен»
все буквы различны, поэтому используем формулу для числа перестановок без повторений
В слове «математика» 3 буквы «а», 2 буквы «м», 2 буквы «т», поэтому число перестановок всех букв разделим на число перестановок повторяющихся букв:
Слайд 15
Задачи
1)Сколькими способами можно составить список из 8 учеников,
если у них различные инициалы?
Решение
Задача сводится к подсчету числа
перестановок ФИО.
Слайд 16
Задачи
2)Сколькими способами можно составить список 8 учеников, так,
чтобы два указанных ученика располагались рядом?
Решение
Можно считать двоих указанных
учеников за один объект и считать число перестановок уже 7 объектов, т.е.
Так как этих двоих можно переставлять местами друг с другом, необходимо умножить результат на 2!
Слайд 17
Задачи
3) Сколькими способами можно разделить 11 спортсменов на
3 группы по 4, 5 и 2 человека соответственно?
Решение.
Сделаем карточки: четыре карточки с номером 1, пять карточек с номером 2 и две карточки с номером 3. Будем раздавать эти карточки с номерами групп спортсменам, и каждый способ раздачи будет соответствовать разбиению спортсменов на группы. Таким образом нам необходимо посчитать число перестановок 11 карточек, среди которых четыре карточки с одинаковым номером 1, пять карточек с номером 2 и две карточки с номером 3.
Слайд 18
Задачи
4) Сколькими способами можно вызвать по очереди к
доске 4 учеников из 7?
Решение. Задача сводится к подсчету
числа размещений из 7 элементов по 4
Слайд 19
Задачи
5)Сколько существует четырехзначных чисел, у которых все цифры
различны?
Решение. В разряде единиц тысяч не может быть нуля,
т.е возможны 9 вариантов цифры.
В остальных трех разрядах не может быть цифры, стоящей в разряде единиц тысяч (так как все цифры должны быть различны), поэтому число вариантов вычислим по формуле размещений без повторений из 9 по 3
По правилу умножения получим
Слайд 20
Задачи
6)Сколько существует двоичных чисел, длина которых не превосходит
10?
Решение. Задача сводится к подсчету числа размещений с повторениями
из двух элементов по 10
Слайд 21
Задачи
7)В лифт 9 этажного дома зашли 7 человек.
Сколькими способами они могут распределиться по этажам дома?
Решение. Очевидно,
что на первом этаже никому не надо выходить. Каждый из 7 человек может выбрать любой из 8 этажей, поэтому по правилу умножения получим
Можно так же применить формулу для числа размещений с повторениями из 8 (этажей) по 7(на каждого человека по одному этажу)
Слайд 22
Задачи
8)Сколько чисел, меньше 10000 можно написать с помощью
цифр 2,7,0?
Решение. Так как среди цифр есть 0, то,
например запись 0227 соответствует числу 227, запись 0072 соответствует числу 72, а запись 007 соответствует числу 7. Таким образом, задачу можно решить, используя формулу числа размещений с повторениями