Типы комбинаторных задач

Содержание.

 

Введение………………………………………………………………………2

Типы комбинаторных задач…………………………………………………3

Разные статистики…………………………………………………………..4-6

Выбор без возвращения  с учетом порядка…………………………………...7

Выбор без возвращения  и без учета порядка……………………………….8

Выбор с возвращением и с учетом порядка………………………………9

Выбор с возвращения без учета порядка…………………………………..10

Примеры…………………………………………………………………11-12

     Таблица решения  комбинаторных задач……………………………………13

    Дополнение………...………………………………………………………14-18

Заключение………………………………………………………………….19

Список литературы…………………………………………………………20

 

                                                  Введение.

Комбинаторика - раздел математики, посвященный решению задач выбора и расположения элементов некоторого, обычно конечного, множества в соответствии с заданными правилами. Каждое такое  правило определяет способ построения некоторой конструкции из элементов  исходного множества, называемой комбинаторной  конфигурацией. Поэтому можно сказать, что целью комбинаторики  является изучение комбинаторных конфигураций, в частности, вопросы их существования, алгоритмы построения, решение задач  на перечисление.

Примерами комбинаторных  конфигураций являются перестановки, размещения и сочетания блок-схемы  и латинские квадраты.

Комбинаторика¹ - один из разделов дискретной математики, который приобрела важное значение в связи с использованием его в теории вероятностей, математической логике, теории чисел, вычислительной технике, кибернетике.

Целый ряд комбинаторных  задач возникает при разбиении  множеств на части: найти, сколькими  способами можно разложить n предметов по k ящикам; найти, сколькими способами можно число n записать в виде суммы k слагаемых, и т.д.

 

 

 

 

                                     Типы комбинаторных задач.

1. Магический квадрат - квадратная таблица (n * n) целых чисел от 1 до nќ такая, что суммы чисел вдоль любого столбца, любой строки и двух диагоналей таблицы равны одному и тому же числу s= n(nќ+1)/2. Число n называют порядком магического квадрата. Доказано, что магический квадрат можно построить для любого n , начиная с n = 3. Уже в средние века был известен алгоритм построения магических квадратов нечетного порядка. Существуют магические квадраты, удовлетворяющие ряду дополнительных условий, например магический квадрат с n=8 , который можно разделить на четыре меньших магических квадрата 4x4. В Индии и некоторых других странах магические квадраты употреблялись как талисманы. Однако общей теории магических квадратов не существует. Неизвестно даже общее число магических квадратов порядка n.

2. Латинский квадрат - квадратная матрица порядка n, каждая строка и каждый столбец которой являются перестановками элементов конечного множества S, состоящего из n элементов.

3. Задача размещения - одна из классических комбинаторных задач, в которой требуется определить число способов размещения m различных предметов в n различных ячейках с заданным числом r пустых ячеек.

4. Задача коммивояжера, задача о бродячем торговце - комбинаторная задача теории графов. В простейшем случае формулируется следующим образом: даны n городов и известно расстояние между каждыми двумя городами; коммивояжер, выходящий из какого-нибудь города, должен посетить n-1 других городов и вернуться в исходный. В каком порядке должен он посещать города (по одному разу каждый) чтобы общее пройденное расстояние было минимальным? Методы решения задачи коммивояжера, по существу, сводятся к организации полного перебора.

                                                

                                               Раскладки. 

 Мы знаем, что  n   различных   частиц   можно   распределить   no  m   ячейкам   тⁿ  способами. Если все эти тⁿ способов при заданной энергии имеют равную вероятность, то говорят о статистике Максвелла — Больцмана.

