Треугольник Паскаля и его связь с биномом Ньютона

Связь Треугольника Паскаля  с биномом Ньютона 

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

Иэвестно, что  
(a+b)^o=1  
(a+b)¹=a+b  
(a+b)²=a²+2ab+b²  
(a+b)³=a³+3a²b+3ab²+b³

Но, как раскрывать скобки при вычислении выражения (a+b)ⁿ? Ответ на этот вопрос дает следующая теорема.  

Теорема

Имеет место  равенство:  (a+b)ⁿ = C^o_n aⁿ b^o + C¹_n a^n-1 b¹ +.....+  C^k_n a^n-k b^k +.....+  Cⁿ_n a^o bⁿ   (1)

где С^k_n= n! / (k!(n-k)!)  

Эту теорему  иногда называют биноминальной теоремой, а числа C ^к_n - биноминальными коэффициентами. Равенство(1) часто называют биномом Ньютона, хотя это название исторически не является справедливым, т.к формулу для  (a+b)ⁿ знали еще среднеазиатские математики Омар Хайям (1048-1131),   Гийас ад-Дин Джелд ал-Коши (ум.ок 1430). В Западной Европе до Ньютона ее знал Паскаль (1623-1662). Заслуга Ньютона состоит в том, что он обобщил эту формулу для нецелого показателя n.

Доказательство  формулы Ньютона можно провести несколькими способами.

Самый традиционный способ - доказательство с помощью  метода математической индукции.(Докажите самостоятельно). 
 
Второй способ основан на методе производящих функций.  
Докажем формулу (1) для частного случая:  
a = 1, b = x, т.е докажем формулу: (1+x)ⁿ=1+ nx + n(n-1)x²/2! + n(n-1)(n-2)x³/3! +....+ xⁿ  (2)

Обозначим коэффициенты в разложении (1+x) при степенях x через B₀, B₁, B₂, ...B_n, т.е

(1+x)ⁿ= B₀ + B₁x + B₂x² +...+ B_nxⁿ  (3)

Подставив в  записи (3)  x=0, найдем значение B₀=1. Возьмем затем производную от обоих частей равенства (3), то получим:  n(1+x)^n-1= B₁ + 2B₂x + ...+ nB_nx^n-1 (4) Отсюда,при x=0 находим B₁=n. 

Теперь возьмем  вторую производную от обоих частей равенства  (3), получим:

n(n-1)(1+x) =  2B₂ +....+ n(n-1)B_nx^n-2 (5)

При x=0 получаем B₂ = n (n-1) / 2 и т.д.  На k-том шаге при вычислении k-й производной для равенства (3), получим B_k = (n (n-1)(n-2)....(n-k)) / k! ,  ч.т.д. 
 

На  содержание

Cвойства биноминальных коэффициентов 

Рассмотрим теперь некоторые из свойств биноминальных  коэффициентов.

1. Одно из важных свойств биноминальных коэффициентов заключается в следующем равенстве: C^k_n = C^k _n-1 + C^k-1_n-1 (6) Докажите это свойство непосредственным вычислением самостоятельно.

Но, мы предлагаем вам более интересный способ доказательства. Для это рассмотрим прямоугольную сетку размерами k x n (см. рис 1) и сформулируем следущее утверждение.

 
Утверждение.  Число различных кратчайших путей на этой сетке, ведущих из левого нижнего угла  ( из точки О(o,o)) в правый верхний угол (в точку В(k,n)) равно C^k_n+k.

Тогда, воспользовавшись данным утверждением, можно заключить, что число различных кратчайшых путей из точки О(0,0) в точку А(k, n-k) равно  C^k_n . Все такие пути можно разделить на две группы: 1) пути, проходящие через точку А1(k-1,n-1). Их число равно  
C^k-1_n-1. 2) пути, проходящие через точку А2(k,n-k-1). Их число равно C^k _n-1 (См. рис.2.) Следовательно, C^k_n =C^k_n-1+ C^k-1_n-1 . 

 
Используя равенство (6), можем выписать последовательно биноминальные  коэффициенты в виде треугольной  таблицы (рис.3), которая называется треугольником Паскаля.

 

   
рис.3

2. Следующим свойством биноминальных коэффициентов является равенство: 
   

C⁰_n+ C¹_n+ C²_n +...+ Cⁿ_n =2ⁿ    (7)

Это равенство  можно заметить, разглядывая треугольник  Паскаля: сумма чисел, стоящая в n-й  строке, равна 2ⁿ. Доказательство этого равенства можно также привести несколькими способами.

Первый способ основан на комбинаторных идеях. Рассмотрим следующую задачу. В доме имеется n  лампочек сколькими способами можно включить k лампочек ( 0<=k<=n), если у каждой из них свой выключатель? 
С одной стороны, для каждой лампочки имеется только две возможности (быть включенной или не быть включенной), т.к всего лампочек n, то по правилу произведения получаем  2ⁿ способов. С другой стороны, из n лампочок можно выбрать и включить 0,1,2,3,...,n лампочек. Количество способов можно тогда записать через число сочетаний: C⁰_n+ C¹_n+ C²_n+...+ Cⁿ_n . Из выше сказанного следует, что C⁰_n+ C¹_n+ C²_n+...+ Cⁿ_n =2ⁿ.

Свойство 2 можно также доказать, используя  формулу (3) бинома Ньютона, подставив  в нее x=1. Можно для доказательства формулы (6) опять использовать метод  математической индукциию.

А теперь перейдем к рассмотрению самого треугольника Паскаля и сформулируем некоторые  основные свойства.  

На  содержание

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

1. Заменим в треугольнике Паскаля четные числа на 0, а нечетные на 1, (т.е рассмотрим треугольник Паскаля по модулю 2) . (рис.4)

 
 

   рис.4

Можно ли увидеть на рисунке 4 какую-нибудь закономерность? Да! Развернем треугольник Паскаля, так как показкно на рисунке 5.

рис.5.

Тогда видно, что все числа расположены  левее диагонали квадрата.(рис 6).

рис.6

Нарисуем  наш треугольник на клетчатой  бумаге так, чтобы каждое число стояло в отдельной клетке. Раскрасим  клеточки следующим образом: если в  клетке стоит число 0, то красим ее белым  цветом, если стоит число 1, то-черным (рис.7).