Дискретно-непрерывная математика (стр. 42 )

Коэффициент при sr и есть искомое число сочетаний. Следовательно, число сочетаний из п предметов по r при условии, что каждый предмет встречается по крайней мере 1 раз, равно 0, если r < п, и равно Cп-1r-1, если r≥ п.

Пример 16. Пусть Ап — число целых неотрицательных решений уравнения

k1х1+ k2x2+ ... +krxr = n, (22)

где k1, k2, ..,, kr - данные натуральные числа.

Обозначим

Легко видеть, что

Запишем равенства

Если перемножить их почленно, то показатели при степенях s будут иметь вид

где все хі получают натуральные значения (такой показатель получится, если в правой части каждого из написанных равенств выбрать соответственно

и перемножить их). Число всех возможных представлений п в выражении (22) как раз и будет коэффициентом при sn в том разложении, которое получим после перемножения всех равенств.

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

Определение. Сверткой двух последовательностей {ап} и {bn} называется последовательность {сп}, общий член которой имеет вид

Теорема. Производящая функция свертки двух последовательностей равна произведению производящих функций этих последовательностей.

Доказательство. Пусть {сп} — свертка последовательностей {ап} и {bn}, а

- производящие функции последовательностей {ап}, {bn}, {сп} сответственно. Требуется доказать, что

С (s) = А (s) В (s).

Перемножим два ряда

Коэффициент при sп в полученном произведении равен

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

A (s) B(s)=C (s).

Для иллюстрации теоремы рассмотрим следующий пример.

Пример 17. На окружности взято 2п точек. Сколькими способами можно соединить попарно эти точки п хордами, не пересекающимися внутри окружности?

Обозначим через ап число способов, которыми можно разбить на пары 2п точек, взятых на окружности, так, чтобы хорды, которые соединяют эти пары точек, не пересекались. Обозначим точки буквами в таком порядке, в котором они размещены на окружности: А1, А2, ..., А2п. Точку А1 можно соединить лишь с одной из точек А2, A4, ..., А2п. в противном случае по каждую сторону от хорды, выходящей из A1, будет размещено нечетное число точек и, значит, при попарном соединении точек между собой по крайней мере одна хорда пересечет хорду, которая выходит из А1.

Определим, сколько существует различных способов соединения точек, при которых А1 соединенная с А2k. По одну сторону от A1A2k размещено 2k — 2 точек; их можно соединить попарно аk-1 способами. По другую сторону от A1A2k размещено 2(п — k) точек; их можно соединить попарно ап-k способами. Комбинируя каждый из аk-1 способов соединения точек А2, ..., A2k-1 с каждым из ап-k способов соединения точек A2k+1, ..., A2n, получим, что число таких способов попарного соединения, при которых A1 соединено с A2k, равно аk-1 ап-k. Но k может принимать значения 1, 2, ..., п, и поэтому

Возьмем а0 = 1, и пусть

— производящая функция последовательности {ап}. Тогда

где п≤1. Умножим обе части предыдущего равенства на sп и просуммируем по п. Тогда

Поскольку

это, применяя теорему о свертке, имеем

A (s) - 1 = sA2 (s). (23)

Решая квадратное уравнение относительно A(s), получим

(24)

Поскольку А(0)= 1, так как а0 = 1, то в формуле (24) нужно выбрать знак минус. Возьмем во внимание, что

Следовательно, производящая функция последовательности {ап} равна

(25)

Теперь остается найти коэффициент при sn в разложении функции (25). Для этого воспользуемся формулой (5). Согласно (5) будем иметь

(26)

Отсюда, согласно (25),

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

Пример 18. Найти число всех перестановок чисел 1, 2, ..., п, в которых т чисел стоят на своих местах.

Пусть А1 — множество тех перестановок, в которых на i-м месте стоит i. Тогда имеем

Микромодуль 17

Индивидуальные тестовые задачи

1. На какое наибольшее число частей могут разделить плоскость п прямых?

2. На какое наибольшее число частей могут разделить пространство п плоскостей?

3. На какое наибольшее число частей могут разделить пространство п сфер?

4. Сколькими способами r различных предметов можно разместить в п ящиках?

5. Сколькими способами r пассажиров могут разместиться в п вагонах поезда?

6. Пусть А (r, п) число таких способов размещения r различных предметов в п ящиках (А(r, п) = 0, если r < п), при которых нет пустых ящиков. Доказать, что

Как следствие установить, что

7. Доказать, что число способов размещения r различных предметов в п ящиках, при которых ровно т ящиков пустые, равно

8. Сколько существует способов размещения r пассажиров в п вагонах поезда, при которых ровно т вагонов будут свободны?

9. Используя результат задачи 6, вычислить сумму

Вычислить производящие функции последовательностей:

10.

11.

Производящая функция последовательности {ап} равна A(s). Вычислить производящие функции последовательностей:

12.

13. bn=can.

14. bn=an+b.

15. bn=an+ an-1+…+a0...

16. bn=an+ an-1a+ an-2a2+ …+a0 an...

17.bn=a2n.

18. Сколькими способами выпуклый п-угольник можно разбить на треугольники диагоналями, которые не пересекаются внутри п-угольника?

19. Вычислить а) φ(100); б) φ(1000); б) φ(р), где р — простое число.

20. Каждый читатель библиотеки прочитал по крайней мере одну книгу из этой библиотеки. О любых k книг из библиотеки (1 ≤k ≤ п, п — число книг в библиотеке) можно сказать, сколько читателей прочитали все эти книги. Как по этим данным установить, сколько читателей в библиотеке?

21. Используя метод включения и исключение, найти число способов размещения r различных предметов в п ящиках, при которых нет пустых ящиков.

22. Используя метод включения и исключение, найти число способов размещения r различных предметов в n ящиках, при которых ровно m ящиков являются пустыми.

23. Пусть Nm(A1, ..., An) — число тех элементов, которые входят по крайней мере в т из множеств A1, ..., Ап. Доеазать, что

24. Найти число способов размещения 8 ладей на шахматной доске так, чтобы они не могли бить друг друга и чтобы ни одна из них не стояла на белой главной диагонали.

25. Будем называть траекторией из точки (0; 0) в точку (х; у) ломаную, соединяющую точки (0;0), (1, s1), .., (k, sk), где

Пусть Тх, у — число траекторий из (0; 0) в (х; у). Доказать, что