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

Дао рождает одно, одно рождает два, два рождает три, а три рождает все существа

Лао-цзы1

Есть в форме треугольника что-то тайное, глубоко символическое. Недаром треугольная форма была выбрана древними египтянами в качестве символа вечности и воплощена в пирамидах. Ту же форму имеет и загадочный масонский символ, изображенный Николаем Рерихом на обратной стороне однодолларовой купюры (это та самая пирамида с тринадцатью ступенями и всевидящим оком на вершине2). В математике такой глубоко символичной пирамидой является знаменитый треугольник Паскаля. Треугольник Паскаля обладает целым рядом замечательных свойств. О нем написано множество статей и книг. С появлением вычислительных машин построение треугольника Паскаля стало излюбленной задачкой для начинающих при изучении основ программирования. Элементами этой арифметической структуры являются так называемые биномиальные коэффициенты. Комбинаторный смысл биномиальных коэффициентов состоит в том, что они представляют собой количества различных k-членных комбинаций из n-элементного множества без повторений. То есть треугольник Паскаля состоит из чисел, каждое из которых есть количество способов выбрать k шариков из мешка, в котором таких шариков n штук (k < или = n). При этом в треугольнике n - это номер строки, а k - номер элемента в строке (и в том, и в другом случае нумерация начинается с нуля). Есть формула, которая позволяет вычислить любой биномиальный коэффициент непосредственно, зная k и n. Но в этой прямой формуле присутствуют факториалы, которые очень быстро переполняют объемы ячеек вычислительной машины с ростом значений k и n. Поэтому для построения треугольника Паскаля воспользуемся одним замечательным его свойством, состоящим в том, что любой из элементов представляет собой сумму двух его верхних соседей. В этом случае умножение заменяется простым сложением. Строго говоря, таким способом нельзя вычислить крайние единички, поскольку над ними нет двух соседей, но при написании программы можно зарезервировать в массиве виртуальные нули и тем самым сохранить универсальность общего правила.

Private Sub Form_Click()
Dim a(16, 16) As Long
n = 15
s = 800
a(1, 0) = 1
For j = 1 To n
 CurrentX = (Width / 2) - j * 0.5 * s
 For i = 1 To j
  x = CurrentX
  a(i, j) = a(i - 1, j - 1) + a(i, j - 1)
  If a(i, j) Mod 2 = 1 Then
   ForeColor = RGB(0, 0, 0)
  Else
   ForeColor = RGB(255, 0, 0)
  End If
  Print a(i, j);
  CurrentX = x + s
 Next i
 Print
 Print
Next j
End Sub

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

А. КОЛЕСНИКОВ,
[email protected]

1 Цит. по Чжан Бэйгунь Проблема первоначала мира в древней китайской философии//О первоначалах мира в науке и теологии.- СПб, "Петрополис" - 1993 г.

2 Если вас заинтересовала история символики на долларовой купюре, можете посетить, например, www.zaistinu.ru/nwo или www.nevskiy.orthodoxy.ru/sobor.html

Версия для печатиВерсия для печати

Номер: 

15 за 2002 год

Рубрика: 

Азбука программирования
Заметили ошибку? Выделите ее мышкой и нажмите Ctrl+Enter!