Размещение, перестановки и сочетания с повторениями.

Определение: Пусть нам заданы два параметра n и k, взятые из множества N₀. Размещением с повторениями из n элементов множества В, В={b₁, b₂,…, b_n} по k элементам будем называть всякую последовательность длины k, составленную из элементов этого множества (среди элементов возможны повторения).

Пример: Пусть нам дано множество С={а, b, с}. Выпишем все размещения с повторениями из 3 элементов по 2 элемента.

={(а,а), (b,b), (с,с), (a,b), (a,c), (b,c), (b,a), (c,a), (c,b)}.

=9

Теоремаn, kÎN₀, В={b₁, b₂,…, b_n}. Число размещений из n элементов по k элементам может быть рассчитано по формуле:

.

Определение: Пусть nÎN₀, В={b₁, b₂,…, b_n}. Перестановкой с повторениями из элементов множества В называется всякое размещение с повторениями длины n.

Пусть k₁, k₂,…, k_m – целые неотрицательные числа, такие, что их сумма k₁+k₂+…+k_m=n. Число перестановок с повторениями в которых m различных элементов множества В и k_i элементов i-го вида ( ) будем обозначать Р_n(k₁, k₂, …,k_m) и называть полиномиальными коэффициентами.

Пример: Дано множество А, содержащее элементы А={а, b, с, d}. Выпишем все перестановки с повторениями, в которых содержится 1 элемент а и 3 элемента b.

k₁=1

k₂=3 n= k₁+k₂=4 (a,b,b,b), (b,a,b,b) (b,b,a,b) (b,b,b,a)

P₄(1,3)

ТеоремаПусть nÎN₀, В={b₁, b₂,…, b_n}, k_i – целое неотрицательное число, такие, что ,тогдачисло перестановок с повторениями можно рассчитать по формуле: Р_n(k₁, k₂, …,k_m)=

Задача: Для запирания сейфов и автоматических камер хранения применяют секретные замки, которые открываются лишь тогда, когда набрано некоторое тайное слово. Это слово набирают с помощью одного или нескольких дисков на которых помещены буквы или цифры. Пусть на диск помещены 12 букв, а секретное слово состоит из 5 букв. Сколько неудачных попыток может быть сделано человеком не знающим секретное слово.

l_неуд=12⁵-1=248831

Задача: Сколько различных слов можно составить переставляя буквы слова «математика»

n=10

A k₁=3

М k₂=2 Р₁₀(3,2,2,1,1,1)= =151200

Т k₃=2

Определение: Пусть параметр k принадлежит множеству N₀, параметр n принадлежит N, сочетаниемиз n элементов по k элементамс повторениями называется совокупность, содержащая k элементов, причем каждый элемент принадлежит к одному из n типов.

Пусть дано множество, состоящее из трех букв В={а, b, с}, составим все сочетания с повторениями из трех заданных букв по 2

n=3 k=2 {а, a}, {b, b}, {c, с}, {а, b}, {а, с},{b, с}

1100 0110 0011 1010 1001 0101

ТеоремаПусть kÎN₀, nÎN, число сочетаний с повторениями: (*)

выбирая некоторый элемет из n каждый раз дополняем множество точно таким же, всего таких дополнений k-1. фактически, выбор делаем из n+k-1 элемента.

Задача: Сколько было бы костей домино, если на костях могут присутствовать а) 11 значков, б)7 значков