Как найти число перестановок изменяющих число

Формула числа перестановок

Определение факториала и числа перестановок

Пусть имеется $n$ различных объектов.
Будем переставлять их всеми возможными способами (число и состав объектов остается неизменными, меняется только их порядок). Получившиеся комбинации называются перестановками, а их число равно

$$P_n=n!=1cdot 2cdot 3 cdot … cdot (n-1) cdot n$$

Символ $n!$ называется факториалом и обозначает произведение всех целых чисел от $1$ до $n$. По определению, считают, что $0!=1, 1!=1$. Факториал растет невероятно быстро (недаром он обозначается восклицательным знаком!), например,
$$10!=3628800,$$ а $$50!=30414093201713378043612608166064768844377641568960512000000000000.$$ Как найти факториал? Умножать вручную, использовать функцию ФАКТР() в Excel или, если устанете умножать самостоятельно, используйте калькулятор ниже.

Пример всех перестановок из $n=3$ объектов (различных фигур) — на картинке справа. Согласно формуле ниже, их должно быть ровно $P_3=3!=1cdot 2cdot 3 =6$, так и получается (вам не напоминает картинка табло игральных автоматов?:)).

Общая формула, которая позволяет найти число перестановок из $n$ элементов, имеет вид (она же — формула для факториала числа $n$):

$$P_n=n!=1cdot 2cdot 3 cdot … cdot (n-1) cdot n.$$

Чтобы вычислить число перестановок $P_n$ онлайн, используйте калькулятор ниже.

Видеоролик о перестановках и Excel

Не все понятно? Посмотрите наш видеообзор для формулы перестановок: как использовать Excel для нахождения факториала и числа перестановок, как решать типовые задачи и использовать онлайн-калькулятор.

Расчетный файл из видео можно бесплатно скачать

Смотрите также: Факториал в Excel

Полезные ссылки

• Как решать задачи по комбинаторике?
• Основные формулы комбинаторики
• Примеры решений
• Заказать контрольную

Поиск решенных задач

Решебник по комбинаторике и теории вероятностей:

1. Что такое перестановка?

Перестановка
– упорядоченный
набор (=множество)
n
элементов множества E,
то есть
расположение их в определённом порядке.

Если
множество Е состоит из n-элементов, то
число перестановок (то
есть вариантов расположения n элементов)
равно
n!,
где n
— длина
перестановки.

Перестановки
бывают четными и нечетными.

1. Что такое транспозиция перестановки?

Транспозиция
— перемена местами двух элементов
перестановки.

Теор.1
Все -перестановок
длины  можно
расположить одну за другой таким образом,
что каждая последующая получается из
предыдущей одной транспозицией. Причем
можно начинать такое упорядочивание с
любой перестановки.

Следствие.
Число четных перестановок из  символов
равно числу нечетных, т.е. 
(при любом
 ).

Теор.2
Любая
транспозиция меняет чётность перестановки
на противоположную.

1. В каком случае два числа образуют инверсию в перестановке?

Инверсию (нарушение
порядка) образует
пара элементов в перестановке когда
меньшее из них расположено правее
большего.

Каждой
перестановке
можно сопоставить
число инверсий в ней,
которое подсчитывается так: для каждого
из элементов определяют количество
стоящих правее его меньших чисел, и
полученные результаты складываются.

Перестановка
называется четной,
если число инверсий
в ней четно, и нечетной –
если инверсий в ней нечётное количество.

ПРИМЕР:
Найти число инверсий в перестановке:
(5,3,1,4,2,6).

Рассмотрим
элементы слева направо по очереди,
считая инверсии для каждого.

1)   инверсии
с 1-м элементом (5,3)
(5,1) (5,4) и (5,2)   =>  4
инверсии

2)  
инверсии с 2-м элементом (3,
1) и (3,2)   =>  2
инверсии

 3)   инверсии
с 3-м элементом 1
  =>  0 инверсий, т.к. 4,2 и 6
больше 1

 4)
инверсии с 4-м элементом (4,2)
  =>  1 инверсия

 5)   инверсии
с 5-м элементом 2
  =>  0 инверсий, т.к. 6 больше
2.

Итого
в перестановке  4
+ 2 + 0 + 1 + 0 = 7 инверсий.
Перестановка нечетная.

1. Какая
   перестановка называется четной?

