новая папка 1 / 298011

Шаг 3. Теперь сложим уравнения для всех значений n :

a0 + a1x + anxn = x + 5 an−1xn − 6 an−2xn.

Левая часть уравнения в точности равна G(x) , а в правой части есть суммы, очень похожие на функцию G(x) , но не равные ей. Эти суммы нужно привести к виду G(x) :

Шаг 4. Теперь исходное уравнение для производящей функции при-

нимает вид:

G(x) = x + 5xG(x) − 6x2G(x),

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

x

G(x) = 1 − 5x + 6x2 .

Осталось разложить в ряд полученную производящую функцию. Для этого разобьем полученную дробь на простые (элементарные) дроби.

11

С другой стороны, мы искали G(x) в виде

∑∞

G(x) = anxn,

n=0

поэтому в силу единственности представления функции в виде степенного ряда (см. стр. 5 настоящего пособия)

an = 3n − 2n ( для n ≥ 0).

Пример 2. Решить рекуррентное соотношение an = 6an−1 −8an−2+ +n (n ≥ 2) c начальными данными a0 = 1 , a1 = 2 с помощью производящей функции. Согласно приведенному на стр. 10 алгоритму запишем условия в виде:

1 · a0 = 1 · 1,

x · a1 = 2 · x,

xn · an = (6an−1 − 8an−2 + n)xn, n ≥ 2.

Теперь сложим уравнения для всех значений n :

a0 + a1x + anxn = 1 + 2x + 6 an−1xn − 8 an−2xn + nxn.

n=2

Преобразовать последнюю сумму очень просто, если вспомнить о производной

12

Последняя сумма может быть свернута:

Таким образом, уравнение (21) принимает вид

G(x) = 1 − 4x + 6xG(x) − 8x2G(x) + x2(2 − x). (1 − x)2

Это уравнение для производящей функции. Из него выражаем G(x) :

1 − 6x + 11x2 − 5x3 G(x) = (1 − 6x + 8x2)(1 − x)2 .

Разложим знаменатель на множители и разобьем дробь на сумму простых дробей:

Воспользовавшись формулами (8), (15) и (16), окончательно получим

Упражнения:

1.Решить следующие рекуррентные соотношения с помощью производящей функции:

1) a0 = 2, an = 4an−1 (n ≥ 1) ;

13

2)a0 = 3, an = 5an−1 (n ≥ 1) ;

3)a0 = 6, an = an−1 + 2 (n ≥ 1) ;

4)a0 = 7, an = an−1 + 4 (n ≥ 1) ;

5)a0 = 2, a1 = 7, an = 2an−1 + 3an−2 (n ≥ 2) ;

6)a0 = 3, a1 = 5, an = 2an−1 + 8an−2 (n ≥ 2) ;

7)a0 = 1, an = 3an−1 + 2n (n ≥ 1) ;

8)a0 = 1, an = 4an−1 + 3n (n ≥ 1) ;

9)a0 = 2, an = 3an−1 + n (n ≥ 1) ;

10)a0 = 3, an = 2an−1 + n (n ≥ 1) .

§5. Производящие функции и комбинаторные подсчеты

Производящие функции находят широкое применение при решении задач перечислительной комбинаторики. Они заключаются в подсчете числа выборок, состоящих из элементов, принадлежащих некоторому конечному или бесконечному множеству элементов произвольной природы.Число таких выборок и процесс выбора предполагаются ограниченными. В этом случае множество выборок конечно, и поэтому его мощность можно подсчитать, расположив в определенном порядке его элементы – выборки. При большом количестве выборок сделать это довольно трудно. Поиск простых решений задач перечислительной комбинаторики приводит к производящим функциям. В зависимости от видов исследуемых комбинаций в качестве производящих функций можно использовать многочлены (бином Ньютона), степенные ряды (числа Фибоначчи), экспоненциальные ряды и другие.

Пусть E = {e1, e2, . . . , en} – множество элементов, из которых строятся различные комбинации – выборки. Это могут быть как упорядоченные выборки (размещения, перестановки), так и неупорядоченные (сочетания с повторениями и без повторений). Это могут быть комбинации элементов из E , подчиненные различным ограничениям, как например в задаче о счастливых билетах (автобусный билет называют счастливым, если сумма трех первых цифр его номера равна сумме трех последних).

