ЭЛЕМЕНТЫ КОМБИНАТОРИКИ

Предварительные сведения

Теорема 37.1. Пары. Из т элементов а, аъ ..., ат и п элементов b/, Ьъ ..., Ь„ можно образовать т хп пар {аи 6/}, содержащих по одному элементу из каждой группы.

Доказательство. Составим из этих пар прямоугольную таблицу (наподобие таблицы умножения) с т строками и п столбцами так, чтобы пара {a,, bj) стояла на пересечении i-Pi строки и /-го столбца. Тогда каждая пара появляется один и только один раз, и утверждение доказано.

Пример 1. Карты для бриджа. В качестве множеств элементов берутся 4 масти и 13 значений соответственно. Каждая карта определяется своей мастью и значением, так что существует 4 х 13 = 52 различных карт.

Теорема 37.2. Комбинации. Дано п элементов а,..., ап, П2 элементов Ь, ..., Ь„2,пг элементов х, ..., хпг. Число возможных комбинаций ah bj, ..., Xk}, содержащих по одному элементу каждого типа, равно п П2-... пг.

Доказательство. Если г - 2, то утверждение сводится к предыдущему. Если г = 3, то рассматриваем пару {ait bj) как элемент нового типа. Существует щ хт таких пар и щ элементов Q-. Каждая тройка {abj, «Д, в свою очередь, является парой, состоящей из {а„ bj} и элемента q. Отсюда число троек равно п х т х щ. Далее по индукции.

Замечание. Многие применения основаны на следующей переформулировке последней теоремы: при г последовательных выборах (решениях) с ровно Пк возможными исходами на к-м шаге можно получить п ХП2 х... хп, различных результатов.

Пример 2. Классификация по многим признакам. Предположим, что люди классифицируются по полу, семейному положению и профессии. Различные категории имеют роль элементов. Если имеется 17 профессий, то всего будет 2-217 - 68 классов.

Пример 3. Размещение г шаров по п ящикам. Для г шаров имеем г независимых выборов, поэтому г шаров можно разместить в п ящиках п ? хг различными способами. Рассматривая грани игральной кости как «ящики», получим, что при бросании г раз игральной кости имеется 6г возможных исходов. Если нас интересует появление единицы, то в 5г исходов единица не появилась. Тогда вероятность того, что при г бросаниях единица не появилась ни разу, равна (5/6)г. Вероятность появления 1 при г бросаниях равна 1 - (5/6)' (при шести бросаниях вероятность появления единицы равна 1 - (5/6) - 0,665).

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >