Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/mmks/dec2011/Volgin_version3.pdf Дата изменения: Wed Nov 30 18:39:34 2011 Дата индексирования: Tue Oct 2 13:59:29 2012 Кодировка: Windows-1251 Поисковые слова: m 13

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

1 Введение В данной статье исследуется интересное наблюдение, сделанное в прошлом (2010) году на лекциях А. В. Спивака. С интервалом в несколько недель, а может и месяцев, он рассказал о двух совершенно различных математических фактах таблицах Конвея (?Квант? 7 выпуск за 1991 год, рубрика ?Математические сюрпризы?, статья ?Один старый факт и несколько новых?) и числах Стирлинга и их свойствах. Вскоре обнаружилось, что по сути таблица чисел Стирлинга и одна из расстановок чисел в кружочках в таблицах Конвея одно и то же. А примерно через неделю гипотеза, возникшая в результате этого наблюдения, была доказана с помощью рекуррентной формулы для чисел Стирлинга. Используемые в статье факты о числах Стирлинга взяты из книги ?Конкретная математика? Р.Грэхема, Д.Кнута и О.Паташника (см. главу 6.1). В первых разделах данной статьи кратко излагаются факты об играх Конвея и числах Стирлинга (см. также ?Квант? 2, 2011 год с.32-33). В четв?ртом разделе даны определения рассматриваемых понятий, сформулированы теоремы и приведены доказательства. 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 степенях и т. д. Кроме того, числа в кружочках по каждой диагонали тоже обладают некоторой закономерностью. Если сверху написать ряд единиц (что мы и сделаем впоследствии), то можно увидеть биноминальные коофициенты для (x + 1)2 ,(x + 2)2 ,(x + 3)2 , . . . в первом случае, и (x + 1)3 ,(x + 2)3 ,(x + 3)3 , . . . во втором. Что же получится, если обводить каждое треугольное число? Напомним, треугольные числа это 1, 1 + 2, 1 + 2 + 3 ...

1

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

2


Используя данную рекурентную формулу легко получить несколько первых чисел Стирлинга:
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 Теоремы о таблицах Конвея Рассмотрим произвольный многочлен A(x) = an x фициенты многочлена A(x + 1).
A(x + 1) =
0kn n-1

n

+ an

-1

x

+ . . . + a0

. Посмотрим, чему равны коэф=
0in k i

(x + 1)k ak =
0kn 0ik

ak x

i

k i

=
0kin

ak x

i

k i

x

i ikn

ak

k i

(1)

Значит, коэффициент многочлена A(x + 1) при i-й степени равен Теперь рассмотрим многочлен A(x)(x + 1).
A(x)(x + 1) =
0kn

n k=i

ak

.
xk (ak + ak
-1

xk ak (x + 1) =
1kn+1

xk a k +
0kn

xk ak = an x

n+1

+
1kn

) + a0
+1

(2)

0

Значит, коэффициент многочлена ).

A(x)(x + 1)

при k-й степени равен

ak + ak

-1

