Тема 4: Элементы комбинаторики
В то время, когда кончается игра в три кости,
То проигравший опять их берет.
И мечет их один в унылой злобе;
Другого провожает целый народ…
Данте «Божественная комедия»
Введение
Представителям самых разных профессий приходится решать задачи, в которых рассматриваются те либо иные комбинации, составленные из букв, цифр и иных объектов. Главе цеха нужно распределить пара видов работ между имеющимися станками, агроному – разместить посевы сельскохозяйственных культур на нескольких полях, заведующему учебной частью школы – составить расписание уроков, ученому-химику – разглядеть вероятные связи между молекулами и атомами, лингвисту – учесть разные варианты значений букв незнакомого языка и т.д. Область математики, в которой изучаются вопросы о том, сколько разных комбинаций, подчиненных тем либо иным условиям, возможно составить из заданных объектов, именуется комбинаторикой.
Комбинаторика как наука появилась в шестнадцатом веке. В жизни тогдашнего общества громадное место занимали азартные игры. В карты и кости выигрывались и проигрывались бриллианты и золото, имения и дворцы, дорогие украшения и породистые кони. Обширно были распространены всевозможные лотереи. Ясно, что первоначально комбинаторные задачи касались по большей части азартных игр – вопросов, какое количество методами возможно выкинуть данное число очков, бросая две либо три кости, либо какое количество методами возможно взять двух королей в данной карточной игре. Эти и другие неприятности азартных игр явились движущейся силой в развитии комбинаторики и развивавшейся в один момент с ней теории возможностей.
Одним из первых занялся подсчетом числа разных комбинаций при игре в кости итальянский математик Н. Тарталья. Он составил таблицу, показывающую, какое количество методами смогут выпасть r костей. Но наряду с этим не учитывалось, что одинаковая сумма очков возможно взята различными методами (к примеру, 1 + 3 + 4 = 4 + 2 + 2).
Исследование вопросов комбинаторики предприняли в семнадцатом веке французские ученые Б. Паскаль и П. Ферма. Исходным пунктом их изучений также были неприятности азартных игр. Особенно громадную роль сыграла тут задача о разделе ставки, которую внес предложение Паскалю его приятель шевалье де Мере, страстный игрок. Неприятность пребывала в следующем: «матч» в орлянку ведется до шести побеждённых партий; он был прерван, в то время, когда один игрок победил 5 партий, а второй – 4; как поделить ставку? Было очевидным, что раздел в отношении 5:4 несправедлив. Применив способы комбинаторики, Паскаль решил задачу в общем случае, в то время, когда одному игроку остается до выигрыша r партий, а второму s партий. Второе ответ дал Ферма.
Предстоящее развитие комбинаторики связано с именами Я. Бернулли, Г. Лейбница и Л. Эйлера. Но и у них главную роль игрались приложения к разным играм (лото, солитер и др.). За последние годы комбинаторика переживает период бурного развития, связанного с неспециализированным увеличением интереса к проблемам дискретной математики. Комбинаторные способы употребляются при ответе транспортных задач, в частности задач по составлению расписаний; для составления замыслов производства и и реализации продукции. Установлены связи между задачами и комбинаторикой линейного программирования, статистики и т.д. Комбинаторика употребляется для декодирования и составления шифров и для ответа вторых неприятностей теории информации.
Несложные комбинаторные задачи
Знакомство с новыми понятиями начнем с двух несложных задач.
Пример 1. какое количество четных двузначных чисел возможно составить из цифр 0, 1, 2, 4, 5, 9?
Ответ. Составим таблицу: слева от первого столбца поместим первые цифры искомых чисел, а выше первой строки – вторые цифры этих чисел. Так как в двузначном числе на первом месте может находиться каждая цифра, не считая 0, то строчки будут отмечены цифрами 1, 2, 4, 5, 9. Значит, в отечественной таблице будет пять строчков. На втором месте в искомом числе обязана находиться четная цифра, значит, столбцы будут отмечены цифрами 0, 2, 4. Всего в таблице будет три столбца.
Клетки таблицы заполняются следующим образом: первая цифра числа равна метке строчка, а вторая цифра – метке столбца, исходя из этого каждое из интересующих нас чисел попадет в определенную клетку таблицы. По столбцам и строкам мы перечислили все вероятные варианты, значит, искомых чисел будет столько же, сколько клеток в таблице, т. е. 5 • 3 = 15.
Ответ: 15.
Тут был осуществлен полный перебор всех вероятных вариантов, либо, как в большинстве случаев говорят в таких случаях, всех вероятных комбинаций. Исходя из этого подобные задачи именуют комбинаторными.
Пример 2. На ланч Вова может выбрать плюшку, бутерброд, пряник либо кекс, а запить их он может кофе, соком либо кефиром. Из какое количество вариантов завтрака Вова может выбирать?
Ответ. Соберем все варианты в таковой таблице:
В ней три строки и четыре столбца, они образуют 12 клеток. Так как выбор напитка и еды происходит независимо, то в каждой клетке будет находиться один из вероятных вариантов завтрака и, напротив, любой вариант завтрака будет записан в одной из клеток. Значит, всего вариантов столько же, сколько клеток в таблице.
| Плюшка | Бутерброд | Пряник | Кекс | |
| Кофе | Кофе, плюшка | Кофе, бутерброд | Кофе, пряник | Кофе, кекс |
| Сок | Сок, плюшка | Сок, бутерброд | Сок, пряник | Сок, кекс |
| Кефир | Кефир, плюшка | Кефир, бутерброд | Кефир, пряник | Кефир, пряник |
Ответ: 12.
Мы видим, что, не смотря на то, что примеры 1 и 2 весьма различные, их решения совсем однообразные. Основаны они на неспециализированном правиле умножения.