Теория графов и комбинаторика

. я г а . Чноло отоОрашшх алемантов -заываегоя объемом выс!ор<и. j-iidofAKa объема Ч- наэываетоя Ч' -выборкой. Выборки (Зынают о iiooropoH.iffi.r,! и без повтораняй. В выборках о повторениями нэко- TopHQ эле- могут повторяться, в BH6opitax без повторений воо элементы разные. Например, пусть отобраны элементы Епл;;V j ^ К , оовокупностъ отобранных элементов Оо^;аэ,уот выборку без новтораштй, в противном о^г'чае - выборку ' о гюаторвН1Ш.м, Крагноотьи K j элемента ITi. € V в данной ьы- 6ojsf.0 р. называется чиоло вхождений в И . Если выборка без яоэторениЯ, то С Кг, й О , еолп же выс^орка R. с повторениями, т Выборки бывают упорадо- чешшг,' п цаугюрядочвиные. Упорядочеиной называется выборка, в которой существен порядок оладования элементов- Упорядоченные BuflojjKi! будем обозначать круглыми скобка:,,.;:(1=№(, •••> 2 ^ ^ ) , а неупорядоченные - фи1урны(.ш: Я=[гГ(| . Неупорядо­ ченные выборки полностью определяитая ооставом элементов. Упо­ рядоченные выборкя очитаютоя равщми, осли они имеют одинако­ вый состав и одинаковый порядок оладования элементов. Очевид­ но, пеулорядоченш, "2-выборки без повторений являются 'ii - Д0да,1Н0!ке0тваш1 множеотва V . При подсчете числа выборок или чиола способов.поотроегая сложного объекта используются два основ rjx правила комбинато­ рики - правила сумш и проязведотт. Правило с...'ммц. Если объект/1 можно выбрать Я опоообаш, 0 объект В д р у г иш \Yi сцоообами, то объект можно выб­ рать И+М опоообаш. Это правило применяето." тогда, когда одновременный выбор обоих объектов невоамо-жен. Оно легко раопроотраляется на олу- чей любого 1"^начного числа объектов. В терш1нах теории множэотв правнло оумлы формулируется так: если V - конечное множество и V i ^ i - - его под­ множества такие, что V •= ^ \/С О В общем случае, когда 3 , справедливо' неравенство (\/( 7 " (У,' ]. Пэдвило птзоизвеления. Еол1? объект/! можно выбрать W спооо- бнми и для каглдагс такого выбора объект 5 можно гыбратъ УУ) опоссбами, Tv., объект Д ^ В в указанном порядка можно выбрать опособами. Применяя тв-риинологиа теории множеотв, .оформулируем прави­ ло произведения для любого тасла объектов oлa^o'ЮIщ^м образом: 78