Элементы комбинаторики
Основные правила комбинаторики.
Комбинаторика— это раздел математики, изучающий способы расположения объектов в соответствии со специальными правилами и методы подсчета числа всех возможных способов. Правило умножения. Если некоторый выбор A можно осуществить m способами, а для каждого из них некоторый другой выбор B можно осуществить n способами, то выбор A и B ( в указанном порядке) можно осуществить m×n способами. Пример 1.На гору ведут 6 дорог. Сколькими способами можно подняться на гору и спуститься с горы, если подъем и спуск должен быть по разным дорогам? Решение. Дорогу на гору можно выбрать 6-ю способами, так как подъем и спуск должны быть по разным дорогам, то выбрать дорогу для спуска можно 5-ю способами. Тогда по правилу умножения число способов выбора дороги для подъема и спуска равно 6×5=30. Правило сложения.
2
Перестановки.
Определение 1.Множество называется упорядоченным, если каждому элементу этого множества поставлено в соответствие некоторое натуральное число от 1 до n, где n — это число элементов данного множества, причем разным элементам поставлены в соответствие разные числа.
Упорядоченные множества считаются различными, если они отличаются либо своими элементами, либо их порядком. Определение 2. Различные упорядоченные множества, составленные из элементов данного множества, отличающиеся лишь порядком элементов, называются его перестановками. Пример 3.Рассмотрим множество M={a,b,c}. Это множество из трех элементов. Составим его различные перестановки: (a,b,c),(a,c,b),(b,a,c),(b,c,a),(c,a,b),(c,b,a). Получили 6 перестановок. Pn — число всех перестановок множества из n элементов.
Pn=n! (1), где
n!=1·2·3·…·n (
читается «н факториал»). Замечание.
0!=1; (n+1)!=n!·(n+1) . Пример
4.Сколько
шестизначных чисел, кратных пяти, можно
составить из цифр 0,1,2,3,4,5, при условии,
что в числе нет одинаковых цифр?
Решение.
Числа, кратные пяти( делящиеся на пять),
оканчиваются либо на 0, либо на 5. Если
последняя цифра числа 0, то остальные
цифры можно располагать в любом порядке,
получим перестановки из пяти элементов,
их P5=5!=120.
Если на конце 5, то остальные можно
расположить P
Вопрос.Сколько существует перестановок из шести элементов?
Ваш ответ : 720
верно
Перестановки с повторениями.
Если взять цифры 1, 2, 3, 4, то из них можно составить 24 перестановки. Но если взять четыре цифры 1, 1, 2, 2, то можно получить только следующие различные перестановки: (1,1,2,2),(1,2,1,2),(1,2,2,1),((2,2,1,1),(2,1,2,1),(2,1,1,2), то есть шесть перестановок, их в 4 раза меньше, чем перестановок из четырех различных чисел, так как перестановки, в которых меняются местами одинаковые числа — это не новые перестановки, их 2!·2!=4. Рассмотрим задачу в общем виде:пусть имеется множество из элементов, в котором элементывстречаютсяраз, элементывстречаютсяраз ,…, элементывстречаютсяраз, причем.
Определение 3.
Перестановки с повторениями — это перестановки из элементов данного множества, в которых элементы повторяются. — число всех перестановок с повторениями. Число перестановок, не меняющих данную перестановку с повторениями равно, ачисел можно переставлятьспособами, поэтому получаем следующую формулу для вычисления числа перестановок с повторениями:(2)
Пример 4.Сколькими способами можно расселить 8 студентов по трем комнатам: одноместной, трехместной и четырехместной? Решение. Различныеспособы расселения студентов по комнатам являются перестановками с повторениями, так как внутри, например, трехместной комнаты выбранные студенты могут занимать спальные места по-разному, но эти варианты не будут являться новыми перестановками, поэтому получаем: То есть всего 280 способов расселения студентов.Вопрос. Вычислить
Сочетания.
Пусть некоторое множество содержит n элементов.
Определение 4.
(3)
Пример 5. Для соревнований из 30 спортсменов надо выбрать трех человек. Сколькими способами это можно сделать? Решение. Команда из 3 спортсменов — это подмножество из трех элементов, то есть сочетание из 30 по 3, поэтому количество способов выбора таких команд вычисляется по формуле (3): .
Свойства сочетаний.
1. 2.. Из данных свойств следует, что, тогда, далее,,и так далее. Можно расположить эти числа в виде таблицы:
……………………………………………..
или
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
…………………..
Эта таблица в виде треугольника называется треугольником Паскаля .
Определение 5. Выражение a+b называется биномом.
(4)
Формула (4) называется биномиальной формулой Ньютона, а коэффициенты называются биномиальными коэффициентами. Из данной формулы вытекает следующее свойство числа сочетаний
(5)
Вопрос. .
Сочетания с повторениями
Пусть имеется множество, содержащее n видов элементов, поэтому есть взять какое-то подмножество этого множества, то в нем могут быть одинаковые элементы. Определение 6.Сочетание с повторениями — это m- элементное подмножество множества, содержащего n видов элементов, в котором элементы повторяются. — число всех сочетаний с повторениями из n по m. Состав m- элементного подмножества имеет вид, где. Заменяя каждое из чиселсоответствующим количеством единиц и разделяя единицы нулями, получаем набор, состоящий из m единиц и n-1 нулей. Каждому составу отвечает только одна запись из нулей и единиц, а каждая запись задает только один состав, следовательно, число различных составов равно числу перестановок с повторениями из n-1 нулей и m единиц. Получаем формулу для вычисления всех сочетаний с повторениями.
(5)
Пример 6.В кондитерском магазине продаются пирожные четырех видов: наполеоны, эклеры, песочные и бисквитные. Сколькими способами можно купить 7 пирожных? Решение. Любая покупка — это подмножество, в котором могут быть одинаковые элементы, поэтому это сочетание с повторениями. Число всех возможных покупок находим по формуле (5): .Вопрос. В формуле (5) m может быть больше n.
Размещения
Определение 7. Упорядоченное m — элементное подмножество n- элементного множества называется размещением. — число всех размещений из n элементов по m. Число всех размещений из n по m больше числа всех сочетаний из n по m, так как из каждого подмножества из m элементов с помощью перестановок можно получить m! упорядоченных подмножеств, получаем формулу для числа размещений
(6)
Пример 7. В группе 25 человек. Нужно выбрать актив группы: старосту, заместителя старосты и профорга. Сколькими способами это можно сделать? Решение. Актив группы — это упорядоченное подмножество из трех элементов, так как надо выбрать не только трех человек, но и распределить между ними должности, значит актив группы — это размещение, число всех размещений вычисляем по формуле (6): .Вопрос. Во сколько раз число сочетаний из 20 по 4 меньше числа размещений из 20 по 4?
Размещения с повторениями
Пусть дано множество из n элементов, в котором есть одинаковые элементы, тогда его подмножества тоже могут содержать одинаковые элементы. Определение 8. Упорядоченные m- элементные подмножества n- элементного множества, в которых элементы могут повторяться, называются размещениями с повторениями. — число всех размещений из n по m. В подмножестве из m элементов первый элемент можно выбрать n способами( то есть любой элемент множества) , так как элементы могут повторяться, то второй элемент тоже можно выбрать n способами, аналогично остальные элементы подмножества можно выбрать n способами, если воспользоваться правилом умножения, получим формулу для вычисления числа размещений с повторениями:
(7)
Пример 8. В лифт десятиэтажного дома вошли 5 человек. Каждый из них может выйти на любом этаже, начиная со второго. Сколькими способами они могут это сделать? Решение. Так как каждый человек может выйти на любом этаже, начиная со второго, то этажей для выхода 9. Надо выбрать этажи для возможности выхода каждого человека: для первого человека — можно выбрать любой из девяти этажей, аналогично для остальных пассажиров, тогда по формуле (7): способов.Вопрос. Вычислить .
studfiles.net
Элементы комбинаторики
Комбинаторика с (лат. соединение, сочетание) — раздел математики изучающий приёмы вычислений числа различных комбинаций.
Какие задачи называют комбинаторными? Те, где спрашивается каким числом можно осуществить требуемое.
1. Принципы в подсчёте числа комбинации или правила суммы и произведения.
Большинство задач решается с помощью этих двух принципов.
Принцип суммы. «Если некоторый объект А можно выбрать т способами, а другой объект В можно выбрать n способами, то выбор «либо А, либо В» можно осуществить (т +n) способами».
Применяется в том случае, когда изучаемые комбинации удаётся разбить на несколько классов, причём каждая комбинация входит в один, и только в один класс.
Пример 1
Принцип произведения. «Если объект А можно выбрать т способами, и если после каждого такого выбора объект В можно выбрать n способами, то выбор пары «А и В» в указанном порядке можно осуществить (тn) способами».
Пример 2……
2. Комбинации по типу перестановок, размещений и сочетаний. Такие комбинации встречаются чаще обычного. Рассмотрим их.
2.1. Перестановки. Пусть имеется множество из n элементов. Установленный в некотором множестве порядок называют перестановкой его элементов.
Примеры перестановок: распределение n различных должностей среди n человек или расположение n различных предметов в одном ряду.
Зададимся вопросом: «Сколько различных перестановок можно образовать в множестве из n элементов!» Число перестановок обозначается Рn (читается «Р из n«).
Чтобы вывести формулу числа перестановок, представим себе n ячеек, пронумерованных числами 1,2,…,n. Все перестановки будем образовывать, располагая элементы множества в этих ячейках. В первую ячейку можно занести любой из n элементов (иначе: первую ячейку можно заполнить n различными способами). Заполнив первую ячейку, можно найти (n-1) вариантов заполнения второй ячейки. Таким образом, существует n(n-1) вариантов заполнения двух первых ячеек. При заполнении первых двух ячеек можно найти (n-2) варианта заполнения третьей ячейки, откуда получается, что три ячейки можно заполнить n(n-1)(n-2) способами. Продолжая этот процесс, получим, что число способов заполнения n ячеек равно n(n—1)(n-2)·…· 3·2 ·1. Отсюда
Рn = n(n—1)(n-2)·…· 3·2 ·1.
Число n (n-2)·…· 3·2 ·1, то есть произведение всех натуральных чисел от 1 до n, называется «n—факториал» и обозначается n! Отсюда Pn=n!
По определению считается: 1!=1. Но чему равен 0!=?. Для любого n>1 справедливо n!=n(n-1)! Положим n=1, тогда 1!=1·0!, следовательно, 0!=1.
Пример 3. Сколько существует вариантов замещения пяти различных вакантных должностей между пятью кандидатами?
N=5!=5·4·3·2·1=120.
2.2. Размещения. Размещениями из n элементов по т элементов будем называть упорядоченные подмножества, состоящие из т элементов множества, состоящего из n элементов. Число размещений из n элементов по т элементов обозначается (читается «А из n по т «).
Зададимся вопросом: «Сколько упорядоченных подмножеств по т элементов в каждом можно получить из заданного множества в n элементов?»
Одно размещение из n элементов по т элементов может отличаться от другого как набором элементов, так и порядком их расположения.
Примеры задач, приводящих к необходимости подсчета числа размещений. Сколькими способами можно выбрать из пятнадцати человек пять кандидатов и назначить их на пять различных должностей? Сколькими способами можно из двадцати книг отобрать двенадцать и расставить их в ряд на полке?
В задачах о размещениях полагается т < п. В случае если т=n, то легко получить = Рn =n!
Для вычисления используем тот же метод, что использовался для подсчетаРn только здесь выберем лишь т ячеек. Первую ячейку можно заполнить n способами, вторую, при заполненной первой, можно заполнить (n-1) способами. Таким образом, существует n(n— 1) вариантов заполнения первых двух ячеек. Можно продолжать этот процесс до заполнения последней т -й ячейки. Эту ячейку при заполненных первых (m – 1) ячейках можно заполнить n – (m – 1) = n – m +1 способами. Таким образом, все т ячеек заполняются числом способов, равным
n(n – 1)(n – 2)… (n – m + 2)(n – m + 1) =
Отсюда получаем:
Пример 4. Сколько существует различных вариантов выбора четырёх кандидатур из девяти специалистов для поездки в четыре страны?
2.3. Сочетания. Сочетаниями из n элементов по т элементов называются подмножества, состоящие из т элементов множества, состоящего из n элементов.
Одно сочетание от другого отличается только составом выбранных элементов, но не порядком их расположения, как у размещений.
Число сочетаний из n элементов по т элементов обозначается (читается «С из n по т «).
Примеры задач, приводящих к подсчету числа сочетаний. Сколько существует вариантов выбора шести человек из пятнадцати кандидатов для назначения на работу в одинаковых должностях? Сколькими способами можно из двадцати книг отобрать двенадцать книг?
Выведем формулу для подсчета числа сочетаний. Пусть имеется множество из n элементов. Образуем подмножество, содержащее т элементов, т.е. сочетание. Известно число упорядоченных подмножеств из т элементов всего множества из n элементов, т.е. размещений из n по т : . Количество неупорядоченных подмножеств будет вm! раз меньше. Т.е. во столько раз сколькими способами можно установить порядок во множестве из т элементов. Следовательно, .
Пример 5. Шесть человек из пятнадцати можно выбрать числом способов, равным
Несложно понять, что осуществить выбор подмножества из т элементов множества, насчитывающего n элементов, можно, выбрав (n — т) элементов, которые не войдут в интересующее нас подмножество. Отсюда следует свойство числа сочетаний
Эту формулу можно легко доказать, используя формулу для числа сочетаний.
studfiles.net
Комбинаторика
Реферат на тему:
Выполнил ученик 10 класса «В»
средней школы №53
Глухов Михаил Александрович
г. Набережные Челны
2002 г.
Содержание
Из истории комбинаторики
Комбинаторика занимается различного вида соединениями, которые можно образовать из элементов конечного множества. Некоторые элементы комбинаторики были известны в Индии еще во 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 элементов обозначают Pn.
Pn =n!
Действительно при n=m:
Примеры задач
Сколько различных шестизначных чисел можно составить из цифр 0, 1, 2, 3, 4,5, если цифры в числе не повторяются?
Решение:
1) Найдем количество всех перестановок из этих цифр: P6 =6!=720
2) 0 не может стоять впереди числа, поэтому от этого числа необходимо отнять количество перестановок, при котором 0 стоит впереди. А это P5 =5!=120.
P6 -P5 =720-120=600
Квартет
Проказница Мартышка
Осел,
Козел,
Да косолапый Мишка
Затеяли играть квартет
…
Стой, братцы стой! –
Кричит Мартышка, — погодите!
Как музыке идти?
Ведь вы не так сидите…
И так, и этак пересаживались – опять музыка на лад не идет.
mirznanii.com
Элементы комбинаторики: перестановки, размещения, сочетания.
Комбинаторика – это наука о расположении элементов в определенном порядке и о подсчете числа способов такого расположения.
Комбинаторный принцип умножения если одну часть действия можно выполнить k способами, а другую — p способами, то все действие можно выполнить k*p числом способов.
Размещением из n элементов множества Х по k элементам назовем любой упорядоченный набор элементов множества Х.
Если выбор делается без возвращения, т.е. каждый элемент множества Х можно выбирать только один раз, то количество размещений из n по k обозначается и определяется равенством
(размещения без повторений).
Если выбор элементов множества Y из Х происходит с возвращением, т.е. каждый элемент множества Х может быть выбран несколько раз, то число размещений из n по k находится по формуле: = nk.
Пусть из множества Х выбирается неупорядоченное подмножество Y (порядок элементов в подмножестве не имеет значения). Сочетаниями из n элементов по k называются подмножества из k элементов, отличающиеся друг от друга хотя бы одним элементом. Общее число всех сочетаний из n по k обозначается и равно
.
Справедливы равенства: , , .
Сочетание с повторениями – сколько способами можно взять из n k элементов с возвращениями и без учета порядка. Число сочетаний с повторениями из n по k равно биномиальному коэффициенту.
Перестановки.
Pn – количество перестановок из n элементов (сколько способами можно упорядочить)
Основные комбинаторные схемы.
— число перестановок (упорядочивание)
— число перемещений (число размещений)
— число сочетаний (без учета порядка)
— число сочетаний с возвращениями с учетом порядка
— число сочетаний с возвращениями без учета порядка (число сочетаний с повторениями)
Основные алгебраические структуры: полугруппы, группы, кольца, поля и их простейшие свойства.
Алгебраическая структура это множество, на котором определены некоторые операции и отношения.
Множество с одной бинарной ассоциативной операцией называется полугруппой. Полугруппы иногда называют моноидами.
Полугруппа называется группой если:
а) есть нейтральный элемент
б) для любого элемента есть обратный.
Множество с двумя ассоциативными операциями (сложения и умножения) называется кольцом, если
а) оно является коммутативной группой относительно сложения
б) операция умножения дитрибутивна относительно операции сложения, то есть для любых элементов a,b,c исходного множества справедливы тождества:
a + (b * c) = a * c + b * c
c * (a + b) = c * a + c * b
Полем называется коммутативное кольцо (то есть обе бинарные операции коммутативны), в котором существует нейтральный элемент по умножению (1) и каждый элемент, отличный от нуля (нуль – нейтральный по сложению), имеет обратный по умножению.
Множество действительных чисел, больших нуля и операцией умножения – коммутативная группа.
Множество целых чисел с операциями сложения и умножения – коммутативное кольцо
Множество всех действительных чисел с операциями сложения и умножения является кольцом и даже полем.
Множество всех комплексных чисел с операциями сложения и умножения – поле
Множество всех квадратных матриц порядка два с действительными элементами, по сложению – коммутативная группа, по умножению – группой не является.
Свойства элементов группы. Подгруппы группы.
Группа – множества с одной бинарной ассоциативной операцией, с нейтральным элементом и обратным элементов для каждого элемента.
Подгруппа – подмножество группы, также является само группой относительно той же операции. (G > H)
e – нейтральный элемент. Если есть в группе, то он есть и в подгруппе. Это один и тот же элемент, и быть другим в подгруппе он не может.
g-1 – обратный, есть и в группе и в подгруппе, отличаться не может.
Отношения эквивалентности.
x1, x2 ∈ X
x1 ρ x2 – находятся в отношении
Отношение эквивалентности – это отношение, для которого выполняются 3 свойства:
1) Для любого х есть свойство быть в отношении самому с собой
x ∈ X
x ρ x
2) x ρ y à y ρ x (свойство симметричности)
3) x ρ y, y ρ x à x ρ z (свойство транзитивности)
Рекомендуемые страницы:
lektsia.com