Документ взят из кэша поисковой машины. Адрес оригинального документа : http://kvant.mccme.ru/pdf/2011/02/kaleidoskop.pdf Дата изменения: Tue Oct 30 14:53:16 2012 Дата индексирования: Sun Feb 3 06:49:35 2013 Кодировка: Windows-1251 Поисковые слова: hst

Числа Стирлинга
20 лет назад, в седьмом номере 'Кванта' за 1991 год, в рубрике 'Математические сюрпризы' была опубликована статья Дж.Конвея 'Один старый факт и несколько новых'. Там на числовых примерах было рассказано о двух чудесах, и автор просил доказать, что они всамделишные. Попробуем с ними разобраться. Начнем издалека, с алгебры. Возрастающими степенями называют следующие многочлены: таким образом,



5 4 5 4 4 = = 1 , = 4 + = 10 , 4 5 4 4 3 5 3 4 4 5 4 4 = 4 3 + 2 = 3 5 , = 4 + = 50 2 2 1 5 4 и = 4 = 24 . 1 1

x1 = x ,
x = x ( x + 1) = x + x ,
2 2

x 3 = x ( x + 1) ( x + 2 ) = x 3 + 3x 2 + 2x ,

Вообще,

x 4 = x 3 + 3x 2 + 2x ( x + 3 ) = x 4 + 6 x 3 + 11x2 + 6 x .
Коэффициенты этих многочленов это и есть числа Стирлинга1 (рис.1). Коэффициент при k-й степени у

(

)

n n n n = 1 , 1 = (n - 1)! , = 0 0 n + 1 n n = n + и при 1 k n . k k k - 1
Теперь комбинаторика. Количество способов разбить n человек на k хороводов это в точности число Стирлинга k (в хороводе может быть от одного до n человек). Доказать это легко по индукции: база случай n = 1 совершенно очевидна. А переход тоже несложен: если нужно разбить на k хороводов n + 1 человек, то либо первый их них образует отдельный

n

Рис. 1

n-го многочлена обозначается символом вычислить пятую возрастающую степень x 5 = x ( x + 1) ( x + 2 ) ( x + 3 ) ( x + 4 ) =

n . Чтобы k

5 5 5 4 5 3 5 2 5 1 = x + x + x + x + x , 5 4 3 2 1 проще всего бесхитростно раскрыть скобки. Но мы поступим хитрее, заодно получим рекуррентные соотношения: x5 = 4 4 4 4 x + 3 4 5 = x + 4 4 4 x 3 + x2 2 4 4 4 + x 4 3 4 + x1 ( x + 4 ) = 1 4 4 + 4 + x3 + 3 2 4 4 4 + 4 + x2 + x1 , 1 2 1

1 Точнее, числа Стирлинга первого рода; бывают еще числа Стирлинга второго рода это количество разбиений множества из n элементов на k непустых подмножеств.

n k

хоровод, и таких способов ровно , либо же надо k - 1 сначала разбить остальных n человек на k хороводов, а затем поставить первого по правую руку от любого из n уже стоящих в хороводах людей. Теперь начинаются чудеса Дж.Конвея. Выпишем в ряд бесконечную последовательность единиц и обведем в кружок те, номера которых треугольные числа: 1, 1 + 2 = 3, 3 + 3 = 6, 6 + 4 = 10, 10 + 5 = 15, Это первая строка рисунка 2. Вторая и последующие строки получаются так: числа записываются только под необведенными числами предыдущей строки, каждое число должно равняться сумме чисел, расположенных непосредственно слева и сверху от него (первое число строки равно просто стоящему над ним числу), в кружок обводятся числа, стоящие наискосок влево-вниз от обведенных чисел предыдущей строки. Обведенные в кружок числа это числа Стирлинга! Чтобы объяснить это чудо, введем новые обозначения. Наш рисунок 2 разбивается на бесконечное число 'треугольных' частей (на рисунке они отделены друг от друга вертикальными прямыми). Занумеруем их. На рисунке 3 изображен четвертый 'треугольник'. Число, стоящее в n-м треугольнике на пересечении i-й строки

n


Рис. 2

и j-го столбца, обозначим (столбцы треугольника i, j нумеруются слева направо, а строки снизу вверх). Для удобства обведенные в кружок числа предыдущего треугольника будем считать нулевым столбцом данного. Обозначения, приведенные рядом с четвертым треугольником на рисунке 3, поясняют сказанное. Оче-

n

то в нижней строке получим квадраты натуральных чисел! Более того, как и для чисел Стирлинга, ряды

Рис. 4

Рис. 3

обведенных кружочками чисел это коэффициенты 2 2 2 2 многочленов ( x + 1) , ( x + 2 ) , ( x + 3 ) , ( x + 4 ) , Если обведем каждую четвертую единицу (рис.5), то в нижней строке получим кубы. Соответствующие мно3 3 3 3 гочлены это ( x + 1) , ( x + 2 ) , ( x + 3 ) , ( x + 4 ) ,

видно, = и n - 1 = 0, n . k k, k Вся таблица не только обведенные в кружок числа Стирлинга! удовлетворяет тому же рекуррентному соотношению, что и сами числа Стирлинга: например,

n

n

n - 1

n

5 5 6 2, 4 = 58 = 5 8 + 18 = 5 2, 4 + 1, 3
и

5 5 6 3, 4 = 71 = 5 9 + 26 = 5 3, 4 + 2, 3 ; n n + 1 n m, k = n m, k + m - 1, k - 1 .

Рис. 5

вообще,

Есть ли у чисел комбинаторный смысл мы не m, k знаем. Может быть, тут нам помогут читатели? Теперь второе чудо. Если обвести не единицы с треугольными номерами, а каждое третье число (рис.4),

n

Аналогичная закономерность верна и при обведении в кружок каждой пятой единицы. Более того, если n1 n2 n3 n4 ... , то при обведении в кружок единиц с номерами n1 , n1 + n2 , n1 + n2 + n3 , n1 + n2 + n3 + n4 , мы получим многочлены, которые замечательным образом разлагаются на множители. Как именно, рассказано в разделе 'Ответы, указания, решения' в конце журнала.
А.Волгин (ученик 8 класса), А.Спивак