Лемма 1

.

Доказательство. Подмножество A₁ можно выбрать способами. Подмножество A₂ выбирается из оставшихся n-k₁ элементов, его можно будет выбрать способами. Подмножество A₃ – способами, и т.д. Выбор подмножества A_m определен предшествующими подмножествами. Отсюда получаем .

Поскольку n – k₁ – ∙∙∙ – k_m-1 = k_m, то после сокращения дроби получаем нужное равенство.