Формулы комбинаторикиПерестановки
1) Перестановки без повторений. Перестановки - это комбинации, состоящие из одних и тех же элементов и отличающиеся только порядком расположения этих элементов. Возьмем n различных элементов a1, a2, a3, … an; будем переставлять эти элементы всевозможными способами, оставляя без изменения число элементов и меняя только порядок их расположения. Обозначим общее число полученных таким образом перестановок P(n). P - первая буква французского словаpermutation - перестановка. Составив таблицу перестановок для n элементов и применив (n - 1) раз правило произведения, получим число всех возможных перестановок: P(n) = n • (n -1) • (n - 2) • … • 3 • 2 • 1 = n! Такие перестановки называются перестановками без повторений (один и тот же элемент не может повториться в комбинации, все элементы различны). Задача: шесть человек могут в разном порядке сесть за круглый стол, сколько существует способов разместить эти шесть человек за столом? Решение: т.к. все люди различны и их комбинации различаются только порядком следования, то мы имеем перестановки без повторений. Определим их число: Р(6) = 6! = 1 • 2 • 3 • 4 • 5 • 6 = 720. 2) Перестановки с повторениями
Рассматривая различные перестановки, мы предполагали, что все n элементов различны. Если же некоторые элементы повторяются, то в этом случае комбинации с повторениями вычисляют по другим формулам. Если среди n элементов есть n1 элементов одного вида, n2 элементов другого вида и т.д., nk элементов к-го вида, то имеем перестановки с повторениями, их число: , где n1+…+nk = n. Задача: сколько различных «слов» можно составить из букв слова ДЕД, МАТЕМАТИКА. Решение: имеем перестановки с повторениями. А) ДЕД n=3, k=2, n1=2, n2=1 P3(2, 1) = 3!/(2! • 1!) = 6 / 2 = 3; Б) МАТЕМАТИКА n=10, k=6, n1=2, n2=3, n3=2, n4=n5=n6=1 P10(2,3,2,1,1,1)=10!/(2! • 3! • 2!)=2•4•5•6•7•9•10 = 134 400. Размещения
1) Размещения без повторений. Размещениями называют комбинации, составленные из n данных элементов по k элементов (k<=n, k>0), которые отличаются либо составом элементов, либо порядком расположения элементов. Обозначаются размещения Ank . А - первая буква французского слова arrangement, что в переводе означает "размещение", "приведение в порядок". Число всех возможных размещений находится по формуле: . Задача: расписание одного дня состоит из двух пар. Определить число вариантов расписания при выборе из пяти дисциплин, если не может быть одинаковых пар. Решение: имеем размещения без повторений из пяти элементов по два, из число: . 2) Размещения с повторениями. Пусть существуют n различных элементов. Выберем из них m штук, действуя по следующему принципу: возьмем любой элемент, но не будем устанавливать его в какой-либо ряд, а просто запишем под номером 1 его название, сам же элемент вернем к остальным элементам. Затем опять из всех n элементов выберем один, запишем его название под номером 2 и снова вернем элемент обратно. Будем выполнять эти операции, пока не получим m названий. Размещения с повторениями вычисляются по формуле: . Задача: сколько четырехзначных номеров можно составить из 10 цифр? Решение: имеем размещения с повторениями из 10 элементов по 4, их число: . Сочетания1) Сочетания без повторений. Сочетаниями называют комбинации, составленные из n различных элементов по k (k =< n) элементов, которые отличаются хотя бы одним элементом. Сочетания обозначаются: Cnk C - первая буква французского слова combinasion- сочетание. Составим из n элементов всевозможные сочетания по k элементов в каждом. Их будет Cnk . Внутри каждого сочетания, состоящего из k элементов, образуем всевозможные комбинации, учитывающие порядок следования в них элементов. Таких комбинаций будет Pk, т.к. мы в нашем сочетании образовываем перестановки. Всего различных комбинаций из n элементов по k в каждой, отличающихся друг от друга либо составом (элементами), либо порядком их следования, будет Cnk • Pk . Но такие комбинации называются размещениями. Таким образом, Ank = Cnk • Pk, тогда: . Задача: в шахматном турнире участвует 7 человек; сколько партий будет сыграно, если между любыми двумя участниками должна быть сыграна партия? Решение: имеем сочетания без повторений из 7 элементов по 2; их число: . 2) Сочетания с повторениями.
Если в сочетаниях некоторые элементы (или все) могут оказаться одинаковыми, то такие сочетания называются сочетаниями с повторениями. Их число определяется по формуле: . Задача: сколько наборов из 7 пирожных можно составить, если в продаже имеется 4 сорта пирожных? Решение: имеем сочетания с повторениями из четырех по 7 по, их число: .
Вопросы и задания! 1. Города A,B,C,D,E попарно соединены дорогами. Сколько разных маршрутов путешествия из города А в город Е с посещением еще каких-то двух городов можно составить? Предполагается, что в маршруте каждый город присутствует не более одного раза, и маршруты, отличающиеся порядком следования городов, различны.
2. Сколькими способами можно распределить среди 20 студентов группы четыре билета в театр, если
3. Есть 4 билета на концерт, 5 билетов в театр и 7 билетов в цирк. Сколькими способами их можно распределить среди 25 студентов группы, если каждый студент может получить не более одного билета на каждое мероприятие? Билеты на одно мероприятие считаются равнозначными.
4. Девочка нанизала n разных бусин на английскую булавку. Сколько различных украшений может получиться таким образом? Два украшения различны, если они отличаются порядком следования бусин на булавке.
5. У англичан принято давать детям несколько имен. Сколькими способами можно назвать ребенка, если ему дадут не более трех имен из 300 возможных, и при этом
|
Календарь
Калькулятор
Поиск
Друзья сайта
|