Комбинаторика
  • Регистрация
1 1 1 1 1 1 1 1 1 1 Рейтинг 0.00 (0 Голоса)

Поставим такой вопрос: сколькими способами можно разложить множество A={a1,a2,…,an}на m подмножеств

,

Таких, что

?

Описанные разбиения можно получить так: возьмем произвольно k1-элементное подмножество B1ÌA (выбор можно осуществить способами), из оставшихся n-k1 элементов выберем k2 - элементное подмножество B2ÌA\B1 (выбор можно осуществить способами) и т. д. Тогда по правилу умножения общее число способов равно:

Полученные числа, равные числу перестановок с повторениями

, (2.9)

Называются Полиномиальными коэффициентами, так как они связаны с полиномиальной формулой:

(2.10)

Перемножив последовательно A1+…+aM n раз, получим слагаемых вида , где каждый множитель равен , или ,…или . Пусть B(r1,r2,…,rk) - совокупность всех тех слагаемых, где A1 встречается R1 раз, A2 - r2 раз,…,Ak - rk раз, причем R1+r2+…+rk=n. Число таких слагаемых равно числу способов представления множества из n элементов k подмножествами, т. е. используя (2.9)

B(r1,r2,…,rk)=Cn(r1,r2,…,rk),

А, следовательно, справедливо соотношение (2.10). При k=2, очевидно, получим форму бинома Ньютона.

Еще одна комбинаторная интерпретация коэффициентов (2.9) может быть дана, если для множества n букв, из которых k1 – букв a1, k2 – букв a2,…,km – букв am, k1+k2+…+km=n. Определим число различных слов длины n. Перенумеровав места, на которых стоят буквы номерами {1,2,…,n}, мы каждое слово определим множествами B1(номера мест, где стоит буква a1),B2(номера мест, где стоит a2),…,Bm(номера мест, где стоит буква am). Таким образом, число различных слов равно числу способов, которыми можно представить множество A={1,2,…,n} в виде т. е. .

Если рассмотреть множество элементов A={a1,…,am}, то можно поставить вопрос о вычислении числа групп (сочетаний) Bk={b1,…,bn}, где bi, может быть равно одному из aj, .

Например, если A={} и n=2, то имеем сочетания с повторениями:

(2.11)

Число различных сочетаний из m элементов по n с повторениями равно

. (2.12)

Для доказательства этой формулы укажем, сколько элементов из A входит в сочетание. Поставим в соответствие каждому сочетанию последовательность нулей и единиц, составленную по правилу: напишем подряд столько единиц, сколько элементов входит в сочетание, далее поставим нуль и после этого напишем столько единиц, сколько элементов в сочетании, и т. д. Например, сочетаниям (2.11) соответствуют последовательности:

1100, 1010, 1001, 0110, 0101, 0011.

Таким образом, каждому сочетанию из m по n однозначно соответствует последовательность n единиц и m-1 нулей. Поэтому число сочетаний из m по n с повторениями равно

.

Задача 2.7. Найти число возможных размещений n одинаковых элементов в m урнах.

Решение. Рассмотрим одно из возможных размещений элементов в урнах следующим способом (рис. 2.2): поместим в урну столько единиц, сколько там элементов, расположив между урнами по нулю. Тогда «слово», составленное из единиц в урнах и нулей между ними, будет содержать m+n-1 символ, из которых n единиц и (m-1) нулей. Следовательно, общее число различных размещений равно


.

Рис.2.2. Распределение элементов по урнам так, чтобы

Задача 2.8. Найти число распределений m+n+s различных элементов на 3 группы по m, n и s элементам каждая.

Решение. Очевидно, что требуется разбить исходное множество A={a1,…,am+n+s} на три подмножества ½A1½=m,½A2½=n,½A3½=s. Используя формулу (2.9), можно записать:

Задача 2.9. Сколько целых неотрицательных корней имеет уравнение: x1+x2+…+xm=n?

Решение. Очевидно, что каждое , может принимать значения 0,1,…,n и их сумма должна быть равна n. Тогда задача состоит в отыскании числа сочетаний из m элементов (по числу переменных) по n (общее число элементов), т. е. по формуле (2,12):

.

Задача 2.10. Сколько целых положительных решений имеет неравенство (m£n)

Решение. Если произвести замену с использованием тривиального решения xi=1, i=1,m, xi=1+yi, то исходное неравенство приобретает вид y1+y2+…+ym£n-m. Тогда для каждого k=1,2,…,n-m число решений уравнения y1+y2+…+ym=k равно в соответствии с решениями задачи 9 равно , а общее число решений исходного неравенства равно:

Рассмотрим теперь выборки из n по r, в которых элементы упорядочены и допускаются повторения элементов. Это так называемые (n, r)-размещения с повторениями. Так, для множества X={1,2,3,} такими (3,2)-размещениями будут:

<1,1>,<2,2>,<3,3>,<1,2>,<2,1>,<1,3>,<3,1>,<2,3>,<3,2>.

Покажем, что число таких размещений равно:

. (2.13)

Действительно, при выборе первого элемента в выборке у нас имеется n возможностей, при выборе второго тоже – n и т. д., всего r раз. Таким образом, по правилу умножения получим:

Добавить комментарий


Защитный код
Обновить