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

.

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

Знакопеременная сумма биномиальных коэффициентов

.

Воспользуемся формулой бинома Ньютона в которой положим а=1 и b=-1.

Как и при доказательстве основного свойства, используем равенство

(1+x)ⁿ= .

Умножим обе части этого равенства на (1+х)ⁿ:

(1+x)²ⁿ= .

Выражение в левой части равенства снова разложим по формуле бинома Ньютона. Рассмотрим коэффициент при хⁿ. Слева он будет равен . В правой части член, содержащий хⁿ, появится n раз: при умножении на , при умножении на , и так далее. Используем свойство симметричности биномиальных коэффициентов, получим коэффициент при хⁿ в правой части равенства:

.

Так как слева и справа стоит один и тот же многочлен, то коэффициенты при хⁿ слева и справа должны быть одинаковыми. Поэтому .

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

Другая, известная как треугольник Паскаля, интерпретация для биномиальных коэффициентов получается, если рассмотреть на бесконечной шашечной доске количество различных путей шашки от данной клетки до всех клеток доски.

Возьмем шахматную доску, ограниченную только с одной стороны, и поставим на поле A (черного цвета) нулевой горизонтали шашку. Двигаясь по правилам игры в шашки, она может попасть на любое поле черного цвета из области, ограниченной прямыми AB и AC. Напишем на каждом поле число способов, которыми можно попасть на данное поле. Получим

А

В С

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

Арифметический треугольник можно записать и в таком виде:

В данном треугольнике, в каждой клетке хранится количество способов попасть в эту клетку из клетки (0, 0), если ходить разрешается только вниз и по диагонали вправо. Каждое число треугольника равно сумме числа, стоящего выше него, и числа, расположенного наискосок влево. На пересечение k-й вертикали и n-й горизонтали можно попасть за n шагов, k из которых будут по диагонали, n – k по вертикали. Поэтому количество способов попасть в клетку с координатами (n, k) равно .

Отметим еще следующие особенности арифметического треугольника: все элементы, расположенные выше главной диагонали, равны нулю, а нулевой столбец состоит из единиц. Числа, стоящие в n-й строке, являются коэффициентами в разложении бинома (1+x)ⁿ по степеням x. Поэтому их называют также биноминальными коэффициентами.

Задача. Раскрыть скобки и привести подобные члены в выражении (х+у)⁵.

Решение. Пятая строка треугольника Паскаля имеет вид: 1 5 10 10 5 1. Поэтому

(х+у)⁵=1x⁰y⁵+5x¹y⁴+10x²y³+10x³y²+5x⁴y¹+1x⁵y⁰.

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

Полиномиальная формула

Полиномом называют выражение вида (x₁+x₂+…x_k)ⁿ.

Полиномиальной формулой называют формулу для вычисления значения выражений (x₁+x₂+…x_k)ⁿ для различного числа слагаемых и различных натуральных степеней n.

Теорема.

Доказательство. Формула доказывается аналогично формуле бинома Ньютона.

Запишем (x₁+x₂+…x_k)ⁿ в виде произведения n сомножителей (x₁+x₂+…x_k)∙(x₁+x₂+…x_k)∙…∙(x₁+x₂+…x_k).

Раскроем скобки в правой части этого равенства и запишем все слагаемые в виде произведения n сомножителей x₁, x₂,…,x_k в том порядке, в котором они появляются. Получим всевозможные размещения с повторениями букв x₁, x₂,…,x_k, состоящие из n элементов. Используем коммутативность и приведем подобные члены. Подобными будут члены, содержащие одинаковое количество множителей x₁, x₂,…,x_k. Членов, в которые входит k₁ множителей х₁, k₂ множителей х₂ и так далее k_m множителей х_m, ровно Р(k₁,k₂,…k_m). Отсюда вытекает, что после приведения подобных членов выражение войдет с коэффициентом . Поэтому формула примет вид: .

Свойства чисел Р(k1k2…k3)

1. .

Доказательство. Если в полиномиальной формуле положить х₁=х₂=…=х_m=1, то получим требуемое равенство.

2. .

Доказательство. Умножим обе части равенства

на (х₁+х₂+…+х_m). Получим

.

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

.

Задача. Раскрыть скобки и привести подобные члены в выражении (x+y+z)⁴, используя полиномиальную формулу.

Решение. Ясно, что коэффициенты при x²yz и xy²z равны. Поэтому достаточно найти коэффициенты для таких разбиений n=k₁+k₂+…k_m, что k_1³k_2³…_³k_m, а потом переставлять показатели всеми возможными способами. Для нашего примера имеем:

4=4+0+0; 4=3+1+0; 4=2+2+0; 4=2+1+1;

Р(4,0,0)=1; Р(3,1,0)=4; Р(2,2,0)=6; Р(2,1,1)=12.

(x+y+z)⁴=

=x⁴+y⁴+z⁴+4x³y+4x³z+4y³x+4y³z+4z³x+4z³y+6x²y²+6x²z²+6y²z²+12x²yz+12xy²z+12xyz².

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

Решение. В задаче нас интересует только коэффициент при х⁵, поэтому нет необходимости искать все коэффициенты. Член, содержащий х⁵, появится только один раз как слагаемое вида 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-го месяца, “прадед” – в конце второго месяца. Исходная пара кроликов зашифровывается при этом последовательностью 000000000000. в последовательности не могут идти подряд две единицы, так как кролики приносят приплод только на второй месяц после рождения.

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

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

Дата добавления: 2014-12-29