Иногда в образовании комбинаторных комбинаций используется не одно, а несколько множеств, тогда в качестве E можно взять объединение всех участвующих в формировании выборок элементов.

Задача перечислительной комбинаторики состоит в том, чтобы найти число выборок, подчиненных некоторым ограничениям и состоящих

14

из объектов, принадлежащих множеству E . Полезно при этом использовать производящие функции. Производящая функция должна содержать столько множителей, сколько элементов содержит множество E . Это следует из правила произведения для комбинаторных объектов. Каждый множитель представляет собой многочлен степени k , где k – максимальное количество возможностей присутствия элемента, соответствующего этому множителю, в различных комбинациях – выборках.

Вприведенных ниже примерах иллюстрируются возможности учета другого вида ограничений на выборки.

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

Начнем с примера: рассмотрим произведение

(1+e1x)(1+e2x)(1+e3x) = 1+(e1+e2+e3)x+(e1e2+e1e3+e2e3)x2+e1e2e3x3.

Здесь коэффициенты перед x формально представляют собой сочетания без повторений из множества {e1, e2, e3} по k . Если нас интересует только количество сочетаний без повторений, можем подставить e1 = e2 = e3 = 1 . Получим производящую функцию для последовательности {C3k}, k = 0, 3 . Эта функция

f(x) = (1 + x)3 = 1 + 3x + 3x2 + x3.

Каждый множитель (1 + x) соответствует одному элементу. Каждый элемент ei может либо не входить в сочетания либо входить один раз, поэтому соответствующий множитель содержит 1 или x .

Для количества сочетаний без повторений из n элементов производящая функция имеет вид

Перейдем к сочетаниям с повторениями. Рассмотрим произведение

(1 + e1x + e21x2)(1 + e2x)(1 + e3x) = 1 + (e1 + e2 + e3)x+

+(e1e2 + e1e3 + e2e3 + e1e1)x2 + (e1e2e3 + e1e1e2 + e1e1e3)x3 + e1e1e2e3x4.

В данном случае каждое слагаемое в коэффициентах при xk , k = 1, 4 , можно рассматривать как сочетание с повторениями из множества {e1, e2, e3} по k , причем элемент e1 имеет кратность2, не превосходя-

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

15

щую 2, а кратность элементов e2, e3 не более единицы. Так как нас интересует только количество сочетаний, снова возьмем e1 = e2 = e3 = 1 . Получаем равенство

Как нетрудно видеть, коэффициент при xk , k = 1, 4 в (23) равен числу таких сочетаний и, следовательно, производящей функцией последовательности таких сочетаний является функция

(1 + x + x2)(1 + x)2.

Если элемент входит в сочетания k = 0, 1, 2, . . . раз, то ему соответствует множитель вида

1 + eix + e2i x2 + e3i x3 + . . . + eki xk + . . . .

Если нас интересует количество сочетаний, то ei = 1 . Получаем для каждого элемента множитель

Так что производящая функция для количества сочетаний с повторениями из n элементов (e1, e2, . . . , en) имеет вид

Пусть теперь имеются некоторые ограничения на состав сочетаний. Например, элемент должен входить не менее m раз. Тогда ему в

производящей функции соответствует множитель

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

16

В общем случае в множитель, соответствующий каждому элементу, входит степень переменной, удовлетворяющей нашему условию.

Пример 3. Определим, сколько существует способов выбора 10 объектов из множества объектов трех типов, если число объектов первого типа – не менее 4, число объектов второго типа – не более 2, число объектов третьего типа кратно 3.

Производящая функция имеет следующий вид:

Нас интересует коэффициент при x10 , ему же соответствует коэффициент при x6 выражения, стоящего в скобках.

Из формулы (24) находим

Упражнения

1.Найти производящую функцию для сочетаний из 3-х элементов, в котором каждый элемент встречается не менее одного раза.

2.Найти число решений в целых неотрицательных числах уравнения

x1 + 2x2 + 3x3 = n.

3.Найти производящую функцию, в которой коэффициент при xn определяет число решений уравнения

e1 + e2 + e3 + e4 = n,

где e1 ≤ 2 , e2 ≥ 3 , e3 четно, e4 нечетно.

4.Сколько последовательностей длины 6 можно сформировать из целых чисел 1, 2, 3, если должно быть не менее одной цифры 1, двух цифр 2, нечетное количество цифр 3?

17

§6. Задача о счастливых билетах

Одним из классических примеров использования производящих функций является задача о счастливых билетах.

