Занятие 2. Правило суммы и произведения в комбинаторике

Цель: Изучить на практике комбинаторные правило суммы (и его следствия) и произведения. В частности.

Содержание:

Задание 2 (на правило суммы).

Задание 3 (на правило произведения.)

Задание 2.

Из k₃=n(AB)=18 студентов группы, факультативно изучавших математику и/или информатику, k₁=n(A)=13 изучало математику, k₂=n(B)=11 изучало информатику. Сколько студентов группы факультативно изучали следующие предметы:

1. математику и информатику одновременно,

2. только математику, но не информатику,

3. только информатику, но не математику?

ПРАВИЛО СУММЫ. КРАТКАЯ ТЕОРИЯ.

Решение.

Пусть даны конечные множества элементов A и B с числом элементов соответственно k₁=n(A) и k₂=n(B). Тогда могут быть определены множества X= A B, X₁= AB, X₂= A\B, X₃= B\A с числом элементов соответственно k₃=n(AB), k₄=n(AB), k₅=n(A\ B), k₆=n(B \A). В этом случае справедливо правило суммы (ф. (1)), два следствия из него (ф. (2-3)), а также контрольное соотношение (ф. (4)):

1) n(AB)= n(A)+n(B)-n(AB), k₄= k₁+ k₂- k₃, (1)

2) n(A\B)= n(A)-n(AB), k₅= k₁- k₄, (2)

3) n(B\A)= n(B)-n(AB), k₆= k₂- k₄, (3)

4) n(AB)= n(A\B)+n(B\A)+n(AB), k₃= k₅+ k₆+ k₄. (4)

КОНЕЦ ТЕОРИИ.

Обозначим через A и B множества студентов группы, факультативно изучавших соответственно математику и информатику с числом элементов, согласно условия, соответственно k₁=n(A)=13 и k₂=n(B)=11. Тогда по определению операции объединения множеств X= AB - множество студентов группы, факультативно изучавших математику и/или информатику. Число его элементов, согласно условия, равно k₃=n(AB)=18.

1) По определению операции пересечения множеств X= AB - множество студентов группы, факультативно изучавших математику и информатику одновременно. Число элементов этого множества, обозначенное через k₄=n(AB), является искомым в пункте 1 вопроса задания. Его мы найдем, по ф.(1) правила суммы (см. краткую теорию). Имеем

n(AB)= n(A)+n(B)-n(AB), k₄= k₁+ k₂- k₃, n(AB)= k₄=13+11-18=6.

Ответ: n(AB)= 6, т. е. 6 студентов группы факультативно изучали математику и информатику одновременно.

2) По определению операции вычитания множеств X₂= A\B - множество студентов группы, факультативно изучавших только математику, но не информатику. Число элементов этого множества, обозначенное через k₅=n(A\B), является искомым в пункте 2 вопроса задания. Его мы найдем, по ф.(2) следствия правила суммы (см. краткую теорию). Имеем

n(A\B)= n(A)-n(AB), k₅= k₁ - k₄, n(A\B)= k₅=13-6=7.

Ответ: n(A\B)= 7, т. е. 7 студентов группы факультативно изучали только математику, но не информатику.

3) По определению операции вычитания множеств X₃= B\A - множество студентов группы, факультативно изучавших только информатику, но не математику. Число элементов этого множества, обозначенное через k₆=n(B\A), является искомым в пункте 3 вопроса задания. Его мы найдем, по ф.(3) следствия правила суммы (см. краткую теорию). Имеем

n(B\A)= n(B)-n(AB), k₆= k₂ - k₄, n(B\A)= k₆=11-6=5.

Ответ: n(B\A)= 5, т. е. 5 студентов группы факультативно изучали только информатику, но не математику.

4) По ф.(4) контрольного соотношения (см. краткую теорию) имеем

n(AB)= n(A\B)+n(B\A)+n(AB), k₃= k₅+ k₆+ k_4, 18=7+5+6=18.

Итак, 18=18. Задание решена верно.

Задание 3. Из пункта K (см. рис. 2) в пункт L ведут k₁=n(A)=13 непересекающихся дорог, а из пункта L в пункт M - k₂=n(B)=11 дорог. Сколько существует способов проезда из пункта K в пункт M через пункт L?

ПРАВИЛО ПРОИЗВЕДЕНИЯ. КРАТКАЯ ТЕОРИЯ.

Пусть даны конечные множества элементов A={a₁, a₂,…, a_r} и B={b₁, b₂,…, b_s} с числом элементов соответственно r=n(A) и s=n(B). Тогда может быть определено множество X= =AB, называемое декартовым произведением множеств A и B в указанном порядке:

X= =AB=

{(a1, b1),	(a1,b2)	…	(a1, bs)
(a2, b1),	(a2,b2)	…	(a2, bs)
…	…	…	…
(ar, b1),	(ar,b2)	…	(ar, bs)}.

Очевидно, в каждой клетке последней прямоугольной таблицы по одной паре элементов множеств A и B, являющиеся, в свою очередь, отдельными элементами множества X= =AB (декартовым произведением множеств A и B). Число элементов последнего множества X=AB, которое мы обозначим n(X)= n(AB) равно числу клеток в последней прямоугольной таблицы размера r строк  s столбцов = r s =n(A) n(B). Итак, мы доказали правило произведения:

n(AB)= n(A) n(B). (5)

КОНЕЦ ТЕОРИИ.

Решение.

Обозначим через A={a₁, a₂,…, a_r} и B={b₁, b₂,…, b_s} множества непересекающихся дорог, ведущих соответственно из пункта K в пункт L и из пункта L в пункт M (см. рис. 2). Их число элементов, согласно условия, равны соответственно r=n(A)=13 и s=n(B)=11.

Составление маршрутов проезда из пункта K в пункт M через пункт L есть по сути составление элементов декартова произведения множеств A и B в указанном порядке. Например, элемент (a₁, b₁) декартова произведения соответствует тому, что из пункта K в пункт L выбрана первая дорога a₁ из списка всех дорог, а из пункта L в пункт M выбрана тоже первая дорога b₁ из списка всех дорог и т. д. Наконец, элемент (a_r, b_s).декартова произведения соответствует тому, что из пункта K в пункт L выбрана последняя дорога a_r из списка всех дорог, а из пункта L в пункт M выбрана тоже последняя дорога b_s из списка всех дорог.

Поэтому искомое число маршрутов проезда из пункта K в пункт M через пункт L есть общее число элементов декартова произведения множеств A и B, то есть равно, согласно правила произведения, n(AB)= n(A) n(B)= r  s =1311 =143.

Ответ: n(AB)= 143, т. е. 143 различных маршрутов проезда из пункта K в пункт M через пункт L.