Докажите тождество: комбинаторика а)а 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}. каждую функцию можно тогда отождествить с последовательностью < f (1), f (n) > =< y1, yn > . каждый член yi последовательности можно выбрать m способами, что дает mn возможностей выбора последовательности < y1, yn > .