5. Правило суммы
 Скачать 15.61 Kb.
|
|
5. 5.1. Правило суммы: если А можно отобрать m способами, а B n, то отбор “А или В” можно сделать m+n способами. Причем отбор одного исключает отбор другого.Правило произведения: если А можно отобрать m способами, а после этого B n, то тогда “А и В” в указанном порядке можно выбрать m*n способами.Принцип Дирихле: Пусть А конечное, |A|=n*k+1 и имеет место разбиение: A= A1 v A2 v….An. Тогда хотяб в одном Аi где i ∈ (1…n) содержится не менее k+1 элементов. Про кроликов.5.2 Сочетанием из n элементов множества A={a1,...,an} по k называется любое k -элементное подмножество множества A. Число различных сочетаний из n по k обозначается как Размещением из n элементов множества A={a1,...,an} по k называется любой упорядоченный набор всех n элементов множества A. Число различных размещений из n по k обозначается как An^k. Перестановка - частный случай размещения - любой упорядоченный набор k различных элементов множества A, взятых по одному разу. Число различных перестановок из n по k обозначается как P(A) 5.3Бином Ньютона — формула для разложения на отдельные слагаемые целой неотрицательной степени суммы двух переменных, имеющая вид:где C называют биномиальным коэффицентом. Числом всех подмножеств множества A является число 2^n, гдe n — мощность множества A.5.4 Перестановку называют чётной, если она содержит чётное число инверсий, иначе её называют нечётной.Транспозицией называют преобразование перестановки, заключающееся в перемене мест двух любых её элементов. 4.1. Пусть A, B - произвольные множества. Отображением множества A в множество B называют всякое правило f, согласно которому каждому элементу из множества A сопоставляется единственный(вполне определённый) элемент из множества B. Отображение f из A в B обозначается как f:A→B .В таком случае, если a∈A, b∈B, то a является прообразом b, а b - образом a По определению, у каждого образа есть хотя-бы один прообраз. Однако, для элемента b∈B прообразов из множества A может как быть много, так и не быть вовсе.Полным прообразом для элемента b∈B является множество всех его прообразов из множества A.4.2Отображение f:A→B называют сюръективным в том случае, когда у каждого b∈B есть хотя бы один прообраз a∈A. все y имеют x, но не обратноf(A)=B (Отображение от множества A возвращает множество B)Отображение f:A→B называют инъективным в том случае, когда оно разные элементы из множества A отображает в разные элементы множества B; все x имеют y, но не обратноОтображение f:A→B называют биективным, когда оно одновременно сюръективно и инъективно. У каждого x есть y, кол-во x = yДля любого множества A существует биективное тождественное отображение εA , которое отображает каждый элемент множества A в него же. εA:A→A, ∀a∈A4.3Существует произведение отображений обозначаемое как f2f1=f1(f2(a))///f1∘f2=f2f1=f2(f1(a)) 4.4Отображение f:A→B называется обратимым, когда существует такое отображение f′:B→A, что ff′=εA и f′f=εB, тогда f′ называется обратным для fКритерием обратимости отображения является его биективность.4.5. Если существует биективное отображение из множества A в множество {1…n} , n∈N, то A является конечным множеством с мощностью n. Соответственно, множества, у которых одинаковая мощность называются равномощными, а множества, у которых нет мощности — бесконечными.Счётное множество — бесконечное множество, элементы которого возможно пронумеровать натуральными числами, все другие являются несчётными. |