Перестановки

СОЕДИНЕНИЯ БЕЗ ПОВТОРЕНИЙ

Сложный выбор объектов

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

Например: Имеется три различных флага. На флагштоке поднимается сигнал, состоящий не менее, чем из 2-х флагов. Сколько различных сигналов можно поднять на флагштоке, если порядок сигналов учитывается?

Решение: Сигнал может состоять либо из 2-х флагов, либо из 3-х. Одновременное выполнение 2-х действий невозможно.

Обозначим через N₂ – число способов составить сигнал из 2-х флагов и через N₃ – из 3-х соответственно. Тогда, общее число способов составить сигнал по правилу суммы равно:

N=N₂+N₃ (правило суммы).

N₂=3´2=6 (правило произведения)

N₃=3´2´1=6 (правило произведения)

N=12.

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

Перестановка из n элементов – упорядоченная последовательность элементов n - элементного множества (кортеж).

Различные перестановки отличаются только порядком элементов в них.

Определим 0!=1

Например:

Пусть A = {1,2,3}.Число различных перестановок равно 3!=6.

Перестановки: {123, 132, 213, 231, 312, 321}.

Например:

1. Число способов стать в очередь за стипендией из 17 человек?

P₁₇=17!

2. Сколькими способами можно расставить на полке 5 книг?

P₅=5!

3. Сколько различных слов можно образовать, переставляя буквы в слове "ковш"?

P₄=4!