Далее: §4. Графы Вверх: Глава I. Элементы комбинаторики Назад: §2. Основные правила комбинаторики

§3. Методы комбинаторики

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

Метод производящих функций является одним из наиболее развитых комбинаторных методов. Главные его идеи были впервые высказаны в конце XVIII века в работах Лапласа по теории вероятностей. Поясним их на следующем примере.

Пример 11. Используя биномиальный ряд Ньютона, получить некоторые свойства для сочетаний.

Решение. Рассмотрим биномиальный ряд Ньютона

$$\left( {1\!+\!x} \right)^\alpha\!=\!1\!+\!\alpha \cdot x + {... ...over\displaystyle k!}x^k + ... , \left\vert x \right\vert < 1,$$

и выбирая в качестве $\alpha$ и $x$ определенные значения, можно получить некоторые комбинаторные соотношения.

1) Пусть $\alpha$ - натуральное число $n$, тогда все слагаемые в правой части, начиная с $n$ + 2 слагаемого ($k = n$ + 1), обращаются в нуль. Получаем в этом случае бином Ньютона

$$\left( {1 + x} \right)^n = 1 + C_n^1 x + C_n^2 x^2 + ... + C_n^m x^m + ... + C_n^n x^n.$$

Придавая теперь различные частные значения переменной $x$, можно получить многие важные тождества.

а) $x = 1$     $2^n = C_n^0 + C_n^1 + C_n^2 + ... + C_n^n ,$

б) $x = -1$     $0 = 1 - C_n^1 + C_n^2 - C_n^3 + ... + ( - 1)^mC_n^m + ... + ( - 1)^nC_n^n .$

Складывая и вычитая полученные соотношения, получаем еще два свойства для чисел сочетаний:

$$\begin{tabular}{c} $C_n^0 + C_n^2 + C_n^4 + ... + C_n^{2m} =... ...n^3 + C_n^5 + ... + C_n^{2m - 1} = 2^{n - 1},$\\ \end{tabular}$$

где $m$ - целая часть числа $n/2.$

В данном случае функцию $f(x)$ = (1 + $x)^{n}$ называют производящей функцией числа сочетаний из $n$ элементов.

Метод сведения к аналогичной задаче для меньшего числа предметов называется методом рекуррентных соотношений (от латинского recurrere - возвращаться). Последовательно уменьшая число предметов, доходим до задачи, которую уже легко решить.

Пример 12. Используя метод рекуррентных соотношений, получить формулу для числа $P_n$ перестановок $n$ элементов без повторений.

Решение. Пусть у нас есть $n$ предметов $a_{1}$, $a_{2}$, ..., $a_{n - 1}$, $a_{n}$. Любую их перестановку можно получить, если присоединить элемент $a_{n}$ к перестановке $a_{1}$, $a_{2}$, ..., $a_{n - 1}$. Число различных мест, которые может занять элемент $a_{n}$, равно $n$, и поэтому перестановок из $n$ элементов в $n$ раз больше, чем перестановок из $n-1$ элементов. Тем самым установлено рекуррентное соотношение

$$P_n=n \cdot P_{n - 1},$$

пользуясь которым, последовательно выводим, что

$$P_{n}=n \cdot P_{n - 1}=n(n-1)\cdot P_{n - 2}=n(n-1)\cdot\ldots \cdot 2 \cdot P_{1}.$$

Поскольку из одного элемента можно сделать лишь одну перестановку, то $P_{1}=1$ и

$$P_{n}=n(n-1)\cdot\ldots \cdot 2 \cdot 1 = n!.$$

Пример 13 (числа Фибоначчи, 1202 год). Пара кроликов приносит раз в месяц приплод из двух крольчат (самки и самца), причем новорожденные крольчата через два месяца после рождения уже приносят приплод. Сколько кроликов появится через год, если в начале года была одна пара кроликов?

Решение. Обозначим через $F(n)$ количество пар кроликов по истечении $n$ месяцев с начала года, тогда через $n+ 1$ месяцев будут эти $F(n)$ пар и еще столько новорожденных пар кроликов, сколько было в конце месяца $n-1$, то есть еще $F(n- 1)$ пар кроликов. Следовательно, имеет место рекуррентное соотношение