Троллейбусный (трамвайный) билет имеет номер, состоящий из шести цифр. Билет считается счастливым, если сумма первых трёх цифр равна сумме последних трёх, например, 024321. Первая цифра номера билета может быть нулём. Известно, что количество счастливых билетов из шести цифр равно 55252. Но как это число было получено? Вообще, как решать более сложную задачу: для любого положительного целого n указать количество 2n -значных счастливых билетов?

Мы рассмотрим один из методов решения данной задачи техникой производящих функций. Обозначим количество счастливых билетов из 2n цифр символом Ln . Введем еще одно обозначение: Dnk — количество n -значных чисел с суммой цифр, равной k (число может начинаться с цифры 0).

Билет состоит из двух частей. Рассмотрим произвольный счастливый билет, скажем, 271334 и заменим цифры второй его части на величину, которой им не хватает до 9: то есть 271665. Теперь сумма всех цифр билета равна 27. Легко заметить, что такой "фокус"проходит с любым счастливым билетом. Таким образом, количество счастливых билетов из 2n цифр равно количеству 2n -значных чисел с суммой цифр, равной

9n , то есть

Ln = D29nn.

Выпишем производящую функцию G(x) , коэффициент при xk у которой будет равен D1k :

G(x) = 1 + x + x2 + x3 + x4 + x5 + x6 + x7 + x8 + x9.

Действительно, сумму k с помощью одной цифры (для k = 0, . . . , 9 ) можно представить одним способом. Для k > 9 — ноль способов.

Заметим, что если возвести функцию G(x) в квадрат, то коэффициент при xk будет равен числу способов получить сумму k с помощью двух цифр от 0 до 9:

G2(x) = 1 + 2x2 + 3x2 + 4x3 + 5x4 + 6x5 + ...

... + 6x13 + 5x14 + 4x15 + 3x16 + 2x17 + x18.

В общем случае, Gn(x) — это производящая функция для чисел Dnk поскольку коэффициент при xk получается перебором всех возможных комбинаций из n цифр от 0 до 9, равных в сумме k . Перепишем

18

производящую функцию в ином виде:

G(x) = 1 + x + . . . + x9 = 1 − x10 .

1 − x

В итоге, нам требуется отыскать

[x27]G6(x).

Для этого посмотрим, что будет получаться, если раскрывать скобки в следующем выражении (нас интересуют только коэффициенты при x27 ), при раскрытии скобок воспользуемся формулами (4) и (18):

§7. Экспоненциальная производящая функция

Экспоненциальная производящая функция – это функция, задаваемая степенным рядом вида

При использовании производящей функции бинома Ньютона коэффициенты при xk показывают число способов, которыми можно выбрать k предметов из n предметов. Коэффициент при xk/k! при использовании экспоненциальной производящей функции дает число способов, которыми k предметов можно выбрать и переупорядочить, другими словами, число упорядоченных k -выборок из n предметов.

Экспоненциальной производящей функцией последовательности {Akn} числа размещений является функция

Для получения числа k -выборок с неограниченным повторением (любой элемент может повторяться в данной k -выборке произвольное

19

число раз) из множества, состоящего из n элементов, рассмотрим производящую функцию

Пример 4. Составляются слова из цифр 0, 1, 2. В каждом слове цифра 0 должна встречаться не менее двух раз, цифра 1 – не более трех раз, а цифра 2 входит нечетное число раз. Определим соответствующую

Упражнения:

1.Составляются слова из цифр 0, 1, 2. В каждом слове цифра 0 должна встречаться не более четырех раз, цифра 1 – не менее пяти раз, а цифра 2 входит четное число раз. Определить соответствующую экспоненциальную производящую функцию.

2.Найти число 3-выборок из множества {e1, e2, e3}, в которые элемент e1 может входить не более одного раз, элемент e2 входит обязательно, но не более двух раз, элемент e3 либо не входит, либо входит два раза.

3.Найти производящую функцию для размещений из 3-х элементов, в котором каждый элемент встречается не менее двух раз.

4.Имеется множество M = {a, b, c}, из элементов которого строятся пятиместные размещения со следующими ограничениями на частоту появления элементов:

а) элемент a может входить в размещения не более одного раза; б) элемент b может входить в размещения один или два раза;

в) элемент c может входить в размещения неограниченное число раз.

Чему равно число размещений описанного типа?

20