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

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

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

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

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

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


\begin{displaymath}

\left( {1\!+\!x} \right)^\alpha\!=\!1\!+\!\alpha \cdot x +

{...

...over\displaystyle k!}x^k + ... , \left\vert x

\right\vert < 1,

\end{displaymath}

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

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


\begin{displaymath}

\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.

\end{displaymath}

Придавая теперь различные частные значения переменной $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{displaymath}

\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}\end{displaymath}

где $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$ элементов. Тем самым установлено рекуррентное соотношение

\begin{displaymath}

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

\end{displaymath}

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

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

\cdot 2 \cdot P_{1}.

\end{displaymath}

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

\begin{displaymath}

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

\end{displaymath}

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

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

\begin{displaymath}

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

\end{displaymath}

По условию $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$ единиц равно числу перестановок с повторениями


\begin{displaymath}

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

\end{displaymath}

Пример 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 $ путей, то по правилу сложения получаем


\begin{displaymath}

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

\end{displaymath}

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


\begin{displaymath}

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

\bar {C}_{n + 1}^m .

\end{displaymath}

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

i}^{n- 1} $, получаем следующее соотношение:


\begin{displaymath}

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{или}}

\end{displaymath}


\begin{displaymath}

\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 .

\end{displaymath}

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

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

1}^{m - 1}.$

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


\begin{displaymath}

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

... (n - 1)!\over\displaystyle (m - 1)! \cdot (n - 1 - m + 1)!} =

\end{displaymath}


\begin{displaymath}

= {\displaystyle (n - 1)!\over\displaystyle m! \cdot

(n - m...

...ystyle (n - 1)!\over\displaystyle m! \cdot (n

- m)!} = C_n^m .

\end{displaymath}

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

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

- 1} $ способами, а может и не входить, тогда вся делегация ($m$ человек) формируется из остальных $n-1$ депутатов. По правилу сложения получаем


\begin{displaymath}

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

\end{displaymath}

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} $ путей соответственно. Тогда получаем


\begin{displaymath}

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

\end{displaymath}

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

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

+ x)^n = (1 + x)f_{n - 1} (x),$ то коэффициенты при $x^{m}$ в левой и в правой частях тождества равны


\begin{displaymath}

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

\end{displaymath}


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

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

Задачи

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


\begin{displaymath}

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

\end{displaymath}

  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. Докажите полиномиальную теорему:


\begin{displaymath}

\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 } } ,

\end{displaymath}

где сумма берется по всем решениям уравнения$n_1 + n_2 + ... +

n_m = n$в целых неотрицательных числах.


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

ЯГПУ, Центр информационных технологий обучения
2006-03-04