Размещения, с  повторениями

Размещением из n элементов по k с повторениями -  кортежи, содержащая m элементов, взятых из данного множества, отличающихся либо элементами, либо их порядком следования, причем элементы в комбинациях могут повторяться от 1 до m раз.

Дано множество X={a,b,c,d}. составить все размещения  из этого четыре элементного множества по два с повторениями. Эта записывается в виде:  Ā _n^k.

Запишем  некоторые  кортежи длины 2. (a; a ), (a; b). (a; c),  (a; d), (b; b) …Всего таковых  кортежей    =  4·4=16. С другой стороны это есть численность декартового произведения  =т(АхА)= 4·4=16

Запишем  некоторые  кортежи длины 3. (a; a; a), (a; a; b) …. Всего таковых  кортежей    =  4·4·4=64

Общая задача. Найти число кортежей дины k, которые можно составить из элементов множества, содержащего n элементов.

 - число размещений с повторения из n элементов по k

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

Необходимо составить шеренгу из 20 физкультурников, среди которых 10 имеют белые майки, 4- синие, 6 – красные. Сколькими способами это можно сделать?  Если бы цвета не повторялись, то это можно сделать P(20)=20!. В виду того, что цвета будут повторяться,  то перестановок с повторениями будет меньше в 10!·41·61· раз.

Общая задача. Имеются  элементы  k видов. Причем k₁ вида   n₁ штук, k₂  вида   n₂ штук и т.д. Сколько перестановок можно сделать из этих элементов?

,  где  n = n₁+n₂+…=n  - сумма всех элементов.

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

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

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

Ситуации такого характера приводят к  сочетаниям с повторениями, Обозначается.

Общая задача. Требуется составить k наборов (кортежей) из элементов данных n  множеств d₁. d₂, d₃,…d_n. Число элементов в каждом из множеств d_i  не меньше числа k.

Формула вычисления числа сочетаний с повторениями имеет несколько разновидностей:

=. = . =P(n-1;k).  . Наиболее предпочтительнее первая формула, сведенная к вычислению сочетаний без повторения.

4. Примеры комбинаторных задач из различных областей знаний. Комбинаторика в древней Греции. Комбинаторика в биологии, генетике, химии и др.

В древне Греции философы, служители религии, астрологи, гадалки много внимания уделяли науке нумерологии – науке о числах. Они устанавливали различные закономерности числе, изучали  влияние чисел и их комбинаций на человека, природу, мироздание.

Модель  строения ДНК была расшифрована  методами комбинаторики в 1953 году в Кембридже Ф.Криком и Дж. Уотсоном. Ими была изготовлена спиральная модель ДНК после рассмотрения различных комбинаций связи нуклеотидов, аминокислот  и других  объектов между собой. При этом был открыт генетический код, который содержит информацию о виде растения или животного, в том числе   наследственную и иную информацию.

Без комбинаторных задач не было бы информатики, компьютера, сотового  телефона. Например, установления кодов в ЭВМ для записи информации, такими, что бы они ни были избыточными и были достаточными для записи любой информации. Соединение элементов в ЭВМ, установление связей в кристалле, и микросхеме  рассчитывается с помощью комбинаторных задач.

С точки зрения теории множеств, комбинаторика изучает подмножества конечных множеств, и операции над ними.

Приведем несколько  общих таковых задач:

1.Найти конфигурацию элементов, обладающих заранее заданными свойствами.  

2. Доказать существование или отсутствие конфигурации с заданным свойством.

3. Найти число конфигураций с заданным свойством

4. Описать все способы решения указанных выше задач.

5. Из всех возможных способов решения такой задачи  выбрать наиболее оптимальную.

К перечисленным задачам подходят такие ситуации как:

1.Соеденить некоторое число точек на плоскости  не пересекающими  (пересекающими в одной, двух и более точках)  линиями.

2. Транспортные задачи, связанные перевозками.

3. Задачи массового обслуживания

4.Определить число выпускаемых лотерейных биолитов, что бы были заинтересованы покупатели и авторы лотереи..

Практические  замятия. Решение комбинаторных задач

Требования к знаниям умениям и навыкам  Студент должен знать:  основные комбинаторные объекты (типы выборок); формулы и правила количества выборок (для каждого из типов  выборок) уметь: определять тип комбинаторного объекта (тип выборки); рассчитывать  количество выборок заданного типа в заданных условиях.