Четная
перестановка —
содержащая четное
количество инверсий.

*Число
инверсий в перестановке
подсчитывается так: для каждого из
элементов определяют количество инверсий
(стоящих правее его меньших чисел), и
полученные результаты складывают.

1. Какая
   перестановка называется нечетной?

Нечетная
перестановка —
содержащая нечетное
количество инверсий.

*Число
инверсий в перестановке
подсчитывается так: для каждого из
элементов определяют количество инверсий
(стоящих правее его меньших чисел), и
полученные результаты складывают

1. Как
   влияет транспозиция на четность
   перестановки?

Любая
транспозиция
(то
есть перемена местами двух любых
элементов)
меняет чётность перестановки на
противоположную.

1. Какая
   подстановка называется четной?

Подстановка называется чётной
если при
всех записях
подстановки  чётности
верхней и нижней строк (перестановок)
– совпадают.

Например,
тождественная подстановка()
будет чётной:

1. Какая
   подстановка называется нечетной?

Подстановка называется нечётной
если при всех записях подстановки  чётности
верхней и нижней строк (т.е. перестановок)
– противоположны.

1. Сформулируйте
   определение определителя матрицы

Определителем
(детерминантом) квадратной матрицы n–го
порядка называют число,
равное алгебраической сумме
всех возможных произведений
элементов этой матрицы, взятых
по одному
из каждой строки и каждого столбца; при
этом знак,
с которым произведение входит в сумму
определяется
по
правилу:

Сомножители
в каждом произведении записываются в
порядке следования строк, тогда номера
столбцов образуют перестановки. Если
перестановка четная, то произведение
берется со знаком «+», а если нечётная
– то со знаком «-».

Произведение
элементов матрицы (слагаемые,
из которых состоит сумма)
называется членом
определителя.

!
Элементы
матрицы при этом могут быть также и
комплексными числами!

НАПРИМЕР,
при n=6 произведение а₂₁а₁₃а₆₂а₃₄а₄₆а₅₅ является
членом определителя, так как в него
входит точно
по одному
элементу из каждой строки и из каждого
столбца.

Подстановка,
составленная из его индексов будет:

В
ней 4 инверсии в верхней строке и 2 в
нижней. Общее число инверсий 6, то есть
подстановка чётная. Значит, этот член
определителя входит в сумму со знаком
«+».

Свойства
определителей:

1. При
   транспонировании матрицы её определитель
   не
   меняется.

2. Если
   поменять местами две строки или два
   столбца определителя, то определитель
   изменит знак, а по абсолютной величине
   не изменится.

3. Пусть C
   = AB где A и B квадратные
   матрицы. Тогда
   det C = detA ∙ detB .

4. Если
   все элементы одной строки (столбца)
   равны нулю, то и определитель равен
   нулю.

5. Определитель
   с двумя одинаковыми строками (столбцами)
   равен 0.

6. Определитель
   с двумя пропорциональными строками
   или столбцами равен 0.

7. Определитель
   треугольной матрицы равен произведению
   диагональных элементов.

8. Определитель
   диагональной матрицы равен произведению
   диагональных элементов.

9. Если
   все элементы строки (столбца) умножить
   на одно и то же число, то определитель
   умножится на это число.

10. Если
    каждый элемент некоторой строки
    (столбца) определителя представлен в
    виде суммы двух слагаемых, то определитель
    равен сумме двух определителей, у
    которых все строки (столбцы) кроме
    данной, прежние, а в данной строке
    (столбце) в первом определителе стоят
    первые, а во втором — вторые слагаемые.

11. Теорема
    Якоби: Если к элементам некоторого
    столбца определителя прибавить
    соответствующие элементы другого
    столбца, умноженные на произвольный
    множитель λ, то величина определителя
    не изменится.

Соседние файлы в папке экз 1 сем

• #
• #

При перестановке букв в слове «толпа» получается P5 = 5! = 120 «слов». Если же переставлять буквы в слове «топот», то получится меньше различных «слов», потому что ни перестановка двух букв «т», ни перестановка двух букв «о» не изменяют «слова»; всего перестановок в данном случае будет . Мы имеем здесь дело с перестановками с повторениями.

Общую задачу сформулируем следующим образом.

