Четыре лекции по комбинаторике. Семенов А.С. - 7 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

Составители: 

Рубрика: 

9
+…+ ),...()1(...)}(
21
1
12 n
n
nnn
AAANAAAN IIIII
−
−−
−+− или
U
n
i
n
k
nk
k
i
AAASAN
1
1
21
1
),,...,,()1()(
=
=
−
∑
⋅−= (9)
где ),...,(
1 nk
AAS есть сумма чисел )...(
1 k
ii
AAN II по всем возможным пере-
сечениям ровно
k
различных множеств из множеств .,...,
1 n
AA
Доказательство. Проведем доказательство методом математической индукции. Из
формулы (8) следует, что формула (9) справедлива для двух множеств, т.е. при
.2=n
Пусть формула (9) верна для всех },1,...,3,2{
−
∈
nm тогда последовательно
получаем
−
+
=
)...()()...(
2121 nn
AANANAAAN UUUUU
−
+
=
− ),...,({)())(...)()((
21113121 nn
AASANAAAAAAN IUUIUI
−−⋅−++−
−
−
),...,({)},...,()1(...),...,(
121121
2
22 nnn
n
n
AAAASAASAAS II
)}.,...,()1(...),...,(
1211
2
1212 nn
n
n
AAAASAAAAS IIII
−
−
⋅−++−
Для того чтобы отсюда получить формулу (9), остается принять во внимание, что
),....,(),...,()(
11211 nn
AASAASAN
=
+ ,
),,...,(),...(),...,(
112112 nknknk
AASAAAASAAS
=
+
−
II
}
;1,...,2
{
−
∈ n
k
).,...,(),...,(
11211 nnnn
AASAAAAS
=
−
II
Следовательно, согласно принципу математической индукции, формула (9) верна
для любого натурального .n Теорема 5 доказана.
Следствие. Если
=
≠∀
ji
AAji I Ø, то
U
n
i
n
i
ii
ANAN
1
1
)()(
=
=
∑
= (10)
Пример 6. Каждый студент в группе – либо девушка, либо блондин, либо говорит по
английски. В группе 16 девушек, из них 6 блондинок, и 4 блондинки знают английский
язык. Всего в группе 11 блондинов, по английски из них говорят 8. Всего студентов,
которые могут общаться на английском языке 20, из них 12 девушек. Сколько сту-
дентов в данной группе ?
Решение. Пусть
−
A
множество девушек,
−
B множество блондинов, −C множе-
ство студентов, которые знают английский язык. Тогда
−)( CBAN UU искомое
число студентов в группе;
−
BA I множество блондинок; −CA I множество деву-
шек, которые говорят по английски;
−
CB I множество всех блондинов (юношей и
девушек), которые знают английский язык;
CBA II множество блондинок, кото-
рые говорят по английски. Из данных задачи следует, что
,12)(,6)(,20)(,11)(,16)( =
=
=== CANBANCNBNAN II
.4)(,8)( == CBANCBN III Теперь по формуле (9) при 3=n получаем
.254)8126(201116)(
=
+
+
+−++=CBAN UU Таким образом, в группе 25 сту-
дентов.

Страницы