МАЛЫЙ МЕХМАТ МГУ

Кружок для старшеклассников, не участвовавших ранее в математических кружках

Занятие 13 (12 декабря 2015 года). Комбинаторика. Биномиальные коэффициенты

Количество способов, которыми можно выбрать k предметов из n, равно \[C_n^k = \binom{n}{k} = \frac{n!}{k!(n-k)!}\] (первое равенство — просто разные обозначения).

Эти числа обладают рядом замечательных свойств, изучению которых и будет посвящено это занятие. Постарайтесь при решении задач использовать не столько явную формулу, сколько их смысл.

1.

Докажите, что \(\binom{n}{k} = \binom{n}{n-k}\).

2.

Найдите все n такие, что а) \(C_n^3 = C_n^8\); б) \(C_n^5 = C_n^{10}\).

3.

Основное биномиальное тождество: \(\binom{n+1}{k} = \binom{n}{k-1}+\binom{n}{k}\).

4*.

Бином Ньютона. \[(a+b)^n = \underbrace{(a+b)(a+b)...(a+b)}_{n} = a^n+\binom{1}{n}a^{n-1}b+\binom{2}{n}a^{n-2}b^{2}+... +\binom{k}{n}a^{n-k}b^{k}+...+\binom{n-1}{n}ab^{n-1}+b^n\] Треугольник Паскаля. Основное биномиальное тождество позволяет расположить биномиальные коэффициенты в виде бесконечной треугольной таблицы на рисунке.

5.

Почему равенства 11² = 121 и 11³ = 1331 похожи на строчки треугольника Паскаля? Чему равно 11⁴?

6.

Докажите, что \(\sum_{k=0}^n \binom{n}{k}=\binom{n}{0}+\binom{n}{1}+...+\binom{n}{n-1}+\binom{n}{n} = 2^n\).

7.

В ящике лежат n черных и n белых шаров. Сколькими способами можно выбрать пару шаров разного цвета? Исходя из полученного результата, докажите, что \(\left(C_n^0\right)^2+\left(C_n^1\right)^2+...+\left(C_n^n\right)^2=C_{2n}^n\).

8.

Вычислите

а)

\(\binom{n}{0}-\binom{n}{1}+\binom{n}{2}-\binom{n}{3}+...+(-1)^{n}\binom{n}{n}\);

б)

\(\sum_{k=0}^nkC_n^k\);

в)

\(\sum_{k=0}^n(k+1)C_n^k\);

г)

\(\sum_{k=0}^n(-1)^{k+1}kC_n^k\).