7.Комбинаторика. Размещение с повторением и без повторения.

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

а)Размещ-е с повторением Опр-е: Картежи длины k составлены из m эл-го мн-ва x, назыв размещениямис повторениями из m эл-ов по k. Обознач . А-«arrangement»- размещение. =m^k

б)Размещ-е без повторений Опр-е: Упорядочен мн-ва длины k составл из эл-ов m эл-го мн-ва x назыв размещениями без повторений из m эл-ов мн-ва x по k.

Опр-е: k элем-ые подмнож-ва m эл-го подмнож-ва x назыв сочет-ми без повторений из эл-ов этого мн-ва по k. Обознач его С^k_m

8.Комбинаторика. Перестановка с повтор-ем и без повтор-я.

а) Переест без повтор: Если длина размещения без повторений равна числу m элем-ов мн-ва x (в размещении учавств все эл-ты), то в таком размещении встречаются по одному разу все эл-ты x. 2 таких размещения отличаются др от др только лишь порядком эл-ов.

Опр-е: Перестановкой без повторений из m эл-ов обознач P_m(permutation- перестановка) назыв размещение без повторений из этих эл-ов по m P_m=m!

Вывод ф-лы:Р_m=m· (m-1) · (m-2)…3·2·1=m!

б)Переест с повтор: Найти число картежей котор м\о получить переставляя компоненты данного картежа. Чтобы уточнить постановку задачи введем понятие состав кортежа. Пусть а-кортеж длины n состав из эл-ов m-эл-го мн-ва x={x_1,x_2,…,x_m}. Кажд числу k(1≤k≤m) соотв число n_k показывающ ск-ко раз эл-т x_k встречается среди компонент картежей а. Выписывая по порядку эти числа получ новые картеж (n_1,n₂,n_3,….n_m) котор наз-ся составом картежа x={x₁,x₂,x₃,x₄} a={x₁, x_3, x₁, x₄ ,x_3, x₁} 2 картежа им один и тотже состав, могут отличаться др от др лишь порядком компонент, их назыв перестаноками с повторениями данного состава. P(n₁,n₂,n₃,…,n_m)=

9. Комбинаторика. Сочетание с повторением и сочетание без повторения

Сочетания без повторений

k – элементные подмножества m – элементного множества Х называют сочетаниями без повторения из элементов этого множества по k.

Вывод ф-лы:

В тех сл-ях когда нас не интересует порядок эл-в в расстановке, и интересует лишь ее состав, то говорят о сочетаниях.

Соч-ми из m различных эл-в по k, называют всевозможные расстановки длины k, обр-е из этих эл-в и отличающихся др. от др. составом, но не порядком эл-в.

Составим все сочетания из m по k, затем переставим в каждом сочетании эл-ты всеми возм-ми способами, теперь мы получим расстановки отличающиеся либо сост., либо порядком, т.е. это все размащения без повтор. из m по k ( ).

учитывая, что каждое сочетание дает k! размещений, то по правилу пр-я получим, что

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

Найдем число различных составов, которые могут иметь кортежи длины n, состоящие из элементов множества Х, содержащего m элементов. Каждый такой состав является картежом состоящим из m чисел ( ) таких, что . Его можно записать в виде кортежа из 0 и 1, заменив каждое число соответствующим числом 1 и подставив 0 после каждой группы единиц кроме последней.

exe: вместо картежа (4,2,1) можно записать: 1,1,1,1,0,1,1,0,1 или (2,0,0,3) – 1,1,0,0,0,1,1,1.

Число единиц входящие в последний кортеж = , а число 0 равно m-1, поэтому число различных кортежей такого вида равно числу перестановок с повторениями из n единиц и m-1 нулей P(n,m-1).

Опр.: Различное число картежей длины n, компоненты которых принадлежат данному m-элементному множеству Х называют также сочетаниями с повторениями из m по n.