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

Треугольник Паскаля1. Связь Треугольника Паскаля с биномом Ньютона
2. Cвойства биноминальных коэффициентов
3. Cвойства треугольника Паскаля

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

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

Известно, что
(a+b)o=1
(a+b)1=a+b
(a+b)2=a2+2ab+b2
(a+b)3=a3+3a2b+3ab2+b3

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

Теорема

Имеет место равенство:
(a+b)n = Con an bo + C1n an-1
b1 +.....+ Ckn an-k bk +.....+ Cnn ao bn (1)

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

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

Доказательство формулы Ньютона можно провести несколькими способами.
Самый традиционный способ - доказательство с помощью метода математической индукции.

Второй способ основан на методе производящих функций.
Докажем формулу (1) для частного случая:
a = 1, b = x, т.е докажем формулу:

(1+x)n=1+ nx + n(n-1)x2/2! + n(n-1)(n-2)x3/3! +....+ xn (2)

Обозначим коэффициенты в разложении (1+x) при степенях x через B0, B1, B2, ...Bn, т.е

(1+x)n= B0 + B1x + B2x2 +...+ Bnxn (3)

Подставив в записи (3) x=0, найдем значение B0=1.
Возьмем затем производную от обоих частей равенства (3), то получим:

n(1+x)n-1= B1 + 2B2x + ...+ nBnxn-1 (4)

Отсюда,при x=0 находим B1=n.

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

n(n-1)(1+x) = 2B2 +....+ n(n-1)Bnxn-2 (5)


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



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



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

  1. Одно из важных свойств биноминальных коэффициентов заключается в следующем равенстве: Ckn = Ck n-1 + Ck-1n-1 (6) .

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



    Утверждение. Число различных кратчайших путей на этой сетке, ведущих из левого нижнего угла ( из точки О(0,0)) в правый верхний угол (в точку В(K,N)) равно Ckn+k.

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

    Следовательно, Ckn =Ckn-1+ Ck-1n-1.

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

    n
    0 1
    1 1 1
    2 1 2 1
    3 1 3 3 1
    4 1 4 6 4 1
    5 1 5 10 10 5 1
    ... ... ... ... ... ... ... ... ... ... ... ...



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

    C0n+ C1n+ C2n +...+ Cnn =2n (7)



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

    Первый способ основан на комбинаторных идеях.
    Рассмотрим следующую задачу. В доме имеется n лампочек. Сколькими способами можно включить k лампочек ( 0<=k<=n), если у каждой из них свой выключатель?
    С одной стороны, для каждой лампочки имеется только две возможности (быть включенной или не быть включенной), т.к всего лампочек n, то по правилу произведения получаем 2n способов.
    С другой стороны, из n лампочок можно выбрать и включить 0,1,2,3,...,n лампочек.
    Количество способов можно тогда записать через число сочетаний: C0n+ C1n+ C2n+...+ Cnn.

    Из сказанного выше следует, что C0n+ C1n+ C2n+...+ Cnn =2n.

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

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


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



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


    1
    1 1
    1 0 1
    1 1 1 1
    1 0 0 0 1
    1 1 0 0 1 1
    .... .... .... .... .... .... .... .... .... .... .... .... ....


    рис.4


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


    1
    1 1
    1 0 1
    1 1 1 1
    1 0 0 0 1
    ... ... ... ... ... ...


    рис.5


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


    1
    1 1
    1 0 1
    1 1 1 1
    1 0 0 0 1
    ... ... ... ... ... ...


    рис.6


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




    рис.7


    Рассмотрим квадраты 4x4 полученного таким образом квадрата. В этом квадрате 16 клеток (см.рис.8).




    рис.8


    Закономерность будет верна для любого m.

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


    « назад в меню