Изучение квантовых явлений  показало, что к участвующим в  них частицам (фотонам, электронам и  т. д.) не применима статистика Максвелла  — Больцмана, При этом все частицы  распадаются на два класса. К одному из них принадлежат частицы, неразличимые друг от друга. Поэтому для таких  частиц имеет значение лишь то, сколько  частиц попало в ту или иную ячейку, а не то, какие именно частицы  в ней находятся.

 Статистику неразличимых  частиц, в которой все эти способы считаются равновероятными, разработали Эйнштейн и индийский ученый Бозе. Поэтому ее называют статистикой Бозе — Эйнштейна.  Ей подчиняются фотоны, атомные ядро и атомы, содержащие четное число элементарных  частиц.

Еще необыкновеннее статистика, которой подчиняются такие частицы, как электроны, протоны и нейтроны. Для этих частиц действует так называемый запрет Паули, по которому две частицы не могут одновременно попасть в одну и ту же ячейку. Поэтому в соответствующей статистике, разработанной английским физиком Дираком и итальянским ученым Ферми, статистике Ферми-Дирака, в каждой ячейке находится не более одной частицы, причем различные распределения, удовлетворяющие указанному условию, считаются равновероятными.

                                                           Размещение.

Есть урна, (то есть ящик), содержащая n занумерованных объектов, которые мы без ограничения общности будем считать шариками. Мы выбираем из этой урны k шариков. Нас интересует, сколькими способами можно выбрать k шариков из n, или сколько различных результатов (то есть наборов, состоящих из k шариков) получится.

На этот вопрос нельзя дать однозначный ответ, пока мы не определимся  с различными результатами выбора.

Рассмотрим следующие  возможные схемы выбора:

1. Выбор с возвращением: каждый выбранный шарик возвращается  в урну, то есть каждый из  k шариков выбирается из полной урны. В полученном наборе, состоящем из k номеров шариков, могут встречаться одни и те же номера (выборка с повторениями).

2. Выбор без возвращения:  выбранные шарики в урну не  возвращаются, и в полученном  наборе не могут встречаться  одни и те же номера (выборка  без повторений).

И в том, и в другом случае результатом выбора является набор  из k номеров шариков. Удобно считать, что шарики всегда выбираются последовательно, по одному (с возвращением или без).

Условимся, какие результаты мы будем считать различными.

 

Есть ровно две возможности.

1. Выбор с учетом порядка:  два набора номеров шариков  считаются различными, если они  отличаются составом или порядком  номеров. Так, при выборе трех  шариков из урны, содержащей 5 шариков,  наборы (1,2,5), (2,5,1) (4,4,5) различны, если  производится выбор с учетом  порядка.

2. Выбор без учета порядка:  два набора номеров шариков  считаются различными, если они  отличаются составом. Наборы, отличающиеся  лишь порядком следования номеров,  считаются одинаковыми. Так, в  примере выше первые два набора (1,2,5), (2,5,1) есть один и тот же  результат выбора, а набор (4,4,5) — другой результат выбора.

 

Подсчитаем теперь, сколько  же возможно различных результатов  при каждой из четырех схем (выбор  с возвращением и без, и в каждом из этих случаев учитываем ли мы порядок или нет).

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Выбор без возвращения, с учётом порядка.

Общее количество различных  наборов при выборе k элементов из n без возвращения и с учётом порядка равняется

Общее количество выборок  в схеме выбора k элементов из n без возвращения и с учетом порядка определяется формулой и называется числом размещений из n элементов по k элементов.

Первый шарик можно  выбрать n способами. При каждом из этих способов второй шарик можно выбрать n-1 способом, и т.д. Последний k-й шарик можно выбрать (n-k+1) способом. Общее число способов выбора равно

 

 Число возможных перестановок  множества из n элементов есть n!

 

 

 

 

 

 

 

 

Выбор без возвращения  и без учёта порядка

Общее количество различных  наборов при выборе k  элементов из n без возвращения и без учёта порядка равняется

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

То есть число выборок, различающихся еще и порядком, в k! раз больше, чем число выборок, различающихся только составом.

 

 

 

 

 

 

 

 

 

 

 

Выбор с возвращением и с учетом порядка.

 

Общее количество выборок в схеме выбора k элементов из n с возвращением и с учетом порядка определяется формулой

