Rambler's Top100





5
Доказательство. При l=2 мы ссылаемся на теорему 1:
n(A
1
A
2
) = n(A
1
) + n(A
2
).
Допустим, что утверждение верно при l = k, то есть
n(A
1
A
2
A
k
) = n(A
1
) + n(A
2
) ++ n(A
k
).
Докажем утверждение при l = k+1. В этом случае
n(A
1
A
2
A
k
A
k+1
) = n((A
1
A
2
A
k
) A
k+1
)
= n(A
1
A
2
A
k
) + n(A
k+1
). Здесь мы воспользовались бази-
сом индукции и, применяя индуктивное предположение, получим:
n(A
1
A
2
A
k
) + n(A
k+1
) = n(A
1
) ++ n(A
k
) + n(A
k+1
).
Следствие доказано.
Иногда принцип сложения, применительно к задачам комбинато-
рики, можно встретить в таком виде: если объект x можно получить m
способами, а объект y можно получить l способами, причем множества
этих способов не пересекаются, то объект x или объект y можно полу-
чить m + l способами. Таким образом, необходимо помнить, что в ком-
бинаторике союз “или” ассоциирован с операцией сложения.
Теорема 3 (принцип умножения). Если множество A состоит из
m элементов, а множество B состоит из l элементов, то n(A B) =ml.
Доказательство. Будем доказывать методом математической ин-
дукции по l. При l=1 множество B состоит из одного элемента:
B={b
1
}. Поэтому множество A B={(a
i
, b
1
)|i =1, 2,…,m} состоит из
m элементов, то есть n(A B)=m · 1=m · l. Базис индукции проверен.
Допустим, утверждение верно при l = k, то есть, если n(A) = m,
n(B) = k, то n(A B) = m · k. Докажем утверждение при l = k + 1.
Пусть B = {b
1
, b
2
,…, b
k
,
b
k+1
} или B = B
'
{b
k+1
}, где множество
B
'
= {b
1
, b
2
,…, b
k
} состоит из k элементов. По индуктивному предпо-
ложению n(A B
'
) = n(A) · n(B
'
) = m · k. С другой стороны
B = B
'
{b
k+1
}, поэтому (A B) = A B
'
A {b
k+1
}, причем
A B
'
A {b
k+1
} = , так как B
'
{b
k+1
} = . По теореме 1
n(A B) = n(A B
'
A {b
k+1
}) = n(A B
'
) + n(A {b
k+1
})=
=m · k + m · 1 = m(k + 1) = m · l. Теорема доказана.
В комбинаторном изложении принцип умножения часто формули-
руют так: если объект x можно сконструировать m способами, объект y
можно сконструировать l способами, то объект (x, y) или (x и y) можно
сконструировать m · l способами. То есть союз “и” в комбинаторики
ассоциирован с операцией умножения.
Теорема 4. Если множества A
1
, A
2
,…,
A
k
конечны, то