Математика в школе - Бунимович Е.
Скачать (прямая ссылка):
9
от повседневной жизни, словом называют любую комбинацию из букв, независимо от того, имеет ли она какой-то смысл, или не имеет.
Пример 2. Выпишем все четырехбуквенные слова, которые можно составить, используя только буквы А и Б: АААА, АААБ, ААБА, ААББ, АБАА, АБАБ, АББА, АБББ, БААА, БААБ, БАБА, БАББ, ББАА, ББАБ, БББА, ББББ.
На этот раз комбинаций получилось гораздо больше, и при их перечислении было очень легко запутаться: например, выписать какое-нибудь слово повторно, или, что еще хуже, какое-то слово пропустить вовсе. Чтобы этого не случилось, важно установить некоторое правило, по которому перечисляются комбинации. Самое универсальное правило - выписывать все комбинации по порядку.
Для чисел выписывание «по порядку» означает «по возрастанию», а для слов -«по алфавиту». Если бы все 16 слов из примера 2 содержались в русском языке, то именно в этом порядке они были бы перечислены в орфографическом словаре.
Во многих задачах приходится иметь дело с комбинациями, в которых любая буква (цифра) может использоваться не более одного раза. Перечисление таких комбинаций может оказаться более сложной задачей.
Пример 3. Перечислим все трехзначные числа, которые можно составить из цифр 0, 1, 2, используя каждую из цифр не более одного раза. Будем выписывать числа в порядке возрастания: 102, 120, 201, 210.
Пример 4. Перечислим все четырехзначные числа, которые можно составить из цифр 0, 1, 2, 3, используя каждую из цифр не более одного раза. Снова будем выписывать числа в порядке возрастания:
сначала выпишем все числа, начинающиеся с цифры 1, затем - с цифры 2, и наконец, - с цифры 3: 1023, 1032, 1203, 1230, 1302, 1320, 2013, 2031, 2103, 2130, 2301, 2310, 3012, 3021, 3102, 3120, 3201, 3210.
Если комбинации нужно составлять из реальных предметов, то используют их кодирование с помощью букв или цифр.
Пример 5. Из Калуги в Москву и из Москвы в Калугу можно добраться тремя способами: на автобусе, на электричке и на такси. Перечислим все способы, которыми можно совершить поездку из Калуги в Москву и обратно.
Обозначим каждый из используемых видов транспорта соответствующей ему буквой: А, Э, Т. Тогда каждой поездке туда и обратно будет соответствовать двухбуквенное слово: АА, АЭ, АТ, ЭА, ЭЭ, ЭТ, ТА, ТЭ, ТТ.
Пример 6. Приехавшие в Москву на экскурсию школьники собираются посетить Третьяковскую галерею, сходить в Парк культуры и отдыха и перекусить в кафе. Выпишем все способы, которыми они могут это сделать.
Обозначим каждое из мест, которые хотят посетить школьники, соответствующей буквой: Т, П, К. Каждому способу будет соответствовать слово из трех букв, в котором все буквы разные (то есть слова будут отличаться друг от друга только порядком следования букв): ТПК, ТКП, ПТК, ПКТ, КТП, КПТ.
До сих пор мы рассматривали комбинации, в которых порядок следования элементов имел значение. В самом деле, числа 12 и 21 - это разные числа, хотя и состоящие из одинакового набора цифр, а АББА и БАБА - это разные слова. Однако есть задачи, в которых этот порядок не важен, поэтому при перечислении комбинаций его учитывать не нужно.
10
Математика в школе 5/2011
Пример 7. Из пяти иностранных языков (английский, немецкий, французский, испанский и итальянский) студентам предлагается выбрать для изучения любые два. Перечислим все способы, которыми они могут сделать свой выбор.
Обозначим каждый из предлагаемых языков своей буквой: А, Н, Ф, И, Т (для итальянского пришлось выбрать букву Т, поскольку И уже занята испанским). Тогда каждому выбору будут соответствовать любые две буквы из этих пяти, причем порядок следования выбранных букв не имеет значения:
АН, АФ, АИ, АТ, НФ, НИ, НТ, ФИ, ФТ, ИТ.
Заметим, что при выписывании каждого слова мы выписывали все его буквы по возрастанию - это позволило избежать повторения одинаковых комбинаций, отличающихся только порядком следования букв.
В качестве еще одного способа перечисления комбинаций можно использовать так называемое дерево перебора или дерево вариантов. Чтобы нарисовать такое дерево, нужно:
1) отметить точку, которая будет служить его корнем;
2) от этой точки провести все возможные отрезки (ветви), на концах которых отметить первые элементы комбинаций;
3) от каждого из этих концов нарисовать все возможные отрезки (ветви), на концах которых отметить вторые элементы комбинаций;
4) и т.д., пока вся комбинация не будет составлена.
Получится рисунок, который действительно напоминает дерево (правда, лежащее на боку или, вообще, «вниз головой»). Двигаясь от корня по ветвям такого де-
рева можно последовательно прочитать любую из полученных комбинаций.
Пример 8. Составим дерево перебора (рис. 1) для всех комбинаций из примера 2 - четырехбуквенных слов из букв А и Б:
А
Подсчет комбинаций
Вторая важнейшая задача комбинаторики - подсчет комбинаций. Иногда подсчет можно свести к перечислению: выписать все комбинации и после этого их пересчитать. Но чаще всего такой способ оказывается невозможным из-за слишком большого количества комбинаций. В этом случае для подсчета используют специальные комбинаторные правила.
