Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/mmks/dec2011/Volgin_version5.pdf Дата изменения: Wed Dec 14 17:07:23 2011 Дата индексирования: Tue Oct 2 13:59:43 2012 Кодировка: Windows-1251 Поисковые слова: m 13

Числа Стирлинга и Игры Конвея
Волгин А. Д., Спивак А. В. 13.12.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 =k n-1 k + n-1 k-1

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

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

1 3 11 50 274

1 6 35 225

1 10 85

1 15

1

А теперь сравните эту таблицу и числа в кружочках в конце предыдущего раздела.
4
1 Vn

Теоремы о таблицах Конвея

Построим таблицу Конвея Vnm, отвечающую S N, где m 1 и n 1. Положим = 1 для любого n. Для каждого s S выделим Vs1 . Каждая следующая m-я строка получается из предыдущейm-1 образом (запо-1 ид?т от n := 1;mпосле каждого шага n := n + 1): таким лнение ћ если Vn выделено или Vnm -1 = 0, то полагаем Vn := 0, m m ћ если Vn -1 не выделено и Vn = 0, то полагаем m m -1 m + Vq , где q наибольшее число, меньшее n, для которого Vqm = 0; если такого q нет, Vn := Vn то полагаем Vnm := Vnm-1. После заполнения m-й строки выделим в ней все числа, справа от которых ноль. Рассмотрим множества lN (множество натуральных чисел, делящихся на n), и +1) S = r(r2 ; r N . Для 3N и 4N таблицы Конвея будут иметь следующий вид (выделенные числа обведены в кружочек; вместо нулей стоят пробелы):
Определение 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

Для

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

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 = 0, и Vnm+1 либо равно 0, либо выделено. И наоборот, ес-1 ли Vnm не выделено, то Vnm+1 = 0, и Vnm+1 либо равно 0, либо не выделено. Если Vnm = 0, то Vnm 1 либо - -1 равно 0, либо выделено, и Vnm+1 тоже равно 0. -1 3


Заметим, что в таблице Конвея, отвечающей lN, выделены числа вида и только они.

V

1+d l k -d

, при всех

k N 0 d l-1

,

В таблице Конвея, отвечающей lN, при соотношение:
Теорема 1.

k N 0 d l-1

,

выполняется следующее
(1)

Vl1+d = k k -d
Определение 2.

d

l-1 d

Числом Стирлинга первого рода n обозначается число способов представления n k объектов в виде k циклов. d В таблице Конвея, отвечающей S , выделены числа вида Vr1++1)/2-d , при r N, 0 d r - 1 и только (r они. В таблице Конвея, отвечающей S, где S множество чисел вида r(r2+1) , при r N, 0 d r - 1 выполняется следующее соотношение:
Теорема 2.

d Vr1++1)/ (r

2-d

=

r r-d

(2)

Для доказательства теорем сначала докажем вспомогательные утверждения про многочлены и две леммы. Рассмотрим произвольный многочлен A(x) = an xn + an-1 xn-1 + . . . + a0 . Коэффициент многочлена A(x + 1) при i-й степени равен n=i k ak . k i Доказательство.
Утверждение 1.

A(x + 1) =
0kn

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

ak x

i

k i

=
0kin

ak x

i

k i

=
0in

x

i ikn

ak

k i

(3)

Утверждение 2.

). Доказательство.
an
+1

=a

-1

=0

Коэффициент многочлена
xk ak (x + 1) =

A(x)(x + 1)

при k-й степени равен
xk ak = an x
n+1

ak + ak

-1

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

A(x)(x + 1) =
0kn

xk ak +
1kn+1 0kn

+
1kn

xk (ak + ak

-1

) + a0

Утверждение 3.

Для чисел Стирлинга существует следующее рекуррентное соотношение:
n n-1 n-1 = (n - 1) + k k k-1

(5)

