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

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

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

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

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

Пусть — число пар кроликов в стае по прошествии п месяцев, и пусть эта стая состоит из Ып пар приплода и Оп «старых» пар, т.е. рп = ы„ + оп.

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

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

(1.26)

Оп+2 - Оц+1 + N'п+ - Fn+l; ^ п+2 — Оп+Х.

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

- °п+2 + Nn+2

= F„+i + F„.

+ 0

/7+1’

(1.27)

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

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

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

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

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

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

С„ = С0Сп_ і + С,С/7_2 + С2Сп_ з + ... + Сп_2С{ + Сп_хС0. ( 1.29)

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

Сп = -Sg- = (2я)! . (1.30)

/7+1 п(п + )

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

[/(1 ) = с;

  • (1.31)
  • 1/(/1 + 1) = 5(/(/1».

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

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

(1.32)

ах = 1;

ап+ ~ ап !•

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

Рассмотрим несколько примеров.

Задача 1.28

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

Решение.

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

хп

  • 1. Запишем формулу для а., члена последовательности а., = —.
  • 2. Запишем формулу для ап+х члена последовательности
  • *"+1 ^77+1 2"+1
  • 3. Разделим ап+х член последовательности на ап и получим

х"*' 2" _ х 2м1 ' х" ~ 2'

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

X

Задача 1.29

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

  • 3 3 3 2 3 з
  • ---х + -х--л: ....
  • 2 4 8 16

Решение.

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

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

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

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

Зх"~'

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

Зхп

~>п+1 •

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

«У, 3-(-1 ГУ Г

а„ 2"*' 3-(-1)"+1х"-‘

X

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

х

Задача 1.30

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

2 3 4

XXX X

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

Решение.

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

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

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

4.

х

/7

ап =

  • 2.
  • (п - 1) • п ? (п + 1)

Запишем формулу для ап+х члена последовательности:

п+1

X

ап+1

3.

/7 • (« + 1) • (л + 2)

Разделим я,7+1 член последовательности на ап и получим

а

/7 + 1

/7+1 _

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

  • (п - 1) • п ? (п + 1) _ (п - 1)
  • — X

X

п

{п + 2)

X

п - 1 п + 2

V

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

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

Строки

  • 1 О
  • 1 1 1 12 1 2
  • 13 3 1 3
  • 14 6 4 1 4
  • 1 5 10 10 5 1 5

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

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

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

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

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

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

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

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

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

(а + Ь)п = (а + Ь)(а + Ь)(а + Ь) = а3 + ЪсгЬ + 3 аЬ2 + Ь3.

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

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

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

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

В разложении

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

С* =-1--биноминальные коэффициенты.

(п-к)к

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

С3°

Сі

г°

Г1

с,°

с]

г°

Г1

С2

С2

с,1

С32

С53

Строки

  • 1
  • 3
  • 5

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

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

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

В разложении

(хх + х2 +

п

к]+к2+...+к„1=п*

?ххх^

у кщ . .Лт

(1.34)

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

к к2...кт

Таким образом, коэффициент при х^хх22 •••х%п равен числу перестановок п объектов, из которых к{ относится к типу 1, к2 относится к типу 2 и т.д.

Например, коэффициент при х4у3і2 в разложении (х+у + г)7 равен

  • 7!
  • 4!- 3!- 2!

= 1260.
 
< Пред   СОДЕРЖАНИЕ     След >