Amn = N*(N-1)*(N-2)*…*(N-M+1), или Amn =N!/(N-M)!

↑

▷ Содержание

Стр 1 из 2Следующая ⇒

Комбинаторные алгоритмы

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

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

Классической задачей комбинаторики является задача о числе перестановок – сколькими способами можно переставить N различных предметов, расположенных на N различных местах.

Перестановкой из N элементов назовем упорядоченный набор из N натуральных чисел, принадлежащих отрезку от 1 до N.

Пример. Пусть N равно 3. Перечислим все перестановки из 3 элементов: (1, 2, 3), (1, 3, 2), (2, 1, 3 ), (2, 3, 1), (3, 1, 2), (3, 2, 1). Количество перестановок из N элементов равно

PN =1 *2*3*…*N=N!

(есть N способов для выбора элемента на первое место, (N-1) способ для выбора элемента на второе место и т.д.)

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

Задача формулируется следующим образом: сколькими способами можно выбрать и разместить по M различным местам M из N различных предметов.

Размещением без повторений из N элементов по M называется упорядоченный набор из M различных чисел, принадлежащих отрезку от 1 до N. Два набора считаются различными, если они отличаются составом и порядком элементов.

Пример. Пусть N = 4, М = 2. Перечислим все размещения без повторений: (1, 2), (2, 1), (1, 3), (3, 1), (1, 4), (4, 1), (2, 3), (3, 2), (2, 4), (4, 2), (3, 4), (4, 3). Количество размещений A^m_n вычисляется по формуле:

Amn = N*(N-1)*(N-2)*…*(N-M+1), или Amn =N!/(N-M)!

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

Даны предметы, относящиеся к N различным типам. Из них составляются всевозможные наборы по k элементов в каждом. При этом в наборы могут входить и предметы одного типа. Два набора считаются различными, если они отличаются или типом входящих в них предметов, или порядком этих предметов.

Пример. Пусть N = 3, k = 2 (как и ранее, рассматриваем натуральные числа). Размещения с повторениями: (1, 1), (1, 2), (1,3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3). Число таких наборов

Познавательные статьи:



Психологические особенности спортивного соревнования

Приготовление дезинфицирующих растворов различной концентрации

Занятость населения и рынок труда

Социальный статус семьи и её типология