Документ взят из кэша поисковой машины. Адрес оригинального документа : http://kvant.mccme.ru/pdf/1999/06/09.pdf Дата изменения: Fri Dec 23 19:25:32 2005 Дата индексирования: Tue Oct 2 00:09:37 2012 Кодировка: Windows-1251 Поисковые слова: galaxy cluster

ЧТО

ТАКОЕ

КОМБИНАТОРИКА

9
сомнительными. Что ж, скептики могут, например, честно перемножить скобки в (11), привести подобные и непосредственно проверить, сколько получится слагаемых и каков окажется коэффициент при 223 xyz. По-человечески жаль их, конечно. Все-таки седьмая степень. Почти наверняка где-то собьются, надо будет искать ошибку, исправлять чтобы после всех трудов 'причалить', наконец, к числам 36, 210, которые мы нашли, можно сказать, устно.

а в 6) величина 1 1 1 1 + + + + 2 ! 0 ! 0 ! 0 ! 2 ! 0 ! 0 ! 0 ! 2 ! 1!1! 0 ! 1 1 + = 4, 5 . + 1! 0 !1! 0 !1!1! Как видим, в случаях 5) , 6) легко обойтись и без . Но представьте себе, что в 6), например, 2 заменено на 200. Запись с останется столь же короткой, а о 'явной' записи (без ) даже думать не хочется. При многоиндексном суммировании довольно часто встречаются 'кратные' ( под знаком ); мы их применять не будем.

b

g

очевидным образом переносится на общий случай. Примем для определенности m = 3, n = 7 и найдем коэффициент при 223 x y z в выражении или, точнее, в выражении, которое получится после возведения в степень и приведения подобных членов. Забудем временно о показателях степени и запишем (10) в виде произведения 7 скобок

b

x+y+z ,

g

7

(10)

b

x + y + z x + y + z K x + y + z .(11)

gb

gb

g

Комбинаторика помогает алгебре
Все знают формулу Эрудиты помнят также выражения для куба суммы двух слагаемых и для квадрата суммы произвольного числа слагаемых. Но даже из эрудитов мало кто подозревает, что все это одна и та же формула, вернее, ее частные случаи. Вот она, эта формула:

c

x1 + x2

h

2

=

2 x1

+ 2 x1 x2 +

2 x2

.

Выполняя почленное умножение без изменения порядка сомножителей, мы будем получать произведения, выглядящие как слова. Скажем, если в каждой скобке берется первое слагаемое, получим ххххххх. Нас, однако, сейчас интересуют произведения, куда х, у и z входят сомножителями 2, 2 и 3 раза соответственно. Например, произведение уxxzzzy, которое получается, если в первой скобке берется второе слагаемое, во второй и третьей первое и т.д. Сколько будет слагаемых этого типа? Знакомая ситуация, не правда ли? Помните, мы переставляли буквы слова КОЛОКОЛ и нашли, что таким образом можно получить 7! = 210 различных слов (пе2!2! 3! рестановки с повторениями)? Теперь у нас вместо К, Л, О буквы x, y, z. Разумеется, на ответ это не влияет. Итак, соответствующее слагаемое имеет вид 7! 223 223 x y z = 210 x y z . 2!2! 3! Мы получили (для m = 3, n = 7) одно из слагаемых в правой части (9). Все остальные получаются точно так же. Да, кстати, а сколько всего этих слагаемых? Конечно же, слагаемых ровно столько, сколько решений в целых числах ki 0 у нашего любимого уравнения k1 + + km = n, т.е. n + m -1 . В данном случае полуm -1

Любимая формула Коровьева (бином Ньютона)
'Подумаешь, бином Ньютона', говаривал небезызвестный Коровьев, вице-премьер еще более небезызвестного Воланда. Что, собственно, он имел в виду? Смысл ясен это, мол, не проблема. Но все-таки: что за бином такой? А это просто частный случай формулы (9) при m = 2:

c

x1 + x2 + K + xm
=

h

n

=
k x1 1

b

x+y

n g = FGH kIJK
n n k=0

x

n- k

y . (12)

k

k1 ,K,km 0 k1 +K + km = n



n! k1 !K km !

K

k xmm

. (9)

Некоторая сложность выражения является, так сказать, платой за универсальность ведь формула верна для любых натуральных m и n. Суммирование в (9) ведется по всем целочисленным кортежам, удовлетворяющим указанным условиям. Читателю предлагается самостоятельно проверить, что при n = 2 (9) переходит в обычную формулу для квадрата суммы. Такая проверка, конечно, не заменяет обоснования, которым мы теперь и займемся. Тот факт, что правая часть (9) является суммой членов вида
Иллюстрация Ю.Ващенко

Кстати, бином в переводе значит двучлен (а речь здесь идет именно о степени двучлена). Теперь читателю ясно, почему числа сочетаний обычно называют биномиальными коэффициентами. Для примера возьмем, скажем, n = = 4:

b

x+y

+
4

4 4 g = FGH 0IJK x + FGH 1IJK x y + F 4I x y + F 4I xy + F 4I GH 2JK GH 3JK GH 4JK
4 4 3 2 2 3 3 2 2 3

y=
4

4

= x + 4 x y + 6 x y + 4 xy + y .(13) Разумеется, для столь малого n(=4) тот же результат легко получить простым возведением в степень 2 например, возведя в квадрат x + 2 + 2ху + y . Суть биномиальной формулы (12) именно в том, что она дает ответ непосредственно, без обращения к низшим степеням. То же относится и к более общей формуле (9) (ее иногда называют полиномиальной). Следующая таблица известна как арифметический треугольник, или

cx1 1 x2 2 K x

k

k

km m

( k1, K, km 0 ,

k1 + K + km = n ),

ясен. Все дело в том, чтобы найти коэффициент с (зависящий, конечно, от k1 , , km ). Чтобы не утомлять читателя суетой с индексами, затемняющей суть дела, мы, как и ранее, ограничимся частным случаем. Основная идея
3 Квант ? 6

F GH

чится

Кому-то наши скоростные способы 'возведения в степень без возведения в степень' могут показаться

F 9I GH 2JK

I JK

= 36 слагаемых.