Избранное
ЭБ Нефть
и Газ
Главная
Оглавление
Поиск +
Еще книги ...
Энциклопедия
Помощь
Для просмотра
необходимо:


Книга: Главная » Введенский Б.А. Большая советская энциклопедия Том 22 нет стр 35-44
 
djvu / html
 

120
КОМБИНАТОРИКА
ными и типичными операциями и связанными с ними задачами К. являются следующие:
1) Упорядочение множества, состоящее в установлении определённого порядка следования элементов множества друг за другом. Упорядочение конечного множества может быть осуществлено нумерацией его элементов. Пусть множество состоит из п элементов; после упорядочения они образуют конечную последовательность [vb v2, ..., >„] (У!—первый элемент, va—второй элемент,..., vn—тг-й элемент), к-рую называют упорядоченным множеством, или перестановкой из п элементов. В связи с этой операцией ставится задача определения числа различных способов упорядочить данное множество, т. е. числа всех различных перестановок из 71 элементов. Это число обозначается через Рп. Можно доказать, что
Ря=1.2.3.....л = я! (1)
(знак п\ читается: «п факториал»; во многих вопросах оказывается целесообразным распространить это обозначение и на значение п= 0, полагая 01 —i, см. Гамма-функция). Напр., множество из трёх элементов а, Ь, с можно упорядочить шестью (3! =6) способами, т. е. существует шесть перестановок из трёх элементов: (я, 6, с); (а, с, Ь); (Ь, а, с); (Ъ, с, а); (с, о, Ь)', (с, Ъ, а).
2) Образование подмножеств, состоящее в выделении из данного множества Л/нек-рой части его элементов. Выделенные элементы образуют подмножество множества М', само множество М также рассматривается как одно из своих подмножеств; кроме того, к подмножествам любого множества причисляют ещё т. н. «пустое» множество, не содержащее ни одного элемента. Если М содержит п элементов, то любое подмножество множества М, содержащее k элементов (А=0, 1, 2,..., п), называется сочетанием из'га элементов данного множества по k элементов (значению k=0 соответствует пустое множество, k=n — само множество М). В связи с этой операцией ставится задача определения числа всевозможных сочетаний из п элементов по k элементов. Это число обозначается через С^> или (?). Можно доказать, что
п!
n (n—1) . . . (n —ft + 1)
ft ! (n—ft)
(2)
___
ft! (n
^т-гт сохраняет смысл при fc=
(выражение
п! и k=n: оГпТ=:^)' Напр., для множества из пяти
элементов а, Ь, с, d, е можно образовать десять (С^=1~2 = 10) подмножеств, содержащих каждое по
два элемента этого множества, т. е. существует десять сочетаний из пяти элементов по два: (а, Ь); (а, с); (a, d); (а, е); (Ь, с); (Ъ, d); (b, е); (с, d); (с, е); (d, е).
Числа С\ называются также биномиальными коэфициентами, так как они входят в разложение ге-й степени двучлена в качестве коэ-фициентов:

Общее число всех подмножеств множества, содержащего 71 элементов, равно 2" (здесь в число подмножеств также включены пустое множество и само множество), т. е.
Важными соотношениями между биномиальными коэфициентами являются ещё следующие:
на последнем соотношении основано построение т. н. треугольника Паскаля (см. Арифметический треугольник).
3) Образование упорядоченных подмножеств приводит к понятию размещения из п элементов по k элементов; так называется каждое упорядоченное подмножество, состоящее из k элементов данного множества (содержащего п элементов); при этом считается, что пустое множество (как и подмножество, состоящее из одного элемента) может быть упорядочено единственным образом. Число размещений из п элементов по k обозначается через А^, оно равно
Л*=п(я-1) ... (я-ft + l). (З)
Действительно, число подмножеств множества из п элементов, состоящих из k элементов, равно С* ; каждое из них может быть упорядочено Pk способами. Это приводит к соотношению
4t = -P*Cj; (4,
между тремя основными комбинаторными функциями Pk, С* и Л*. Из формул (4), (1) и (2) вытекает равенство (3).
Формулы К. [в том числе и приведённые выше формулы (1) и (2)] выводятся, как правило, из рекуррентных соотношений методом полной математич. индукции или путём составления и изучения производящих функций (см.).
Основные проблемы К. возникли в связи с формированием в 17 и 18 вв. алгебры многочленов и теории вероятностей и тогда же были разрешены. В качестве примера можно привести возведение в степени многочлена:
= 23
ч,
здесь суммирование производится по значениям q\, qz, . . . , qk, связанным соотношением ?i+?2+ • • • + -\-qk=n', коэфициент А^п — т. н. п о л и-
2/е х QI 1 <Ь> • • • > 9.';
номиальный коэфициент — определяется формулой:
^(н) ___ /"tTl—Qj /~iTl—Q[—fjj /"*® __
9i, 9i, •••,9t n n — _________nl
9,! g2l ... g/jl
В теории вероятностей комбинаторные задачи появились, напр., при подсчёте вероятностей на основании гипотезы о «равновозможных» или «равновероятных» событиях. В дальнейшем задачи комбинаторного характера возникли во многих математич. дисциплинах. Весьма сложные комбинаторные функции, требующие для своего изучения использования аппарата математич. анализа, встречаются в теории чисел. Типичным примером является число р(п) существенно различных разложений натурального числа п на сумму произвольного числа положительных целых слагаемых (включая и «разложение», состоящее из самого числа; два разложения, отличающиеся только порядком слагаемых, при определении р(п) существенно различными не считаются). Так, р(5) — 7 (5 = 1+4 = 2 + 3 = 1+1 + + 3 = 1^2 + 2=1 + 1+ 1 + 2=1 + 1+1 + 1 + 1). Производящей функцией для комбинаторной функции р(п) является
оо
= ^ р (п) ж".
п=0
.
(\ чЛ {\ -V2^ (\ fa\
\ i Л) {1 А ) \\. Л )
р(0)=1.
К К. тесно примыкает понятие подстановки (см.), сыгравшее значительную роль в общем исследовании

 

1 10 20 30 40 50 60 70 80 90 100 110 120 121 122 123 124 125 126 127 128 129 130 140 150 160 170 180 190 200 210 220 230 240 250 260 270 280 290 300 310 320 330 340 350 360 370 380 390 400 410 420 430 440 450 460 470 480 490 500 510 520 530 540 550 560 570 580 590 600 610 620


Большая Советская Энциклопедия Второе издание