Элементами. Из определения следует, что элементы множества обладают двумя свойствами 1 вполне различимы 2

• Название: Элементами. Из определения следует, что элементы множества обладают двумя свойствами 1 вполне различимы 2
• Дата: 16.01.2018
• Размер: 0.67 Mb.
• Имя файла: shpora_dmiml.docx
• Тип: Документы; #34346
• страница: 3 из 9

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

Пусть n ϵ N₀, B = {b₁,b₂,…,b_n}. Перестановкой из элементов множества B называется всякое размещение этого множества по n элементов.

Очевидно, что количество всевозможных перестановок множества B не зависит от природы элементов множества В. Поэтому количество перестановок произвольного n-элементного множества обозначим через P_n.

Теорема 1: P_n = n!

Доказательство: Согласно определению перестановки P_n=A_nⁿ =n*(n-1)*…*1=n!.

Сочетание.

Пусть n, kϵN₀, knиB = {b₁,b₂,…,b_n} -- n-элементное множество. Всякое k-элементное подмножество В называется сочетанием из n элементов этого множества по k элементов.

Совершенно очевидно, что количество всевозможных сочетаний по k элементов множества В не зависит от природы элементов множества В. В силу этого, количество всевозможных сочетаний произвольного n-элементного множества по kэлементов обозначим через С_n^k.

Сnk =

n! k!(n - k)!

Теорема 1: Число всех k-элементных подмножеств множества из n элементов

Свойства сочетаний:

1. С_n⁰ = 1.

2. С_n^k = С_n^n - k.

3. С_n^k = С_{n - 1}^{k - 1} + С_{n - 1}^k

4. С_n⁰ + С_n¹ + С_n² + ... + С_n^{n - 1} + С_nⁿ = 2ⁿ.

Бином Ньютона.

Бином Ньютона - это отношение, позволяющее представить выражение (a + b)ⁿ (n ∈ Z⁺) в виде многочлена.

Теорема 1: Имеет место равенство

(a + b)ⁿ = aⁿ + С_n¹a^{n - 1}b + С_n²a^{n - 2}b² + ... + С_n^ka^n - kb^k + ... + С_n^{n - 1}ab^{n - 1} + bⁿ. (1)

Формулу (1) можно записать в виде (a + b)ⁿ = ⁿ_k=0C_n^ka^n-kb^k.

Числа С_n¹, С_n², ... , С_n^{n - 1} называются биномиальными коэффициентами.

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

1

1

1  1

2

1  2  1

3

1  3  3  1

4

1  4   6   4  1

5

1  5  10  10  5  1

6

1  6  15  20  15  6  1

7

1  7  21  35  35  21  7  1

8

1  8  28  56  70  56  28  8  1

Слева указана степень n, справа значения соответствующих биномиальных коэффициентов.
№24 r- выборки из n - множества.

Определение1. Набор элементов , ,…, из множества называется выборкой объема r из n элементов (или, иначе, -выборкой).

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

Замечание. Две упорядоченные выборки, различающиеся лишь порядком следования элементов, считаются различными.

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

В выборках могут допускаться или не допускаться повторения элементов.

Определение2.Упорядоченная-выборка, в которой элементы могут повторяться, называется -размещением с повторениями.

Определение3.Упорядоченная-выборка, элементы которой попарно различны, называется -размещением без повторений (или, иначе, -размещением).

Замечание.-размещения без повторений называются перестановками множества X.

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

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

Замечание. Любое -сочетание можно рассматривать, как r-элементное подмножество n-элементного множества.

Число -размещений с повторениями будем обозначать , а без повторений – через . Число перестановок n-элементного множества будем обозначать через (т.е. ). Число -сочетаний с повторениями будем обозначать через , а без повторений – через .

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

Пусть задано конечное множество U={a₁,a₂,…,a_n}. Рассмотрим набор из элементов a_i1,a_i2,…,a_ik где aiU, i, k≤n этот набор называется выборкой объемов к из n элементов.

