metod_15.03.04_atppp_moas_2016 (1016590), страница 7

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 7)

Так как сочетания являются подмножествами, то их можнозадавать с помощью характеристических векторов, как описано в доказательстветеоремы 2. Характеристический вектор, соответствующий(n,k)–сочетанию,имеет n компонент, среди которых ровно k единиц. Этот вектор можно рассматривать также как слово в алфавите E.

Таким образом, имеется взаимно однозначное соответствие между (n,k)–сочетаниями и словами длины n в алфа n kвите E. Отсюда следует, что число таких слов равно   .Сочетания с повторениями n  k  1.k Теорема 6. Число (n,k)–сочетаний с повторениями равно Д о к а з а т е л ь с т в о . Для того, чтобы задать сочетание с повторениямииз n по k, достаточно указать для каждого числа от 1 до n, сколько раз оновстречается в данном сочетании. Пусть k i – количество вхождений числа i всочетание, i = 1,2,...,n.

Так как общее число элементов в сочетании равно k, тоk1  k 2  k n  k . Поставим в соответствие данному сочетанию слово в алфавитеE следующим образом. В начале слова поставим k1 нулей, после них единицу,за ней k 2 нулей, после них вторую единицу, и т.д.

Все слово будет состоять изn групп нулей, разделенных единицами, причем в i–той группе (считая слева)число нулей равно k i . Заметим, что после последней группы единица не ставится, т.е. слово оканчивается k n нулями. Всего, таким образом, будет k нулейи n  1 единица, а длина слова равна n  k  1 . Обратно, если взять любое слово, топо нему можно построить (n,k)–сочетание с повторениями: нули разбиваютсяединицами на n групп и число i необходимо включить в сочетание столько раз,сколько нулей в i–той группе. Таким образом, имеется взаимно однозначное соответствие между (n,k)–сочетаниями с повторениями и словами длины n  k  1 валфавите E, содержащими ровно k нулей.

Число таких слов, как было показано n  k  1.k выше, равно Бином Ньютона. Это формула, представляющая выражение( a + b ) n при положительном целом n в виде многочлена:Решение задач на перестановки. Размещения, сочетания с повторениями.Задача 1. Сколько перестановок можно сделать из букв слова «Миссисипи»?Задача 2. Запишите всевозможные размещения с повторениями из трехэлементов a, b, c по 2Задача 3. Дано p+q+r различных предметов. Сколькими способами можноразбить эти предметы на 3 группы так, чтобы первая группа содержала p предметов, вторая q предметов, а третья r предметов?Задача 4.

Дано p+q+r различных предметов. Сколькими способами можноразбить эти предметы на 3 группы так, чтобы первая группа содержалапред-метов, вторая предметов, а третья предметов?Задача 5. Имеетсяодинаковых предметов. Сколькими способами можнораспределить эти предметы междуЗадача 6.лицами?шаров размещаются поящикам. Сколько существует спосо-бов разместить их так, что пустых ящиков нет?Задачи для самостоятельного решения.1. Есть три билета в различные театры. Сколькими способами они могутбыть распределены между 25 школьниками, если каждый школьник может получить только один билет?2.

Есть три билета на КВН 1 апреля. Сколькими способами они могут быть распределены между 25 школьниками (более одного билета в руки не давать!!!)?3. Телефонный номер состоит из 7 цифр. Насколько легче угадать правильныйномер, если знать, что все его цифры различны?4. В буфете продаются 5 сортов пирожков: с яблоками, с капустой, картошкой, мясом и грибами (цена всех пирожков одинакова).

Скольким числом способов можно сделать покупку из 10 пирожков?5. (Продолжение). Скольким числом способов можно сделать покупку так,чтобы попробовать пирожков всех видов?6. (Продолжение). Скольким числом способов можно сделать покупку так,чтобы в нее вошло не менее двух пирожков с мясом и хотя бы один пирожок сяблоками?7. Скольким числом способов можно вывести на арену цирка 5 львов и 4тигра так, чтобы никакие два тигра не шли друг за другом (оказавшись рядом,они начинают драться)?8.

За круглым столом короля Артура сидят 12 рыцарей. Из них каждыйвраждует со своими соседями. Для участия в спецоперации по освобождениюзаколдованной принцессы нужно выбрать 5 рыцарей, но при этом нельзя посылать вместе рыцарей, враждующих друг с другом. Скольким числом способовэто можно сделать?9. Докажите формулу10. Докажите, что число различных решений уравненияв неотрицательных целых числах равно11.Докажите,чтов натуральных числах равночисло.различныхрешенийуравнения.12. Сколькими способами можно разложить 15 одинаковых шаров по 5 различным ящикам так, чтобы оказалось не более двух пустых ящиков?13.

Сколькими способами можно разложить 20 одинаковых шаров по 5 различным ящикам так, чтобы в каждом ящике оказалось не менее двух шаров?14. Сколькими способами можно разложить 20 одинаковых шаров по 6 различным ящикам так, чтобы в каждом ящике оказалось не более 5 шаров?15. Докажите, что число таких перестановоксел, которые удовлетворяют условиючи-при всех , равноЗанятие 5 – практическое занятие № 9 (интерактивное). Защита домашнейработы по комбинаторике.Занятие проводится в интерактивной форме по методике «семинар-конференция).Элементы теории графовОсновные понятия теории графовТЕОРИЯ ГРАФОВ - это область дискретной математики, особенностью которой является геометрический подход к изучению объектов.

