3 Элементы комбинаторики - лекции
.pdf
Эту формулу можно обобщить для подсчѐта числа элементов, обладающих или не обладающих данным набором свойств.
Пусть дано множество n элементов и множество k свойств p1 , p2 , …, pk , которыми могут обладать или не обладать эти элементы. Произ-
вольным образом выделим r свойств pi , |
pi |
, …, |
pi |
. |
|
|
|||||||||
|
|
|
|
|
1 |
|
2 |
|
|
r |
|
|
|||
Число элементов, обладающих всеми r |
свойствами, обозначим |
||||||||||||||
n ( pi , |
pi |
|
, …, pi |
). Отсутствие какого-либо свойства |
pi |
у элемента обо- |
|||||||||
1 |
|
|
2 |
|
r |
|
|
|
|
|
|
|
|
|
|
значим |
|
pi |
. Тогда запись n ( p1 , p2 , p3 ) означает число элементов со свой- |
||||||||||||
ствами p1 |
и p3 , но без свойства p2 . |
|
|
|
|
|
|
|
|
||||||
Найдѐм число элементов, не обладающих набором определѐнных |
|||||||||||||||
свойств. Начнѐм с простого случая. |
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
||||||||
1. |
|
|
Пусть имеется одно свойство p , тогда n( p) |
n |
n( p) . |
||||||||||
2.Имеется конечное число свойств p1 , p2 , …, pk , несовместимых
|
|
|
|
|
|
|
k |
|
друг с другом. Тогда n( p1 , p2 , ..., pk ) n |
n( pi ) . |
|||||||
|
|
|
|
|
|
|
i |
1 |
3. Элементы обладают комбинациями различных свойств (эти свойства совместимы между собой). Тогда справедлива формула, аналогичная (1):
|
|
|
|
|
|
|
k n( pi ) |
k |
|
|
k |
|
||
n( p1 , p2 , ..., pk ) n |
n( pi , p j ) |
|
n( pi , p j , pl ) ... |
|||||||||||
|
|
|
|
|
|
|
i 1 |
1 i j k |
|
|
|
1 i j l k |
|
|
|
|
|
|
|
|
|
... |
( 1)k n( p , p |
2 |
,..., p |
k |
) . |
(2) |
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
||
В левой части (2) может стоять не только число вида n( p1, p2 , ..., pk ) ,
но и, например, n( p1 , p2 , p3 , p4 ) – число элементов, обладающих свойствами p1 , p3 и не обладающих свойствами p2 , p4 :
n( p1 , p2 , p3 , p4 ) n( p1 , p3 ) n( p1 , p3 , p2 ) n( p1 , p3 , p4 ) n( p1 , p3 , p2 , p4 ) .
►Пример. В комнате несколько человек, знающих хотя бы один из трѐх языков. Шестеро знают английский, шестеро – немецкий, семеро – французский. Четверо знают английский и немецкий, трое – немецкий и французский, двое – французский и английский. Один человек знает все три языка. Сколько человек в комнате? Сколько из них знают только английский язык?
Решение. Задачу можно решить двумя способами: «вычерпывания» и по формуле включения и исключения. Запишем компактно условие задачи (табл. 1):
|
|
|
|
|
|
Табл. 1 |
|
|
|
|
|
|
|
|
|
А |
Н |
Ф |
АН |
НФ |
ФА |
|
АНФ |
|
|
|
|
|
|
|
|
6 |
6 |
7 |
4 |
3 |
2 |
|
1 |
|
|
|
|
|
|
|
|
109
Пусть из комнаты ушѐл человек, знающий все три языка, тогда таблица 1 примет вид:
|
|
|
|
|
|
Табл. 2 |
|
|
|
|
|
|
|
|
|
А |
Н |
Ф |
АН |
НФ |
ФА |
|
АНФ |
|
|
|
|
|
|
|
|
5 |
5 |
6 |
3 |
2 |
1 |
|
0 |
|
|
|
|
|
|
|
|
Пусть теперь ушли три человека (из оставшихся), знающие одновременно английский и немецкий языки. Число людей, знающих другие пары языков, не изменится.
|
|
|
|
|
|
|
Табл. 3 |
|
|
|
|
|
|
|
|
|
|
А |
|
Н |
Ф |
АН |
НФ |
ФА |
|
АНФ |
|
|
|
|
|
|
|
|
|
2 |
|
2 |
6 |
0 |
2 |
1 |
|
0 |
|
|
|
|
|
|
|
|
|
|
Пусть уйдут двое, знающие немецкий и французский. |
|
|
|||||
|
|
|
|
|
|
|
Табл. 4 |
|
|
|
|
|
|
|
|
|
|
А |
|
Н |
Ф |
АН |
НФ |
ФА |
|
АНФ |
|
|
|
|
|
|
|
|
|
2 |
|
0 |
4 |
0 |
0 |
1 |
|
0 |
|
|
|
|
|
|
|
|
|
|
Наконец, уходит человек, знающий французский и английский язы- |
|||||||
ки. Тогда получим: |
|
|
|
|
|
|
||
|
|
|
|
|
|
|
Табл. 5 |
|
|
|
|
|
|
|
|
|
|
А |
|
Н |
Ф |
АН |
НФ |
ФА |
|
АНФ |
|
|
|
|
|
|
|
|
|
1 |
|
0 |
3 |
0 |
0 |
0 |
|
0 |
|
|
|
|
|
|
|
|
|
Значит, в комнате остался один человек, знающий только английский язык, и трое, знающих только французский язык. Кроме того, вышло семь человек. Следовательно, сначала в комнате было одиннадцать человек.
Решим теперь эту задачу методом включений и исключений. Пусть свойство pA есть знание английского языка, pH – знание немецкого языка, pФ – знание французского языка. Общее число людей составляют все, знающие хотя бы один язык. Не знающих хотя бы одного языка в условии нет. По формуле (1) имеем:
n n( pA ) n( pH ) n( pФ ) |
n( рА , рН ) |
n( рА , рФ ) |
|
n( рН , рФ ) n( рА , рН , рФ ) |
|||||||||||||
6 |
6 |
7 |
(4 |
3 |
2) |
1 |
19 |
9 |
1 |
11. |
|
|
|
|
|||
|
|
|
|
|
|
|
|
||||||||||
Число людей, знающих только английский язык, есть n( pА , pН , pФ ) . |
|||||||||||||||||
По формуле (2) найдѐм это число: |
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|||||||||
n( pА , pН , pФ ) |
n( pА ) |
n( pА , pН ) |
n( pА , pФ ) |
n( pА , pН , pФ ) |
|||||||||||||
6 4 2 1 1.◄
110