Первый шарик можно  выбрать n способами. При каждом из этих способов второй шарик можно выбрать также n способами, и так k раз.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Выбор с возвращением и без учёта порядка

Общее количество различных  наборов при выборе k элементов из n с возвращением и без учёта порядка равняется

и называется числом сочетаний  из n  элементов по k элементов.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Задача 1. Сколькими способами можно выбрать три из пяти букв слова «пенал»?

Решение: n=5(общее количество букв), выбираем три, значит к=3.

Подставляем в формулу:     =5!/3!(5!–3!)=5!/3!2!=10.

Задача 2. Сколькими способами можно выбрать двух из четырёх гостей?

Решение: n=4, выбираем двух, значит к=2. Подставляем в формулу:

                                                              

 

Задача 3.Сколько трёхзначных чисел можно составить из цифр 1, 2, 3, 4, 5, 6, 7, если цифры в числах не повторяются?

Решение: Из множества, содержащего 7 различных элементов, выбираются 3 элемента. Порядок существенен (31 и 13 – разные числа), элементы не могут повторяться. Следовательно, необходимо найти число размещений без повторений из семи элементов по три элемента в каждом, т. е.

                                               =5*6*7=210.

 

Задача 4. 10 спортсменов разыгрывают одну золотую, одну серебряную и одну бронзовую медали. Сколькими способами эти медали могут быть распределены между спортсменами?

Решение. Предположим, что спортсмены пронумерованы числами от 1 до 10 и  – номера спортсменов, получивших золотую, серебряную и бронзовую медали. (х1,х2,х3)

 Каждому такому распределению  медалей соответствует строка  (х1,х2,х3) , состоящая из различных чисел (номеров спортсменов).

Обратно каждой строке (х1,х2,х3) соответствует способ распределения медалей.

 Следовательно, число  способов распределения медалей  равно числу размещений без  повторений из 10 элементов по 3, т.е.

Задача 5. В почтовом отделении продаются открытки десяти видов. Сколькими способами можно купить здесь набор из восьми открыток, если открыток каждого вида имеется не менее восьми штук?

Решение: Рассматриваемое множество состоит из 10 различных элементов (виды открыток), а подмножество – из 8 (открытки каждого вида). Следовательно, наборов можно составить 

                      = (10+8–1)!/8!(10–1)!=17!/8!9!=24310 способов способов купить набор из восьми открыток.

 

Задача 6. Сколько можно построить различных прямоугольных параллелепипедов, если длина каждого его ребра может выражаться любым целым числом от1 до10?

Решение: Рассматриваемое множество состоит из 10 различных элементов (длина ребра), а подмножество – из 3х (высота, ширина, длина – т. е. по три разных ребра). Следовательно, различных прямоугольных параллелепипедов можно построить    =(10+3–1)!/3!(10–1)!= 12!/3!9!=220

 

Задача 7. Сколькими способами можно разложить в два кармана 9 монет разного достоинства?

Решение: Рассматриваемое множество состоит из 2 элементов (2 кармана), а выборка –из 9 (количество монет). Здесь необходимо составить размещения с повторениями.

 

                                              = =512.

 

 

 

Задача 8. Сколькими способами можно распределить 12 различных учебников между четырьмя студентами?

Решение: Рассматриваемое множество состоит из 4 элементов (4 студента), а выборка – из 12 (количество учебников). Здесь необходимо составить размещения с повторениями.

                                                  = =16777216. 
Таблица решения комбинаторных задач.

Анализируя условие задачи, определяют, какой из двух моделей  оно соответствует (какое «действие» осуществляется с предметами: выбирают их, или размещают).

В случае если необходимо найти  количество комбинаций размещений,  находят в таблице «Число исходов  размещения m шаров по n коробкам» (это верхняя часть таблицы). Затем определяют тип предметов (шаров), различимы они или неразличимы и тип размещений (с повторением или без повторения). На пересечении выбранных столбца и строки  находят способ определения количества комбинаций.