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

Содержание

Некоторые элементы комбинаторики были известны в Индии еще во 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 - множества , а - область пересечения.

Например: Решение: Выразим условие этой задачи графически.

Обозначим кругом тех, кто знает английский, другим кругом - тех, кто знает французский, и третьим кругом - тех, кто знают немецкий. Аналогично получаем, что только английским и немецким владеют 8-3=5 человек, а немецким и французским 5-3=2 туриста.

Вносим эти данные в соответствующие части. По условию задачи всего 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. P n =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 Квартет Проказница Мартышка Осел, Козел, Да косолапый Мишка Затеяли играть квартет … Стой, братцы стой! – Кричит Мартышка, - погодите! Как музыке идти? Ведь вы не так сидите… И так, и этак пересаживались – опять музыка на лад не идет. Тут пуще прежнего пошли у низ раздоры И споры, Кому и как сидеть… Вероятно, крыловские музыканты так и не перепробовали всех возможных мест.

Однако способов не так уж и много.

Сколько? Здесь идет перестановка из четырех, значит, возможно P 4 =4!=24 варианта перестановок.

Сочетания без повторений Сочетанием без повторений называется такое размещение, при котором порядок следования элементов не имеет значения.

Всякое подмножество X состоящее из m элементов, называется сочетанием из n элементов по m. Таким образом, количество вариантов при сочетании будет меньше количества размещений. Число сочетаний из n элементов по m обозначается Примеры задач Сколько трехкнопочных комбинаций существует на кодовом замке (все три кнопки нажимаются одновременно), если на нем всего 10 цифр.

Решение : Так как кнопки нажимаются одновременно, то выбор этих трех кнопок – сочетание.

Отсюда возможно У одного человека 7 книг по математике, а у второго – 9. Сколькими способами они могут обменять друг у друга две книги на две книги.

Решение: Так как надо порядок следования книг не имеет значения, то выбор 2 ух книг - сочетание.

Первый человек может выбрать 2 книги способами.

Второй человек может выбрать 2 книги При игре в домино 4 игрока делят поровну 28 костей.

Сколькими способами они могут это сделать? Первый игрок делает выбор из 28 костей.

Второй из 28-7=21 костей, третий 14, а четвертый игрок забирает оставшиеся кости.

Следовательно, возможно Размещения и сочетания с повторениями Часто в задачах по комбинаторике встречаются множества, в которых какие-либо компоненты повторяются.

Например: в задачах на числа – цифры. Для таких задач при размещениях используется формула Примеры задач Сколько трехзначных чисел можно составить из цифр 1, 2, 3, 4, 5? Решение . Так как порядок цифр в числе существенен, цифры могут повторяться, то это будут размещения с повторениями из пяти элементов по три, а их число равно В кондитерском магазине продавались 4 сорта пироженных: эклеры, песочные, наполеоны и слоеные.

Сколькими способами можно купить 7 пироженных.

Решение : Покупка не зависит от того, в каком порядке укладывают купленные пироженные в коробку.

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

Следовательно, количество различных покупок равно числу сочетаний четырех видов пироженных по семь - Обезьяну посадили за пишущую машинку с 45 клавишами, определить число попыток, необходимых для того, чтобы она наверняка напечатала первую строку романа Л.Н. Толстого «Анна Каренина», если строка содержит 52 знака и повторений не будет? Решение : порядок букв имеет значение. Буквы могут повторяться.

Значит, всего есть вариантов.

Перестановки с повторениями 1 ,n 2 ,…,n r -количество одинаковых элементов.

Примеры задач Сколькими способами можно переставить буквы слова «ананас»? Решение : всего букв 6. Из них одинаковы n 1 «а»=3, n 2 «н»=2, n 3 «с»=1. Следовательно, число различных перестановок равно Задачи для самостоятельного решения Сколько перестановок можно сделать из букв слова «Миссисипи». Ответ: 2520 Имеется пять различных стульев и семь рулонов обивочной ткани различных цветов.

Сколькими способами можно осуществить обивку стульев. Ответ: 16807 На памятные сувениры в «Поле Чудес» спонсоры предлагают кофеварки, утюги, телефонные аппараты, духи.

Сколькими способами 9 участников игры могут получить эти сувениры? Сколькими способами могут быть выбраны 9 предметов для участников игры? Ответ: 4 9 , 220 Сколькими способами можно расставить на шахматной доске 8 ладей так, чтобы на одна из них не могла бить другую? Ответ: 40320 Сколько может быть случая выбора 2 карандашей и 3 ручек из пяти различных карандашей и шести различных ручек? Ответ:200 Сколько способов раздачи карт на 4 человека существует в игре «Верю не верю» (карты раздаются полностью, 36 карт). Ответ: В течении 30 дней сентября было 12 дождливых дней, 8 ветреных, 4 холодных, 5 дождливых и ветреных, 3 дождливых и холодных, а один день был и дождливым, и ветреным, и холодным. В течение скольких дней в сентябре стояла хорошая погода. Ответ: 15 На ферме есть 20 овец и 24 свиньи.