$$F(n+1)=F(n)+F(n-1).$$

По условию $F(0) = 1$ и $F(1) = 2$, а далее последовательно находим $F(2) = 3$, $F(3) = 5,$ $F(4) = 8,$ $F(5) = 13, \ldots , F(12) = 377.$ Числа $F(n)$ называют числами Фибоначчи.

Геометрический способ в комбинаторике основан на подсчете различных кратчайших путей (ломаных), ведущих из точки $O(0, 0)$ в точку $A(n,m)$. Такие пути можно зашифровать последовательностью из $n$ нулей и $m$ единиц: нуль означает место, где ломаная идет вправо, а единица - место, где она идет вверх. Число последовательностей из $n$ нулей и $m$ единиц равно числу перестановок с повторениями

$$P_{n,m} = {\displaystyle (n + m)!\over\displaystyle n! \cdot m!} = C_{n + m}^n = C_{n + m}^m .$$

Пример 14. Используя геометрический метод, докажите свойства числа сочетаний (с повторениями и без повторений):

а)	$C_{n + m}^m = C_{n - 1}^0 + C_n^1 + C_{n + 1}^2 + ... + C_{n + m - 1}^m$или
	$\bar {C}_{n + 1}^m = \bar {C}_n^0 + \bar {C}_n^1 + \bar {C}_n^2 + ... + \bar {C}_n^m ;$
б)	$C_{n + m}^n = C_{n - 1}^{n - 1} + C_n^{n - 1} + C_{n + 1}^{n - 1} + ... + C_{n + m - 1}^{n - 1}$или
	$\bar {C}_{m + 1}^n = \bar {C}_1^{n - 1} + \bar {C}_2^{n - 1} + \bar {C}_3^{n - 1} + ... + \bar {C}_{m + 1}^{n - 1} .$

Решение. Выберем точку $A(n,m)$ и прямую $x = n- 1$, на которой выделим $m + 1$ точку $A_{0}(n-1, 0),$$A_{1}(n-1, 1), \ldots , A_{m}(n- 1,m)$. Каждый путь, проходящий через точку $A_{i}$, и уходящий вправо, единственным способом по прямой $x = n$ достигает точки $A$.

а) Поскольку от точки $O(0, 0)$ до точки $A_{i}(n-1,i)$, ( $i = 0, 1, 2, \ldots , m)$, существует $C_{n - 1 + i}^i$ путей, то по правилу сложения получаем

$$C_{n - 1}^0 + C_n^1 + C_{n + 1}^2 + ... + C_{n + m - 1}^m = C_{n + m}^m .$$

Полученное соотношение можно переписать на языке сочетаний с повторениями:

$$\bar {C}_n^0 + \bar {C}_n^1 + \bar {C}_n^2 + ... + \bar {C}_n^m = \bar {C}_{n + 1}^m .$$

б) Учитывая, что количество кратчайших путей от точки $O$ до точки $A_{i}$ можно найти и иначе, а именно как $C_{n - 1 + i}^{n- 1}$, получаем следующее соотношение:

$$C_{n - 1}^{n - 1} + C_n^{n - 1} + C_{n + 1}^{n - 1} + ... + C_{n + m - 1}^{n - 1} = C_{n + m}^n \quad{\text{или}}$$

$$\bar {C}_1^{n - 1} + \bar {C}_2^{n - 1} + \bar {C}_3^{n - 1} + ... + \bar {C}_{m + 1}^{n - 1} = \bar {C}_{m + 1}^n .$$

Следующий пример, с одной стороны, важен для авторского доказательства теоремы Бернулли (см. [перейти] далее §8), а с другой, является хорошим поводом для иллюстрации принципа вариативности при решении математических задач.

Пример 15. Доказать, что $C_n^m = C_{n - 1}^m + C_{n - 1}^{m - 1}.$

Решение. 1 способ (вычислительный).

$$C_{n - 1}^m + C_{n - 1}^{m - 1} = {\displaystyle (n - 1)!\ov... ... (n - 1)!\over\displaystyle (m - 1)! \cdot (n - 1 - m + 1)!} =$$