Доказательство. В любом представлении n объектов в виде k циклов можно указать объект, который стоит в цикле перед n-м. Если это он сам, то, выбросив цикл, состоящий из n-го элемента, получаем -1 представление n - 1 объектов в виде k - 1 циклов, а значит, таких представлений n-1 . Если же перед k n-м в цикле стоит один из оставшихся n - 1 объектов, то, объединив его с n-м, получаем представление n - 1 объектов в виде k циклов, а значит, таких представлений n-1 . В итоге получаем формулу (5) k
Утверждение 4.

n

x=

n

где

k=1

nk x, k

(6)

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

4


Доказательство. Докажем эту формулу по индукции. База индукции переход:
n-1

x1 = x =

1 1

x

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
k

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

n x k

Определение 3. Лемма 1.

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

=
i=1

i Vm

+1-i

n-i n-k

(8)

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

n=1

: тогда
k i=1

k=1 V

и
n-i n-k

i m+1-i

1 = Vm

+1-1

1 = Vm = 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 k=1

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

=V

n m+1-n

n-1 n + Vm+1 = Vm+1-

n

0 0

n-1

+
i=1

V

i m+1-i

n-1-i 0

n

=

i Vm i=1

+1-i

n-i 0

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

2k n-1
i Vm+1-i

:

k Vm+1+n-k

=

k Vm-1 n-k +1+

+V

k m+n-k

=
i=1

V

i m+1-i

n-1-i + n-k

k

Формула (8) доказана. m Многочлен Hn +n+1 (x) представляется как
n m Hn +n +1 n

i=1

n-1-i n-1-k

k

=
i=1

V

i m+1-i

n-i n-k

n+1-j

( x) =
j =0

xj V

n+1-j m+1+j

=
j =0

x

j i=1

V

i m+1-i

n-i+1 j in-i+1

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

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

). Сделав замену
V
n+1-i m-n+i

, получаем

( x) =
j =0

x

j i=j

i j

Из утверждения 1 следует

m Hn +n

+1

m (x) = Hn (x + 1)

5


Заметим, что методом, аналогичным доказательству формулы (8), можно было доказать е? обобщение: для всех k, l 0, k + l n: k+1 k+l-i+1 1+k i Vm+1+l = Vm+1-i (9) l
i=1
Лемма 2.

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

Vm

+1

= Vm

k k Vm+1 -k = Vm +1

+1-k n+2 m-n

+V =V

k+1 m-k

; (1 k n)

V

m+1 m По утверждению 2 это значит, что Hn+1 (x) = (x + 1)Hn (x) Доказательство теоремы 1. Рассмотрим таблицу Конвея, отвечающую lN.

n+1 m-n

1 H0 (x) = 1

; cогласно лемме 2,

H

k+2 k+1

(x) = (x + 1)H
+1

k+1 k

( x)

для

0k l-2

, откуда :

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

k Hk

(x) = (x + 1)k .

k = l - 1 Hll-1 (x) = (x + 1) H

l-1

. Из леммы 1 следует, что
l(k-1) -1

lk l-1

(x) = Hl

(x + 1),
-1

k Hll-1 (x) = (x + k )l

, k
d l-1 d

а его коэффициент при

(l - 1 - d)

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

Vl1+d k -d

по определению 3, и

по биному Ньютона

Доказательство теоре+1)/22. Рассмотрим таблицу Конвея, отвечающую мы k(k+1)/2+k k(k (k+2)(k+1)/2 Hk-1 (x) = Hk-1 (x + 1), а из леммы 2 следует, что Hk 1(1+1)/2 Учитывая, что H1-1 (x) = 1, получаем
Hk Hk
k(k+1)/2 -1

S k(k+1)/ (x) = (x + 1)Hk-1

. Согласно лемме 1, 2+k (x).

(x) = (x + 1)

k -1

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

(x) = (x + 2)

k -1

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

6

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

n k

k m

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

n = d

k
i=0

i

n i

n-i d-i

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

7