Имеется n элементов k различных типов: n1 элементов первого типа, n2 элементов второго типа, …, nk элементов k-го типа, . Сколько можно составить различных перестановок из этих элементов?

Число перестановок c повторениями обозначают . Сколько же их? Если бы все элементы были различны, то число перестановок равнялось бы n!. Но из-за того, что некоторые элементы совпадают, получится меньшее число перестановок. В первой группе элементы (первого типа) можно переставлять друг с другом n1! способами. Но так как все эти элементы одинаковы, то перестановки ничего не меняют. Точно также ничего не меняют n2! перестановок элементов во второй группе и т. д. Перестановки элементов в разных группах можно делать независимо друг от друга. Поэтому (из принципы умножения) элементы можно переставлять друг с другом способами так, что она остаётся неизменной.

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

, (11.1) где .

Замечание. Отметим, что формула числа сочетаний из n элементов по k элементов совпадает с формулой для числа перестановок с повторениями из k элементов одного типа и n–k элементов другого типа:

.

Пример 11.1. Сколькими способами можно нанизать на нить 4 зеленых, 5 синих и 6 красных бус?

Решение. Речь идет об отыскании числа перестановок с повторениями, которые можно сделать из k1=4 элементов первого типа (зеленых бус), k2=5 элементов второго типа (синих бус) и k3=6 элементов третьего типа (красных бус). По формуле (6) получаем

.

Пример 11.2. У мамы было 2 одинаковых яблока, 3 одинаковых груши и 4 одинаковых апельсина. Каждый день она давала ребенку по одному фрукту. Сколькими способами она могла это сделать?

Решение. Данная задача есть задача на отыскание числа перестановок с повторениями:

.

Пример 11.3. Сколько различных браслетов можно сделать из пять одинаковых изумрудов, шести одинаковых рубинов и семи одинаковых сапфиров (в браслет входят все 18 камней)?

Решение. Камни можно переставлять P(5, 6, 7) способами. При циклических перестановках и при зеркальном отражении браслет остается неизменным. В результате получаем

.

Пример 11.4. Сколько способами можно переставлять буквы слова «огород» так, чтобы: а) три буквы «о» не стояли рядом? б) если запрещается, чтобы две буквы «о» стояли рядом?

Решение. а) Буквы данного слова можно переставлять P(3,1,1,1) способами. Если три буквы «о» стоят рядом, то их можно считать за одну букву. Тогда буквы можно переставлять 4! Способами. Вычитая этот результат из предыдущего, получим

.

Б) Сначала расставляем согласные (3! способов). Для трёх букв «о» остаётся 4 места, и их можно расставить способами. Всего получаем способа.

Упражнения

11.1. Сколькими способами можно расположить в ряд две зелёные и четыре красные лампочки?

Ответ: .

11.2. Десять человек надо разбить на три группы соответственно по 2, 3, 5 человек в группе. Сколькими способами можно это сделать?

Ответ: .

11.3. Сколькими способами можно упаковать девять различных книг в трёх бандеролях соответственно по два три, четыре книги в каждой бандероли?

Ответ: .

11.4. Группу командировочных из восьми человек требуется расселить в три комнаты, из которых две трёхместные и одна двухместная. Сколько вариантов расселения возможно?

Ответ: .

11.5. Сколько различных слов можно получить, переставляя буквы в следующих исходных словах: а) академия, б) электротехника, в) молокопродукт?

Ответ: .

11.6. Сколькими способами можно разделить 12 предметов между тремя студентами, чтобы каждому досталось ровно по четыре предмета?

Ответ: .

11.7. Для премий на математической олимпиаде выделено 3 экземпляра одной книги, 4 экземпляра другой и 8 экземпляров третьей. Сколькими способами могут быть распределены эти премии между 30 участниками олимпиады, если каждому вручается не более одной книги?

Ответ: .

11.8. Сколькими способами можно переставить буквы слова «обороноспособность» так, чтобы две буквы «о» не шли подряд?

Ответ: .

11.9. Сколькими способами можно переставить буквы слова «каракули» так, чтобы никакие две гласные не стояли рядом?

Ответ: Гласные можно переставлять P(2,1,1)=12 способами, Аналогично, P(2,1,1)=12 способами можно расставить согласные буквы. Если согласные уже расставлены, то для гласных останется 5 мест. Поэтому места для них можно выбрать способами. Всего способов.