$$= {\displaystyle (n - 1)!\over\displaystyle m! \cdot (n - m... ...ystyle (n - 1)!\over\displaystyle m! \cdot (n - m)!} = C_n^m .$$

2 способ (комбинаторный).

Пусть формируется делегация для заграничной поездки из $m$ человек от Государственной Думы, состоящей из $n$ депутатов. Существует $C_n^m$ способов выбора делегации, и в делегацию спикер может входить, тогда остальные члены делегации выбираются $C_{n - 1}^{m - 1}$ способами, а может и не входить, тогда вся делегация ($m$ человек) формируется из остальных $n-1$ депутатов. По правилу сложения получаем

$$C_n^m = C_{n - 1}^m + C_{n - 1}^{m - 1} .$$

3 способ (геометрический).

Обратим внимание на то, что к точке $A(m,n-m)$ можно пройти обязательно через одну из двух точек $A_{1 }(m, n - m - 1),$ и $A_{2 }(m- 1,n - m)$, а к ним ведут $C_{(n - m - 1) + m}^m$ и $C_{(n - m) + (m - 1)}^{m - 1}$ путей соответственно. Тогда получаем

$$C_n^m = C_{n - 1}^m + C_{n - 1}^{m - 1} .$$

4 способ (производящих функций).

В примере 11 показано, что $f_n (x) = (1 + x)^n$ является производящей функцией для числа сочетаний. Поскольку $f_n (x) = (1 + x)^n = (1 + x)f_{n - 1} (x),$ то коэффициенты при $x^{m}$ в левой и в правой частях тождества равны

$$C_n^m = C_{n - 1}^m + C_{n - 1}^{m - 1} .$$

Вопросы для самоконтроля

1. Какие функции называются производящими? Примеры.
2. Производящие функции для сочетаний и размещений.
3. Использование производящих функций для получения комбинаторных соотношений.
4. Показать на примерах эффективность метода производящих функций.
5. Метод рекуррентных соотношений.
6. Получите последовательность чисел Фибоначчи.
7. В чем смысл геометрического метода в комбинаторике?
8. Приведите примеры использования геометрического метода.

Задачи

I 21. Докажите свертку Вандермонда:

$$C_n^k = \sum\limits_{r = 0}^n {C_{n - m}^r \cdot C_m^{k - r} } .$$

  22. Докажите, что $\sum\limits_{k = 0}^n {\left( {C_n^k } \right)^2 = C_{2n}^n } .$

  23. Найдите десятый член последовательности Фибоначчи.

  24. Докажите, что $C_{n + 1}^2 + C_n^2 + C_{n - 1}^2 + ... + C_3^2 + C_2^2 = C_{n + 2}^3 .$

  25. Укротитель хищных зверей хочет вывести на арену цирка 6 львов и 5 тигров, при этом нельзя, чтобы два тигра шли друг за другом. Сколькими способами он может расположить зверей?

  26. В окружность вписан правильный $2n$-угольник. Сколькими способами можно попарно соединить его вершины так, чтобы получающиеся отрезки не пересекались друг с другом?

II 27. Найдите нумератор и производящую функцию для сочетаний без повторений.

  28. Докажите, что $\sum\limits_{k = 1}^n {{\displaystyle ( - 1)^{k - 1}\over\displaystyle k} \cdot... ...aystyle 1\over\displaystyle 2} + ... + {\displaystyle 1\over\displaystyle n}.}$

III 29. Докажите тождества:

а) $\sum\limits_{k = 0}^n {k \cdot C_n^k } = n \cdot 2^{n - 1};$

б) $\sum\limits_{k = 0}^n {k^2 \cdot C_n^k } = n(n + 1) \cdot 2^{n - 2}.$

  30. Докажите полиномиальную теорему:

$$\left( {\sum\limits_{i = 1}^m {a_i } } \right)^n = \sum {{\d... ...!}a_1^{n_1 } \cdot a_2^{n_2 } \cdot \cdot \cdot a_m^{n_m } } ,$$

где сумма берется по всем решениям уравнения$n_1 + n_2 + ... + n_m = n$в целых неотрицательных числах.

Далее: §4. Графы Вверх: Глава I. Элементы комбинаторики Назад: §2. Основные правила комбинаторики