Перестановки, размещения и сочетания. Формулы
жүктеу/скачать 21,79 Kb.
|
- Бұл бет үшін навигация:
- Перестановки с повторениями
- Сочетания без повторений из n элементов по
| Пример №3
В морозилке лежат пять порций мороженого от различных фирм. Сколькими способами можно выбрать порядок их съедения? Решение Пусть первому мороженому соответствует цифра 1, второму – цифра 2 и так далее. Мы получим множество U={1,2,3,4,5}, которое будет представлять содержимое морозилки. Порядок съедения может быть таким: (2,1,3,5,4) или таким: (5,4,3,1,2). Каждый подобный набор есть (5,5)-выборка. Она будет упорядоченной и без повторений. Иными словами, каждая такая выборка есть перестановка из 5 элементов исходного множества. Согласно формуле (3) общее количество этих перестановок таково: P5=5!=120. Следовательно, существует 120 порядков выбора очередности съедения. Ответ: 120. Перестановки с повторениями Перестановка с повторениями – упорядоченная (n,k)-выборка с повторениями, в которой элемент a1 повторяется k1 раз, a2 повторяется k2 раза так далее, до последнего элемента ar, который повторяется kr раз. При этом k1+k2+…+kr=k. Общее количество перестановок с повторениями определяется формулой: Pk(k1,k2,…,kr)=k!k1!⋅k2!⋅…⋅kr!(4) Пример №4 Слова составляются на основе алфавита U={a,b,d}. Сколько различных слов из семи символов может быть составлено, если в этих словах буква "a" должна повторяться 2 раза; буква "b" – 1 раз, а буква "d" – 4 раза? Решение Вот примеры искомых слов: "aabdddd", "daddabd" и так далее. Буквы каждого слова образуют (3,7)-выборку с повторениями: (a,a,b,d,d,d,d), (d,a,d,d,a,b,d) и т.д. Каждая такая выборка состоит из двух элементов "a", одного элемента "b" и четырёх элементов "d". Иными словами, k1=2, k2=1, k3=4. Общее количество повторений всех символов, естественно, равно объёму выборки, т.е. k=k1+k2+k3=7. Подставляя эти данные в формулу (4), будем иметь: P7(2,1,4)=7!2!⋅1!⋅4!=105. Следовательно, общее количество искомых слов равно 105. Ответ: 105. Сочетания без повторений из n элементов по k Сочетание без повторений из n элементов по k – неупорядоченная (n,k)-выборка без повторений. Общее количество сочетаний без повторений из n элементов по k определяется формулой: Ckn=n!(n−k)!⋅k!(5) жүктеу/скачать 21,79 Kb. Достарыңызбен бөлісу:
|