Сочетания

Первое свойство непосредственно вытекает из формул:

$$\boxed{{\rm{C}}_{\rm{n}}^{\rm{k}} = {\rm{C}}_{{\rm{n - 1}}}^{{\rm{k - 1 }}} + {\rm{C}}_{{\rm{n - 1}}}^{{\rm{k }}}}$$

Доказательство:

Составим $$k$$ -элементные сочетания из $$n$$ элементов $$a_1, a_2, a_3, ...., a_{n-1}, a_n$$ и разобьем их на два класса:

1-й класс - сочетания, содержащие элемент $$a_n$$ ;

2-й класс - сочетания, не содержащие элемент $$a_n$$.

Если из любого сочетания 1-го класса откинуть элемент $$a_n$$, то останется $$(k-1)$$ сочетание из $$a_1, a_2, a_3, ...., a_{n-1}$$, их число $${\rm{C}}_{{\rm{n - 1}}}^{{\rm{k - 1 }}}$$.

Сочетания 2-го класса являются $$k$$ -элементными сочетаниями, составленными из $$a_1, a_2, a_3, ...., a_{n-1}$$, их число $$С^k_{n-1}$$. Поскольку любое $$k$$ -элементное сочетание из $$a_1, a_2, a_3, ...., a_{n-1}, an$$ принадлежит одному и только одному из этих классов, а общее число равно $$С^k_n$$, то приходим к равенству (6.2).

Пример.

Пусть дано множество $$М = \left\{ {a, b, c, d, e} \right\}$$. Тогда $$M_c = \left\{ {(a,b), (a, c), (a, d), (\underline {a, e}), (b, c), (b, d), (\underline {b, e}), (c, d), (\underline {c, e}), (\underline {d, e})} \right\}$$.

$$M^1_c = \left\{ {(\underline {a, e}), (\underline {b, e}), (\underline {c, e}), (\underline {d, e})} \right\}. M^2_c = \left\{ {(a, b), (a, c), (a, d), (b, c),(b, d), (c, d),} \right\}$$.

С другой стороны, $${\rm{C}}_{\rm{5}}^{\rm{2}} = \frac{{{\rm{5!}}}}{{{\rm{2!3!}}}} = 10$$. $${\rm{C}}_{\rm{5}}^{\rm{2}} = {\rm{C}}_{\rm{4}}^{{\rm{1 }}} + {\rm{C}}_{\rm{4}}^{{\rm{2 }}}= 4 + 6 = 10$$.

$$\boxed{{\rm{C}}_{\rm{n}}^{\rm{0}} + {\rm{C}}_{\rm{n}}^{{\rm{1 }}} + \ldots + {\rm{C}}_{\rm{n}}^{{\rm{k }}} + \ldots + {\rm{C}}_{\rm{n}}^{{\rm{n }}} = 2^{\rm{n}}}$$

Доказательство:

$$2^n$$ - это число всех $$n$$ размещений с повторениями из элементов двух типов. Разобьем эти размещения на классы, отнеся в $$k$$ -й класс те, в которые входят $$k$$ элементов 1-го типа и $$(n-k)$$ элементов 2-го типа. Размещения k-го класса - это не что иное, как всевозможные перестановки из $$k$$ элементов 1-го типа и $$(n-k)$$ элементов 2-го типа. Мы знаем, что число таких перестановок равно

Вспомним формулу

где $$i_1 = k, i_2 = n-k, P(k, n-k) = C^k_n$$. Значит, общее число размещений всех классов равно $${\rm{C}}_{\rm{n}}^{\rm{0}} + {\rm{C}}_{\rm{n}}^{{\rm{1 }}} + \ldots + {\rm{C}}_{\rm{n}}^{{\rm{k }}} + \ldots + {\rm{C}}_{\rm{n}}^{{\rm{n }}}$$. С другой стороны, это же число равно $$2^n$$. Тем самым соотношение доказано.

Рассмотрим $$m$$ -элементные сочетания с повторениями, составленные из элементов $$n+1$$ типов, скажем из $$n+1$$ букв a, b, c,..., x. Число таких сочетаний равно

Разобьем все сочетания на классы, отнеся к $$k$$ -му классу сочетания, в которые $$k$$ раз входит буква $$a$$, остальные $$(m-k)$$ мест могут быть заняты оставшимися $$n$$ буквами с повторениями. Поэтому в $$k$$-й класс входит столько сочетаний, сколько можно составить $$(m-k)$$ -элементных сочетаний с повторениями из элементов $$n$$ типов, т. е. $${\rm{}}_{{\rm{n}} + {\rm{m - k - 1}}}^{{\rm{m - k}}}$$, значит, общее число всех сочетаний равно $${\rm{C}}_{{\rm{n}} + {\rm{m - 1}}}^{\rm{m}} + {\rm{C}}_{{\rm{n}} + {\rm{m - 2}}}^{{\rm{m - 1 }}} + \ldots + {\rm{C}}_{\rm{n}}^{{\rm{1 }}} + \ldots + {\rm{C}}_{{\rm{n - 1}}}^{{\rm{0 }}}$$. С другой стороны, мы видим, что это число равно $${\rm{C}}_{{\rm{n}} + {\rm{m}}}^{\rm{m}}$$, т. е. утверждение доказано.

Заменяя $$n$$ на $$n+1$$ и $$m$$ на $$m+1$$ в соотношении (6.4), и помня, что $${\rm{C}}_{\rm{n}}^{\rm{k}} = {\rm{C}}_{\rm{n}}^{{\rm{n - k}}}$$, получаем, что

Частными случаями формулы (6.5) при $$n = 1, 2, 3$$ являются следующие суммы рядов:

$$n = 1$$:

$$n = 2$$:

Аналогично для $$n = 3$$:

Следовательно,

$$\boxed{\begin{array}{l} 1 \times 2 \times 3 + 2 \times 3 \times 4 + 2 \times 3 \times 2 \times 5 + 2 \times 3 \times 4 \times 5 + ... \\ + m(m + 1)(m + 2) = 1 \times 2 \times 3 + 2 \times 3 \times 4 + 3 \times 4 \times 5 + 4 \times 5 \times 6 + ... \\ + m(m + 1)(m + 2) = \frac{{m(m + 1)(m + 2)(m + 3)}}{4}. \\ \end{array}}$$

С помощью формулы (6.7) легко найти сумму квадратов натуральных чисел от $$1$$ до $$m.$$