(0 голоса, среднее 0 из 5)

Комбинаторика. Размещения

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

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

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

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

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

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

Другими словами .  Выведем формулу для числа Первый элемент выборки можно выбрать 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

Вычислить 

Решение

Ответ. 12.

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

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

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

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

Пример 2

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

Решение

Последняя цифра искомого числа должна быть 0 или 5. В первом случае остальные шесть цифр можно выбирать из множества {1, 2, 3, ..., 9}, и число вариантов равно  Пусть теперь число оканчивается цифрой 5. Тогда в качестве первой цифры можно взять любую из цифр 1, 2, 3, 4, 6, 7, 8, 9. Цифры со второй по шестую можно выбрать  способами. Значит, всего таких семизначных цифр существует

Ответ. 114240.

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

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

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

Пример 3

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

Решение По формуле , где n = 26, k = 5, получаем:

Пример 4

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

Решение

При расстановке монет в альбоме важен порядок следования монет – значит, речь идет о количестве перестановок. Всего монет 9, и общее количество перестановок равно 9!. Однако если мы переставим местами две одинаковых копейки, то набор от этого не изменится. Значит, ответ нужно поделить на 2. Точно так же не изменится набор и в том случае, если переставить друг с другом пенсы или лиры. Количество перестановок 3 пенсов равно 3!, лир – также 3!. Десятицентовик у Васи всего один, и количество перестановок для него равно 1!, но для завершённости формулы учтём и его. Итак, количество способов, которыми можно расставить монеты в альбоме, равно

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

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



Похожие статьи:
Следующие статьи:
Предыдущие статьи:

Комментарии
Добавить новый Поиск
Оставить комментарий
Имя:
Email:
 
Тема:
UBB-Код:
[b] [i] [u] [url] [quote] [code] [img] 
 
 
:angry::0:confused::cheer:B):evil::silly::dry::lol::kiss::D:pinch:
:(:shock::X:side::):P:unsure::woohoo::huh::whistle:;):s
:!::?::idea::arrow:
 
Пожалуйста, введите проверочный код, который Вы видите на картинке.

3.26 Copyright (C) 2008 Compojoom.com / Copyright (C) 2007 Alain Georgette / Copyright (C) 2006 Frantisek Hliva. All rights reserved."

Поиск по сайту

Голосование

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

Сейчас в чате



Нет пользователей online



Rambler's Top100