Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/mmks/dec2011/Volgin_version1.pdf Дата изменения: Sun Nov 6 21:14:53 2011 Дата индексирования: Tue Oct 2 13:59:08 2012 Кодировка: Windows-1251 Поисковые слова: m 13

Числа Стирлинга и Игры Конвея
Волгин А. Д., Спивак А. В. 04.11.2011

1 Введение В данной статье исследуется интересное наблюдение, сделанное в прошлом (2010) году на лекциях А. В. Спивака, где он знакомит школьников и студентов с различными математическими фактами, открывает интересные взаимосвязи между различными областями математики: комбинаторикой, алгеброй, геометрией и так далее. С интервалом в несколько недель, а может и месяцев, он рассказал о двух совершенно различных математических фактах. Однажды он рассказывал о чудесах Месснера, описанных в статье Конвея в ?Кванте? (7 выпуск за 1991 год, рубрика ?Математические сюрпризы?), статья ?Один старый факт и несколько новых?). Числа выстраивались в ряд, определенным образом обводились в кружочки, выписывались новые ряды и вдруг в результате в кружочках получались то полные квадраты чисел, то кубы, можно было также заметить числа из треугольника Паскаля и даже факториалы. В другой раз рассказ был о числах Стирлинга, их комбинаторном и алгебраическом смысле, доказывались рекуррентные формулы. Первые несколько чисел Стирлинга выписывались в таблицу. Вскоре обнаружилось, что по сути таблица чисел Стирлинга и одна из расстановок чисел в кружочках в чудесах Месснера одно и то же. А примерно через неделю эта теорема была доказана с помощью другой рекуррентной формулы для чисел Стирлинга, найденной в книге ?Конкретная математика? Р.Грэхема, Д.Кнута и О.Паташника. В самой книге доказательство не приводится, поэтому его пришлось придумывать самостоятельно. Но как бы то ни было, общая задача про чудеса Месснера оставалась нереш?нной, и завершить доказательство в общем случае удалось лишь к концу весны 2011 года. В первых главах данной статьи кратко излагаются факты об ?играх Конвея?, основные формулы с числами Стирлинга и соответствующих многочленах. В последней главе даны определения рассматриваемых понятий, сформулированы теоремы и приведены доказательства. 2 Игры Конвея В своей статье Конвей предлагает посмотреть на ряд чисел и обвести в кружочек каждое второе, каждое третье или даже каждое ?треугольное? число (т.е. числа вида n(n2+1) = 1 + 2 + . . . + n). После этого под первым рядом выписываются числа таким образом, чтобы каждое следующее число было равно сумме чисел слева и сверху от него. При этом под обведенными в кружочек числами остается пропуск. Получается ряд чисел, разбитый пропусками на группы, после чего каждое число в конце группы также обводится в кружочек. Затем аналогичным образом выписываются третий, четвертый ряд и т. д. В результате получаются следующие представления:
mmmmmmmmm 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 m4 m 9 16 25 m m m 36 49 64 81 mmmm 1 m m m m m 17 18 m 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 m 7 12 19 27 m m 37 48 61 75 91 108 m m 13 m m m m 1 8 27 64 125 216

Можно заметить, что внизу первого представления получаются полные квадраты, а внизу второго кубы. Если продолжить обводить каждое четвертое число, каждое пятое и так далее, то внизу в кружочках будут получаться числа в 4, 5 степенях и т. д. Кроме того, числа в кружочках по каждой диагонали 1


тоже обладают некоторой закономерностью. Если сверху написать ряд единиц (что мы и сделаем впоследствии), то можно увидеть биноминальные коофициенты для (x + 1)2 ,(x + 2)2 ,(x + 3)2 , . . . в первом случае, и (x + 1)3 ,(x + 2)3 ,(x + 3)3 , . . . во втором. Что же получится, если обводить каждое треугольное число? Напомним, треугольные числа это 1, 1 + 2, 1 + 2 + 3 . . .
m m m m m 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 m m m m 2 6 11 18 26 35 46 58 71 85 m m 6 24 50 96 154 225 m 24 120 274 120

