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

Итак, число кратчайших путей из точки (0; 0) в точку (т; п) равно Сmт+п=Сmт+п.

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

(5.7)

Легко убедиться в справедливости равенства (5.7), используя формулу

Советуем читателю сделать это самостоятельно. Приведем еще два других доказательства.

Доказательство 1. Рассмотрим некоторый элемент а множества А, состоящего из п элементов, и все k-элементные подмножества множества А (число таких подмножеств равно Сkп). Все k-элементные подмножества множества А разделим на 2 группы: подмножества, в состав которых входит а, и подмножества, в состав которых а не входит. Число подмножеств в первой группе равно Сk-1п-1, так как каждое такое подмножество получается присоединением к а некоторого (k —1)-элементного подмножества множества А. Число подмножеств во второй группе равно Сkп-1, так как каждое такое подмножество есть k -элементное подмножество множества А — {а}. Следовательно,

Доказательство 2. Число кратчайших путей из точки О(0; 0) в точку A(k; n — k) равно Ckk+(n-k) = Сkп (рис. 5.4).

Рис. 5.4

Все такие пути можно разделить на 2 группы: пути, которые проходят через точку A1(k—1; n—k) (число их равно и пути, которые проходят через точку A2(k; n — k —1) (число их равно

Следовательно,

3 а д а ч а 4. Доказать тождество

(4.8)

Решение. Число кратчайших путей из точки О (0; 0) в точку А(п;п) равно Сп2п. Каждый тякой путь проходит через одну и только одну из точек Ak(k; n — k), лежащих на диагонали BD (рис. 5.5).

Рис. 5.5

Число путей из точки О в точку Аk равно Ckk+(n-k) = Сkп, а из точки Аk в точку А равно Ckп-k+k = Сkп, поэтому число путей из О в А, проходящих через Аk, равно Сkп·Сkп=(Сkп)2 (правило умножения). Прибавив количество путей, которые проходят через кождую из точек

Аk (k = 0, 1, ..., п), получим общее количество путей из О в А, т. е. Сп2п. Это соображение и доказывает равенство (5.8).

5.3.2. Количество подмножеств данного множества.

Выясним теперь, сколько всего подмножеств имеет множество А, состоящее из п элементов (пустое множество также является подмножеством А).

Теорема. Число всех подмножеств множества из п элементов равно 2п.

Приведем два различных доказательства.

Доказательство 1. Пусть Ма — множество всех подмножеств множества А, которые содержат элемент а. Очевидно, что каждое такое подмножество полностью определено, если указаны все его остальные (кроме а) элементы. Поэтому таких подмножеств будет столько, сколько будет подмножеств в множестве А'= А — {а}, которое содержит все элементы А, кроме а. Это множество имеет п — 1 элементов. Поэтому, если qn — число подмножеств множества из п элементов, то N(Ma) = qn-1.

Если — множество всех подмножеств множества А, не содержащих а, то N ( ) также будет равно qn-1. Поскольку М(А) = Ма+ , то N(M(A)) =2qn-1. Отсюда находим qn =2qn-1. Таким образом, qn = 2qn-1 — 22 qn-2= ... = 2п-1q1. Множество, которое состоит из 1 элемента, имеет 2 подмножества (все множество и пустое множество). Поэтому q1 = 2. Следовательно, qn = 2г.

Доказательство 2. Перенумеруем элементы множества А и для каждого подмножества множества А построим последовательность длиной п из нулей и единиц по следующему правилу: на k-м месте пишем 1, если элемент с номером k входит в подмножество, и 0, если элемент с номером k не входит в подмножество. Итак, каждому подмножеству соответствует своя последовательность нулей и единиц. Например, пустому множеству соответствует последовательность из одних нулей. Число всех возможных последовательностей длины п, составленных из нулей и единиц, равно, согласно правилу умножения, . Следовательно, и число всех подмножеств множества А равно 2п.

Как было указано выше, удобно считать 0!=1. При этом предположении формула

остается в силе и при k = п и при k = 0.

Следствие. Имеет место равенство

В самом деле, поскольку Сkп — число k-элементных подмножеств множества из п элементов, то сумма в левой части есть число всех подмножеств.

5.4. Упорядоченные множества. Перестановки и

размещения

5.4.1. Перестановки даного множества.

Множество называется упорядоченным, если каждому элементу этого множества поставлено в соответствие некоторое число (номер элемента) от 1 до п, где п — число элементов множества, так что различным элементам соответствуют различные числа. Всякое конечное множество можно сделать упорядоченным, если, например, переписать все элементы множества в некоторый список (а, b, с, ...), а потом поставить в соответствие каждому элементу номер места, на котором он стоит в списке. Будем обозначать упорядоченное множество, кторое получено из множества А, через . Очвидно, что каждое множество, которое содержит больше одного элемента, можно упорядочить не единственным способом. Упорядоченные множества считаются различными, если они отличаются либо своими элементами, либо их порядком. Различные упорядоченные множества, которые отличаются лишь порядком элементов (т. е. могут быть получены из того же самого множества), называются перестановками этого множества.

Пример. Перестановки множества А = {а, b, с} из 3 элементом имеют вид

(а, b, с), (а, с, b), (b, а, с),

(b, с, а), (с, а, b), (с, b, а).

Найдем число различных способов, которыми может быть упорядочено данное множество, т. е. число перестановок множества А. Пусть множество А имеет п элементов. Обозначим число ее перестановок через Рп.

Теорема.

Рп=п!.

Доказательство 1. Выберем некоторый элемент а из множества А. Рассмотрим все перестановки, в которых а имеет номер 1. Число таких перестановок будет равно числу перестановок из п—1 элементов множества А, которые остаются после исключения из множества элемента а. Поэтому число перестановок, для которых а имеет номер 1, равно Рп-1. Обозначим через М множество всех перестановок множества А, а через Ма — множество перестановок, в которых а имеет номер 1. Тогда

М = Ма Мb... Mf,

где а, b, ..., f — все элементы множества А. Поскольку никакие 2 множества из множеств Ма, Мb, ..., Mf не имеют общих элементов (напомним, что элементы этих множеств — перестановки, в различных множествах на первом месте стоят различные элементы, следовательно, и соответствующие перестановки будут различными), то

N(M) = N(Ma) + N(Mb)+ ... +N(Mf).

Следовательно,

Рп=п·Рп-1=п!.

Доказательство 2. Будем последовательно выбирать элементы множества А и размещать их в определенном порядке на п местах. На первое место можно поставить каждый из п элементов. После того как заполнено первое место, на второе место можно поставить любой из оставшихся п — 1 элементов и т. д. По правилу умножения все п мест можно заполнить

п( п— 1)(п — 2) ... 2· 1 =п!

способами. Следовательно, множество А из п элементов можно упорядочить п! способами.

Задача 1. Сколькими способами можно разместить на полке 4 книги (обозначим их А, В, С, D)?

Решение. Искомое число способов равно числу способов упорядочения множества, которое состоит из 4 элементов, т. е.

Р4 = 1 • 2 • 3 • 4 = 24.

Задача 2. Сколькими способами можно упорядочить множество

{1, 2, ..., 2п} так, чтобы каждое четное число имело четный номер?

Решение.. Четные числа можно расставить на местах с четными номерами (таких мест п) п! способами; каждому способа размещения четных чисел на местах с четными номерами соответствует п! способов размещения нечетных чисел на местах с нечетными номерами. Поэтому общее число перестановок указанного типа по правилу умножения равно п!·п!= (п!)2.