Полная версия

Главная arrow Математика, химия, физика

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ   >>

Рекуррентные соотношения, треугольник Паскаля и бином Ньютона

Теоретические сведения

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

Понятие рекуррентных соотношений проиллюстрируем классическим решением определения чисел Фибоначчи.

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

Пусть Т7,, число пар кроликов в стае по прошествии п месяцев, и пусть эта стая состоит из Nп пар приплода и Оп «старых» пар, т.е. Рп = Nn + Оп.

Таким образом, в очередном месяце произойдут следующие события: Оп+1 = Nп + Оп = Рп. Старая стая в (п + 1)-й момент увеличится на число родившихся кроликов в момент времени п.

В последующий месяц эта картина повторяется:

Оц+2

  • *п+2
  • - Оп+1 + Nn+X ~ Оп+-

(1.27)

Объединяя эти равенства, получим следующее рекуррентное соотношение:

Fn+2

Fn+2

= О

п+2

= F.

П+1

+ N п+2

+ Fn

+ 0

п+>

(1.28)

Будем предполагать F0 = О, Fx = 1 (иногда F0 = F{ = 1).

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

Иначе это рекуррентное соотношение имеет вид

F(n + ) = F(n)+ F(n-), (1.29)

где F(n) называются числами Фибоначчи.

Другим примером являются числа Каталина. Они появляются в контексте следующей задачи: нужно найти число различных последовательных действий, чтобы вычислить сумму S0,..., Sn, складывая любые два рядом стоящих числа и результат помещая на их место. Тогда если обозначить искомое число через Сп, то производящая функция будет выглядеть как

с«= OA-і + ССп_2 + с2сп_з +... + ся_2с, + сп_{с0. ( і .зо)

Для чисел Каталана известно и нерекуррентное соотношение:

п + 1

  • (2/7)! п(п + 1)!
  • (1.31)

Таким образом, рекуррентное соотношение стоится следующим образом:

(1.32)

f/(D = с;

ІД/І+ !) = $(/(/!)).

Первая строка системы уравнений показывает глубину рекурсии, т.е. начальное значение, равное константе С. Второе уравнение показывает шаг рекурсии, т.е. выражение формулы в точке п + 1 через суперпозицию ? и значение в точке п.

Например, простейшее рекуррентное соотношение для натуральных чисел задается следующим образом:

(1.33)

Рекурсия может быть каскадной, как в случае чисел Фибоначчи, когда мы опираемся не на одно, а на несколько предыдущих значе-

нии.

Одной из самых известных и изящных числовых схем для порождения рекуррентных соотношений является треугольник Паскаля. Блез Паскаль (1623—1662), французский математик и философ, посвятил ей специальный «Трактат об арифметическом треугольнике».

Треугольник Паскаля — это бесконечная числовая таблица «треугольной формы», в которой на вершине и по боковым сторонам стоят единицы, каждое из остальных чисел равно сумме двух чисел, стоящих над ним слева и справа в предшествующей строке. Таблица обладает симметрией относительно оси, проходящей через его вершину (рис. 1.8).

Строки

О

  • 3
  • 5
  • 1 2 1
  • 13 3 1
  • 4 6 4
  • 5 10 10 5

Рис. 1.8. Треугольник Паскаля

Треугольник Паскаля обладает замечательными свойствами:

• сумма чисел п-й строки треугольника Паскаля равна 2", потому что при переходе от каждой строки к следующей сумма членов

удваивается, а для нулевой строки она равна единице;

  • • все строки треугольника Паскаля симметричны, потому что при переходе от каждой строки к следующей свойство симметричности сохраняется, а нулевая строка симметрична;
  • • каждый член строки треугольника Паскаля с номером п тогда и только тогда делится на К, когда К — простое число, а п — степень этого простого числа.

Существует три способа построения треугольника Паскаля.

  • 1. Каждое число в треугольнике Паскаля равно , где п — номер строки (0, 1, 2,...), а к — номер элемента в строке (0, 1,2,...).
  • 2. Каждое число равно сумме чисел предыдущей диагонали, начиная со стороны треугольника и кончая числом, стоящим над данным (в силу симметричности треугольника Паскаля это утверждение справедливо для любой диагонали).
  • 3. Каждое число треугольника Паскаля, уменьшенное на единицу, равно сумме всех чисел, заполняющих параллелограмм, ограниченный теми правой и левой диагоналями, на пересечении которых стоит данное число, причем сами эти диагонали в рассматриваемый параллелограмм не включаются.

Между рядом Фибоначчи и треугольником Паскаля существует связь. Образуем для каждой восходящей диагонали треугольника Паскаля сумму всех стоящих на этой диагонали чисел. Получим для первой диагонали 1, для второй 1, для третьей 2, для четвертой 3, для пятой 5. Эта последовательность не что иное, как пять начальных чисел Фибоначчи.

Оказывается, что всегда сумма чисел п-й диагонали треугольника Паскаля есть я-е число Фибоначчи.

Тесная связь существует и между треугольником Паскаля и биномом Ньютона. В этом случае нам интересен первый способ построения треугольника Паскаля, через коэффициенты Ск.

Числа Скп возникают как коэффициенты при раскрытии скобок в биноме + Ь)п. Например, рассмотрим бином

(|а + Ь)п = + Ь)(а + Ь)(а + Ь) = а3 + 3 а2Ь + 3 аЬ2 + Ьъ.

