Реферат на тему:
Выполнил ученик 10 класса «В»
средней школы №53
Глухов Михаил Александрович
г. Набережные Челны
2002 г.
Содержание
| Из истории комбинаторики_________________________________________ | 3 |
| Правило суммы___________________________________________________ | 4 |
| - | |
| Правило произведения_____________________________________________ | 4 |
| Примеры задач____________________________________________________ | - |
| Пересекающиеся множества________________________________________ | 5 |
| Примеры задач____________________________________________________ | - |
| Круги Эйлера_____________________________________________________ | - |
| Размещения без повторений________________________________________ | 6 |
| Примеры задач____________________________________________________ | - |
| Перестановки без повторений_______________________________________ | 7 |
| Примеры задач____________________________________________________ | - |
| Сочетания без повторений__________________________________________ | 8 |
| Примеры задач____________________________________________________ | - |
| Размещения и сочетания без повторений______________________________ | 9 |
| Примеры задач____________________________________________________ | - |
| Перестановки с повторениями_______________________________________ | 9 |
| Примеры задач____________________________________________________ | - |
| Задачи для самостоятельного решения________________________________ | 10 |
| Список используемой литературы___________________________________ | 11 |
Из истории комбинаторики
Комбинаторика занимается различного вида соединениями, которые можно образовать из элементов конечного множества. Некоторые элементы комбинаторики были известны в Индии еще во II в. до н. э. Нидийцы умели вычислять числа, которые сейчас называют "сочетания". В XII в. Бхаскара вычислял некоторые виды сочетаний и перестановок. Предполагают, что индийские ученые изучали соединения в связи с применением их в поэтике, науке о структуре стиха и поэтических произведениях. Например, в связи с подсчетом возможных сочетаний ударных (долгих) и безударных (кратких) слогов стопы из n слогов. Как научная дисциплина, комбинаторика сформировалась в XVII в. В книге "Теория и практика арифметики" (1656 г.) французский автор А. Также посвящает сочетаниям и перестановкам целую главу.
Б. Паскаль в "Трактате об арифметическом треугольнике" и в "Трактате о числовых порядках" (1665 г.) изложил учение о биномиальных коэффициентах. П. Ферма знал о связях математических квадратов и фигурных чисел с теорией соединений. Термин "комбинаторика" стал употребляться после опубликования Лейбницем в 1665 г. работы "Рассуждение о комбинаторном искусстве", в которой впервые дано научное обоснование теории сочетаний и перестановок. Изучением размещений впервые занимался Я. Бернулли во второй части своей книги "Ars conjectandi" (искусство предугадывания) в 1713 г. Современная символика сочетаний была предложена разными авторами учебных руководств только в XIX в.
Все разнообразие комбинаторных формул может быть выведено из двух основных утверждений, касающихся конечных множеств – правило суммы и правило произведения.
Правило суммы
Если конечные множества не пересекаются, то число элементов X U Y {или} равно сумме числа элементов множества X и числа элементов множества Y.
То есть, если на первой полке стоит X книг, а на второй Y, то выбрать книгу из первой или второй полки, можно X+Y способами.
Примеры задач
Ученик должен выполнить практическую работу по математике. Ему предложили на выбор 17 тем по алгебре и 13 тем по геометрии. Сколькими способами он может выбрать одну тему для практической работы?
Решение: X=17, Y=13
По правилу суммы X U Y=17+13=30 тем.
Имеется 5 билетов денежно-вещевой лотереи, 6 билетов спортлото и 10 билетов автомотолотереи. Сколькими способами можно выбрать один билет из спортлото или автомотолотереи?
Решение: Так как денежно-вещевая лотерея в выборе не участвует, то всего 6+10=16 вариантов.
Правило произведения
Если элемент X можно выбрать k способами, а элемент Y-m способами то пару (X,Y) можно выбрать k*m способами.
То есть, если на первой полке стоит 5 книг, а на второй 10, то выбрать одну книгу с первой полки и одну со второй можно 5*10=50 способами.
Примеры задач
Переплетчик должен переплести 12 различных книг в красный, зеленый и коричневые переплеты. Сколькими способами он может это сделать?
Решение: Имеется 12 книг и 3 цвета, значит по правилу произведения возможно 12*3=36 вариантов переплета.
Сколько существует пятизначных чисел, которые одинаково читаются слева направо и справа налево?
Решение: В таких числах последняя цифра будет такая же, как и первая, а предпоследняя - как и вторая. Третья цифра будет любой. Это можно представить в виде XYZYX , где Y и Z -любые цифры, а X - не ноль. Значит по правилу произведения количество цифр одинаково читающихся как слева направо, так и справа налево равно 9*10*10=900 вариантов.
Пересекающиеся множества
Но бывает, что множества X и Y пересекаются, тогда пользуются формулой
, где X и Y - множества, а - область пересечения.
Примеры задач
20 человекзнаютанглийскийи 10 - немецкий, изних 5 знаютианглийский, инемецкий. СколькоЧеловеквсего?
Ответ: 10+20-5=25 человек.
Также часто для наглядного решения задачи применяются круги Эйлера. Например:
Из 100 туристов, отправляющихся в заграничное путешествие, немецким языком владеют 30 человек, английским - 28, французским - 42. Английским и немецким одновременно владеют 8 человек, английским и французским - 10, немецким и французским - 5, всеми тремя языками - 3. Сколько туристов не владеют ни одним языком?
Решение: Выразим условие этой задачи графически. Обозначим кругом тех, кто знает английский, другим кругом - тех, кто знает французский, и третьим кругом - тех, кто знают немецкий.
Всеми тремя языками владеют три туриста, значит, в общей части кругов вписываем число 3. Английским и французским языком владеют 10 человек, а 3 из них владеют еще и немецким. Следовательно, только английским и французским владеют 10-3=7 человек.
Аналогично получаем, что только английским и немецким владеют 8-3=5 человек, а немецким и французским 5-3=2 туриста. Вносим эти данные в соответствующие части.
Определим теперь, сколько человек владеют только одним из перечисленных языков. Немецкий знают 30 человек, но 5+3+2=10 из них владеют и другими языками, следовательно, только немецкий знают 20 человек. Аналогично получаем, что одним английским владеют 13 человек, а одним французским - 30 человек.
По условию задачи всего 100 туристов. 20+13+30+5+7+2+3=80 туристов знают хотя бы один язык, следовательно, 20 человек не владеют ни одним из данных языков.
Размещения без повторений.
Сколько можно составить телефонных номеров из 6 цифр каждый, так чтобы все цифры были различны?
Это пример задачи на размещение без повторений. Размещаются здесь 10 цифр по 6. А варианты, при которых одинаковые цифры стоят в разном порядке считаются разными.
Если X-множество, состоящие из n элементов, m≤n, то размещением без повторений из n элементов множества X по m называется упорядоченное множество X, содержащее m элементов называется упорядоченное множество X, содержащее m элементов.
Количество всех размещений из n элементов по m обозначают
n! - n-факториал (factorial анг. сомножитель) произведение чисел натурального ряда от 1 до какого либо числа n
n!=1*2*3*...*n 0!=1
Значит, ответ на вышепоставленную задачу будет
Задача
Сколькими способами 4 юноши могут пригласить четырех из шести девушек на танец?
Решение : два юноши не могут одновременно пригласить одну и ту же девушку. И варианты, при которых одни и те же девушки танцуют с разными юношами считаются, разными, поэтому:
Возможно 360 вариантов.
Перестановки без повторений
В случае n=m (см. размещения без повторений) из n элементов по m называется перестановкой множества x.
Количество всех перестановок из n элементов обозначают P n.
Действительно при n=m:
Примеры задач
Сколько различных шестизначных чисел можно составить из цифр 0, 1, 2, 3, 4,5, если цифры в числе не повторяются?
1) Найдем количество всех перестановок из этих цифр: P 6 =6!=720
2) 0 не может стоять впереди числа, поэтому от этого числа необходимо отнять количество перестановок, при котором 0 стоит впереди. А это P 5 =5!=120.
P 6 -P 5 =720-120=600
Проказница Мартышка
Да косолапый Мишка
Затеяли играть квартет
Стой, братцы стой! –
Кричит Мартышка, - погодите!
Как музыке идти?
Ведь вы не так сидите…
И так, и этак пересаживались – опять музыка на лад не идет.
Аналоги комбинаторных концепций и методов используются и в топологии, при изучении дерева принятия решений, частично упорядоченных множеств, раскрасок графа и др.
25) Что называют перестановками?
Перестановки - различные упорядоченные множества, которые отличаются лишь порядком элементов (т.е. могут быть получены из того же самого множества).
26) По какой формуле вычисляют число перестановок из n различных элементов?
Перестановки. Возьмём n различных элементов: a 1 , a 2 , a 3 , …, a n . Будем переставлять их всеми возможными способами, сохраняя их количество и меняя лишь порядок их расположения. Каждая из полученных таким образом комбинаций называетсяперестановкой. Общее количество перестановок из n элементов обозначается P n . Это число равно произведению всех целых чисел от 1 до n :
Символ n ! (называется факториал ) - сокращённая запись произведения: 1 · 2 · 3 · … · (n – 1) · n .
П р и м е р. Найти число перестановок из трёх элементов: a , b , c .
Р е ш е н и е. В соответствии с приведенной формулой: P
3 = 1 · 2 · 3 = 6.
Действительно, мы имеем 6 перестановок: abc, acb, bac, bca, cab, cba.
27) Что называют размещениями? Запишите формулу, по которой вычисляют число размещений из n элементов по m.
Размещения - это упрядоченные подмножества данного конечного множества.
Размещения. Будем составлять группы из m n элементов, располагая эти m взятых элементов в различном порядке. Полученные комбинации называются размещениями из n элементов по m .
Их общее количество обозначается: и равно произведению:
П р и м е р. Найти число размещений из четырёх элементов a, b, c, d по два.
Р е ш е н и е. В соответствии с формулой получим:
Вот эти размещения: ab, ba, ac, ca, ad, da, bc, cb, bd, db, cd, dc.
28) Что называют сочетаниями? Запишите формулу, по которой вычисляют число сочетаний из n элементов по m.
Сочетание без повторений из n элементов по m есть m -элементное подмножество некоторого n -элементного множества.
Коротко такие сочетания называют "сочетания из m по n " и их число обозначают или . Далее n -элементное множество будем обозначать как n -множество.
Сочетания. Будем составлять группы из m различных элементов, взятых из множества, состоящего из n элементов, не принимая во внимание порядок расположения этих m элементов. Тогда мы получим сочетания из n элементов по m .
Их общее количество обозначается и может быть вычислено по формуле:
Из этой формулы ясно, что
Заметим, что можно составить только одно сочетание из n элементов по n , которое содержит все n элементов. Формула числа сочетаний даёт это значение, если только принять, что 0! = 1 , что является определением 0! .
В соответствии с этим определением получим:
Общее число сочетаний можно вычислить, пользуясь и другим выражением:
П р и м е р. Найти число сочетаний из пяти элементов: a, b, c, d, e по три.
Р е ш е н и е:
Эти сочетания: abc, abd, abe, acd, ace, ade, bcd, bce, bde, cde.
29) По какой формуле вычисляется число перестановок из n элементов, если элементы повторяются?
Перестановками из n элементов называются размещения из этих n элементов по n (Перестановки - частный случай размещений).
Число перестановок без повторений (n
Пример . Возьмем буквы Б, А, Р . Какие перестановки из этих букв можно получить? Сколько таких наборов получится, если: 1) буквы в наборе не повторяются; 2) буква А повторяется два раза?
Решение.
1. Получатся наборы: БАР, БРА, АРБ, АБР, РАБ, РБА.
По формуле (3.3) получаем: 
наборов.
2. Получатся наборы: БАРА, БРАА, БААР, ААРБ, ААБР, АБАР, АРАБ, АРБА, АБРА, РАБА, РААБ, РБАА.
По формуле (3.4) получаем: 
наборов.
Пример . Сколько шестизначных чисел можно составить из цифр 0, 1, 2, 3, 4, 5 так, чтобы цифры в числе не повторялись?
Решение. Из данных шести цифр можно составить Р 6 = 6! = 720 перестановок. Но числа, начинающиеся на нуль, не являются шестизначными. Такие числа отличаются друг от друга перестановкой пяти остальных цифр, значит, их будет Р 5 = 120. Поэтому шестизначных чисел будет 720 - 120 = 600 чисел.
Пример . Сколькими способами можно расставить белые фигуры (2 ладьи, 2 коня, 2 слона, ферзь и король) на первой линии шахматной доски?
Решение. Первая линия шахматной доски представляет собой 8 клеток, на которых и надо расположить эти 8 фигур. Различные варианты расположения будут отличаться только порядком фигур, значит, это будут перестановки с повторениями Р 8 (2,2,2).
По формуле (3.4) получаем: способов.
30) Какой формулой определяется число размещений с повторениями из n элементов по m элементов?
Размещения
Размещениями из n элементов по m элементов (m < n ) называются комбинации, составленные из данных n элементов по m элементов, которые отличаются либо самими элементами, либо порядком элементов.
Число размещений без повторений из n по m (n различных элементов) вычисляется по формуле:
Пример . Возьмем буквы Б, А, Р . Какие размещения из этих букв, взятых по две, можно получить? Сколько таких наборов получиться, если: 1) буквы в наборе не повторяются; 2) буквы могут повторяться?
Решение.
1. Получатся следующие наборы: БА, БР, АР, АБ, РБ, РА .
По формуле (3.1) получаем: 
наборов.
2. Получатся наборы: ББ, БА, БР, АА, АБ, АР, РР, РБ, РА.
По формуле (3.2) получаем: наборов.
Пример. Вдоль дороги стоят 6 светофоров. Сколько может быть различных комбинаций их сигналов, если каждый светофор имеет 3 состояния: "красный", "желтый", "зеленый"?
Решение. Выпишем несколько комбинаций: КККЖЗЗ, ЗЗЗЗЗЗ, КЖЗКЖЗ... Мы видим, что состав выборки меняется и порядок элементов существенен (ведь если, например, в выборке КЖЗКЖЗ поменять местами К и Ж, ситуация на дороге будет другой). Поэтому применяем формулу (3.2) и вычисляем число размещений с повторениями из 3 по 6, получаем комбинаций.
31) Какой формулой определяется число сочетаний с повторениями из n элементов по m элементов?
Сочетания
Сочетаниями из n элементов по m элементов называются комбинации, составленные из данных n элементов по m элементов, которые различаются хотя бы одним элементом (отличие сочетаний от размещений в том, что в сочетаниях не учитывается порядок элементов).
Число сочетаний без повторений (n различных элементов, взятых по m ) вычисляется по формуле:
Пример . Возьмем буквы Б, А, Р . Какие сочетания из этих букв, взятых по две, можно получить? Сколько таких наборов получится, если: 1) буквы в наборе не повторяются; 2) можно брать по два одинаковые буквы.
Решение .
1. Получатся наборы: БА (БА и АБ - один и тот же набор), АР и РБ
По формуле (3.5) получаем: 
наборов.
2. Получатся наборы: ББ, БА, БР, АА, АР, РР.
По формуле (3.6) получаем: наборов.
Пример . Из 20 учащихся надо выбрать двух дежурных. Сколькими способами это можно сделать?
Решение. Надо выбрать двух человек из 20. Ясно, что от порядка выбора ничего не зависит, то есть Иванов-Петров или Петров-Иванов - это одна и та же пара дежурных. Следовательно, это будут сочетания из 20 по 2.
По формуле (3.5) получаем: 
способов.
Пример . В хлебном отделе имеются булки белого и черного хлеба. Сколькими способами можно купить 6 булок хлеба?
Решение. Обозначая булки белого и черного хлеба буквами Б и Ч, составим несколько выборок: ББББББ, ББЧЧББ, ЧЧЧЧЧБ, ... Состав меняется от выборки к выборке, порядок элементов несущественен, значит это - сочетания с повторениями из 2 по 6. По формуле (3.6) получаем способов.
Cделаем проверку и выпишем все варианты покупки: ББББББ, БББББЧ, ББББЧЧ, БББЧЧЧ, ББЧЧЧЧ, БЧЧЧЧЧ, ЧЧЧЧЧЧ. Их действительно 7.
32) Что называют суммой двух событий?
Суммойдвух событийи
называют событие, состоящее в появлении события , или события , или обоих этих событий.
Суммой нескольких событий
называют событие, состоящее в появлении хотя бы одного из этих событий.
33) Что называют произведением двух событий?
Произведением двух событийи называют событие , состоящее в совместном появлении этих событий.
34) Чему равна вероятность суммы двух несовместных событий?
Событие
называют независимым от события
, если появление события не меняет вероятности появления события , то есть если условная вероятность события равна его безусловной вероятности:
.
Свойство независимости событий взаимно: если событие не зависит от события , то и событие не зависит от события .
Теорема.
Вероятность совместного появления двух независимых событий равна произведению вероятности этих событий:
.
Несколько событий называют попарно независимыми
, если каждые два из них независимы.
Несколько событий называют независимыми в совокупности
, если независимы каждые два из них и независимы каждое событие и все возможные произведения остальных.
35) Сформулируйте теорему сложения?
Вероятность р (А + В ) суммы событий А и В равна
Р (А + В ) = р (А ) + р (В ) – р (АВ ). (2.2)
Доказательство.
Докажем теорему сложения для схемы случаев. Пусть п – число возможных исходов опыта, т А – число исходов, благоприятных событию А , т В – число исходов, благопри-ятных событию В , а т АВ – число исходов опыта, при которых происходят оба события (то есть исходов, благоприятных произведению АВ ). Тогда число исходов, при которых имеет место событие А + В , равно т А + т В – т АВ (так как в сумме (т А + т В ) т АВ учтено дважды: как исходы, благоприятные А , и исходы, благоприятные В ). Следовательно, вероятность суммы можно определить по формуле 2,2 что и требовалось доказать.
Рассмотрим задачу подсчета числа выборок из данного множества в общем виде. Пусть имеется некоторое множество N , состоящее из n элементов. Любое подмножество, состоящее из m элементов можно рассматривать без учета их порядка, так и с его учетом, т.е. при изменении порядка переходим к другой m – выборке.
Сформулируем следующие определения:
Размещения без повторения
Размещением без повторения из n элементов по m N , содержащее m различных элементов .
Из определения следует, что два размещения отличаются друг от друга, как элементами, так и их порядком, даже если элементы одинаковы.
Теорема 3 . Число размещений без повторения равно произведению m сомножителей, наибольшим из которых является число n . Записывают:
Перестановки без повторений
Перестановками из n элементов называются различные упорядочения множества N .
Из этого определения следует, что две перестановки отличаются только порядком элементов и их можно рассматривать как частный случай размещений.
Теорема 4 . Число различных перестановок без повторений вычисляется по формуле
Сочетания без повторений
Сочетанием без повторения из n элементов по m называется любое неупорядоченное подмножество множества N , содержащее m различных элементов.
Из определения следует, что два сочетания различаются только элементами, порядок не важен.
Теорема 5 . Число сочетаний без повторений вычисляют по одной из следующих формул:
Пример 1 . В комнате 5 стульев. Сколькими способами можно разместить на них
а) 7 человек; б) 5 человек; в) 3 человека?
Решение:
а) Прежде всего надо выбрать 5 человек
из 7 для посадки на стулья. Это можно
сделать
способом. С каждым выбором конкретной
пятерки можно произвести
перестановок местами. Согласно теореме
умножения искомое число способов посадки
равно.
Замечание: Задачу можно решать, используя только теорему произведения, рассуждая следующим образом: для посадки на 1-й стул имеется 7 вариантов, на 2-й стул-6 вариантов, на 3-й -5, на 4-й -4 и на 5-й -3. Тогда число способов посадки 7 человек на 5 стульев равно . Решения обоими способами согласуются, так как
б) Решение очевидно
-
в)
- число выборов занимаемых стульев.
- число размещений
трех человек на трех выбранных стульях.
Общее число выборов равно .
Не трудно проверить
формулы
;
;
Число всех подмножеств множества, состоящего из n элементов.
Размещения с повторением
Размещением с повторением из n элементов по m называется всякое упорядоченное подмножество множества N , состоящее из m элементов так, что любой элемент ожжет входить в это подмножество от 1 до m раз, либо вообще в нем отсутствовать .
Число
размещений с повторением обозначают
и вычисляют по формуле, представляющей
собой следствие из теоремы умножения:
Пример 2
.
Пусть дано множество из трех букв N
= {a,
b,
c}.
Назовем словом любой набор из букв,
входящих в это множество. Найдем
количество слов длиной 2, которые можно
составить из этих букв:
.
Замечание:
Очевидно, размещения с повторением
можно рассматривать и при
.
Пример 3 . Требуется из букв {a, b}, составить всевозможные слова длиной 3. Сколькими способами это можно сделать?
Ответ
:
В данной статье речь пойдет об особом разделе математики под названием комбинаторика. Формулы, правила, примеры решения задач - все это вы сможете найти здесь, прочитав статью до самого конца.
Итак, что же это за раздел? Комбинаторика занимается вопросом подсчета каких-либо объектов. Но в данном случае объектами выступают не сливы, груши или яблоки, а нечто иное. Комбинаторика помогает нам находить вероятность какого-либо события. Например, при игре в карты - какова вероятность того, что у противника есть козырная карта? Или такой пример - какова вероятность того, что из мешка с двадцатью шариками вы достанете именно белый? Именно для подобного рода задач нам и нужно знать хотя бы основы данного раздела математики.
Комбинаторные конфигурации
Рассматривая вопрос основных понятий и формул комбинаторики, мы не можем не уделить внимание комбинаторным конфигурациям. Они используются не только для формулировки, но и для решения различных Примерами таких моделей служат:
- размещение;
- перестановка;
- сочетание;
- композиция числа;
- разбиение числа.
О первых трех мы поговорим более подробно далее, а вот композиции и разбиению мы уделим внимание в данном разделе. Когда говорят о композиции некого числа (допустим, а), то подразумевают представление числа а в виде упорядоченной суммы неких положительных чисел. А разбиение - это неупорядоченная сумма.
Разделы
Прежде чем мы перейдем непосредственно к формулам комбинаторики и рассмотрению задач, стоит обратить внимание на то, что комбинаторика, как и другие разделы математики, имеет свои подразделы. К ним относятся:
- перечислительная;
- структурная;
- экстремальная;
- теория Рамсея;
- вероятностная;
- топологическая;
- инфинитарная.
В первом случае речь идет об исчисляющей комбинаторике, задачи рассматривают перечисление или подсчет разных конфигураций, которые образованы элементами множеств. На данные множества, как правило, накладываются какие-либо ограничения (различимость, неразличимость, возможность повтора и так далее). А количество этих конфигураций подсчитывается при помощи правила сложения или умножения, о которых мы поговорим немного позже. К структурной комбинаторике относятся теории графов и матроидов. Пример задачи экстремальной комбинаторики - какова наибольшая размерность графа, который удовлетворяет следующим свойствам… В четвертом пункте мы упомянули теорию Рамсея, которая изучает в случайных конфигурациях наличие регулярных структур. Вероятностная комбинаторика способна нам ответить на вопрос - какова вероятность того, что у заданного множества присутствует определенное свойство. Как нетрудно догадаться, топологическая комбинаторика применяет методы в топологии. И, наконец, седьмой пункт - инфинитарная комбинаторика изучает применение методов комбинаторики к бесконечным множествам.
Правило сложения
Среди формул комбинаторики можно найти и довольно простые, с которыми мы достаточно давно знакомы. Примером является правило суммы. Предположим, что нам даны два действия (С и Е), если они взаимоисключаемы, действие С выполнимо несколькими способами (например а), а действие Е выполнимо b-способами, то выполнить любое из них (С или Е) можно а+b способами.
В теории это понять достаточно трудно, постараемся донести всю суть на простом примере. Возьмем среднюю численность учеников одного класса - допустим, это двадцать пять. Среди них пятнадцать девочек и десять мальчиков. Ежедневно в классе назначается один дежурный. Сколько есть способов назначить дежурного по классу сегодня? Решение задачи достаточно простое, мы прибегнем к правилу сложения. В тексте задачи не сказано, что дежурными могут быть только мальчики или только девочки. Следовательно, им может оказаться любая из пятнадцати девочек или любой из десяти мальчиков. Применяя правило суммы, мы получаем достаточно простой пример, с которым без труда справится школьник начальных классов: 15 + 10. Подсчитав, получаем ответ: двадцать пять. То есть существует всего двадцать пять способов назначить на сегодня дежурного класса.
Правило умножения
К основным формулам комбинаторики относится и правило умножения. Начнем с теории. Допустим, нам необходимо выполнить несколько действий (а): первое действие выполняется с1 способами, второе - с2 способами, третье - с3 способами и так далее до последнего а-действия, выполняемого са способами. Тогда все эти действия (которых всего у нас а) могут быть выполнены N способами. Как высчитать неизвестную N? В этом нам поможет формула: N = с1 * с2 * с3 *…* са.
Опять же, в теории ничего не понятно, переходим к рассмотрению простого примера на применение правила умножения. Возьмем все тот же класс из двадцати пяти человек, в котором учится пятнадцать девочек и десять мальчиков. Только на этот раз нам необходимо выбрать двух дежурных. Ими могут быть как только мальчики или девочки, так и мальчик с девочкой. Переходим к элементарному решению задачи. Выбираем первого дежурного, как мы решили в прошлом пункте, у нас получается двадцать пять возможных вариантов. Вторым дежурным может быть любой из оставшихся человек. У нас было двадцать пять учеников, одного мы выбрали, значит вторым дежурным может быть любой из оставшихся двадцати четырех человек. Наконец, применяем правило умножения и получаем, что двоих дежурных можно избрать шестью сотнями способов. Мы данное число получили умножением двадцати пяти и двадцати четырех.
Перестановка
Сейчас мы рассмотрим еще одну формулу комбинаторики. В данном разделе статьи мы поговорим о перестановках. Рассмотреть проблему предлагаем сразу же на примере. Возьмем бильярдные шары у нас их n-ое количество. Нам нужно подсчитать: сколько есть вариантов расставить их в ряд, то есть составить упорядоченный набор.
Начнем, если у нас нет шаров, то и вариантов расстановки у нас так же ноль. А если у нас шар один, то и расстановка тоже одна (математически это можно записать следующим образом: Р1 = 1). Два шара можно расставить двумя разными способами: 1,2 и 2,1. Следовательно, Р2 = 2. Три шара можно расставить уже шестью способами (Р3=6): 1,2,3; 1,3,2; 2,1,3; 2,3,1; 3,2,1; 3,1,2. А если таких шаров не три, а десять или пятнадцать? Перечислять все возможные варианты очень долго, тогда нам на помощь приходит комбинаторика. Формула перестановки поможет нам найти ответ на интересующий нас вопрос. Pn = n *P (n-1). Если попытаться упростить формулу, то получаем: Pn = n* (n - 1) *…* 2 * 1. А это и есть произведение первых натуральных чисел. Такое число называется факториалом, а обозначается как n!
Рассмотрим задачу. Вожатый каждое утро выстраивает свой отряд в шеренгу (двадцать человек). В отряде есть три лучших друга - Костя, Саша и Леша. Какова вероятность того, что они будут стоять рядом? Чтобы найти ответ на вопрос, нужно вероятность «хорошего» исхода поделить на общее количество исходов. Общее число перестановок составляет 20! = 2,5 квинтиллиона. Как посчитать количество «хороших» исходов? Предположим, что Костя, Саши и Леша - это один сверхчеловек. Тогда мы имеем всего восемнадцать субъектов. Число перестановок в данном случае равняется 18 = 6,5 квадриллионов. При всем этом, Костя, Саша и Леша могут произвольно перемещаться между собой в своей неделимой тройке, а это еще 3! = 6 вариантов. Значит всего «хороших» расстановок у нас 18! * 3! Нам остается только найти искомую вероятность: (18! * 3!) / 20! Что равняется примерно 0,016. Если перевести в проценты, то это получается всего 1,6%.
Размещение
Сейчас мы рассмотрим еще одну очень важную и необходимую формулу комбинаторики. Размещение - это наш следующий вопрос, который предлагаем вам рассмотреть в данном разделе статьи. Мы идем на усложнение. Предположим, что мы хотим рассмотреть возможные перестановки, только не из всего множества (n), а из меньшего (m). То есть мы рассматриваем перестановки из n предметов по m.
Основные формулы комбинаторики стоит не просто заучивать, а понимать их. Даже несмотря на то, что они усложняются, так как у нас не один параметр, а два. Предположим, что m = 1, то и А = 1, m = 2, то А = n * (n - 1). Если далее упрощать формулу и перейти на запись при помощи факториалов, то получится вполне лаконичная формула: А = n! / (n - m)!
Сочетание
Мы рассмотрели практически все основные формулы комбинаторики с примерами. Теперь перейдем к заключительному этапу рассмотрения базового курса комбинаторики - знакомство с сочетанием. Сейчас мы будем выбирать m предметов из имеющихся у нас n, при этом всем мы будем выбирать всеми возможными способами. Чем же тогда это отличается от размещения? Мы не будем учитывать порядок. Этот неупорядоченный набор и будет являться сочетанием.
Сразу введем обозначение: С. Берем размещения m шариков из n. Мы перестаем обращать внимание на порядок и получаем повторяющиеся сочетания. Чтобы получить число сочетаний нам надо поделить число размещений на m! (m факториал). То есть С = А / m! Таким образом, способов выбрать из n шаров немножко, равняется примерно столько, сколько выбрать почти все. Этому есть логическое выражение: выбрать немножко все равно, что выкинуть почти все. Еще в данном пункте важно упомянуть и то, что максимальное число сочетаний можно достигнуть при попытке выбрать половину предметов.
Как выбрать формулу для решения задачи?
Мы подробно рассмотрели основные формулы комбинаторики: размещение, перестановка и сочетание. Теперь наша задача - облегчить выбор необходимой формулы для решения задачи по комбинаторике. Можно воспользоваться следующей довольно простой схемой:
- Задайте себе вопрос: порядок размещения элементов учитывается в тексте задачи?
- Если ответ нет, то воспользуйтесь формулой сочетания (С = n! / (m! * (n - m)!)).
- Если ответ нет, то необходимо ответить на еще один вопрос: все ли элементы входят в комбинацию?
- Если ответ да, то воспользуйтесь формулой перестановки (Р = n!).
- Если ответ нет, то воспользуйтесь формулой размещения (А = n! / (n - m)!).
Пример
Мы рассмотрели элементы комбинаторики, формулы и некоторые другие вопросы. Теперь перейдем к рассмотрению реальной задачи. Представьте, что перед вами лежат киви, апельсин и банан.
Вопрос первый: сколькими способами их можно переставить? Для этого воспользуемся формулой перестановок: Р = 3! = 6 способов.
Вопрос второй: сколькими способами можно выбрать один фрукт? Это очевидно, у нас всего три варианта - выбрать киви, апельсин или банан, но применим формулу сочетаний: С = 3! / (2! * 1!) = 3.
Вопрос третий: сколькими способами можно выбрать два фрукта? Какие есть у нас вообще варианты? Киви и апельсин; киви и банан; апельсин и банан. То есть три варианта, но это легко проверить при помощи формулы сочетания: С = 3! / (1! * 2!) = 3
Вопрос четвертый: сколькими способами можно выбрать три фрукта? Как видно, выбрать три фрукта можно одним-единственным способом: взять киви, апельсин и банан. С = 3! / (0! * 3!) = 1.
Вопрос пятый: сколькими способами можно выбрать хотя бы один фрукт? Это условие подразумевает, что мы можем взять один, два или все три фрукта. Следовательно, мы складываем С1 + С2 + С3 =3 + 3 + 1 = 7. То есть у нас есть семь способов взять со стола хотя бы один фрукт.
