Поиск

Полнотекстовый поиск:
Где искать:
везде
только в названии
только в тексте
Выводить:
описание
слова в тексте
только заголовок

Рекомендуем ознакомиться

'Документ'
15 ноября 2013г. Филиал УрГЭУ в г. Березники планирует провести научно-практическую конференцию, посвящённую наиболее актуальным проблемам развития со...полностью>>
'Документ'
Современный уровень развития средств вычислительной техники и уровень развития информационных технологий, используемых при ведении бухгалтерского учет...полностью>>
'Конкурс'
Для участия в конкурсе принимаются работы, повествующие как об одном конкретном памятнике, так и о нескольких. Работы должны основываться на собственн...полностью>>
'Документ'
Настоящий Закон в соответствии с Федеральным законом «Об охране здоровья граждан от воздействия окружающего табачного дыма и последствий потребления т...полностью>>

Главная > Документ

Сохрани ссылку в одной из сетей:
Информация о документе
Дата добавления:
Размер:
Доступные форматы для скачивания:


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

Федеральное агентство РФ по образованию

ГОУ ВПО «Горно-Алтайский государственный университет»

Комбинаторика

и начала теории вероятностей

Горно-Алтайск 2007

Деев М.Е., Соловьев С.П., Соловьева Л.А. Комбинаторика и начала теории вероятностей. – Горно-Алтайск, 2007.

Настоящее пособие подготовлено для учащихся и преподавателей лицеев, гимназий, школ и классов с углубленным изучением математики для проведения факультативов и спецкурсов

Составители:

Деев М.Е., канд. физ.-мат. наук, доцент Горно-Алтайского государственного университета;

Соловьев С.П., канд. физ.-мат. наук, доцент Горно-Алтайского государственного университета;

Соловьева Л.А., старший. преподаватель Горно-Алтайского государственного университета.

 Горно-Алтайский госуниверситет

ВВЕДЕНИЕ………………………………………………………….

Раздел I. Комбинаторика

1. Общие правила комбинаторики………………………………….

2. Размещения………………………………………………………..

3. Перестановки……………………………………………………...

4. Сочетания………………………………………………………….

5. Треугольник Паскаля. Бином Ньютона…………………………

6. Примеры более сложных задач на сочетания,

размещения и перестановки без повторений……………………..

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

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

9. Сочетания с повторениями……………………………………….

10. Схема определения вида комбинации…………………………

11. Примеры более сложных задач комбинаторики………………

12. Задачи для самостоятельного решения………………………...

Раздел II. Теория ВЕРОЯТНОСТЕЙ

13. Классическое определение вероятности……………………….

14. Статистическое определение вероятности…………………….

15. Геометрические вероятности…………………………………...

16. Сумма событий………………………………………………….

17. Произведение событий………………………………………….

18. Вероятность суммы совместимых событий…………………...

19. Условные вероятности………………………………………….

20. Вероятность произведения зависимых событий………………

21. Формула полной вероятности…………………………………..

22. Формула Байеса………………………………………………….

23. Формула Бернулли………………………………………………

24. Случайные величины……………………………………………

25. Числовые характеристики случайной величины……………...

26. Задачи для самостоятельного решения………………………..

ЛИТЕРАТУРА……………………………………………………….

Ответы к задачам для самостоятельного решения………………..

3

3

5

6

7

9

10

12

14

15

16

11

20

23

24

25

28

29

30

31

31

32

33

34

35

35

39

41

42

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ

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

Комбинаторика возникла в XVI веке. Первоначально она, как и теория вероятностей, применялась для расчета шансов на выигрыш в различных азартных играх: рулетке, игре в кости, а также в карточных играх. Теоретические исследования вопросов комбинаторики предпринимали итальянские математики Тарталья и Кардано, французы Паскаль и Ферма, причем в работах последних были уже заложены основы теории вероятностей. Постепенно комбинаторные методы стали тем аппаратом, с помощью которого удалось получить замечательные результаты в теории вероятностей. Здесь можно отметить работы Я. Бернулли, который комбинаторными методами доказал первую содержательную теорему теории вероятностей – так называемый закон больших чисел. Серьезный вклад в разработку теории вероятностей сделали русские и советские математики П.Л. Чебышев, А.А.Марков, А.М.Ляпунов, А.Н.Колмогоров и другие. И хотя ее аппарат чрезвычайно расширился и усложнился по сравнению с аппаратом теории вероятностей XIX века, комбинаторные методы сохраняют свое значение и сегодня.

Раздел I. Комбинаторика

1. Общие правила комбинаторики

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

Правило суммы. Если объект А можно выбрать n способами, а объект Вk способами, то объект «А или В» можно выбрать n+k способами.

Пример 1. В ящике находятся 20 шаров: 5 белых, 6 черных, 7 синих и 2 красных. Сколькими способами можно взять из ящика один цветной шар?

