uzluga.ru
добавить свой файл


Комбинаторика


Определение множества



  • Как мы знаем, в каждой комбинаторной задаче требуется дать ответ на один и тот же вопрос: сколько различных комбинаций подчиняющихся

  • тем или иным условиям, можно составить из заданного множества объектов.

  • Вместо слова «комбинация» используется слово

  • «расстановка».

  • Термин «расстановка» представляется предпочтительнее термина «комбинация»,поскольку в нем содержаться указания на то, как именно получается та или иная комбинация: нужно расположить, расставить в определенном порядке некоторые из данных объектов.



  • Но чтобы расставить объекты, их надо предварительно выбрать из данного множества, руководствуясь некоторыми правилами. Поэтому многие комбинаторные задачи естественным образом укладываются в следующую схему выбора.

  • Имеется некоторое конечное множество, содержащее n различных объектов. Из него последовательно выбирается к объектов, при этом выбранный объект может быть как возвращен в множество (и следовательно, выбран повторно; тогда говорят о выборе с возвращением, этот способ выбора приводит к расстановкам с повторениями), так и не возвращен ( тогда говорят о выборе без возвращения, при таком выборе получаются расстановки без повторения).



  • При этом по смыслу задачи нас могут интересовать порядок объектов, или, как мы будем говорить, элементов в выборке, а может и не интересовать.

  • В первом случаи говорят об упорядоченных выборках, во втором - о неупорядоченных выборках.

  • По данной классификации приведите примеры ранее изученных задач.



  • Расстановки с повторениями:

  • задача о замке, задача о поваре,

  • о пловцах.

  • Расстановки без повторения:

  • выбор в цветочном городе, экзаменационная комиссия, турнир по футболу.

  • Упорядоченные выборки:

  • задача о замке, выбор в цветочном городе,

  • о пловцах.

  • Неупорядоченные выборки:

  • задача о поваре, экзаменационная комиссия.



Размещения без повторений.

  • Имеется n различных элементов. Сколько из них можно составить к расстановок?

  • При этом две расстановки считаются различными, если они отличаются друг от друга хотя бы одним элементом, либо состоят из одних и тех же элементов, но расположенных в разном порядке.

  • Такие расстановки называют размещения без повторений, а их число обозначают (читается «а из n по к»; А-первая буква французского слова Arrangement, что означает приведение в порядок).

  • Справедлива формула:

  • =n(n-1)(n-2)….(n-k+1)



Задачи

  • 1. В первой группе класса «А» первенства по футболу участвуют 17 команд. Разыгрываются медали: золотые, серебряные, бронзовые. Сколькими способами они могут быть распределены? (решение)

  • 2. Научное общество состоит из 25 человек. Надо выбрать президента общества, вице-президента, ученого секретаря, казначея. Сколькими способами может быть сделан этот выбор, если каждый член общества может занимать лишь один пост? (решение)

  • 3. Расписание одного дня содержит пять уроков. Определить количество таких расписаний при выборе из одиннадцати дисциплин? (решение)



Перестановки

  • При составлении размещений без повторений из n элементов по к мы получили расстановки, отличающиеся друг от друга и составом, и порядком элементов. Но если брать расстановки, в которые входят все n элементов, то они могут отличаться друг то друга лишь порядком входящих в них элементов. Такие расстановки называют перестановками из n элементов, или, короче, n-перестановками. Обозначается Р (Р-первая буква французского слова Permutation- «перестановка»).

  • = =n(n-1)…2*1=n!

  • =



Задачи

  • 1.Семь девушек стоят в круге. Сколькими различными способами они могут встать в круг? (решение)

  • 2. Семь девушек водят хоровод. Сколькими различными способами они могут встать в круг? (решение)

  • 3. Сосчитать сколько ожерелий можно составить из 7 различных бусинок? (решение)



Перестановки с повторениями

  • До сих пор мы переставляли предметы, которые были попарно различны. Если же некоторые переставляемые предметы одинаковы, то получается меньше перестановок- некоторые перестановки совпадут друг с другом.

  • Например переставляя буквы в слове «март», мы получим Р =4!=4*3*2*1=24 перестановки. А если взять слово «мама» стр 38



  • Задачи

  • 1.Сколько перестановок можно сделать из букв слова «Миссисипи»? решение

  • 2. Сколько перестановок можно сделать из букв слова «задача»? решение

  • 3. Сколько перестановок можно сделать из букв слова «математика»? решение



Сочетания

  • Всякая неупорядоченная выборка объема к из множества, состоящего из n различных объектов, полученная в схеме выбора без возвращений, называется сочетанием из n элементов по к.

  • Таким образом, сочетания различаются составом входящих в них объектов, но непорядком этих объектов. Из определения выбора без возвращений следует, что к удовлетворяет неравенствам 0 к n.

  • Обозначают С (читается: «це из n по к»; С-первая буква французского слова Combinasion- «сочетания»). Вычисляют по формуле



Задачи

  • В полуфинале по шахматам участвуют 20 человек, а в финал выходят только трое. Сосчитать число различных исходов полуфинала. (решение)

  • Сколькими способами можно поставить на шахматную доску 8 ладей? (решение)

  • Сколькими способами можно поставить на шахматную доску 8 ладей так, чтобы они не могли бить друг друга? (решение)

  • В кондитерском магазине продавались 4 сорта пирожных: наполеоны, эклеры, песочные и слоеные. Сколькими способами можно купить 7 пирожных? (решение)



Решение





  • Р =8!=40320





Решение

  • Р(4,3,1,1)=9!:(4!*3!*1!*1!)=2520



Решение

  • Р(3,1,1,1)=6!:(3!*1!*1!*1!)=120



Решение

  • Р(3,2,2,1,1,1)=10!(3!*2!*2!)=151200





Решение

  • А =17*16*15=4080



Решение

  • А =25*24*23*22=303600



Решение

  • А =11*10*9*8*7=55440



Решение задач

  • Р =7!=7*6*5*4*3*2*1=5040



Решение



Решение

  • 720:2=360 (ожерелье можно не только повернуть по кругу, но и перевернуть). Рисунок?