Глава 4. Комбинаторика

4.2.

Назад Вперед
Назад Вперед

4.2.2.

Пусть задано некоторое конечное множество из n различных элементов. Пусть из числа его элементов выбраны k различных штук (k ≤ n), тогда говорят, что произведена выборка объёма k. Если важен порядок, в котором произведена выборка элементов, то говорят об упорядоченной выборке, если порядок не важен, то о неупорядоченной.

 

Упорядоченная выборка объёма k из множества, состоящего из n элементов, (k ≤ n) называется размещением из n элементов по k. Количество размещений обозначается

Символ читается «а из эн по ка».

Модель 4.3. Размещения
 

Размещение из n элементов по n называется перестановкой из n элементов. Количество перестановок обозначается Pn.

Модель 4.2. Перестановки

Другими словами, Выведем формулу для числа Первый элемент выборки можно выбрать n различными способами, второй – n − 1 способом, ..., k-й − n − (k − 1) способом. Значит, k элементов можно выбрать
способами.
В частности, Pn = n · (n – 1) · ... · 2 · 1.

Введём следующее обозначение: n! = n · (n – 1) · ... · 2 · 1. Символ «!» называется знаком факториала или просто факториалом. По определению считается, что 0! = 1. С помощью факториала можно компактно записать выражение для и

Количество размещений из n элементов по k:

В частности, количество перестановок из n элементов:
Pn = n!.

Пример 1

Вычислить

Показать решение

Вычислять факториалы от больших чисел не очень удобно. Для больших n можно использовать оценочную формулу, предложенную шотландским математиком Джеймсом Стирлингом.

При больших n выражение n! можно приближенно вычислить по формуле:

Буквой e здесь, как обычно, обозначено основание натурального логарифма e = 2,71828… При n = 10 погрешность при вычислении факториала с помощью этой формулы составляет менее 1 %, а при n = 100 – меньше 1/10 процента.

 

Вернемся к формуле Из неё следует, что В подобных ситуациях полагают, что 0! = 1, и это логично: единственный способ переставить 0 объектов – это ничего не делать.

Пример 2

Сколько семизначных чисел, кратных 5, можно составить из цифр при условии, что цифры в записи числа не повторяются?

Показать решение

В предыдущем примере цифры в числе не должны были повторяться. Не менее часто, однако, встречаются задачи, в которых элементы в выборке могут повторяться. Подобные выборки называются размещениями с повторениями и обозначаются

Найдем число На первое место можно выбрать элемент n способами, на второе – также n способами, и так далее. Если количество мест равно k, то по правилу количество различных выборок равно


 

Количество размещений с повторениями обозначается символом и вычисляется по формуле

Пример 3

Сколько различных пятибуквенных «слов» можно составить из 26 букв латинского алфавита?

Показать решение

Пример 4

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

1
Показать решение

Можно сформулировать общее правило.

 

Количество перестановок из n элементов, среди которых имеется n1 одинаковых элементов первого сорта, n2 одинаковых элементов второго сорта, nk одинаковых элементов k-го сорта, называется количеством перестановок с повторениями, обозначается символом и вычисляется по формуле


Назад Вперед
Наверх

Включить/Выключить фоновую музыкуВключить/Выключить звуки событий

 

Смотрите также: Математика, Английский язык, Химия, Биология, Физика, География, Астрономия.
А также: библиотека ЭОРов и образовательный онлайн-сервис с тысячами интерактивных работ "Облако знаний".