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

ЧТО

ТАКОЕ

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

7
Очевидно, столько же, сколько 2-подможеств у 20-элементного множества, т.е.

речень больше основного. Каждое слово вспомогательного перечня закодируем кортежем длины 4, где первая компонента соответствующее слово основного перечня (число таких слов обозначим через х), а остальные определяют порядок следования индексов. Так, слово О2 К2 К1О1 Л1 Л2 О3 получит код ОККОЛЛО, К2 К1 , Л1 Л2 , O2 O1O3 (для определенности выбираем алфавитный порядок букв). Такие коды образуют множество простой структуры. Действительно, компоненты пробегают возможные значения независимо одна от другой, причем первая пробегает х значений, а остальные 2!, 2!, 3! значений соответственно (это обычные числа перестановок). Итак, по принципу умножения число слов вспомогательного перечня (т.е. 7!) равно в то же время x 2 ! 2 ! 3 ! , откуда 7! x= = 210 . 2!2!3! Данные рассуждения переносятся на общий случай практически без изменений. Новый индекс можно ставить, например, вверху: получаем n 1 1 различных букв A1 , , A1n1 , , Ak ,... nk , Ak . Из них можно составить n! слов вспомогательного перечня. Кодируя их, как выше, и пересчитывая вторым способом с помощью принципа умножения, получаем равенство (х искомое число)
x n1 ! n2 ! K nk ! = n !,

нях и состояниях физической системы, но формула от этого, конечно, не меняется. Помимо принципа умножения этого излюбленного орудия элементарной комбинаторики выше был применен новый для нас прием 'растождествления'. Он показывает, как с пользой для дела можно переходить от одного понятия тождества (или различия) к другому. Если при нечеткости формулировок в связи с этим возникали путаница и недоразумения, то при точном понимании терминов т.е. при соблюдении Главного Правила Комбинаторики здесь открываются новые возможности решения задач.

F 20I GH 2 JK

=

20 19 12

= 190 .

Сочетания
В задаче 3 мы подсчитывали число всех подмножеств у n-множества. Поставим теперь вопрос иначе. Задача 8. Сколько существует mподмножеств у n-множества? Естественно, имеются в виду различные m-подмножества (эта оговорка ради краткости обычно опускается). Подразумевается, конечно, что m n. Неискушенного человека могло бы удивить, что ответ на этот вопрос по существу дан в предыдущем пункте. Там ведь речь шла об упорядоченных наборах с повторениями, а подмножества неупорядоченные наборы без повторений. Но наш читатель, надеемся, не забыл, как удачно кодируются подмножества двоичными векторами. А двоичный вектор это ведь слово в алфавите из двух 'букв' 0 и 1. При таком кодировании каждому m-подмножеству n-множества отвечает слово, содержащее m 'букв' 1 и n m 'букв' 0. Итак, искомое число равно n! n n - 1 ... n - m + 1 . = m! n - m ! 1 2 K m (5)

К тому же результату легко прийти и непосредственно: каждая из 20 команд проводит по 19 встреч; всего вроде бы получается 20 19 встреч, при этом каждая встреча засчитывается дважды, так что надо еще поделить на 2. Фактически это повторение общего рассуждения для очень простого частного случая. Столько же рукопожатий при встрече 20 человек если все здороваются друг с другом. Задача 10. Сколькими способами можно выбрать 3 дежурных в классе из 25 человек? Ответ очевиден:

поэтому число слов основного перечня равно n! (4) n1 ! n2 !K nk ! . Из доказанного следует, между прочим, что эта дробь всегда является целым числом. Полученное выражение для числа перестановок с повторениями центральный результат элементарной комбинаторики. Как частные случаи, оно содержит выражения для числа обычных перестановок (при k = n) и для числа сочетаний (при k = 2, см. ниже). Стоит еще упомянуть, что в знаменитой работе физика Л.Больцмана, где впервые был выяснен статистический смысл второго начала термодинамики, также не обошлось без выражения (4). Речь там шла не о буквах и словах, а о молекулах, энергетических уров2

b

g

b

gb

g

Тут важно, что все трое дежурных равноправны, и, значит, от порядка, в котором названы 3 фамилии, выбор не зависит. Иное дело, если бы речь шла о трех разных поручениях допустим, выбираются староста, кассир и физорг. Это были бы уже не сочетания, а размещения, и способов было бы в 3! = 6 раз больше (предполагается, что школьнику дается не более одного поручения). Рассмотрим теперь прямоугольную сетку, образованную равноотстоящими прямыми (см. рисунок). Можно считать, например, что это уличная сеть (чересчур правильная для реального города). Сколько существует кратчайших путей из A1 в A2 , проходящих по этой сетке? Если расстояния между соседними прямыми равны 1, то все кратчайшие пути имеют, очевидно, длину 12. Один из них выделен на рисунке.
)

F 25I GH 3 JK

=

25 24 23 12 3

= 2300 .

Величина (5) обозначается обычно n m и называется числом Cn или m сочетаний из n по m; часто эти числа называются также биноминальными коэффициентами (причина такого названия станет ясной чуть позже). Встречаются эти величины очень часто. Вот несколько примеров. Задача 9. Сколько встреч будет проведено в турнире 20 команд по круговой системе (в 1 круг)?

FI GH JK

)



Основной момент в решении кодирование путей. Каждый из 12 единичных этапов кратчайшего пути на-

*