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

Размещено на http://www.allbest.ru/

Министерство образования и науки Российской Федерации

ФГОУ СПО «Томский государственный промышленно-гуманитарный колледж»

Методические рекомендации по учебной дисциплине

«Теория вероятностей и математическая статистика»

Для выполнения лабораторно-практической работы

Тема: «Элементы комбинаторики»

Томск-2013г.



Практическая работа 1

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

Цель занятия. Решение задач комбинаторики средствами MS Excel. Использование встроенных функций MS Excel для вычисления перестановок, сочетаний и размещений.

Основные понятия комбинаторики

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

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

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

В комбинаторике принято следующее обозначение: если в множестве имеется n элементов, то Пn - число перестановок элементов этого множества.

Рассмотрим конкретные множества:

n=0; П0=1 - по определению;

n=1; П1=1;

n=2: например, есть множество {1, 2}, возможные числа - 1 2 и 2 1, а значит П2=2;

n=3: сколько различных трёхзначных чисел можно составить из множества {1, 2, 3}? Комбинаций этих чисел, начинающихся с:

1: будет 1 2 3 1 3 2;

2: будет 2 1 3 2 3 1;

3: будет 3 1 2 3 2 1.

Всего получается 6 чисел. Это значит, что П3=6.

Можно предположить, что

Пn=n* Пn-1 (1)

И это действительно так. Доказать данное равенство можно методом математической индукции.

Формула (1) называется рекуррентной, так как позволяет вычислять значение очередной величины через предыдущее.

Применяя формулу (1) для множества n элементов последовательно, начиная с первого, получим:

Пn=n*(n-1)*(n-2)*…*3*2*1=1*2*3*…*n;

Пn=1*2*3*…*n=n! (2)

Формула (2) и есть формула перестановок в множестве из n элементов.

Для нахождения числа перестановок в MS Excel используется специальная функция категории «Математические» - ФАКТР.

1.2 Сочетания

Рассмотрим пример. Какие наборы можно составить из различного количества предметов, если их всего 4: Шампанское, Печенье, Конфеты, Апельсины?

Были составлены наборы из 1 предмета, из 2-х предметов, из 3-х предметов, из 4-х предметов на основе исходных 4-х предметов.. Иначе можно сказать: были составлены подмножества из 1, 2, 3, 4 предметов, из 4 элементов данного множества.

Такие подмножества называются сочетаниями.

По 1 предмету	По 2 предмета	По 3 предмета	По 4 предмета
Ш	Ш, А	Ш, А, П	Ш, А, П, К
А	Ш, К	Ш, А, К
П	Ш, П	П, К, А
К	К, П	П, К, Ш
	К, А
	П, А
Всего 4	Всего 6	Всего 4	Всего 1

Определение 2. Сочетаниями называются конечные подмножества, составленные из элементов данного множества.

Если в множестве элементов - n, а в подмножестве - m, то общее количество всех сочетаний обозначается и читается как число сочетаний из n элементов по m:

Очевидно, что n m. Формула для вычисления сочетаний выглядит следующим образом:

Для нахождения числа сочетаний в MS Excel используется специальная функция - ЧИСЛКОМБ. В функции ЧИСЛКОМБ(число; число выбранных) должны быть заданы следующие параметры: число - это число объектов n; число выбранных - это число объектов в каждой комбинации m.

1.3 Размещения

Допустим, что есть ткань трёх цветов: Красная, Синяя, Белая. Какие сочетания по 2 цвета можно составить из этих тканей?

Очевидно, что следующие сочетания: {К, С}, {К, Б}, {С, Б}. Если же поставить вопрос следующим образом: а сколько различных двухцветных флагов можно составить, то количество комбинаций в этом случае будет равно 6: {К, С}, {С, К}, {С, Б}, {Б, К}, {К, Б}, {Б, К}. То есть в данном случае подмножеств, состоящих из элементов «красная» и «синяя» будет два, поскольку каждое из них представляет свою расцветку флага: {К, С}, {С, К}. Эти подмножества отличаются от сочетаний тем, что здесь важен порядок расположения элементов. Такие подмножества называются размещениями.

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

