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

Рождение комбинаторики в западноевропейской математике произошло в XVII веке благодаря работам Блеза Паскаля (1623— 1662) и Пьера Ферма (1601—1655), которые заинтересовались математическими аспектами азартных игр. Поэтому неудивительно, что ее развитие шло бок о бок с теорией вероятностей, которая изучает число возможных вариантов, представленных в том или ином случайном процессе. Укрепление комбинаторики как независимой ветви в математике обязано фундаментальным трудам Якоба Бернулли (1654—1705) и Вильгельма Лейбница (1646—1716), которые заложили теоретические основы теории вероятностей, определив для этого основные понятия комбинаторики. Именно Лейбниц ввел термин «комбинаторика» в своей работе «Dissertatio de Arte Combinatoria» («Об искусстве комби¬наторики»).
Швейцарский математик Леонард Эйлер (1707—1783) разработал целую школу комбинаторной математики
В начале 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}=\frac{(m+n-1)!} {n!(n ? 1)!}
И ещё одна головоломка. У нас имеется ряд из девяти шаров разных цветов: двух белых, трех синих и четырех красных. Сколько возможных комбинаций существует? Речь о перестановках, но о перестановках с повторением. Поскольку при смене места шаров одинакового цвета порядок не нарушается, то сокращается количество вариантов перестановок. Чтобы узнать число оставшихся возможностей, надо сосчитать число перестановок для девяти объектов и разделить его на перестановки из 2 элементов, из 3 и из 4:
P_{9;2,3,4}=\frac{P_9}{P_2 \cdot P_3 \cdot P_4}=\frac{9!}{2! \cdot 3! \cdot 4!}=1260
Основное выражение таково:
P_{m;n,p,q}=\frac{P_m}{P_n \cdot P_p \cdot P_q}.
Подобными методами умные люди пользуются и по сей день, например, если вы строите или покупаете недвижимость в Ирпене в новостройке и вам надо рассчитать сколько и каких квартир можно разместить на одном этаже. Какие площади оставить на парковки или сад и т.д. Ну, а если вы уже прикупили квартирку в этом красивом месте, то можете просчитать сколькими вариантами можно расставить мебель в комнате.

И ещё есть много интересных задач, которые решаются с помощью комбинаторики.

Поделиться в соц. сетях

Опубликовать в Facebook

Оцените материал:

1 Star2 Stars3 Stars4 Stars5 Stars (1 голосов, рейтинг: 5,00 с 5)
Loading...Loading...

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Можно использовать следующие HTML-теги и атрибуты: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>