Размещения без повторений

В размещении с повторениями были допустимы повторы элементов в каждой ячейке. Как на примере кодового замка - одну крутящуюся "крутилку :)" с цифрами можно сопоставить с одной ячейкой, а цифры от нуля до девяти на ней - элементами. Очевидно, что может быть несколько ячеек с одинаковой цифрой. "Отоно шо, Мыхалыч, от оно шо", потому и называется размещения с повторениями. А что если ячейками является несколько стульев, а элементами люди? Очевидно, что на трех разных стульев не может сидеть один и тот же человек (Конечно если он не наберется наглости и не ляжет вдоль стульев, чем эффектно испортит весь эксперимент). Вот как раз в такие моменты и используется формуларазмещения без повторения которая выглядит вот так: Где m - количество элементов, а k - количество ячеек. m! - рассчитывает все возможные варианты комбинаций данных элементов. (m-k)! - все возможные варианты элементов оставшихся без ячеек. Разделив одно на другое - каким-то боком узнаем, все варианты размещения без повторений О_о Это была удобная продвинутая формула. Но так же есть и более простая. То есть если так же выбрать кто будет сидеть на трех стульях из 14 человек, можно не вспоминать то нечто ужасное с восклицательными знаками, а просто перемножить таким образом: 14 (садим одного на стул)*13(посадили еще одного)*12(и еще одного, 3 стула заняты)=2184 комбинации. Если подставить в формулу выше - получим тот же ответ. И накой же нам тогда верхняя формула с факториалами? А на тот случай, если стульев окажется эдак 80, а человек эдак 120. Не перемножать же все долгой длинной цепочкой =)

Где все это применяется, уже очевидно. Осталось только привести несколько хитрых примеров:

Известно, что бы нейтрализовать студента П. (гыгы) требуется 4 человека, всего кандидатов на эту должность 230 человек. Сколькими комбинациями можно нейтрализовать студента П. Ответ таков: Или 230*229*228*227 = (нейтрализовали) Или 230!/(230-4)! = (нейтрализовали) Тут можно заметить, что более простая формула была более эффективна, так как можно все посчитать на калькуляторе, а не вычислять долго и нудно факториал из достаточно больших чисел. Или так: На балл пришло 74 гусара и 55 дам. Гусары кинулись расхватывать дам, пока была возможность. И кто успел - нашел себе пару. Сколько могло получиться комбинаций с гусаров и дам. Здесь даже и не хочется использовать простой метод, потому как аж 55 раз перемножать число (хотя фига тут с одной стороны). Но с хорошим калькулятором (или таблицей факториалов от 1 до 100) легко и просто высчитываем: 74!/(74-55)!= и смотрим как долго гусары могли бегать за дамами =)

5. Сочетания без повторений

В комбинаторике сочетанием из n по k называется набор k элементов, выбранных из данных n элементов. Наборы, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми, этим сочетания отличаются от размещений.

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

Всякое подмножество X состоящее из m элементов, называется сочетанием из n элементов по m.

Таким образом, количество вариантов при сочетании будет меньше количества размещений.

Сочетания без повторений — комбинаторныесоединения из n элементов по m, составленные из этих элементов и отличающиеся друг от друга только составом.

 

формула для нахождения количества сочетаний без повторений: