Увлекательные диагонали треугольника Паскаля

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

Например, одним из таких свойств является то, что сумма n-го ряда треугольника Паскаля имеет вид

2^{n}

2n.

Важно отметить, что строки и столбцы работают по индексу, основанному на 0, подобно тому, как мы привыкли работать с массивами в программировании.

Содержание

Некоторые важные моменты
Задача
Часть 1: n-й член
Часть 2: сумма k-й строки
[БОНУС] Часть 3: сумма креста
Заключение

Некоторые важные моменты

Каждому числу в треугольнике Паскаля может быть присвоено значение

(\frac{строка}{столбец})

(колонкастрока) пара координат. Примером этого является то, что 20 происходит в точке

(\frac{6}{3})

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

(\frac{n}{k})

(kn) где n — строка, а k — столбец:

(\frac{n}{k}) = \frac{n!}{k! (n — k)!}

(kn)=k!(n—k)!n!

Задача

Как найти сумму диагональных линий треугольника Паскаля? Горизонтальные линии просты как

2^{n}

2nтак ли это просто? Не совсем. Быстрый способ решить эту задачу — сделать из нее больше задач, и две из них мы рассмотрим ниже:

Каков n-й член диагональной линии k?
Какова сумма диагональной линии k?
БОНУС: Чему равна сумма пересечения диагональных линий k и -k?

Часть 1: n-й член

Важное замечание, которое необходимо сделать перед решением этой части задачи, показано выше. Между линиями k и -k существует симметрия, это показано выше линиями 2 и -2. Это означает, что в нашей формуле n-го члена мы должны обозначать k как |k|, чтобы сохранить эту симметрию (так как она всегда будет положительной).

Давайте пока будем работать только с линией k = 2 (игнорируя симметричную k = -2). Ниже приведены координаты этой линии, нанесенные на наш треугольник.

Мы видим, что все координаты столбцов = 2. Если мы ищем n-й член, то координата строки становится равной n + 1. Это означает, что любая координата в этой строке имеет вид:

(\frac{n + 1}{2}) = \frac{(n + 1)!}{2! (n — 1)!} = \frac{1}{2} [n (n + 1)] = \frac{1}{2} [n^{2} + n]

(2n+1)=2!(n—1)!(n+1)!=21[n(n+1)]=21[n2+n]

Это и есть наша формула для n-го члена k = 2. Давайте подтвердим это с помощью следующего кода:

def secondRow(n):
    return (pow(n, 2) + n) // 2

for i in range(5):
    print(secondRow(i + 1))

Войти в полноэкранный режим Выйти из полноэкранного режима

Для ряда k = 3 аналогичная история:

(\frac{n + 2}{3}) = \frac{(n + 2)!}{3! (n — 1)!} = \frac{1}{6} [n (n + 1) (n + 2)] = \frac{1}{6} [n^{3} + 3 n^{2} + 2 n]

(3n+2)=3!(n—1)!(n+2)!=61[n(n+1)(n+2)]=61[n3+3n2+2n]

Отсюда довольно просто заметить, что для любой диагональной линии k, n-й член дается в виде

\frac{1}{∣ k ∣!} \prod_{j = 0}^{∣ k ∣ — 1} (n + j)

∣k∣!1j=0∏∣k∣—1(n+j)

Это аккуратно сводится к

\frac{(n + ∣ k ∣ — 1)!}{∣ k ∣! (n — 1)!}

∣k∣!(n—1)!(n+∣k∣—1)!который является n-м членом строк k и -k. Первая часть решена.

Часть 2: сумма k-й строки

Мы проделали всю тяжелую работу в первой части, теперь все становится проще. Чтобы найти сумму k-й строки, мы должны выбрать n-й член для суммирования, поскольку эти диагонали теоретически могут продолжаться бесконечно. Мы можем выразить это в нотации суммирования и затем просуммировать довольно просто, как показано ниже:

\sum_{j = 1}^{n} \frac{(j + ∣ k ∣ — 1)!}{(j — 1)! ∣ k ∣!} = \frac{(∣ k ∣ + n) (∣ k ∣ + n + 1)!}{(∣ k ∣ + 1) (n — 1)! ∣ k ∣!} = \frac{n (∣ k ∣ + n)!}{(∣ k ∣ + 1) ∣ k ∣! n!}

j=1∑n(j—1)!∣k∣!(j+∣k∣—1)!=(∣k∣+1)(n—1)!∣k∣!(∣k∣+n)(∣k∣+n+1)!=(∣k∣+1)∣k∣!n!n(∣k∣+n)!

Давайте проверим это с помощью еще одного кода (:

import math

def nthTerm(k, n):
    return math.factorial(n + abs(k) - 1) // (math.factorial(abs(k)) * math.factorial(n - 1))

def sumOfRow(k, n):
    total = 0

    for i in range(n):
        total += nthTerm(k, i + 1)

    return total

print(sumOfRow(2, 5))

Вход в полноэкранный режим Выйти из полноэкранного режима

Мы можем самостоятельно убедиться, что сумма первых 5 членов второго ряда равна 35 — наша формула работает!

[БОНУС] Часть 3: сумма креста

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

Благодаря этой симметрии, найти эту формулу должно быть просто, верно? Мы просто умножим наш результат на 2, как показано ниже:

\frac{2 n (∣ k ∣ + n)!}{(k + 1) ∣ k ∣! n!}

(k+1)∣k∣!n!2n(∣k∣+n)!

Это работает, но иногда не работает. Это происходит, когда между линиями есть пересечение. Это происходит, когда неравенство

n — 1 > ∣ k ∣

n—1>∣k∣ верно. Поэтому мы должны иногда вычитать значение координаты пересечения, но как ее найти? Вспомните нашу формулу координат, приведенную ранее, и обратите внимание, что координата пересечения равна

(\frac{2 ∣ k ∣}{∣ k ∣})

(∣k∣2∣k∣). Это дает следующую формулу, когда это неравенство верно:

\frac{2 n (∣ k ∣ + n)!}{(k + 1) ∣ k ∣! n!} — (\frac{2 ∣ k ∣}{∣ k ∣})

(k+1)∣k∣!n!2n(∣k∣+n)!—(∣k∣2∣k∣)

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

f (x)

f(x) такой, что:

Заключение

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

И хотя вся эта математика может оказаться полной чепухой, которая, скорее всего, никогда не будет использована, как однажды сказал Сенека Младший: «Лучше, конечно, знать бесполезные вещи, чем не знать ничего».