Перестановки с повторениями
Перестановки без повторений.
Перестановки
Формулы комбинаторики
Перестановки - это комбинации, состоящие из одних и тех же элементов и отличающиеся только порядком расположения этих элементов. Возьмем 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.
Рассматривая различные перестановки, мы предполагали, что все 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.