(полагаем, что

an

= a-1 =

Возьм?м таблицу, бесконечную вправо и вниз; будем обозначать число, стоящее в ней на1 пересечении m-й строки и n-го столбца Vnm (отсч?т строк и столбцов вед?тся с единицы).1Положим Vn = 1 для любого n N. Пусть у нас есть множество S N. Для всех n S выделим Vn . Каждая следующая строка получается таким образом: двигаясь слева направо, записываем на пересечение m-й строки и n-го столбца сумму Vnm-1 и ближайшего числа, стоящего слева от этой клетки таблицы, если Vnm-1 не выделено, и не записываем ничего в противном случае (Для крайнего числа строки будем считать, что его левый сосед равен нулю). После этого выделим все числа, справа от которых пустая клетка таблицы. Полученную таблицу назов?м таблицей Конвея, отвечающей S. Рассмотрим множества Sn = nN (множество натуральных чисел, делящихся на n), и S = m(m+1) ; m N . 2 Для S3 и S4 таблицы Конвея будут иметь следующий вид (выделенные числа обведены в кружочек):
Определение 1.

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

Для

таблица Конвея будет такой:

3


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

Заметим, что если Vnm выделено, то числа Vnm+1 не существует, и число Vnm+1 , если существует, то выде-1 лено. И наоборот, если Vnm не выделено, то число Vnm+1 существует, и число Vnm+1 , если существует, то -1 не выделено. Если числа Vnm не существует, то число Vnm 1 либо выделено, либо не существует, и числа - m Vn-+1 тоже не существует. 1 1+d Заметим, что в таблице Конвея, отвечающей Sn , выделены числа вида Vnk-d , при всех k N, 0 d n - 1 и только они. В таблице Конвея, отвечающей Sn (где Sn = nN множество натуральных чисел, делящихся на n), при k N, 0 d n - 1 выполняется следующее соотношение:
Теорема 1.

1+d Vnk-d = k

d

n-1 d

(3)
n

1+ В таблице Конвея, отвечающей S , выделены числа вида Vm-dd , при всех m = n(n2+1) , n N, 0 d n - 1 и только они. Числом Стирлинга первого рода n обозначается число способов представления k объектов в виде k циклов. Для чисел Стирлинга существует следующее рекуррентное соотношение:
Определение 2.

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

(4)

Его легко доказать комбинаторно. В любом представлении n объектов в виде k циклов можно указать объект, который стоит в цикле перед n-м. Если это он сам, то, выбросив цикл, состоящий из n-го элемента, -1 получаем представление n - 1 объектов в виде k - 1 циклов, а значит, таких представлений n-1 . Если k же это один из оставшихся n - 1 объектов, то, объединив его с n-м, получаем представление n - 1 объектов в виде k циклов, а значит, таких представлений n-1 . В итоге получаем формулу (4). k Рассмотрим многочлены:
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

(5)

Нетрудно заметить, что коэффициенты у получившихся многочленов совпадают с числами Стирлинга:
n

xn =
k=1

n x k

k

(6)

Докажем эту формулу по индукции. База индукции формулы (5). Индукционный переход: Заметим,

4


что

(x + n - 1)xk = x

k+1

+ (n - 1)x
n-1

k

. Тогда:
n-1 k=1

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

= (x + n - 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

(7)

=
k=1

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

=
k=1

nk x, k

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

nN 0d

,

В таблице Конвея, отвечающей S, где S множество чисел вида n - 1 выполняется следующее соотношение:
1+ Vm-d = d

m=

n(n+1) 2

, при
(8)

n n-d

Для доказательства теорем сначала докажем две леммы:
1 Рассмотрим произвольное выделенное число Vm +1 первой строке таблицы Конвея, отвечаюв n 2 3 1 щей S. Пусть существуют числа Vm, Vm-1, Vm-2, . . . , Vm-n, прич?м 1множествоnS 1и число nnтаковы, 2 1 что все числа вида Vm+d, 1 d n, не выделены. Обозначим A(x) = Vmxn + Vm-1x - + . . . + Vm-n-1x + n+1 n+1 n-1 n 1 n 2 + . . . + Vm+2 x + Vm+1 . Тогда B (x) = A(x + 1). Vm-n , B (x) = Vm+n+1 x + Vm+n x Доказательство. Докажем по индукции следующую формулу при 1 k n:
Лемма 1.

k k Vm +1+n-k

=
i=1

i Vm

+1-i

n-i n-k

(9)

База индукции

n=1

: тогда
k i=1

k=1 V

и
n-i n-k
1 = Vm +1-1

i m+1-i

=V

1 m

=V

1 m+1

Индукционный переход

n-1n

. Тогда, по предположению индукции для любого
k k Vm +n-k

1k n-1

верно

=
i=1

V

i m+1-i

n-1-i n-1-k

Для

k=n V

можно проверить правильность формулы (9):
n m+1

=V

n m+1-n

+

n-1 Vm+1

=V

n m+1-n

0 0

n-1

+
i=1

V

i m+1-i

n-1-i 0

n

=
i=1

V

i m+1-i

n-i 0

Для
k Vm

k=1

формула (9) очевидна. Оста?тся проверить е? для
k-1 k = Vm-1 n +1+ -k

2k n-1
i Vm

:
k

+1+n-k

+V

k m+n-k

=
i=1

i Vm

+1-i

n-1-i + n-k

k +1-i

i=1

n-1-i n-1-k

=
i=1

i Vm

+1-i

n-i n-k

5


Формула (9) доказана. Многочлен B (x) представляется как
n n n+1-j

B ( x) =

xj V
j =0

n+1-j m+1+j

=
j =0

x

j i=1

V

i m+1-i

n-i+1 j in-i+1

по формуле (9) (

m + 1 + j = m + 1 + (n + 1) - (n + 1 - j )
n n

). Сделав замену
i j

, получаем

B (x) =
j =0

x

j i=j

V

n+1-i m-n+i

что в точности соответствует формуле (1), откуда
k+1 1+k Vm+1+l = i=1
Лемма 2.

B (x) = A(x + 1) k, l 0 k + l n

Заметим, что аналогичным методом можно доказать для всех
i Vm +1-i

,

, что (10)

k+l-i+1 l

1 Рассмотрим произвольное невыде2ленное3 число Vm nв+1 первой строке таблицы Конвея, отве1 чающей S. Пусть существуют числа Vm, Vm-1, Vm-2, . . . , Vm-n, а чисел вида Vpn+2, где p < m - n не n+1 1 2 n 1 2 существует. Обозначим A(x) = Vmxn + Vm-1xn-1 + . . . + Vm-n-1x + Vm-n, B(x) = Vm+1xn+1 + Vmxn + n+1 n+2 . . . + Vm-n+1 x + Vm-n . Тогда B (x) = A(x)(x + 1). Доказательство. 1 1

V

k+1 m+1-k

=

Тогда
n

Vm+1 = Vm k k Vm+1-k + Vm+1 -k n+2 n+1 Vm-n = Vm-n

; (1 k n)

n

B (x) = V

1 n+1 m+1 x

+
k=1

xk V

n+2-k m+k-n

+V

n+2 m-n

1 = Vm + k=1

xk (V

n+1-k m+k-n

+V

n+2-k m+k-n-1

)+V

n+2 m-n

что в точности соответствует формуле (2), откуда B (x) = A(x)(x + 1) Доказательство теоремы 1. Рассмотрим таблицу Конвея, отвечающую

Sn 1 2 D0 (x) = 1, D1 (x) = x + 1, . . . , Dk (x) = Vk+1 xk + Vk xk-1 + . . . + V2k x + V1k+1 , . . . 1 Dk+1 (x) = (x + 1)Dk (x) 0 k n-2 Dk (x) = (x + 1)k Ak (x) = Vnk x n-1 2 n-2 n n-1 Vnk-1 x + . . . + Vnk-n+2 x + Vnk-n+1 A1 (x) = Dn-1 (x) = (x + 1) Ak+1 (x) = Ak (x + 1) Ak (x) = (x + k )n-1 (n - 1 - d) 1+d Vnk-d k d n-1 d
1 Ak (x) = Vk(k 1 Bk (x) = Vk(k

, и обозначим многочлены Согласно лемме 2, n-1 для , откуда . Далее, пусть + . Заметим, что . Из леммы 1 следует, что , откуда , а его коэффициент при -й степени равен по определению, и по биному Ньютона Доказательство теоремы 2. Рассмотрим таблицу Конвея, отвечающую S. Пусть
+1)/2

xk x

-1

2 + Vk(k 2 + Vk(k

+1)/2-1

xk

-2

+ ... + V

k -1 k(k-1)/2+2

x+V

k k(k-1)/2+1 k k(k+1)/2+1

k -1

+1)/2+k

+1)/2+k-1

x

k-2

k1 + . . . + Vk(-+1) k

/2+2

x+V

Ak ( x ) = 1

Согласно лемме 1, Bk , получаем

(x) = Ak (x + 1)

, а из леммы 2 следует, что
Ak (x) = (x + 1)
k-1 k -1

( k N)

A

k+1

(x) = (x + 1)Bk (x)

. Учитывая, что

Bk (x) = (x + 2)

n Коэффициент многочлена An (x) при (n - d - 1)-й степени равен Vn1+d /2-d по определению, и n-d по (n+1) формуле (6) Интересно отметить, что хотя принцип заполнения таблицы Конвея в теоремах и их доказательства похожи друг на друга, результат в них получился совершенно различный. Это объясняется тем, что в первой теореме мы пользовались леммой 2 только вначале, а затем только леммой 1. Во второй же теореме на каждом шагу мы пользовались комбинацией двух лемм.

6


5 Заключение В заключение следует сказать несколько слов об авторстве идей, использованных в статье. В прошлом году Волгин Андрей, ученик 8 класса обнаружил совпадение между таблицей с числами Стирлинга и таблицами Конвея. Он преобразовал эти таблицы таким образом, чтобы они начинались с ряда единиц и доказал, что в случае с треугольными числами в выделенных диагоналях всегда будут получаться числа Стирлинга. Первое доказательство теорем о таблицах Конвея было сделано с использованием следующего рекуррентного соотношения:
n+1 = m+1
k

n k

k m

В книжке эта формула была приведена без доказательства, и он доказал е? сначала по индукции, а затем и комбинаторно. (Доказать, что задача сводится к этому соотношению, можно примерно так же, как мы доказывали лемму 1.) Для чисел сочетаний есть аналогичное соотношение:
(k + 1)
d

n = d

d

k
i=0

i

n i

n-i d-i

Весной был сделан доклад в школе по данной теме. Несколько позже Спивак А. В. привел другое доказательство рассмотренных теорем и познакомил с ним на лекции своих учеников. Это доказательство можно применить не только к рассмотренным частным случаям таблиц Конвея, а также и к другим задачам такого рода. Таким образом, можно в дальнейшем выявить какие-нибудь интересные закономерности для других множеств S (другой последовательности выделения единиц в таблице), поэтому в данной статье Волгин Андрей оформил идею этого последнего доказательства в более строгий вид.

7