Докажите тождество: комбинаторика

а) А 7 91: Р 7 = С 14 21

б) С 8 13 * P 8 = А 8 13

в) С m n + C m (n+1) + C m (n+2) + ... + C m (n+m-1) = C (m+1) (n+m)

Лемма 1. Если |X| = n, |Y | = m, то количество всех функций

f : X → Y равно mn

.

Эквивалентное утверждение. Число слов длины n в алфавите

из m символов равно mn

.

Доказательство. Без потери общности можно всегда считать,

что X = {1, ..., n}, Y = {1, ..., m}. Каждую функцию можно

тогда отождествить с последовательностью

=. Каждый член yi

последовательности можно выбрать m способами, что дает mn

возможностей выбора последовательности.