Общее количество размещений обозначается как (число размещений из n по m, при условии, что n ? m.

Формула вычисления числа размещений следующая:

(3)

Для нахождения числа размещений в MS Excel можно воспользоваться формулой

или специальной функцией категории «Математические» - ПЕРЕСТ. В функции ПЕРЕСТ(число; число_выбранных) должны быть заданы следующие параметры: число - число объектов n; число_выбранных - число объектов в каждой комбинации m.

1.4 Основные правила комбинаторики

Если некоторый выбор A можно осуществить m способами, а выбор B n способами, то выбрать либо A либо B можно m+n способами. Это правило называется правилом суммы.

Если некоторый выбор A можно осуществить m различными способами, а для каждого из этих способов некоторый другой выбор B можно осуществить n способами, то выбор A и B можно осуществить m*n способами. Это правило произведения.

Эти оба правила могут быть распространены на произвольное число совместно осуществляемых выбора.

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

А для этого следует ответить на два вопроса:

1. Все элементы множества используются или нет? Если используются все элементы, то это перестановка.

2. Важен порядок расположения элементов или нет? Если порядок важен, то это размещение. В противном случае - сочетание.

1.4.1 Основные комбинаторные формулы

Комбинаторные принципы сложения и умножения позволяют решать практически все элементарные задачи комбинаторики. В частности, можно вывести следующие формулы:

,

для любых натуральных n и m, таких, что 1 m n.

При решении комбинаторных задач обычно используются следующие формулы:

биномиальный коэффициент формула комбинаторный



Первое равенство можно получит, если правую часть равенства умножить и разделить на (n-m)!=(n-m)*(n-m-1)*…*3*2*1. Действительно

Отсюда, в свою очередь, легко выводится формула второго равенства:

.

Если в последнем равенстве m заменить на (n-m), то получим следующее равенство:

.

1.5 Бином Ньютона

Бином Ньютона служит для возведения в степень суммы двух слагаемых (бином - это двучлен). Формулы для квадрата и куба суммы хорошо известны:



Бином	Коэффициенты разложения
(a+b)1=a1+b1	1; 1
(a+b)2=a2+2ab+b2	1; 2; 1
(a+b)3=a3+3a2b+3ab2+b3	1; 3; 3; 1
(a+b)4=(a+b)3(a+b)=a4+3a3b+3a2b2+ab3+a3b+3a2b2+3ab3+b4= a4+4a3b+6a2b2+4ab3+b4	1; 4; 6; 4; 1

По аналогии можно записать формулу бинома в общем виде:

Это соотношение называется формулой бинома Ньютона.

При этом формула общего члена может быть представлена выражением:

Тогда в сокращённой записи формула бинома будет выглядеть как:

Кроме того, возможна и другая запись бинома n-ой степени:

,

которая получается, если в предыдущей формуле поменять местами a и b.



1.5.1 Свойства биномиальных коэффициентов

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

или, более определённо

1

1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

1 6 15 20 15 6 1

Из треугольника Паскаля вытекают следующие свойства биномиальных коэффициентов:

1. Члены всякой строки треугольника Паскаля сначала возрастают (до середины строки), а затем - убывают.

Например

1<4<6 6>4>1 4-ая строка

1<5<10 10>5>1 5-ая строка.

2. Всякая строка треугольника Паскаля симметрична относительно своей середины (или: члены всякой строки треугольника Паскаля, равноудалённые от её краёв, равны между собой).

Формально это свойство записывается в виде равенства:

3. Сумма членов n-ой строки треугольника Паскаля равна 2n:

Это можно рассматривать как следствие формулы бинома Ньютона при a=b=1. Поскольку есть число m-элементных подмножеств n-элементного множества, то левую часть последнего равенства можно рассматривать как число всех подмножеств n-элементного множества (включая пустое подмножество и само n-элементное множество). А всякое n-элементное множество имеет 2n подмножеств.

Действительно, составить подмножество данного множества {a1, a2, … ,an} - это значит определить для каждого его элемента, попадёт он в это подмножество или не попадёт (два варианта). Следовательно, по комбинаторному принципу умножения, задача решается 2*2*2*…*2=2n способами.

4. Всякое непустое множество имеет столько подмножеств с чётным числом элементов, сколько и подмножеств с нечётным числом элементов, то есть, другими словами, при n 1

С помощью двух последних равенств можно конкретизировать:

Последнее соотношение получается применением формулы бинома Ньютона к левой части тождества (1-1)n=0.

5. Крайние члены треугольника Паскаля равны 1. Каждый же из остальных членов равен сумме двух смежных с ним членов, стоящих в предыдущей строке.

Например, в 4-ой строке: 4=1+3 6=3+3 4=3+1.

В общем случае (при 1 m n)

Доказать это равенство можно непосредственными вычислениями с помощью формулы . А также при доказательстве можно обратиться к её комбинаторной трактовке: тех сочетаний из элементов {a1, a2, … ,an, an+1} по m, которые не содержат an+1, очевидно будет , тех же сочетаний, которые содержат an+1, будет .

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

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

1. Получить задание.

2. Используя MS EQUATION 3.0 записать формулы вычисления перестановок, размещений и сочетаний.

3. Используя стандартные функции MS Excel ФАКТР, ЧИСЛКОМБ, ПЕРЕСТ выполнить вычисления.

4. Показать расчёты преподавателю.

1.7 Варианты заданий

Вариант 1.

1.1 Определить, сколькими способами можно расставить 7 различных книг на полке.

1.2 Определить, сколько различных списков дежурных из 5 человек можно составить в группе из 25 человек.

1.3 Определить, сколькими способами можно расставить на полке 3 выбранных книги из 9 книг, имеющихся в наличии.

1.4 Вычислить:

Вариант 2.

2.1 Определить, сколькими способами можно рассадить за столом 8 человек гостей.

2.2 Определить, сколько различных букетов из 9 цветков можно составить из 16 полевых ромашек.

2.3 Определить, сколько можно составить четырёхзначных чисел из цифр 7, 9, 6, 3, 5, 4.

2.4 Вычислить:

Вариант 3.

3.1 Определить, сколько различных восьмизначных чисел можно составить из цифр 1, 2, 3, 4, 5, 6, 7, 8.

3.2 На флагштоке 5 мест и 5 флагов: 2 красных и 3 белых. Определить, сколько различных сигналов можно изобразить, используя все флаги одновременно.

3.3 Определить, сколько трёхзначных чисел, не начинающихся с 0, можно составить из цифр 0, 1, 2, 3, 4, 5, 6, 7, 8.

3.4 Вычислить:

Вариант 4.

4.1 Определить, сколько различных комбинаций букв можно составить из всех букв слова «бухгалтер».

4.2 В секции по плаванию 11 юношей и 9 девушек. Для участия в соревнованиях из них нужно составить команду, в которую должны войти 8 юношей и 4 девушки. Определить, сколькими способами это можно сделать.

4.3 Определить, сколькими способами можно из 20 человек шахматного клуба выбрать: капитана команды, казначея и секретаря.

4.4 Вычислить:

Вариант 5.

5.1 Определить, сколько различных комбинаций букв можно составить из всех букв слова «колобок».

5.2 На прямой отмечено 6 точек: A, B, C, D, E, F. Определить, сколько отрезков определяют эти точки.

5.3 На собрании членов кооператива присутствует 45 человек. Определить, сколькими способами из присутствующих можно выбрать: председателя собрания, его заместителя и секретаря.

5.4 Вычислить:

Вариант 6.

6.1 Определить, сколько различных слов можно составить из всех букв слова «пудель», если принять, что с «ь» знака слова не начинаются.

6.2 Определить, сколькими способами можно 16 шахматистов разбить на две группы по 8 человек так, чтобы двое наиболее сильных шахматистов оказались в разных группах.

6.3 Определить, сколькими способами можно среди 12 шахматистов распределить первые 3 места.

6.4 Вычислить:

Вариант 7.

7.1 Вычислить:

7.2 Определить, сколькими способами можно 18 спортсменов разбить на две команды по 9 человек так, чтобы двое наиболее сильных спортсменов оказались в одной группе.

7.3 Определить, сколькими способами можно распределить призовые места (1, 2 и 3) среди 17 артистов, принимающих участие в конкурсе.

7.4 Вычислить:

Вариант 8.

8.1 Вычислить:

8.2 В сборной по биатлону 15 человек. Определить, сколькими способами из числа этих членов для участия в эстафете можно отобрать 3-х спортсменов.

8.3 Определить, сколькими способами из 7 цветных отрезов тканей можно сделать трёхцветных полотен.

8.4 Вычислить:

Вариант 9.

9.1 Вычислить:

9.2 Определить, сколькими способами можно выстроить по два человека 16 участников спартакиады.

9.3 Определить, сколькими способами можно распределить 5 первых мест среди 15 членов команды.

9.4 Вычислить:

Вариант 10.

10.1 Химик использует 8 ингредиентов для приготовления эликсира жизни. Определить, сколько существует различных порядков вливания их в сосуд.

10.2 Определить, сколькими способами можно выбрать 3 книги из 9 книг, имеющихся в наличии.

10.3. Определить, сколькими способами можно распределить из 17 книг первые 4 места наиболее часто читаемых.

10.4 Вычислить:

Вариант 11.

11.1 Сколько шестизначных цифр можно составить из цифр: 7, 9, 6, 2, 5, 3?

11.2 У флориста 12 различных цветков. Сколько различных букетов из 7 цветков может составить флорист?

11.3 Определить, сколькими способами можно распределить из 15 участников конкурса первые 4 места.

11.4 Вычислить:



Вариант 12.

12.1 Определить, сколько различных комбинаций букв можно составить из всех букв слова «колобок».

12.2 Определить, сколькими способами, из имеющихся в наличии 11 цветов лент, можно составить различных комбинаций, состоящих из 4-х разных цветов лент.

12.3 Определить, сколькими способами можно распределить из 19 актёров первые 5 мест наиболее популярных.

12.4 Вычислить:

Вариант 13.

13.1 У школьника 6 карандашей разных цветов. Определить, сколько существует различных цветовых комбинаций при разложении всех этих карандашей в ряд.

13.2 Определить, сколькими способами из 12 человек можно выбрать комиссию из 5 человек.

13.3 Сколько можно составить трёхзначных чисел из цифр 1, 2, 3, 4, 5, 6?

13.4 Вычислить:

Вариант 14.

14.1 Сколько различных маршрутов можно составить для знакомства с городами Париж, Вена, Берлин, Мадрид, Рим, если клиент пожелал первым посетить Рим?

14.2 Сколько различных пятибуквенных слов можно составить из букв слова «треугольник» (слово может начинаться с любой буквы и представлять собою любую комбинацию букв).

14.3 Определить, сколькими способами можно распределить из 9 участников конференции первые 3 места.

14.4 Вычислить:

Вариант 15.

15.1 Сколько различных маршрутов можно составить для знакомства с городами Париж, Вена, Берлин, Мадрид, Рим?

15.2 В подразделении 60 солдат и 5 офицеров. Сколькими способами можно сформировать патруль, состоящий из одного офицера и двух солдат?

15.3 Определить, сколькими способами можно распределить 7 именных стипендии среди 22 студентов.

15.4 Вычислить:



Используемая литература

1. Кочетков Е.С. и др. Теория вероятностей и математическая статистика: Учебник. - 2-е изд. - М.:ФОРУМ, 2008. - 240 с.: ил.

2. Вентцель Е.С., Овчаров Л.А. Задачи и упражнения по теории вероятностей. Учебное пособие. - М.: Высшая школа, 2002. - 448 с.: ил.

3. Гельман В.Я Решение математических задач средствами MS Excel: Практикум. - СПб.: Питер, 2003 - 237 с.: ил.

Размещено на Allbest.ur