Теория графовнаходится сейчас в самом расцвете. Обычно её относят к топологии (потому чтово многих случаях рассматриваются лишь топологические свойства графов), однако она пересекается со многими разделами теории множеств, комбинаторнойматематики, алгебры, геометрии, теории матриц, теории игр, математической логики и многих других математических дисциплин. Основной объект теории графов-граф и его обобщения.Первые задачи теории графов были связаны с решением математическихразвлекательных задач и головоломок (задача о Кенигсбергских мостах, задача орасстановке ферзей на шахматной доске, задачи о перевозках, задача о кругосветном путешествии и другие).

Одним из первых результатов в теории графовявился критерий существования обхода всех ребер графа без повторений, полученный Л. Эйлером при решении задачи о Кенигсбергских мостах. Вот пересказотрывка из письма Эйлера от 13 марта 1736 году: ” Мне была предложена задачаоб острове, расположенном в городе Кенигсберге и окруженном рекой, через которую перекинуто 7 мостов.

Спрашивается, может ли кто-нибудь непрерывнообойти их, проходя только однажды через каждый мост. И тут же мне было сообщено, что никто еще до сих пор не смог это проделать, но никто и не доказал,что это невозможно. Вопрос этот, хотя и банальный, показался мне, однако, достойным внимания тем, что для его решения недостаточны ни геометрия, ни алгебра, ни комбинаторное искусство. После долгих размышлений я нашел лёгкоеправило, основанное на вполне убедительном доказательстве, с помощью которого можно во всех задачах такого рода тотчас же определить, может ли бытьсовершен такой обход через какое угодно число и как угодно расположенныхмостов или не может“. Кенигсбергские мосты схематически можно изобразитьтак:Правило Эйлера:1.В графе, не имеющем вершин нечетных степеней, существует обходвсех рёбер (причем каждое ребро проходится в точности один раз) с началом влюбой вершине графа.2.В графе, имеющем две и только две вершины с нечетными степе-нями, существует обход с началом в одной вершине с нечетной степенью и концом в другой.3.В графе, имеющим более двух вершин с нечетной степенью, такогообхода не существует.Существует еще один вид задач, связанных с путешествиями вдоль графов.

Речь идёт о задачах, в которых требуется отыскать путь, проходящий черезвсе вершины, причем не более одного раза через каждую. Цикл, проходящий через каждую вершину один и только один раз, носит название гамильтоновой линии( в честь Уильяма Роуэна Гамильтона, знаменитого ирландского математикапрошлого века, который первым начал изучать такие линии). К сожалению, покаеще не найден общий критерий, с помощью которого можно было бы решить,является ли данный граф гамильтоновым, и если да, то найти на нём все гамильтоновы линии.Сформулированная в середине 19 в.

проблема четырех красок также выглядит как развлекательная задача, однако попытки ее решения привели к появлению некоторых исследований графов, имеющих теоретическое и прикладноезначение. Проблема четырех красок формулируется так: ”Можно ли область любой плоской карты раскрасить четырьмя цветами так, чтобы любые две соседниеобласти были раскрашены в различные цвета?”. Гипотеза о том, что ответ утвердительный, была сформулирована в середине 19в.

В 1890 году было доказаноболее слабое утверждение, а именно, что любая плоская карта раскрашивается впять цветов. Сопоставляя любой плоской карте двойственный ей плоский граф,получают эквивалентную формулировку задачи в терминах графов: Верно ли,что хроматическое число любого плоского графа меньше либо равно четырёх?Многочисленные попытки решения задачи оказали влияние на развитие ряданаправлений теории графов.

В 1976 году анонсировано положительное решениезадачи с использованием ЭВМ.Другая старая топологическая задача, которая особенно долго не поддавалась решению и будоражила умы любителей головоломок, известна как “задача об электро -, газо - и водоснабжении”. В 1917 году Генри Э.ДьюдениСветводагаздал ей такую формулировку. В каждый из трёх домов, изображенных нарисунке, необходимо провести газ, свет и воду.Можно ли так проложить коммуникации, чтобы они, нигде не пересекаясьдруг с другом, соединяли каждый дом с источниками электричества, газа и воды?Иначе говоря, можно построить плоский граф с вершинами в шести указанныхточках? Оказывается, такой граф построить нельзя.

Об этом говорится в однойочень важной теореме – так называемой теореме Куратовского. Теорема утверждает, что каждый граф, не являющийся плоским, содержит в качестве подграфаодин из двух простейших пространственных графов:В середине 19 в. появились работы, в которых при решении практическихзадач были получены результаты, относящиеся к теории графов.

Так, например,Г. Кирхгоф при составлении полной системы уравнений для токов и напряженийв электрической схеме предложил по существу представлять такую схему графом и находить в этом графе остовные деревья, с помощью которых выделяютсялинейно независимые системы контуров. А. Кэли, исходя из задач подсчетачисла изомеров предельных углеводородов, пришел к задачам перечисления иописания деревьев, обладающих заданными свойствами, и решил некоторые изних.В 20 в. задачи, связанные с графами, начали возникать не только в физике,химии, электротехнике биологии, экономике, социологии и т.д., но и внутри математики, в таких разделах, как топология, алгебра, теория вероятностей, теориячисел. В начале 20 в.

Характеристики

Список файлов учебной работы