Решение. Здесь предполагается, что цветной шар – это синий или красный, поэтому надо применять правило суммы. Цветной шар можно выбрать 7 + 2 = 9 способами.

Правило произведения. Если объект А можно выбрать n способами, а объект В независимо от него – k способами, то пару объектов «А и В» можно выбрать nk способами.

Пример 2. Сколько может быть различных комбинаций выпавших граней при бросании двух игральных костей? (Игральная кость – это кубик, на гранях которого нанесены числа 1, 2, 3, 4, 5, 6 )

Решение. На первой кости может выпасть 1, 2, 3, 4, 5 или 6 очков, то есть всего будет 6 вариантов. Точно так же и на второй кости 6 вариантов. По правилу произведения получится всего 6  6 = 36 способов.

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

Пример 3. Из города А в город В ведут 5 дорог, а из города В в город С – 3 дороги. Сколькими способами можно проехать из города А в город С?

Решение. Чтобы проехать из А в С, надо проехать из А в В и из В в С, поэтому применим правило произведения. 5  3 = 15.

Пример 4. На книжной полке стоят 3 книги по алгебре, 4 книги по геометрии и 5 книг по литературе. Сколькими способами можно взять с полки одну книгу по математике?

Решение. Книга по математике – это книга по алгебре или по геометрии. Применяем правило суммы. 3 + 4 = 7.

Пример 5. В меню имеется 4 первых блюда, 3 вторых и 2 третьих. Сколько различных полных обедов можно из них составить?

Решение. Полный обед состоит из первого, и второго, и третьего блюд. По правилу произведения получаем 4  3  2 = 24 различных полных обеда.

2. Размещения

Если из данного множества предметов мы будем выбирать некоторое подмножество, то его будем называть выборкой. Выборки бывают упорядоченные и неупорядоченные. В упорядоченной выборке существенен порядок, в котором следуют ее элементы, другими словами, изменив порядок элементов, мы получим другую выборку. Например, из цифр 1, 2, 3, 4, 5 составляем трехзначные числа 123, 431, 524, …и т.д. Это упорядоченные трехэлементные выборки, ведь 123 и 132 – разные числа. Другой пример: из 20 учащихся класса будем выбирать двух дежурных. Любая пара дежурных представляет собой неупорядоченную двухэлементную выборку, так как порядок их выбора не важен.

Определение 2.1. Размещениями из n элементов по m (mn) называются упорядоченные m-элементные выборки из данных n элементов.

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

Число размещений из n по m обозначается . Чтобы вывести формулу числа размещений, заметим, что первый элемент в выборку мы можем выбрать n способами, второй из оставшихся n–1 элементов (n–1) способами, третий – (n–2) способами и так далее, m-й элемент можно выбрать n–(m–1) = nm+1 способами. По правилу произведения получим:

(2.1)

Это и есть формула для вычисления числа размещений.

Найдем, например, число размещений из 7 по 3. Здесь n = 7, nm +1 =5. Значит, . Заметим, что верхний индекс 3 показывает, сколько сомножителей надо взять в произведение. Приведем еще несколько примеров:

Пример 6. Составить все размещения из трех букв А, В, С по две буквы.

Решение. Это будут: АВ, АС, ВС, ВА, СА, СВ. Проверим по формуле: Их действительно 6 штук. Отметим, что АВ и ВА – разные размещения.

Пример 7. На пяти карточках написаны числа 1, 2, 3, 4, 5. Сколько различных трехзначных чисел можно из них составить?

Решение. Трехзначные числа представляют собой трехэлементные выборки из пяти цифр, причем, выборки упорядоченные, поскольку порядок цифр в числе существенен. Значит, этих чисел будет столько, сколько существует размещений из пяти элементов по 3.

. Ответ: 60 чисел.

Часто формулы комбинаторики записывают с помощью факториалов. Произведение всех последовательных натуральных чисел от 1 до n обозначается n! (читается: эн-факториал).

n! = 1  2  3  …  n.

Формулу (1.1) можно теперь преобразовать следующим образом. Умножим и разделим правую часть этой формулы на выражение (nm)! = 1  2  3  … (nm). Тогда получится:

(2.2)

Вычислим, например, по этой формуле:

Мы видим, что здесь приходится еще сокращать дробь, поэтому для вычисления числа размещений с конкретными значениями m и n первая формула предпочтительнее. Условились считать, что 0! =1.

3. Перестановки

Определение 3.1. Перестановками из n элементов называются размещения из n элементов по n.

Из определения следует, что в данном случае в упорядоченную выборку входят все n элементов и отличаться выборки могут только порядком. Поэтому все перестановки имеют один и тот же состав и отличаются только порядком элементов.

Число перестановок из n элементов обозначается Рn. Подставляя в формулу (2.1) или (2.2) m = n, получим формулу для вычисления числа перестановок из n элементов:

(3.1)

Приведем несколько примеров использования этой формулы.

