Дипломная работа: Элементы комбинаторики

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

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

Число размещений без повторений находится по формуле:

– Итак, в примере 1 нам нужно было составить двузначные числа из известных 3 цифр. По формуле получаем способов

Задача. Сколько трехзначных чисел можно записать, используя цифры 1,3,6,7,9, если каждая их них может быть использована в записи только один раз? Постройте дерево возможных вариантов.

Решение: по формуле получаем: способов

– Как вы думаете, как удобнее решать эти задачи: деревом возможных вариантов или по формуле?

5.Закрепление

Задача 1. Для запирания автоматической камеры применяется секретный замок, который открывается лишь тогда, когда набрано «тайное слово». Это слово набирают с помощью пяти дисков, на каждом из которых изображено 12 букв. Сколько неудачных попыток может быть сделано человеком, не знающим секретного слова и подбирающего его наудачу?

Решение. Из условия задачи видно, что порядок выбираемых букв очень важен. Поэтому мы имеем дело с кортежем длиной 5 (пять дисков). Каждый элемент кортежа может быть выбран 12-ю способами (букв на каждом диске 12). Поэтому число комбинаций 12⁵ =248 831.

Задача 2. Сколько различных четырехзначных чисел можно составить из цифр 2, 6, 7, 8 и 9, если каждая цифра может входить в комбинацию несколько раз?

Решение. Порядок цифр важен, т.к. 2678 или 6278 – это разные числа. Поэтому имеем дело с кортежем длины 4 (четырехзначное число), каждый элемент которого можно выбрать пятью способами (цифр дано пять). Следовательно, число различных комбинаций равно 4⁵ =1024.

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

Решение. Получаем кортеж длины 4 (столько вопросов в бюллетене), каждый элемент может быть выбран двумя способами («да» или «нет»). Поэтому число различных возможностей равно 2⁴ =16

Задача 4. Неудовлетворенные решением Париса Гера, Афина и Афродита обратились к трем мудрецам с просьбой назвать прекраснейшую из них. Каждый из мудрецов высказал свое мнение. Сколько могло возникнуть вариантов ответа на поставленный вопрос у этой тройки? (6³ =216)

Задача 5. У Лены есть восемь красок. Она хочет написать ими слова «Новый Год». Сколькими способами она может это сделать, если собирается каждую букву раскрашивать одним цветом? (8⁸ =16777216)

Задача 6 . Сколькими различными способами можно распределить между шестью лицами две различные путевки в санаторий?

Решение.

Задача 7. Из 20 учащихся надо выбрать старосту, его заместителя и редактора газеты. Сколькими способами это можно сделать?

Решение: способами

Задача 8. В классе изучаются 7 предметов. В среду 4 урока, причем все разные. Сколькими способами можно составить расписание на среду?

Решение: способов

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

Решение:

Задача 10 . Из десяти различных книг выбирают четыре для посылки. Сколькими способами это можно сделать?

Решение.

Задача 11 . Для запирания сейфа на диск нанесены 12 букв, а секретное слово состоит из 5 букв. Сколько неудачных попыток может быть сделано человеком, не знающим секретного слова? (12⁵ =248 832 удачных попыток, следовательно, неудачных 248 831)

6. Итог урока

Что нового узнали на уроке?