Дискретно-непрерывная математика (стр. 34 )

Например, из трех элементов а, b, с можно составить такие сочетания по два с повторениями:

аа, асс, be, ab, bb, cc.

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

fnm = С т-1п+ т-1 = Сnт+ п—1

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

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

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

Пример. Кости домино можно рассматривать как сочетания с повторениями по два из семы цифр: 0, 1,2, 3, 4, 5, 6. Число всех таких сочетаний равно

5.7. Прямое произведение множеств

Предположим, что задано множества А1, ..., Аk. Множество всех элементов вида (а1, ..., аk), где а1 А1, а2 А2, ..., ak Ak, называется прямым произведением множеств А1, ..., Ak и обозначается

А1× А2×… × Ak

Пример 1 . Если А = {а, b}, В ={с, d, e}, то

А×В = {(а, с), (a, d), (а, е), (b, с), (b, d), (b, e)}.

Пример 2. Пусть имеется множество А из п элементов. Возьмем из А какой-нибудь элемент, обозначим его через а1 и вернем снова в множество А. Далее возьмем из А некоторый элемент, обозначим его через а2 (в частности, может случиться, что попадеться снова элемент а1). Проделав эту операцию k раз, получим набор (а1, ..., аk), который называют k-словом, составленным из элементов множества А. Множество всех k-слов, составленных из элементов А, является прямым произведением А×А×…...×А и кратко обозначается Аk. Например, если А — множество из двух букв {а, b}, то множество А2 всех слов имеет вид {аа, ab, bа, bb}. С k-словами мы часто сталкиваемся в различных ситуациях. Все десятичные записи чисел являются словами, составленными из цифр 0, ..., 9; обычные слова - это слова, состоящие, например, из букв русского алфавита; фразы - это «слова», что состоящие из русских слов, и т. д.

Естественно задать вопросы: сколько различных k-слов можно составить из элементов множества А, имеющего п элементов?

Следующая теорема дает ответ на этот и на более общий вопрос: сколько элементов содержит прямое произведение А1× А2×… × Ak?

Теорема. N ( А1× А1×… × Ak) =N (А1).. .N(Ak).

Доказательство. Покажем сначала, что

N (А1 × А2) = N (А1) • N (А2).

Обозначим через подмножество множества А1 × А2, которое состоит из элементов вида (с1, а2), где с1 — фиксированный элемент из А1, а а2 произвольный элемент из А2. Тогда N ( ) = N (А2), так как эквивалентно А2 (элементу (c1, a2) соответствует a2). Если а1, b1,..,f1 — все элементы множества А1,то

Множества , , ,.., , попарно не имеют общих элементов. Поэтому

Примем теперь во внимание, что множества

А1 × (А2 × … × Ak) и A1×А2 … × Аk

эквивалентны: элементу [а1 (а2, . . ., ak)] соответствует элемент (а1, а2.....ak). Поэтому

что и требовалось доказать.

Пример 3. Число k-слов, составленных из элементов множества А, равно

N (А k) = [N (А)] k.

Пример 4. Дадим ответ на вопрос, сколькими способами можно распределить k разных предметов сред п лиц?

Пусть А — множество лиц, среди которых распределяют предметы. Перенумеруем предметы и поставим в соответствие каждому способу распределения символ (а1, а2.....ak), где а1 — лицо, которое получило первый предмет, ..., аk — лицо, которое получило k-й предмет. Очевидно, (а1, а2.....ak) - k-слово, составленное из элементов множества А. Установленное соотношение является взаимно однозначным, и поэтому число способов распределения k предметов сред п лиц равно числу k-слов, которые можно составить из элементов множества А, т. е., ровно пk.

5.8. Бином Ньютона и полиномиальная формула

5.8.1. Бином Ньютона.

Известно, что

(а + b)2= а2 + 2ab + b2,

(а + b)3 = а3 + 3a2b + 3ab2 + b3.

Как раскрыть скобки при вычислении выражения (а + b)п? Ответ на этот вопрос дает следующая теорема

Теорема. Имеет место равенство

(5.9)

где

Эту теорему иногда называют биномиальной теоремой, а числа Ckn — биномиальными коэффициентами. Равенство (5.9) часто называют биномом Ньютона, хотя это название исторически не является справедливым, так как формулу для (а + b)п знали еще среднеазиатские математики Омар Хайям (1048— 1131), Гийас ад-Дин Джемшид ал-Каши (умер ок. 1430). В Европе до Ньютона ее знал Паскаль, (1623-1662). Заслуга Ньютона в том, что он обобщил формулу (5.9) для нецелого показателя п. Вид формулы бинома в этом случае рассмотрен в п. 5.9. Напомним, что Ckn есть число k-элементных подмножеств множества из п элементов. Формулу (5.9) можно записать в виде

Доказательство. Перемножим последовательно (а + b) п раз. Тогда получим сумму 2п слагаемых вида d1d2 ... dn, где dі (i=1,...,n) равно либо а, либо b. Разобьем все слагаемые на п+1 группу В0, B1, ..., Вп, относя к Bk все те произведения, в которых b встречается множителем k раз, а а - (п — k) раз. Число произведений в Bk равно, очевидно, Ckn (таким числом способов среди п множителей d1, ..., dn можно выбрать k множителей, которые будут равны b), а каждое слагаемое в Bk равно an-kbk. Поэтому

Теорема доказана.

Напомним следующее важное свойство биномиальных коэффициентов:

(5.10)

Оно было установлено в п. 4 3.

Равенство (5.10) показывает, что биномиальные коэффициенты можно последовательно выписывать в виде треугольной таблицы, которая называется треугольником Паскаля:

В п-й строке треугольника Паскаля стоят коэффициенты разложения (а + b)п, причем каждый коэффициент, кроме крайних двух, которые равны 1, равен сумме соответствующих коэффициентов из предыдущей строки.

5.8.2. Полиномиальная теорема.

Рассмотрим вопрос о том, как раскрывать скобки при вычислении выражения вида

(а1 + а2+ ... + ak)n

Полиномиальная теорема. Выражение

(а1 + а2+ ... + ak)n

равно сумме всех возможных слагаемых вида

где

r1 + r2+ ... +rk = п,

т. е.

(5.11)

Доказательство. Перемножим последовательно а1 + а2+ ... + ak n раз. Тогда получим kп слагаемых вида d1d2 ... dn, где каждый множитель dі равен или а1, или а2, ..., или ап. Обозначим через В( r1... rk) совокупность всех тех слагаемых, где а1 встречается множителем r1 раз, а2 — r2 раз, ..., ak — rk pаз.