Сочетание и перестановки с повторением в комбинаторике

Рождение комбинаторики в западноевропейской математике произошло в XVII веке благодаря работам Блеза Паскаля (1623— 1662) и Пьера Ферма (1601—1655), которые заинтересовались математическими аспектами азартных игр. Поэтому неудивительно, что ее развитие шло бок о бок с теорией вероятностей, которая изучает число возможных вариантов, представленных в том или ином случайном процессе. Укрепление комбинаторики как независимой ветви в математике обязано фундаментальным трудам Якоба Бернулли (1654—1705) и Вильгельма Лейбница (1646—1716), которые заложили теоретические основы теории вероятностей, определив для этого основные понятия комбинаторики. Лейбниц ввел термин «комбинаторика» в своей работе «Dissertatio de Arte Combinatoria» ("Об искусстве комбинаторики").В начале XVIII века швейцарский математик Леонард Эйлер (1707—1783) разработал целую школу комбинаторной математики и создал так называемые «производящие функции последовательности», которые послужили основой для последующего развития вычисления комбинаторных конфигураций. В предложенном им решении задачи о семи мостах Кенигсберга уже проступали контуры будущей теории графов — теории, тесно связанной с комбинаторикой и имеющей широкое применение на практике.

Сейчас рассмотрим несколько задач в которых применяется комбинаторика практически. В цветочном магазине есть пять видов цветов — скажем, розы, гвоздики, георгины, лилии и камелии, а нам необходимо купить букет из десяти цветов. Сколько у нас есть способов составления букета? Конечно, тут не важен порядок, нас интересует только какие цветы выбрать и сколько. Таким образом, речь идет о сочетании. Но в данном случае присутствует повторение, ведь никто не мешает составить букет хоть из 10 цветов одного вида, если этот вид нам особенно нравится.

Количество С’_5,10 этих сочетаний с повторением пяти элементов, взятых из 10 по 10, решается путем перевода задачи к другим сочетаниям без повторений. Однако как нам узнать количество элементов, которое позволило бы выбрать эти равнозначные сочетания без повторения? Для этого надо сложить 5 и 10 и вычесть 1; элементы берутся из 10 по 10: С’_5,10 = С’_5+10-1,10 = С’_14,10 = 1001. Итак, для числа С’_m,n в сочетаниях с повторением m элементов, взятых из n по n: C′m,n=(m+n−1)!n!(n—1)!Cm,n′=(m+n−1)!n!(n—1)! И ещё одна головоломка. У нас имеется ряд из девяти шаров разных цветов: двух белых, трех синих и четырех красных. Сколько возможных комбинаций существует? Речь о перестановках, но о перестановках с повторением. Поскольку при смене места шаров одинакового цвета порядок не нарушается, то сокращается количество вариантов перестановок. Чтобы узнать число оставшихся возможностей, надо сосчитать число перестановок для девяти объектов и разделить его на перестановки из 2 элементов, из 3 и из 4: P9;2,3,4=P9P2⋅P3⋅P4=9!2!⋅3!⋅4!=1260P9;2,3,4=P9P2⋅P3⋅P4=9!2!⋅3!⋅4!=1260 Основное выражение таково: Pm;n,p,q=PmPn⋅Pp⋅PqPm;n,p,q=PmPn⋅Pp⋅Pq. И ещё есть много интересных задач, которые решаются с помощью комбинаторики.