Легко заметить, что числа в кружочках 1, 2, 6, 24, 120 являются факториалами. А что можно сказать об остальных числах в кружочках?
3 Числа Стирлинга В предыдущей главе мы обратили внимание на то, что в первых двух случаях в кружочках получались биноминальные коэффициенты. В книге ?Конкретная математика? 6 глава начинает знакомство читателя с числами Стирлинга, которые названы в ней ?близкими родственниками биноминальных коэффициентов?. Итак, эти числа выступают в двух разновидностях, традиционно носящих незатейливые названия ?чисел Стирлинга первого и второго рода?. Числом Стирлинга второго рода n обозначается число способов k разбиения множества из n элементов на k непустых подмножеств (или, если угодно, число способов разложить n разных предметов в k одинаковых мешков так, чтобы ни один из мешков не остался пустым). В данной работе нас будут в большей степени интересовать числа Стирлинга первого рода, поэтому на них мы остановимся более подробно. Числом Стирлинга первого рода n обозначается число способов k представления n объектов в виде k циклов (или число способов посадить n человек с номерами на майках за k одинаковых круглых столов так, чтобы за каждым столом кто-то сидел). Заметим, что нам важен порядок, в котором они расположены, в отличие отn второго рода. Исходя из этого, например, можно доказать, что для любых n и k выполняется n k k Рассмотрим теперь перестановку, которая переводит 123456789 в 384729156. Для наглядности е? можно представить в двух строках:
123456789 384729156

откуда видно, что 1 переходит в 3, 2 переходит в 8 и т. д. Возникает циклическая структура, ибо число 1 переходит в 3, которое переходит в 4, которое переходит в 7, которое переходит обратно в 1, т. е. это цикл [1, 3, 4, 7]. Другим циклом в этой перестановке является [2, 8, 5], еще одним [6, 9]. Таким образом, перестановка 384729156 эквивалентна циклическому представлению, состоящем из трех циклов:
[1, 3, 4, 7] [2, 8, 5] [6, 9]

Аналогичная этому разбиению рассадка людей за столами:
1 2 6 '$ '$ '$ 7 3 &%5 &% &% 8 4 9

Теперь выведем рекуррентную формулу для вычисления чисел Стирлинга первого рода. Разделим варианты рассадки n человек за k столов на две группы: I. n-й человек сидит за отдельным столом, II. n-й человек сидит за одним столом еще с кем-либо. Тогда понятно, что количество вариантов группы I будет 2


-1 равно n-1 . Чтобы рассадить людей II-м способом, нужно сначала рассадить n - 1 человека за k столов k ( n-1 вариантов), а затем подсадить к ним n-го человека (n - 1 вариантов, каждый из которых является k способом выбрать его левого соседа). Таким образом, общее количество вариантов будет:

n-1 n-1 n = (n - 1) + k k-1 k

(1)

Используя данную рекурентную формулу легко получить несколько первых чисел Стирлинга:
n 0 1 2 3 4 5 6 n 0 1 0 0 0 0 0 0 n 1 1 1 2 6 24 120 n 2 n 3 n 4 n 5 n 6

1 3 11 50 274

1 6 35 225

1 10 85

1 15

1

А теперь сравните эту таблицу и числа в кружочках в конце предыдущей главы.
4 Многочлены Перед тем как перейти к доказательству теоремы, сформулированной в следующей главе, докажем несколько вспомогательных фактов, связанных с многочленами. Рассмотрим многочлены:
x1 = x = x x2 = x(x + 1) = x2 + x x3 = x(x + 1)(x + 2) = x3 + 3x2 + 2x x4 = x(x + 1)(x + 2)(x + 3) = x4 + 6x3 + 11x2 + 6x

(2)

Нетрудно заметить, что коэффициенты у получившихся многочленов совпадают с числами Стирлинга. Запишем в общем виде: n nk xn = x (3) k Докажем эту формулу по индукции. База индукции формулы выше. Индукционный переход: Заметим, что (x + n - 1)xk = xk+1 + (n - 1)xk . Тогда:
n-1 k=1

xn = (x + n - 1)x
n-1

n-1

= (x + n - 1)
k=1 n-1

n-1 k x= k

=
k=1 n-1

n-1 x k n-1 x k

k+1

+
k=1 n

(n - 1)

n-1 k x= k
n

=
k=0 n

k+1

+
k=1

n-1 k (n - 1) x= k
n k

k=1

n-1 k x+ k-1

n

k=1

