Перестановки, размещения и сочетания. Формулы
жүктеу/скачать 21,79 Kb.
|
- Бұл бет үшін навигация:
- Размещения с повторениями из n элементов по
- Перестановки без повторений из n элементов
| Пример №1
Алфавит состоит из множества символов E={+,∗,0,1,f}. Определим количество таких трёхсимвольных слов в этом алфавите, которые не содержат повторяющихся букв. Решение Под трёхсимвольными словами будем понимать выражения вида "+*0" или "0f1". В множестве E пять элементов, поэтому буквы трехсимвольных слов образуют (5,3)-выборки. Первый вопрос: эти выборки упорядочены или нет? Слова, которые отличаются лишь порядком букв, полагаются различными, поэтому порядок элементов в выборке важен. Значит, выборка является упорядоченной. Второй вопрос: допускаются повторения или нет? Ответ на этот вопрос даёт условие: слова не должны содержать повторяющихся букв. Подводим итоги: буквы каждого слова, удовлетворяющего условию задачи, образуют упорядоченную (5,3)-выборку без повторений. Иными словами, буквы каждого слова образуют размещение без повторений из 5 элементов по 3. Вот примеры таких размещений: (+,∗,f),(∗,+,f),(1,+,0) Нас же интересует общее количество этих размещений. Согласно формуле (1) количество размещений без повторений из 5 элементов по 3 будет таким: A35=5!(5−3)!=5!2!=60. Т.е. можно составить 60 трёхсимвольных слов, буквы которых не будут повторяться. Ответ: 60. Размещения с повторениями из n элементов по k Размещение с повторениями из n элементов по k – упорядоченная (n,k)-выборка с повторениями. Количество размещений с повторениями из n элементов по k определяется следующей формулой: ¯Akn=nk(2) Пример №2 Сколько пятизначных чисел можно составить из множества цифр {5,7,2}? Решение Из данного набора цифр можно составить пятизначные числа 55555, 75222 и так далее. Цифры каждого такого числа образуют (3,5)-выборку: (5,5,5,5,5), (7,5,2,2,2). Зададимся вопросом: что это за выборки? Во-первых, цифры в числах могут повторяться, поэтому мы имеем дело с выборками с повторениями. Во-вторых, порядок расположения цифр в числе важен. Например, 27755 и 77255 – разные числа. Следовательно, мы имеем дело с упорядоченными (3,5)-выборками с повторениями. Общее количество таких выборок (т.е. общее количество искомых пятизначных чисел) найдём с помощью формулы (2): ¯A53=35=243. Следовательно, из заданных цифр можно составить 243 пятизначных числа. Ответ: 243. Перестановки без повторений из n элементов Перестановка без повторений из n элементов – упорядоченная (n,n)-выборка без повторений. По сути, перестановка без повторений есть частный случай размещения без повторений, когда объём выборки равен мощности исходного множества. Количество перестановок без повторений из n элементов определяется следующей формулой: Pn=n!(3) Эту формулу, кстати, легко получить, если учесть, что Pn=Ann. Тогда получим: Pn=Ann=n!(n−n)!=n!0!=n!1=n! жүктеу/скачать 21,79 Kb. Достарыңызбен бөлісу:
|