Выборка называется упорядоченной, если в ней задан порядок следование элементов, если порядка следования не существует, то выборка называется неупорядоченной. Упорядоченные выборки n из n называется перестановкой. Число таких перестановок P_n=n! Упорядочен выборки объем m из n элементов(m, число таких размещений .

Перестановка с повторениями : пусть имеется n элементов среди которых , к₁ элементов 1 типа , к₂ элементов 2 типа … к_r элемент r типа. Причем к₁+к₂+…+ к_r=n упорядочен выборки из таких m элементов по n называется перестановкой с повторением и обозначается

(k1,k2,…,kr) =, их называют полиниальными коэффициентами.
26. Полиномиальная теорема. Принцип Дирихле.

Принцип Дирихле : Если в m ящиках расположены n кроликов, при этом (n>m) то хотя бы в 1 из ящиков будет находиться больше чем 1 кролик . (Например :9 ящиков , 10 кроликов.) Если n кроликов рассажены в m ящиках, то хотя бы в 1 ящике находится не менее кроликов, а также хотя бы в 1 ящике не более кроликов.

Полиномиальная теорема: Выражение равно сумме всех возможных слагаемых вида , где r1+r2+…+=n, то

есть =.

Доказательство: Перемножим последовательность

n раз. Тогда получаем

слагаемых вида d1…dn, где каждый множитель di равен или а1, или а2 ,…, или .Обозначим

через В(r1,…,) совокупность всех слагаемых ,

где а1 встречается множителем r1 раз ,а2-r2 раз ,

…, - раз .Число таких слагаемых равно

Cn( r1,…,). Но Cn( r1,…,)= .

Следовательно =.


27.Рекуррентные соотношения и производящие функции.

Рекуррентные соотношения :это соответствия позволяющие свести решение комбинаторной задачи для некоторого числа объектов к аналогичной задаче с меньшей размерностью.

Пусть f(n) некоторое рекуррентное соотношение и для него известно =F()(1). Где F(y₁,…,y_k) известная функция от k переменных тогда (1) называется рекуррентным соотношением к –ого порядка. Последовательность чисел называется решением соотношения (1), если при подстановке в (1) получается верное равенство.

Если в (1) первые к соотношений f1,f2,…fk заданы произвольно то соотношение (1) имеет бесконечное число соотношений.

Опр: Пусть f(n) общее решение соотношения (1) если оно зависит от к произвольных постоянных то записывают =(С₁,С₂…С_n,n). Если для любого X_n существует С₁’,С₂’…С_к’ что является решением то записывают X_n=(С₁’,С₂’…С_к’,n).

Опр: Линейное однородное рекуррентное соотношение 2-го порядка с постоянными коэффициентами называется рекуррентным соотношением вида =,n=1,2…(2)

Уравнение =а₁+а₂ (3) называется характеристическим уравнением соотношения (2).

Теор: Если характеристическое уравнение (3) имеет 2 различных корня 2 то общее решение рекуррентного соотношения (2) имеет вид, =С+С2. Если уравнение (3) имеет кратные корни то общее решение имеет вид =(С1+С2).

Опр: Линейное рекуррентное соотношение к-го порядка называется соотношение вида =а1+а2+…+ + (4).

Характеристическим для (4) будет уравнение вида =а1+а2+…++.(5)

Теор: 1)Пусть ,…, Попарно различные корни характеристического уравнения (5) Тогда общее уравнение (4) записывается в виде =С+С₂…+ С_n

Пусть ,…, попарно различны корни характеристического уравнения (5) имеющие кратность mi причем m₁+m₂+…+m_p=k, i=1,p. Тогда общее решение уравнения (4) имеет вид

=(С11+С12n+…+)+…+(Cp1+Cp2+…). Для решения рекуррентных соотношений используют так же метод производящих функций.

Пусть задано линейное рекуррентное соотношение а₀=0, а₁=1, а_n=5, n>=2.

Производящую функцию G(z)будем искать в виде ряда =a0+a1z+a2+… с этой целью отношение G умножают соответственно на …. 0+1+…+(5)+…+a0+a1z+=z+5-6 G(z)=z+5zG(z)-6G(z). Откуда производящая функция G(z)=. Оно задает производящую функцию последовательности (5) в замкнутом виде =+. An=-,n=0,1,2… решение рекурсивного выражения 5.
28. Принцип включения и исключения:

Теорема. Если А₁, A₂, ..., A_n – некоторые конечные множества, то:

m(A₁A₂…)=[m(A₁)+…+m(A_n)]-[m(A₁)+m(A₁A₃)+…+m(A_n-1)]+[m(A₁)+…+m(A_n-2)]-…+([m(A₁)].

Поясним формулировку этой теоремы. Правая часть формулы в теореме представляет собой алгебраическую сумму n слагаемых (взятых в квадратные скобки), имеющих попеременно знак «+» и «–».Первое слагаемое – число элементов, входящих хотя бы в одно из множеств А₁, A₂, ..., A_n, второе – число элементов, входящих хотя бы в одно из множеств (i < j, i = 1, …, n, j = 1, …, n), третье – число элементов, входящих хотя бы в одно из множеств (i < j < k, i = 1, …, n, j = 1, …, n, k = 1, …, n) и так далее. . Последнее слагаемое, взятое со знаком , – число элементов в множестве A₁ . Такое попеременное включение и исключение слагаемых с целью учета каждого элемента только один раз и послужило причиной для названия этой формулы: формула включений и исключений.

Эту формулу можно доказать, используя метод математической индукции. Мы ограничимся ее доказательством только для случая n = 3, то есть покажем, что m(AUBUC)= m(A)+m(B)+m(C)-m(B)-m(A)-m(A)+m(A)

Доказательство. Чтобы не писать индексы, рассмотрим множества А, В, С. Используя очевидное равенство AU B UC = AU(B UC) и то, что эта формула доказана для двух множеств, получим:

m(AU B UC) = m(AU[B UC]) = m(A) + m(B UC) − m(A [B UC]) ,