|
|
Статьи Соросовского Образовательного журнала в текстовом формате
Изложены некоторые классические и новые арифметические, геометрические и комбинаторные свойства широко известного треугольника Паскаля, а также пирамиды Паскаля и некоторых их обобщений.
ТРЕУГОЛЬНИК И ПИРАМИДА ПАСКАЛЯ:СВОЙСТВА И ОБОБЩЕНИЯ
О. В. КУЗЬМИН
Иркутский государственный университет
Пожалуй, одной из наиболее известных и изящных численных схем во всей математике является треугольник Паскаля. Блез Паскаль, французский математик и философ XVII века, посвятил ей специальный "Трактат об арифметическом треугольнике". Впрочем, эта треугольная таблица была известна задолго до 1665 года, даты выхода в свет труда Паскаля. Так, в 1529 году треугольник Паскаля был воспроизведен на титульном листе учебника арифметики, написанного Петром Апианом, астрономом из Ингольштадтского университета. Изображен треугольник и на иллюстрации в книге "Яшмовое зеркало четырех элементов" китайского математика Чжу Шицзе, выпущенной в 1303 году. Омар Хайям, не только поэт и философ, но и математик, знал о существовании треугольника около 1100 года, в свою очередь заимствовав его из более ранних китайских или индийских источников.
1. ТРЕУГОЛЬНИК ПАСКАЛЯ
И БИНОМИАЛЬНЫЕ КОЭФФИЦИЕНТЫ
1.1. Треугольник Паскаля часто выписывают в виде равнобедренного треугольника (рис. 1), в котором на вершине и по боковым сторонам стоят единицы, каждое из остальных чисел равно сумме двух чисел, стоящих над ним слева и справа в предшествующей строке. Треугольник можно продолжать неограниченно. Он обладает симметрией относительно вертикальной оси, проходящей через его вершину.
Треугольник Паскаля прост, но в то же время таит в себе неисчерпаемые сокровища и связывает воедино различные разделы математики, не имеющие на первый взгляд ничего общего. В статье столь ограниченного объема нет возможности даже перечислить все известные свойства и приложения [1, 2]. Отметим лишь некоторые из них.
Вдоль диагоналей, параллельных сторонам треугольника, выстроены треугольные числа и их обобщения на случай пространств всех размерностей. Суммы чисел, стоящих вдоль восходящих диагоналей, образуют хорошо известную последовательность чисел Фибоначчи. Если, спускаясь по центральному столбцу, из каждого числа вычитать соседнее справа (или слева!), то возникает последовательность чисел Каталана. И наконец, каждый элемент является биномиальным коэффициентом. Именно это фундаментальное свойство треугольника Паскаля связывает его не только с комбинаторикой и теорией вероятностей, но и другими областями математики и ее приложений [3].
1.2. Биномиальные коэффициенты можно получить путем разложения соответствующей степени бинома:
где n $ 0, k # n. Они удовлетворяют рекуррентному соотношению (правилу Паскаля)
с начальными условиями
если min(n, k, n - k) < 0, граничным условиям
и равенству
подтверждающему наличие оси симметрии (см. рис. 1). Между биномиальными коэффициентами установлены сотни различных тождеств и соотношений. Приведем широко известные формулы суммирования
и свертку Вандермонда
1.3. Биномиальные коэффициенты строятся из натуральных чисел при помощи арифметических операций
n $ 1, 1 # k # n.
Они широко используются как в самой математике, так и в ее приложениях. Эти обстоятельства побуждают искать всевозможные обобщения коэффициентов (2). Приведем некоторые.
Возьмем числовую последовательность ai ? 0. В числителе и знаменателе правой части равенства (2) каждый множитель заменим членом последовательности, имеющим тот же номер. Получим коэффициенты
подчиняющиеся рекуррентной формуле
при условиях
n $ 0,
и
если min(n, k, n - k) < 0.
Важным частным случаем при ai = fi являются так называемые фибономиальные коэффициенты
где m, n - неотрицательные целые, fk - k-е число Фибоначчи: fn = fn - 1 + fn - 2 , f0 = 1, f1 = 1. Полагая в (3) ai = fi , получим
1.4. Для биномиальных коэффициентов известно множество различных интерпретаций. Самая популярная из них - комбинаторная: - число сочетаний из n элементов по k (или k-подмножеств n-множества).
Интересна следующая геометрическая интерпретация.
Пусть дана прямоугольная сетка квадратов размерами nk (шахматный город, состоящий из n i k прямоугольных кварталов, разделенных k - 1 горизонтальными и n - 1 вертикальными улицами (рис. 2)). Тогда - число различных кратчайших на этой сетке путей, ведущих из левого нижнего угла O(0; 0) в правый верхний угол M (n; k).
2. ОБОБЩЕННЫЙ ТРЕУГОЛЬНИК ПАСКАЛЯ
Обобщенным треугольником Паскаля (V-треугольником) называем треугольную таблицу, элементы которой удовлетворяют следующим рекуррентным соотношениям [4, с. 92]:
где V(0, 0) = V0 , V(n, k) = 0, если min(n, k, n - k) < 0.
Число V0 , стоящее в вершине V-треугольника, оговаривается особо. Величины an, k и bn, k называют весовыми коэффициентами. При фиксированных n и k элементы образуют n-строку и k-столбец V-треугольника соответственно.
2.1. Многие комбинаторные числа являются частными случаями элементов V-треугольника. В этом разделе считаем V0 = 1.
Положим an, k = bn, k = 1, n $ 1, 0 # k # n, тогда V(n, k) = то есть имеем треугольник Паскаля.
Пусть an, k = 1, bn, k = mn - 1 , n $ 1, 0 # k # n, тогда а из соотношения (5) следует рекуррентная формула
для обобщенных чисел Стирлинга 1-го рода (см. [4, с. 27]).
При an, k = 1, имеем и рекуррентную формулу
для обобщенных чисел Стирлинга 2-го рода (см. [4, с. 27]). Последовательность называем базой, а треугольники, составленные из и - соответственно B- и A-треугольником.
Положим n $ 1, 0 # k # n, тогда и из (5) получаем рекуррентную формулу (3).
Пусть n $ 1, 0 # k # n, тогда и из соотношения (5) получаем рекуррентную формулу (4). Если an, k = fn - k - 2 , bn, k = fk + 1, n $ 1, 0 # k # n, то также а из (5) имеем новую рекуррентную формулу.
2.2. Обобщенный треугольник Паскаля допускает следующую простую биологическую интерпретацию (см. [4, с. 92]). Дискретное множество переменного состава, элементы которого способны рождаться, отмирать и переходить из одной качественной категории в другую, назовем популяцией. Первоначально популяция однородна - состоит из одинаковых элементов. Развитие популяции рассматриваем дискретно по итогам его последовательных этапов, номера которых n $ 0, и по номерам видов элементов k $ 0. Пусть на протяжении этапа развития популяции элементы k-го вида способны порождать элементы только k-го и (k + 1)-го видов, то есть ориентируемся на эволюцию без отступлений и с условием, что за один этап можно сделать не более одного шага вперед. Тогда:
V(n, k) - число элементов k-го вида после n-го этапа;
bn, k - доля элементов k-го вида, сохранившаяся от объема V(n, k) этого вида на протяжении n-го этапа;
an, k - доля от объема V(n - 1, k), в котором элементы k-го вида породили элементы (k + 1)-го вида на протяжении n-го этапа.
Объем популяции в итоге n-го этапа (n $ 1) будет
Если задано V0 и известны весовые коэффициенты, то по формулам (5) и (8) можно найти общий объем популяции и присущее ей распределение по видам элементов на каждом из этапов развития. Обратная задача не является однозначной.
3. A- и B-ТРЕУГОЛЬНИКИ И ИХ СВОЙСТВА
3.1. Получим производящие функции (п.ф.) для некоторых составных частей A- и B-треугольников. Пусть k $ 0. Несложными преобразованиями с учетом (7) доказывается
Лемма 1. П.ф. Ak(z) k-столбца A-треугольника удовлетворяет рекуррентному соотношению
Теорема 1. П.ф. k-столбца A-треугольника имеет вид
Доказательство проводим индукцией по k. Для k = 0 и k = 1 формула (10) проверяется непосредственно.
Пусть (10) верно при k = t - 1, тогда с учетом (7) и (9) получаем
что дает соотношение (10) при k = t. Теорема доказана.
C учетом (10) общей п.ф. A-треугольника будет
Обозначим Несложными преобразованиями с учетом соотношения (6) доказывается
Лемма 2. П.ф. n-строки B-треугольника удовлетворяет следующему рекуррентному соотношению:
Применив n раз формулу (11), можно убедиться в том, что верна
Теорема 2. П.ф. n-строки B-треугольника имеет вид
C учетом (12) общей п.ф. B-треугольника будет
3.2. Приведем перечислительные интерпретации чисел и
- сумма весов множества всех размещений n различимых объектов по двум различным ячейкам, при которых k объектов попадает в ячейку 1 при условии, что вес очередного i-го объекта в зависимости от ячейки, в которую он попадает, равен 1 или mi - 1 соответственно, а вес всего размещения равен произведению весов составляющих его объектов.
- сумма весов множества всех размещений n различимых объектов по двум различным ячейкам, при которых k объектов попадает в ячейку 1 при условии, что вес очередного объекта в зависимости от ячейки, в которую он попадает, равен 1 или mj соответственно, где j - число объектов, уже имеющихся в ячейке 1, а вес всего размещения равен произведению весов составляющих его объектов.
4. ПИРАМИДА ПАСКАЛЯ
И ТРИНОМИАЛЬНЫЕ КОЭФФИЦИЕНТЫ
Используя две переменные x0 и x1 , разложение (1) можно записать в виде
Обозначая триномиальные коэффициенты символом где n, k, l - неотрицательные целые числа, и полагая
записываем разложение n-й степени тринома x0 + x1 + + x2 в форме
Представление (13) упорядочивает расположение в пирамиде Паскаля и ее сечениях (рис. 3): n указывает номер сечения пирамиды, k - номер строки сечения, а l - номер столбца.
4.1. Для триномиальных коэффициентов справедлива рекуррентная формула
с начальными условиями
если min(n, k, l, n - k - l) < 0.
Триномиальные коэффициенты удовлетворяют условиям
и равенствам
подтверждающим наличие трех осей симметрии. Приведем формулы суммирования
а также трехмерный аналог формулы суммирования Коши
4.2. Пирамиду Паскаля можно строить в форме тетраэдра, а также пирамиды с различными значениями двухгранных углов, один из которых прямой. В n-м сечении (треугольнике) пирамиды (n $ 0), параллельном основанию, располагаем коэффициенты подобно коэффициентам в треугольнике Паскаля. Число элементов в n-м сечении пирамиды - (n + 1)-е треугольное число, равное Число элементов в n + 1 сечениях пирамиды (от 0-го до n-го включительно) - (n + 1)-е пирамидальное число, равное По трем внешним ребрам пирамиды (рис. 3) стоят единицы. Каждая из трех боковых граней представляет собой треугольник Паскаля. Соотношение (14) позволяет сделать вывод о том, что любой внутренний элемент пирамиды Паскаля, стоящий в n-м сечении, равен сумме трех элементов, расположенных в углах элементарного треугольника (n - 1)-го сечения пирамиды.
Построение n-го сечения можно связать с равенством
n $ 0, 0 # k # n; 0 # l # k.
Сечение получается из треугольника Паскаля, основанием которого служит n-я строка Паскаля, умножением элементов его строк почленно на элементы основания, повернутого против часовой стрелки на угол p /2. Рис. 4, а иллюстрирует построение сечения при n = 4. Расположение элементов сечения показано на рис. 4, б. Если сечение пирамиды Паскаля является правильным треугольником, то при любом n оно имеет три оси симметрии. На рис. 5 указаны оси симметрии сечения при n = 4.
4.3. Дадим интерпретации триномиальных коэффициентов.
Пусть имеется урна с красными, белыми и черными шарами. Мы вынимаем шар, отмечаем его цвет и возвращаем в урну. Коэффициент можно интерпретировать как число перестановок, в которых за n испытаний можно вынуть k красных, l черных и n - k - l белых шаров.
Триномиальные коэффициенты можно интерпретировать и как число размещений n различимых объектов по трем различным ячейкам, при которых k объектов попадает в ячейку 1, l объектов - в ячейку 2 и n - k - l объектов - в ячейку 3.
5. ОБОБЩЕННАЯ ПИРАМИДА ПАСКАЛЯ
Обобщенной пирамидой Паскаля (V-пирамидой) называем трехгранный пирамидальный массив, элементы которого удовлетворяют рекуррентным соотношениям [5]
V(n, k, l) = an, k - 1, lV(n - 1, k - 1, l) +
+ bn, k, l - 1V(n - 1, k, l - 1) + gn, k, lV(n - 1, k, l)
при условиях
V(0, 0, 0) = V0 ; V(n, k, l) = 0,
если min(n, k, l, n - k - l) < 0.
Число V0 , стоящее в вершине V-пирамиды, оговаривается особо.
При k = 0, l = 0 и k + l = n получаем соответственно правую, левую и заднюю грани V-пирамиды, каждая из которых является V-треугольником.
При фиксированном k элементы образуют левый k-сегмент, а при фиксированном l - правый l-сегмент V-пирамиды.
При фиксированных k и l элементы образуют (k, l)-столбец, а при n и k - (n, k)-диагональ V-пирамиды.
5.1. Ряд комбинаторных чисел можно считать частными случаями элементов V-пирамиды. В этом разделе считаем V0 = 1.
Положим an, k, l = bn, k, l = gn, k, l = 1, n $ 0, 0 # k + l # n, тогда то есть имеем пирамиду Паскаля.
Если an, k, l = an - 1 , bn, k, l = bn - 1 , gn, k, l = gn - 1 , n $ 1, 0 # # k + l # n, то имеем и из (15) следует рекуррентная формула
для обобщенных триномиальных коэффициентов 1-го рода [6].
При an, k, l = ak , bn, k, l = bk , gn, k, l = gk , n $ 1, 0 # k + l # # n, получаем а из (15) имеем рекуррентную формулу
для обобщенных триномиальных коэффициентов 2-го рода [6]. Пирамиды, составленные из и будем называть B- и A-пирамидой соответственно.
Пусть ai ? 0, i $ 1, тогда а из (15) получаем
При an, k, l = n - k + l - 1, bn, k, l = 0, gn, k, l = k, n $ 1, 0 # k + l # n, V(n, k, l) = Al(n, k), а из (15) следует рекуррентная формула
Al(n, k) = (n - k + l)Al(n - 1, k - 1) + kAl(n - 1, k)
для чисел Эйлера высшего порядка Al(n, k). При l = 1 из (18) имеем рекуррентную формулу для чисел Эйлера A(n, k).
5.2. Построенная обобщенная пирамида Паскаля допускает следующую интерпретацию. Пусть популяция состоит из одинаковых элементов, обладающих двумя свойствами A и B. Развитие популяции рассматриваем дискретно по итогам его последовательных этапов, номера которых n $ 0, и по двойным номерам элементов (k, l ) - степеням обладания элементом свойствами A и B соответственно (k, l $ 0, k + l # n). Пусть на протяжении одного этапа элементы вида (k, l ) способны порождать элементы только (k, l ), или (k + 1, l), или (k, l + 1) видов. Тогда:
V(n, k, l ) - число элементов (k, l )-го вида после n-го этапа;
an, k, l - доля от объема V(n - 1, k, l ), в котором элементы (k, l )-го вида породили элементы (k + 1, l )-го вида на n-м этапе;
bn, k, l - доля от объема V(n - 1, k, l ), в котором элементы (k, l )-го вида породили элементы (k, l + 1)-го вида на на n-м этапе;
gn, k, l - доля элементов (k, l )-го вида, сохранившаяся от объема V(n - 1, k, l ) на на n-м этапе.
Объем популяции Vn после n-го этапа, n $ 1, будет
При заданных значениях V0 , an, k, l , bn, k, l и gn, k, l по формулам (15) и (19) можно рассчитать общий объем популяции и присущее ей распределение по видам элементов на каждом из этапов развития. Обратная задача не является однозначной.
5.3. Для чисел Al (n, k) известны следующие интерпретации.
Возьмем n-перестановку (a1 , a2 , _, an) и разместим l нулей на n + 1 позициях между ее элементами. Полученную таким образом последовательность b = (b1 , b2 , _, bn + l) назовем (n, l)-последовательностью. Возрастанием в (n, l)-последовательности b назовем пару bi , bi + 1 , для которой верно неравенство bi < bi + 1 . Начальный элемент образует возрастание, если b1 $ 1. Тогда Al + 1(n, k) - число (n, l)-последовательностей с k возрастаниями. При l = 0 имеем интерпретацию чисел Эйлера A(n, k).
С колоды, содержащей n карт произвольной спецификации и l джокеров, снимаем карты до появления первой, отличной от джокера. Начиная с нее складываем карты в одну стопку до тех пор, пока они выпадают в невозрастающем порядке (джокер считается самой младшей из карт). Каждое появление карты старшей, нежели предшествующая, дает начало образованию новой стопки. Тогда l !Al + 1(n, k) - число таких способов расположения карт в колоде, при которых образуется точно k стопок. При l = 0 получаем известную задачу Симона Ньюкомба.
6. A- И B-ПИРАМИДЫ И ОБОБЩЕННЫЕ ТРИНОМИАЛЬНЫЕ КОЭФФИЦИЕНТЫ
6.1. Начнем с A-пирамиды. Пусть Несложными преобразованиями с учетом формулы (17) доказывается
Лемма 3. П.ф. (k, l )-столбца A-пирамиды удовлетворяет рекуррентному соотношению
Теорема 3. П.ф. (k, l )-столбца A-пирамиды имеет вид
где числа построены на базе
Доказательство проводим индукцией по k и l. Для пар значений k = l = 0; k = 1, l = 0; k = 0, l = 1 и k = l = 1 справедливость (21) проверяется непосредственно с учетом формулы (20).
Пусть (21) выполняется для пар значений k = t, l = s - 1 и k = t - 1, l = s, тогда с учетом (20) и (при ai ╞ 1, l = 1) (17) получаем
что дает соотношение (21) при k = t, l = s. Теорема доказана.
В частном случае ai = bi = gi = 1 из (21) получаем п.ф. (k, l )-столбца пирамиды Паскаля:
Теорема 4. П.ф. правого k-сегмента A-пирамиды имеет вид
Доказательство. С учетом соотношения (21) имеем
Используя равенство (см. [4, с. 46]), где построены на базе после ряда преобразований получаем (22). Теорема доказана.
Непосредственно из (22) следует
Теорема 5. П.ф. A-пирамиды имеет вид
В частном случае ai = b = gi = 1 и x = y = 1 из (23) получаем п.ф. пирамиды Паскаля:
6.2. Перейдем к B-пирамиде. Пусть n $ 1. Несложными преобразованиями с учетом (16) доказывается
Лемма 4. П.ф. n-сечения B-пирамиды удовлетворяет рекуррентному соотношению
Применив n раз формулу (24), можно убедиться в том, что верна
Теорема 6. П.ф. элементов n-сечения B-пирамиды имеет вид
n $ 1.
6.3. Найдем соотношения между суммами чисел и и числами и Обозначим Несложными преобразованиями с учетом соотношения (16) доказывается
Лемма 5. П.ф. (n, k)-диагонали B-пирамиды удовлетворяет рекуррентному соотношению
Теорема 7. П.ф. (k, l )-диагонали B-пирамиды имеет вид
где построены на базе
Доказательство. Поделив обе части (25) на получим Обозначив имеем и, сравнивая с (6), убеждаемся, что где построены на базе Теорема доказана.
Аналогично доказывается
Теорема 8. П.ф. (k, l )-диагонали A-пирамиды имеет вид
где построены на базе
6.4. Дадим интерпретации чисел и
- сумма весов множества размещений n различимых объектов по трем различным ячейкам, при которых k объектов попадает в ячейку 1, l объектов - в ячейку 2 и n - k - l объектов - в ячейку 3 при условии, что вес очередного i-го объекта в зависимости от номера ячейки, в которую он попадает, равен ai - 1 , bi - 1 или gi - 1 , а вес всего размещения равен произведению весов составляющих его объектов.
- сумма весов множества размещений n различимых объектов по трем различным ячейкам, при которых k объектов попадает в ячейку 1, l объектов - в ячейку 2 и n - k - l объектов - в ячейку 3 при условии, что вес очередного объекта в зависимости от ячейки, в которую он попадает, равен aj , bj или gj соответственно, где j - число объектов, уже имеющихся в ячейке 1, а вес всего размещения равен произведению весов составляющих его объектов. При ai ╞ bi ╞ gi ╞ 1 имеем уже приведенную интерпретацию
ЛИТЕРАТУРА
1. Успенский В.А. Треугольник Паскаля. М.: Наука, 1979. 48 с.
2. Green T.M., Hamberg C.L. Pascal's Triangle. Palo Alto: Dale Seymour, 1986. 280 p.
3. Бондаренко Б.А. Обобщенные треугольники и пирамиды Паскаля, их фрактали, графы и приложения. Ташкент: Фан, 1990. 192 с.
4. Докин В.Н., Жуков В.Д., Колокольникова Н.А. и др. Комбинаторные числа и полиномы в моделях дискретных распределений. Иркутск: Изд-во Иркут. ун-та, 1990. 208 с.
5. Кузьмин О.В. Некоторые комбинаторные числа в обобщенной пирамиде Паскаля // Асимптотические и перечислительные задачи комбинаторного анализа. Иркутск: Изд-во Иркут. ун-та, 1997. С. 90-100.
6. Колокольникова Н.А., Кузьмин О.В. Обобщения триномиальных коэффициентов // Исследования по геомагнетизму, аэрономии и физике Солнца. М.: Наука, 1983. Вып. 63. С. 60-67.
Рецензент статьи Ю.П. Соловьев
* * *
Олег Викторович Кузьмин, кандидат физико-математических наук, доцент кафедры математической статистики и теории вероятностей Иркутского государственного университета. Область научных интересов - комбинаторный анализ и его приложения. Автор и соавтор более 70 научных работ, двух монографий и двух учебных пособий для студентов.
