Сумма квадратов биномиальных коэффициентов

Решение. В задаче нас интересует только коэффициент при х⁵, поэтому нет необходимости искать все коэффициенты. Член, содержащий х⁵, появится только один раз как слагаемое вида 2⁷(х²)¹(-х³)¹, коэффициент при этом члене согласно полиномиальной формуле будет равен Р(7, 1, 1)=72. Следовательно, коэффициент при х⁵ равен (–1) × 2⁷× 72 =–9 216.

Задача. Найти коэффициенты при х¹² после раскрытия скобок и приведения подобных членов в выражении (1+х²+х⁵)⁸.

Решение. Данная задача отличается от предыдущей тем, что член, содержащий х¹², появится два раза: как слагаемое вида 1²∙(х²)⁶ (х⁵)⁰ и 1⁵ (х²)¹ (х⁵)². В первом случае коэффициент будет равен Р(2, 6, 0)=28, во втором – Р(5, 1, 2)=168. Следовательно, коэффициент при х¹² равен 28+168=196.

Рекуррентные соотношения

Задача. Сколькими способами можно замостить прямоугольную доску размером 2 × 7 костями домино, если все кости считать одинаковыми и учитывать только положение кости: горизонтальное или вертикальное?

Решение. Обозначим через Ф(k) количество способов замостить костями домино прямоугольную доску размером 2 × k. Угловая клетка может быть закрыта одним из двух способов: либо костью, которая лежит вертикально, тогда оставшуюся k–1 кость можно положить Ф(k–1) способами, либо костью, которая лежит горизонтально, тогда еще одну кость можем положить только горизонтально, а оставшиеся k–2 кости можно уложить Ф(k–2) способами. Используя правило суммы, приходим к соотношению Ф(к)=Ф(к–1)+Ф(к–2). Учитывая, что Ф(0)=Ф(1)=1, можем для любого значения k найти ответ: Ф(2)=2, Ф(3)=3, Ф(4)=5, Ф(5)=8, Ф(6)=13, Ф(7)=21. Имеем 21 способ замостить костями домино прямоугольную доску размером 2 × 7.

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

Пример.Используя метод рекуррентных соотношений, можно по-новому вывести формулу для вычисления числа перестановок из k предметов.

Обозначим за Р(k) количество перестановок из элементов k типов. В перестановке на первом месте может быть любой из k предметов, а оставшиеся k–1 предметов можно в каждом из этих случаев переставить Р(k–1) способами. По правилу произведения получаем формулу Р(k)=k∙Р(k-1). Далее замечаем, что Р(1)=1, и получаем, что Р(k)=k!

Числа Фибоначчи

Формула, которую мы получили при решении задачи о домино, впервые была опубликована в книге «Liber Abaci», появившейся в 1202 году, где итальянский математик Фибоначчи среди многих других задач привел следующую:

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

Из условия задачи следует, что через месяц будет две пары кроликов. Через два месяца приплод даст только первая пара кроликов, и получится 3 пары. А еще через месяц приплод дадут и исходная пара кроликов, и пара кроликов, появившаяся два месяца тому назад. Поэтому всего будет 5 пар кроликов.

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

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

Так как, по условию, F(0)=1 и F(1)=2, то последовательно находим

F(2)=3, F(3)=5 F(4)=8 и т. д.

Полученные числа называют числами Фибоначчи.

Чтобы найти F(12), нам придется последовательно вычислить F(3), F(4), … F(11), что достаточно долго. А если нам необходимо было бы вычислить F(100), то это займет еще больше времени. Попробуем выразить закономерность последовательности Фибоначчи с помощью расчетной формулы (вместо неявного рекуррентного соотношения). Для этого присвоим двоичный номер каждой паре кроликов. Единицам соответствуют месяцы появления на свет одной из пар «предков» данной пары (включая и исходную), а нулями – все остальные месяцы. Например, последовательность 010010100010 устанавливает такую «генеалогию» – сама пара появилась в конце 11-го месяца, ее родители – в конце 7-го месяца, «дед» – в конце 5-го месяца, «прадед» – в конце 2-го месяца. Исходная пара кроликов зашифровывается при этом последовательностью 000000000000. В последовательности не могут идти подряд две единицы, так как кролики приносят приплод только на второй месяц после рождения.

Тем самым устанавливается связь между числами Фибоначчи и следующей комбинаторной задачей: найти число n-последовательностей, состоящих из нулей и единиц, в которых никакие две единицы не идут подряд. Число таких последовательностей, в которые входит ровно k единиц и n–k нулей, равно . Так как при этом должно выполняться неравенство k<=n–k+1, то k изменяется от 0 до целой части числа (n+1)/2. Применяя правило суммы, получаем F(n)= , где p – целая часть числа (n+1)/2.

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