Полученные коэффициенты соответствуют числу сочетаний С3,

С, С2, С33. Интерпретировать эти значения можно следующим образом в зависимости от степени одной переменной, например Ь. В первом слагаемом мы не выбираем переменную Ь (0! = 1), во втором слагаемом — одним из трех способов, в третьем — двумя способами из трех, в четвертом слагаемом — тремя из трех способов [7].

В общем виде получаем формулу для бинома Ньютона.

Теорема 1.11. Бином Ньютона

В разложении

(.а + Ь)п = С„° • ап + С ? ап~х ? Ь + С2п ? ап~2Ь2 + ... + Спп • 6",(1.34)

к /|!

  • 1--биноминальные коэффициенты.
  • (п - к)к

Биноминальные коэффициенты Ск в этом случае полезно располагать в виде треугольника Паскаля (рис. 1.9).

Каждая (п + 1)-я строка треугольника Паскаля состоит из биноминальных коэффициентов, получающихся при раскрытии скобок

(а + Ь)п.

С0°

0

с,°

с)

1

С2°

С'

С2

2

сз° сз

С3[1]

с3[2]

3

с1

'“'4

С4[1]

С4[2] с44

4

С1 с[1]

С?

с4 с/

5

Рис. 1.9. Треугольник Паскаля из биноминальных коэффициентов

Теорема 1.12. Полиномиальные коэффициенты

В разложении

(х, + х2 +

+ хтУ- X

П

к ..к-

к+к2+...+кт=пК 1 *

-X* 1Х

X

лт

(1.35)

Рп =-:--полиномиальные коэффициенты.

к] к2...кт

Таким образом, коэффициент при Х1х2[1]...х^" равен числу перестановок п объектов, из которых к| относится к типу 1, к2 относится к типу 2 и т.д.

Задачи

Задача 1.109. Найти рекуррентное соотношение для бесконечной п осл едовател ьн ости

2’ 2[1] ’ ’ 2"’ ""

Решение.

Наша задача состоит в том, чтобы выразить ап+х-й член последовательности на ап. Для это сделаем следующие шаги.

1. Запишем формулу для ап-го члена последовательности:

ап+і _ *

п+1

2п

а

П

П+1 Л

4. Тогда рекуррентное соотношение имеет вид

л;

л:

ап+1 ' ап-

Задача 1.110. Найти рекуррентное соотношение для бесконечной п осл едовател ьн ости

  • 3 3 3 2 3 з
  • ---X + -х--X ... .
  • 2 4 8 16

Решение.

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

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

Во-вторых, первый элемент последовательности не зависит отх.

1. Запишем формулу для ап-го члена последовательности:

Зх"-1 2я '

2. Запишем формулу для ап+ ,-го члена последовательности:

+2 Зх"

а

П+

= (-1)

,п+1 •

3. Разделим ап+гй член последовательности на ап-й и получим

в„+, _ 3-(-1)"+2х" 2" _ х

а„ ~ 2"+|2

4. Тогда рекуррентное соотношение имеет вид

х

Задача 1.111. Найти рекуррентное соотношение для бесконечной последовательности

2 3 4

XX XX

2’ 1-2-3’ 2-3-4’ 3-4-5’

Решение.

Алгоритм решения задачи не изменяется.

1. Запишем формулу для ап-го члена последовательности:

_ х"

  • 77 (п - 1) • п ? (п + 1)
  • 2. Запишем формулу для ап+]-го члена последовательности:

х77+1

  • 77+1 п ? (п + 1) • (п + 2)
  • 3. Разделим ап+]-й член последовательности на ап-й и получим

ап+1 *я+1__(п-)-п-(п + ) = х (п-)

ап п ? (п + ) ? (п + 2) хп (п + 2)

4. Тогда рекуррентное соотношение имеет вид

л:

а -1 2

ап+1 = ^

/7 - 1

п + 2

Я/,.

4 3_2

Пример 1.112. Найти коэффициент при ху I в разложении (х + у + 1)1 ?

Решение.

= 1260.

Коэффициент при х4у3^2 в разложении (х + у +1)1 равен 7!

4!- 3!- 2!

Задача 1.113. Построить рекуррентное соотношение для последо-

3 3 3 2 3 з

вательности- + —х + -х + —х ....

2 4 8 16

Задача 1.114. Построить рекуррентное соотношение для последо-

_ х2 - 3 х3 - 3 х4 - 3

вательности х - 3--+---....

2 4 8

Задача 1.115. Построить рекуррентное соотношение для последо-

х — 1 х2-х х32 х43

вательности-+-+-+-....

2 4 8 16

Задача 1.116. Построить рекуррентное соотношение для последо-

, х2 + 2 х3 + 2х х4 + 2х2

вательности 1--+----1-....

3 4 5

  • [1] Запишем формулу для ап+х-го члена последовательности: ап+ 2«+1'
  • [2] Разделим ап+[-й член последовательности на ап-й и получим
  • [3] Запишем формулу для ап+х-го члена последовательности: ап+ 2«+1'
  • [4] Разделим ап+[-й член последовательности на ап-й и получим
  • [5] Запишем формулу для ап+х-го члена последовательности: ап+ 2«+1'
  • [6] Запишем формулу для ап+х-го члена последовательности: ап+ 2«+1'
  • [7] Запишем формулу для ап+х-го члена последовательности: ап+ 2«+1'
 
<<   СОДЕРЖАНИЕ   >>