Р5 = 5! = 1 2 3  4 5 = 120; Р2 = 2! = 1 2 = 2; Р1 = 1! = 1.

Пример 8. Составить все размещения из трех букв А, В, С.

Решение. АВС, АСВ, ВАС, ВСА, СВА, САВ. Проверим по формуле: Р3 = 1 2 3 = 6.

Пример 9. Сколькими способами можно расставить 7 книг на книжной полке?

Решение. Каждая расстановка будет отличаться от другой порядком следования книг. Поэтому это будут перестановки из семи элементов.

Р7 = 7! = 1 2 3  4 5 6 7 = 5040. Ответ: 5040 способами.

Пример 10. Сколько шестизначных чисел можно составить из цифр 0, 1, 2, 3, 4, 5 так, чтобы цифры в числе не повторялись?

Решение. Из данных шести цифр можно составить Р6 = 6! = 720 перестановок. Но числа, начинающиеся на нуль, не являются шестизначными. Такие числа отличаются друг от друга перестановкой пяти остальных цифр, значит, их будет Р5 = 120. Поэтому шестизначных чисел будет 720 – 120 = 600. Ответ: 600 чисел.

4. Сочетания

Определение 4.1. Сочетаниями из n элементов по m (mn) называются неупорядоченные m-элементные выборки из данных n элементов.

Ясно, что все сочетания отличаются друг от друга хотя бы одним элементом, а порядок элементов здесь не существенен. Число сочетаний из n по m обозначается . Чтобы из сочетаний получить размещения, надо упорядочить каждую m-элементную выборку, а это можно сделать m! способами. Следовательно, число сочетаний меньше числа размещений в m! раз. Учитывая этот факт, из формул (2.1) и (2.2) получим соответствующие формулы для вычисления числа сочетаний:

(4.1)

и (4.2)

Например,

Пример 11. Составить все сочетания из трех букв А, В, С по две буквы.

Решение. Это будут АВ, АС, ВС. Проверим по формуле:

(Обратите внимание, что АВ и ВА – это одно и то же сочетание, на разные размещения.)

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

Решение. Надо выбрать двух человек из 20. Ясно, что от порядка выбора ничего не зависит, то есть Иванов-Петров или Петров-Иванов – это одна и та же пара дежурных. Следовательно, это будут сочетания из 20 по 2.

Ответ: 190 способами.

Пример 13. Сколькими способами можно группу из 15 учащихся разделить на две группы так, чтобы в одной группе было 4, а в другой – 11 человек?

Решение. Чтобы разделить эту группу, достаточно выбрать 4 человека из 15, а оставшиеся сами образуют другую группу. А выбрать 4 человека из 15 можно способами.

. Ответ: 1365 способами

Эту задачу можно было решить по-другому: из 15 учащихся выбрать 11, а остальные 4 образуют другую группу. Это можно осуществить способами.

.

Получается тот же ответ и возникает подозрение, что . Это действительно так. Сочетания обладают свойством

, (4.3)

в чем легко убедиться с помощью формулы (4.2):

.

Пользуясь этой формулой, вычислим .



Похожие документы:

  1. Мониторинг 30. 09. 2013

    Документ
    ... математике и физике для учащихся выпускных классов Московского физико-технического института, для проведения ... учреждением с углубленным изучением математики. А с 2004 года открыты классы с углубленным изучением информатики. В школе работает ...
  2. Пособие адресовано преподавателям, аспирантам и студентам педагогических институтов и университетов, а также слушателям системы повышения квалификации работников образования. Ббк 74. 03

    Документ
    ... состав учащихся в классе; 2) твердый порядок проведения занятий по времени и расписанию; 3) занятия преподавателя со всем классом ... клуб". В некоторых школах (гимназия Репман) ликвидировали возрастные классы и создавали группы для изучения тех или иных ...
  3. 1. Проблема демократизации школы

    Реферат
    ... нового набора учащихся. Хрони­ческую нужду в преподавателях математики и естественных наук испытывает школа Англии. В ... и т. д. ). В начальных классах Московской гимназии вводилось обучение музыке и живописи, в старших классахизучение вместо одного ...
  4. Медиаобразовани е в ведущих странах Запада

    Документ
    ... проведения занятий с учащимися. А комплексное изучение ... факультативов, спецкурсов, ... изучение медиакультуры стало обязательным для учащихся всех канадских средних школ с 1 по 12 класс ... «финансистов», составителей графиков « ... пособий для преподавателей ...
  5. Содержание общие вопросы методики преподавания русского языка 3

    Документ
    ... пособий видеофильмы, которые демонстри­руются с помощью видеомагнитофона. В настоящее время для ... ­теля, и учащихся. Преподаватель сам выбирает те ... речь. Программы для I-XI классов с углубленным изучением предмета (гимназии, лицеи, школы гуманитарного про ...

Другие похожие документы..