n-1 k (n - 1) x= k

(4)

=
k=1

n-1 k n-1 x + (n - 1) x k-1 k

=
k=1

nk x, k

что и требовалось доказать. 3


Теперь рассмотрим произвольный многочлен A(x) чему равны коэффициенты многочлена B (x) = A(x

= an xn + an + 1) k
k

+ . . . + a0 . Далее мы посмотрим, . -й член этого многочлена равен:
-1

x

n-1

ak (x + 1)k = ak
i=0

k i

x

i

(5)
B (x) = bn xn +

Просуммировав коэфициенты для x в степени i получаем формулу для коэффициентов bn-1 xn-1 + . . . + b0 :
n

bi =
k=i

k i

a

k

(6)

A(x + 1)

Обозначим операцию, переводящую многочлен A в многочлен B как F (A). Т. е. B (x) = F (A(x)) = . Теперь рассмотрим преобразование G(B (x)) = B (x)(x + 1). Здесь несложно подсчитать коэффициенты для многочлена C (x) = G(B (x)):
c0 = b cn
+1 0 n

=b

(7)
i-1

ci = bi

-1

+ bi ; i [1; n] ))

Интересно отметить, что если нов:

A0 = 1 Ai = G(F (A A0 = 1 A1 = x + 1

,

, то мы получим последовательность многочле(8)

A2 = (x + 1)(x + 2) A3 = (x + 1)(x + 2)(x + 3) A4 = (x + 1)(x + 2)(x + 3)(x + 4)

Таким образом, получаем простую формулу Ai = xi , а значит все коэфициенты многочленов Ai - числа Стирлинга. Отсюда, к слову, можно вывести еще одно рекуррентное соотношение для чисел Стирлинга:
n+1 = m+1
k

n k

k m

Первое доказательство чудес Месснера было сделано Волгиным Андреем с использованием данного рекуррентного соотношения. Причем сначала им была доказана сама формула по индукции, а затем и комбинаторно. Но, к сожалению, это первое доказательство не проходит для более общих случаев. В данной статье будут использоваться идеи доказательства, выдвинутые А. В. Спиваком, так как эти доказательства могут быть использованы для любой последовательности чисел в кружочках.
5 Теоремы о таблицах Месснера Теперь мы сформулируем и докажем теоремы, показывающие взаимосвязь между таблицами, предложенными в чудесах Месснера, биноминальными коэффициентами и числами Стирлинга. Прежде всего мы немного изменим подход Конвея, и введем новые определения - таблица Месснера, и выделенная диагональ таблицы Месснера. Рассмотрим бесконечный вправо ряд единиц. Пусть у нас есть множество S N. Будем обводить в кружочек m-ую единицу тогда и только тогда, когда m S. Каждый следующий ряд получается таким образом: двигаясь слева направо, выписываем под каждым необведенным числом предыдущего ряда сумму чисел, стоящих слева и сверху от него (Для крайних чисел слева будем считать, что их левые соседи равны нулю). В результате мы получим ряд чисел, разделенный пробелами на группы. Далее, обведем в кружочек те и только те числа, справа от которых есть пробел. В результате выписывания таких рядов мы получим таблицу чисел, которую и будем называть таблицей Месснера. Согласно приведенному алгоритму заполнения таблицы Месснера, числа, обведенные в кружочек будут располагаться диагоналями. В каждом следующем ряду число, обведенное в кружочек будет слева

4


от числа, обведенного в кружочек в предыдущем ряду. Таким образом, выделенная диагональ таблицы Месснера Lk (S) это множество чисел, обведенных в кружочек по диагонали от k -го элемента множества S. Рассмотрим множества Sn = nN (множество натуральных чисел, делящихся на n), и S = m(m+1) ; m N . 2 Для S3 и S4 таблицы Месснера будут иметь следующий вид:
m m m m m m 111111111111111111 m34 m56 m78 m 9 10 11 12 m m 12 m m m m m m 1 4 9 16 25 36 m m m m m 11111111111111111111 m456 m 7 8 9 10 11 12 13 14 15 m m m 123 m m m m m 13 7 12 19 27 37 48 61 75 m m m m 1 8 27 64 125 S

Для

таблица Месснера будет такой:

mm m m m m 111111111111111111111 m 23 m 456 m 7 8 9 10 m 11 12 13 14 15 m 1 m m m m 2 6 11 18 26 35 46 58 71 85 m m 6 24 50 96 154 225 m 24 120 274 120

Выпишем несколько выделенных диагоналей данных таблиц Месснера:
L1 (S3 ) = (1, 2, 1) L2 (S3 ) = (1, 4, 4) L3 (S3 ) = (1, 6, 9) L1 (S4 ) = (1, 3, 3, 1) L2 (S4 ) = (1, 6, 12, 8) L3 (S4 ) = (1, 9, 27, 27) L1 (S ) = (1) L2 (S ) = (1, 1) L3 (S ) = (1, 3, 2) L4 (S ) = (1, 6, 11, 6)
Выделенные диагонали таблиц Месснера Lk (Sn ), (где Sn = nN множество натуральных чисел, делящихся на n) представляют из себя набор биноминальных коэффициентов разложения многочлена (x + k )n , то есть:
Теорема 1.

(9)

Lk (Sn ) =
Теорема 2.

ni k ;0 i n i

(10)

Выделенные диагонали таблиц Месснера

Lm (S ), (где S =

m(m+1) 2

; m N ) представля-

ют из себя набор чисел Стирлинга:

Lm (S ) =

m ;0 i m - 1 m-i

(11)

Для доказательства теорем сначала докажем две леммы:
Лемма 1.

Рассмотрим произвольную выделенную диагональ Lm (S) таблицы Месснера и обозначим е? сверху вниз an , an-1 , . . . , a0 . Теперь в верхнем ряду отсчитаем вправо от обведенной an = 1 еще n единиц

5


и обозначим n + 1-ую единицу за bn (единицы до bn будем обозначать an ). Полагаем при этом, что множество S таково, что между an и bn нет единицы в кружочке. При этом bn может быть обведена, а может и нет. Далее, двигаясь по-диагонали (каждый раз спускаясь на уровень вниз и влево), обоn i значим числа bn-1 , . . . , b0 . Поставим в соответствие полученным наборам многочлены A = i=0 ai x , n i B = i=0 bi x . Тогда B (x) = F (A(x)) = A(x + 1)

1ћ ћћ ћћ ћћ ћ. am 0

ћ ћ am 1 nЕ ћ Еї ћ an-1 ћ an-2 Е ї an an-3 ї an ..

an
an + an + an
-1 -1

an 2an + an
-2

an
-1

3an + a

n-1

+ an

+ . . . + an

-3

... ...

... ...

. . . . . . an ... bn-1 b n-2

bn

... b0 = an + . . . + a0

Доказательство. Рассмотрим таблицу чисел, получающуюся между рассматриваемыми диагоналями таблицы Месснера. Пусть нумерация столбцов и строк этой таблицы начинается с 0. Согласно алгоритму заполнения числовой последовательности, в 0-м стобце мы получим числа: (an ; an + an-1 ; . . . ; an + an-1 + . . . + a0 ), в 1-ом столбце (an ; 2an + an-1 ; 3an + 2an-1 + an-2 ; . . .), в общем виде можно записать выражение ij ij для ячейки в i-ой строке и j -ом столбце как n=0 Ck ak , где Ck - это соответствующие коэффициенты в k строке i и столбце j для k - го элемента последовательности (an , . . . , a0 ). Давайте выпишем, чему будут равны эти коэффициенты, например, для an

( ij Получили треугольник Паскаля (немного повернутый)! Действительно, согласно алгоритму, Ck = Cki-1)j + i(j -1) Ck , что в точности соответствует алгоритму формирования треугольника Паскаля. Очевидно, это утверждение будет справедливо для всех коэффициентов, так как при уменьшении k таблица коэффициентов просто сдвигается на одну строку вниз. Для an-1 получаем:

1 1 1 1 1 1 ..

.

1 2 3 4 5 ..

1 3 6 10 .. .

1 4 10 .. .

1 1 ... 5 ... ... .

ij Следовательно, Ck это биноминальные коэффициенты. Напомним, что нумерация строк и столбцов начинается с 0, тогда:

0 1 1 1 1 1 ..

.

0 1 2 3 4 ..

0 1 3 6 .. .

0 1 4 .. .

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

C

ij n

=

i+j j

ij Cn-1 = ij Cn-2 =

(i - 1) + j j

C

ij k

=

(i - 2) + j j ... (i - n + k ) + j j

6


bn

Возвращаясь к коэффициентам bi заметим, что bn находится в нулевой строке и n - ом столбце таблицы, -1 в первой строке и (n - 1) - ом столбце, и так далее, значит bi находится в (n - i)- ой строке, i - ом столбце. Отсюда: n n
bi =
k=0

ak Ck

(n-i)i

=
k=0 n

ak k i

n-i-n+k+i i

=

ak
k=0

В 3 главе мы доказали, что в таком случае

B (x) = A(x + 1)

Лемма 2. Рассмотрим произвольную диагональ в таблице Месснера, не являющуюся выделенной, и обозначим е? числа сверху вниз bn , bn-1 , . . . , b0 . Тогда следующая за ней диагональ cn+1 , cn , . . . , c0 удовлетворяет преобразованию многочленов:

C (x) = (x + 1)B (x) = G(B ) 1 ћ ћ ћ ћ b0 c0 ћ ћ ћ ћ ... c1 ћ ћ ћ ћ ћ 1 bn-1 cn-1 bn cn c
n+1

bn - 2 bn-3 cn-2 ...

Доказательство.

Согласно алгоритму заполнения числовой последовательности, можно выписать формулу для вычисления ci :
c0 = b
+1 0

cn ci = bi

= bn

(x + 1)B (x) = G(B )

А в главе о многочленах мы показали, что данная формула преобразования соответствует

-1

+ bi ; i [1; n]

C (x) =

Доказательство теоремы 1.

Поставим в соответствие диагоналям, начиная с первой единицы в таблице Месснера для Sn ) многочлены D0 = 1, D1 = x + 1 . . .. Согласно лемме 2, каждый следующий многочлен получается из предыдущего путем умножения на x + 1, таким образом для выделенной диагонали получим в соответствие многочлен Dn = (x + 1)n . Теперь сменим обозначения и поставим в соответствие первой выделенной диагонали многочлен A1 (x) = (x + 1)n . В соответствии с леммой 1 каждая следующая диагональ будет получаться путем преобразования Ai (x) = F (Ai-1 (x)) = Ai-1 (x + 1). Отсюда несложно получить: n
A1 (x) = (x + 1) A2 (x) = (x + 2) A3 (x) = (x + 3) ...
n n

Таким образом, для i - ой диагонали мы получим внизу in , и вся диагональ представляет из себя коэффициенты многочлена (x + i)n .

Ai (x) = (x + i)n

7


Несложно заметить, в случае когда ?расстояние? между выделенными диагоналями таблицы Месснера увеличивается на 1, то это означает, что каждый следующий многочлен, поставленный в соответствие выделенным диагоналям будет получаться из предыдущего комбинацией преобразований, полученных в леммах 1 и 2: Ai (x) = G(F (Ai-1 (x))). Отсюда получается уже известная последовательность многочленов:
Доказательство теоремы 2.

A0 = 1

A1 = x A2 = x A3 = x ...

1 2 3

А значит в каждой диагонали в кружочках будут стоять числа Стирлинга, в частности, внизу каждой выделенной диагонали будут стоять факториалы, что и требовалось доказать.
6 Заключение В заключении следует сказать несколько слов об авторстве идей, использованных в статье. В прошлом году Волгин Андрей, ученик 8 класса обнаружил совпадение между таблицей с числами Стирлинга и таблицами Месснера в статье Конвея. Он преобразовал таблицы Месснера таким образом, чтобы они начинались с ряда единиц и доказал, что в таблице Месснера с треугольными числами в выделенных диагоналях всегда будут получаться числа Стирлинга. Так как он воспользовался рекуррентной формулой для чисел Стирлинга, которая была приведена в книжке без доказательства, то попутно он доказал и эту формулу. Весной был сделан доклад в школе по данной теме. Несколько позже Спивак А. В. привел другое доказательство рассмотренных теорем и познакомил с ним на лекции своих учеников. Это доказательство годится также для решения более общих задач, когда единицы обводятся по более сложным законам, чем в статье Конвея, поэтому в данной статье Волгин Андрей оформил идею этого последнего доказательства в более строгий вид.

Ai = x

i

8