Элементы комбинаторики

Цель работы: Ознакомиться с размещения и сочетания, с перестановкой и подстановкой, разбиением.

Порядок выполнения работы:

Практическая работа рассчитана на 1 час аудиторных занятий, включающих в себя следующее:

1. Изучить:

- Размещения и сочетания.

- Перестановки и подстановки. Разбиения

- Формула включений и исключений.

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

3. Оформить отчет о проделанной работе в соответствии с требованиями.

4. Проработать контрольные задания СРС.

Требования к отчету:

Отчет по практической работе распечатывается в виде твердой копии и состоит из следующих пунктов:

Вариант индивидуального задания;

Результаты полученных решений заданий;

Ответы на контрольные задания СРС.

Методические указания

Комбинаторика – это область дискретной математики, которая занимается исследованием дискретных конечных математических структур. Например, набор формул для решения комбинаторных задач.

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

Обозначается факториал n!:

n! = 1*2*3*4*...×*(n-1)*n.

Функцию n! можно записать в виде n! = (n - 1)! n.

Пример: Записать со знаком факториала: 1×2×3×4×4×5×6.

Это произведение чисел натурального ряда, но число 4 в нем встречается два раза. Если одну четверку удалить, то останутся числа натурального ряда без повторов. Их произведение можно представить в виде 6!, следовательно:

1×2×3×4×4×5×6 = 4×6!

В общем случае: если один элемент множества А₁ можно выбрать çА₁ç способами, элемент множества А₂-çА₂ç способами и так далее до множества А_n, один элемент которого можно выбрать çА_nç способами, то выбрать все n элементов в заданном порядке можно N способами:

N=çА₁ç×çА₂ç×…×çА_nç

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

Формулу для числа перестановок без повторений можно вывести на основе правила произведения. Первый из n элементов можно выбрать n способами. Останется n - 1 элементов. Следовательно, второй элемент можно выбрать n - 1 способами, третий – n - 2 способами и так далее до последнего элемента, который выбирается единственным способом. Таким образом:

Р_n = n (n - 1)(n - 2)- ... • 3•2•1 = n!

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

Число перестановок из n элементов равно n!, если все n элементов различны. Однако в данном случае n₁! перестановок неразличимы. Неразличимы и n₂! перестановок и т. д. Следовательно:

Это окончательная формула для определения числа размещений из n элементов по m без повторений.

.

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

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

,

где символ используется для обозначения числа размещений из n элементов по m с повторениями.

Сочетания же отличаются одно от другого только элементами. Если число разделить на m!, то получим формулу для нахождения числа сочетаний из n элементов по m:

.

На основании этой формулы можно получить следующие простые тождества

Числа Фибоначчи

Последовательность чисел 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …каждый член которой является суммой двух предыдущих является числами Фибоначчи.

В общем виде имеем: F₀ = 0; F₁ = 1; F₂ = 1; F_n+2 = F_n+1 + F_n;

Упражнения для выполнения:

1. Записать со знаком факториала: 1×2×3×4×4×5×6.

2. Записать с использованием знака факториала: 1×2×3×4×5×7×8×9×10.

3. Упростить:

4. В урне пять шаров с номерами 1, 2, 3, 4, 5. Вынимают один шар и записывают его номер. Шар возвращают в урну и наугад снова выбирают один шар и номер его записывают справа от первой цифры. Получится двухразрядное число. Сколько таких чисел возможно?

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

6. Пусть даны множества:

Р1 = {1,2, 4,7, 9}; Р2 ={1,4,5,6,8}.

Сколько элементов во множестве P₁ U Р₂?

7. Из 100 студентов английский язык знают 28 человек, немецкий - 30, французский - 42, английский и немецкий - 8, английский и французский - 10, немецкий и французский - 5, все три языка знают 3 человека. Сколько студентов не знают ни одного иностранного языка?

8. Имеется 12 ролей. Четыре артиста могут играть любую роль, и им предлагается выбор. Сколькими способами можно распределить роли между ними?

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

10. Дано множество букв: А = {а, б, в, г, д, е}. Сколько двух- и трехбуквенных слов можно составить из этих букв?

Контрольные задания для СРС

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

Приведите примеры комбинаторных задач.

Дата добавления: 2015-07-26; просмотров: 384; Нарушение авторских прав

Мы поможем в написании ваших работ!