Пример 3

Сколькими способами можно упорядочить множество {1, 2,...,2 n } так, чтобы каждое четное число имело четный номер?

Решение. Определение. Множество называется упорядоченным, если каждому элементу этого множества поставлено в соответствие некоторое число (номер элемента) от 1 до n, где n – число элементов множества, так что различным элементам соответствуют различные числа.

Определение. Различные упорядоченные множества, которые отличаются лишь порядком элементов (т.е. могут быть получены из того же самого множества), называются перестановками этого множества.

Число перестановок множества из n элементов P_n равно

P_n = n!

Четные числа можно расставить на местах с четными номерами (таких мест n) n! способами; каждому способ размещения четных чисел на местах с четными номерами соответствует n! способов размещения нечетных чисел на местах с нечетными номерами. Поэтому общее число перестановок указанного типа равно n!× n! = (n!)².

Ответ: (n!)² способов.

Пример 4

Сколько можно составить перестановок из n элементов, в которых данные два элемента не стоят рядом?

Решение. Определим число перестановок, в которых данные два элемента a и b стоят рядом. Могут быть следующие случаи: a стоит на первом месте, a стоит на втором месте,..., a стоит на (n – 1) – месте, а b стоит правее a; число таких случаев равно n – 1. Кроме того, a и b можно поменять местами, и, следовательно, существует 2(n - 1) способов размещения a и b рядом. Каждому из этих способов соответствует (n – 2)! Перестановок других элементов. Следовательно, число перестановок, в которых a и b стоят рядом, равно 2×(n - 1)×(n - 2)! = 2×(n – 1)!. Поэтому искомое число перестановок равно