Дискретная математика

Доказательство этой формулы можно провести по тому же плану, что и приведенное выше доказательство бинома Ньютона. Раскрывая скобки, не группируя при этом сомножителей, получаем сумму, слагаемыми в которой выступают всевозможные слова длины в алфавите . Группируя затем сомножители, получаем слагаемые вида , причем такое слагаемое появляется столько раз, сколько имеется слов с соответствующим составом букв, то есть