Реферат: Комбинаторика. Комбинаторика математика реферат

Реферат по математике на тему "Комбинаторика"

Реферат

По дисциплине: Математика

„ Комбинаторика “

Комбинаторика

Комбинаторика (Комбинаторный анализ) — раздел математики, изучающий дискретные объекты, множества (сочетания, перестановки, размещения и перечисления элементов) и отношения на них (например, частичного порядка). Комбинаторика связана со многими другими областями математики — алгеброй, геометрией, теорией вероятностей и имеет широкий спектр применения в различных областях знаний (например, в генетике, информатике, статистической физике).

Термин «комбинаторика» был введён в математический обиход Лейбницем, который в 1666 году опубликовал свой труд «Рассуждения о комбинаторном искусстве».

Иногда под комбинаторикой понимают более обширный раздел дискретной математики, включающий, в частности, теорию графов.

Примеры комбинаторных конфигураций и задач

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

• Размещением из n элементов по k называется упорядоченный набор из k различных элементов некоторого n-элементного множества.

• Перестановкой из n элементов (например, чисел 1,2,…,n) называется всякий упорядоченный набор из этих элементов. Перестановка также является размещением из n элементов по n.

• Сочетанием из n по k называется набор k элементов, выбранных из данных n элементов. Наборы, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми, этим сочетания отличаются от размещений.

• Композицией числаn называется всякое представление n в виде упорядоченной суммы целых положительных чисел.

• Разбиением числаn называется всякое представление n в виде неупорядоченной суммы целых положительных чисел.

Примеры комбинаторных задач:

1. Сколькими способами можно разместить n предметов по m ящикам, чтобы выполнялись заданные ограничения?

2. Сколько существует функций из m-элементного множества в n-элементное, удовлетворяющих заданным ограничениям?

3. Сколько существует различных перестановок из 52 игральных карт?

Ответ: 52! (52 факториал), то есть, 80658175170943878571660636856403766975289505440883277824000000000000 или примерно 8,0658 × 1067.

4. При игре в кости бросаются две кости, и выпавшие очки складываются; сколько существует комбинаций, в которых сумма очков на верхних гранях равна двенадцати?

Решение: Каждый возможный исход соответствует функции (аргумент функции — это номер кости, значение — очки на верхней грани). Очевидно, что лишь 6+6 даёт нам нужный результат 12. Таким образом, существует лишь одна функция, ставящая в соответствие 1 число 6, и 2 число 6. Или, другими словами, существует всего одна комбинация, при которой сумма очков на верхних гранях равна двенадцати.

Разделы комбинаторики

Перечислительная комбинаторика

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

Количество конфигураций, образованных несколькими манипуляциями над множеством, подсчитывается согласно правилам сложения и умножения.

Типичным примером задач данного раздела является подсчёт количества перестановок. Другой пример — известная Задача о письмах.

Структурная комбинаторика

К данному разделу относятся некоторые вопросы теории графов, а также теории матроидов.

Экстремальная комбинаторика

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

Теория Рамсея

Теория Рамсея изучает наличие регулярных структур в случайных конфигурациях элементов. Примером утверждения из теории Рамсея может служить следующее:

в группе из 6 человек всегда можно найти трёх человек, которые либо попарно знакомы друг с другом, либо попарно незнакомы.

В терминах структурной комбинаторики это же утверждение формулируется так:

в любом графе с 6 вершинами найдётся либо клика, либо независимое множество размера 3.

Вероятностная комбинаторика

Этот раздел отвечает на вопросы вида: какова вероятность присутствия определённого свойства у заданного множества.

Топологическая комбинаторика

Топологическая комбинаторика (англ.) применяет идеи и методы комбинаторики в топологии, при изучении дерева принятия решений, частично упорядоченных множеств, раскрасок графа и др.

Инфинитарная комбинаторика

Инфинитарная комбинаторика (англ.) — применение идей и методов комбинаторики к бесконечным (в том числе, несчётным) множествам.

Открытые проблемы

Комбинаторика, и в частности, теория Рамсея, содержит много известных открытых проблем, подчас с весьма несложной формулировкой. Например, неизвестно, при каком наименьшем N в любой группе из N человек найдутся 5 человек, либо попарно знакомых друг с другом, либо попарно незнакомых (хотя известно, что 49 человек достаточно).[1]

Исторический очерк

Джероламо Кардано написал математическое исследование игры в кости, опубликованное посмертно. Теорией этой игры занимались также Тарталья и Галилей. В историю зарождавшейся теории вероятностей вошла переписка заядлого игрока шевалье де Мерэ с Пьером Ферма и Блезом Паскалем, где были затронуты несколько тонких комбинаторных вопросов. Помимо азартных игр, комбинаторные методы использовались (и продолжают использоваться) в криптографии — как для разработки шифров, так и для их взлома.

Треугольник Паскаля

Блёз Паскаль много занимался биномиальными коэффициентами и открыл простой способ их вычисления: «треугольник Паскаля». Хотя этот способ был уже известен на Востоке (примерно с X века), Паскаль, в отличие от предшественников, строго изложил и доказал свойства этого треугольника. Наряду с Лейбницем, он считается основоположником современной комбинаторики. Сам термин «комбинаторика» придумал Лейбниц, который в 1666 году (ему было тогда 20 лет) опубликовал книгу «Рассуждения о комбинаторном искусстве». Правда, термин «комбинаторика» Лейбниц понимал чрезмерно широко, включая в него всю конечную математику и даже логику. Ученик Лейбница Якоб Бернулли, один из основателей теории вероятностей, изложил в своей книге «Искусство предположений» (1713) множество сведений по комбинаторике.

В этот же период формируется терминология новой науки. Термин «сочетание» (combination) впервые встречается у Паскаля (1653, опубликован в 1665 году). Термин «перестановка» (permutation) употребил в указанной книге Якоб Бернулли (хотя эпизодически он встречался и раньше). Бернулли использовал и термин «размещение» (arrangement).

После появления математического анализа обнаружилась тесная связь комбинаторных и ряда аналитических задач. Абрахам де Муавр и Джеймс Стирлинг нашли формулы для аппроксимации факториала.

Окончательно комбинаторика как самостоятельный раздел математики оформилась в трудах Эйлера. Он детально рассмотрел, например, следующие проблемы:

Кроме перестановок и сочетаний, Эйлер изучал разбиения, а также сочетания и размещения с условиями.

Комбинаторика в языкознании

Комбинаторика (языкознание) — это свойство единиц языка и соответствующих им единиц речи вступать в синтагматические отношения, то есть в отношения сочетаемости.

Литература

• Андерсон Джеймс. Дискретная математика и комбинаторика = Discrete Mathematics with Combinatorics. — М.: «Вильямс», 2006. — С. 960. — ISBN 0-13-086998-8.

• Виленкин Н.Я. Популярная комбинаторика. — М.: Наука, 1975.

• Ерош И. Л. Дискретная математика. Комбинаторика — СПб.: СПбГУАП, 2001. — 37 c.

• Липский В. Комбинаторика для программиста. — М.: Мир, 1988. — 213 с.

• Раизер Г. Дж. Комбинаторная математика. — пер. с англ. — М., 1966.

• Райгородский А. М. Линейно-алгебраические и вероятностные методы в комбинаторике. — Летняя школа «Современная математика». — Дубна, 2006.

• Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. — М.: Мир, 1980. — 476 с.

• Риордан Дж. Введение в комбинаторный анализ — пер. с англ. — М., 1963.

• Р. Стенли. Перечислительная комбинаторика = Enumerative Combinatorics. — М.: «Мир», 1990. — С. 440. — ISBN 5-03-001348-2.

• Р. Стенли. Перечислительная комбинаторика. Деревья, производящие функции и симметрические функции = Enumerative Combinatorics. Volume 2. — М.: «Мир», 2009. — С. 767. — ISBN 978-5-03-003476-8.

referat-4all.ru

Дипломная работа - Комбинаторика - Математика

/>Реферат на тему:

/>

Выполнилученик 10 класса «В»

среднейшколы №53

ГлуховМихаил Александрович

г. Набережные Челны

2002 г. Содержание

Из истории комбинаторики

Комбинаторика занимается различного вида соединениями,которые можно образовать из элементов конечного множества. Некоторые элементыкомбинаторики были известны в Индии еще во II в. до н. э. Нидийцы умеливычислять числа, которые сейчас называют «сочетания». В XII в.Бхаскара вычислял некоторые виды сочетаний и перестановок. Предполагают, чтоиндийские ученые изучали соединения в связи с применением их в поэтике, науке оструктуре стиха и поэтических произведениях. Например, в связи с подсчетомвозможных сочетаний ударных (долгих) и безударных (кратких) слогов стопы из nслогов. Как научная дисциплина, комбинаторика сформировалась в XVII в. В книге«Теория и практика арифметики» (1656 г.) французский автор А. Такжепосвящает сочетаниям и перестановкам целую главу. Б. Паскаль в «Трактате об арифметическом треугольнике» и в«Трактате о числовых порядках» (1665 г.) изложил учение обиномиальных коэффициентах. П. Ферма знал о связях математических квадратов и фигурныхчисел с теорией соединений. Термин "комбинаторика"стал употребляться после опубликования Лейбницем в 1665 г. работы«Рассуждение о комбинаторном искусстве», в которой впервые данонаучное обоснование теории сочетаний и перестановок. Изучением размещенийвпервые занимался Я. Бернулли во второй части своей книги «Arsconjectandi» (искусство предугадывания) в 1713 г. Современная символикасочетаний была предложена разными авторами учебных руководств только в XIX в.

Все разнообразие комбинаторных формул может бытьвыведено из двух основных утверждений, касающихся конечных множеств – правилосуммы и правило произведения.

Правило суммы

Если конечные множества не пересекаются, то число элементов X U Y{или} равно сумме числа элементов множества X и числа элементов множества Y.

То есть, если на первойполке стоит X книг, а на второй Y, то выбрать книгу из первой или второй полки,можно X+Y способами.

Ученик должен выполнить практическую работу по математике. Емупредложили на выбор 17 тем по алгебре и 13 тем по геометрии. Сколькимиспособами он может выбрать одну тему для практической работы?

Решение: X=17, Y=13

По правилу суммы X U Y=17+13=30 тем.

Имеется 5 билетов денежно-вещевой лотереи, 6 билетов спортлото и 10билетов автомотолотереи. Сколькими способами можно выбрать один билет изспортлото или автомотолотереи?

Решение: Так как денежно-вещевая лотерея в выборе не участвует, товсего 6+10=16 вариантов.

Если элемент X можно выбрать k способами, а элемент Y-m способамито пару (X,Y) можно выбрать k*m способами.

То есть, если на первой полке стоит 5 книг, а на второй 10, то выбратьодну книгу с первой полки и одну со второй можно 5*10=50 способами.

Решение: Имеется 12 книг и 3 цвета, значит по правилу произведениявозможно 12*3=36 вариантов переплета.

Сколько существует пятизначных чисел, которые одинаково читаются слеванаправо и справа налево?

Решение: В таких числах последняя цифра будет такая же, как и первая, апредпоследняя — как и вторая. Третья цифра будет любой. Это можно представить ввиде XYZYX, где Y и Z -любые цифры, а X — не ноль. Значит по правилупроизведения количество цифр одинаково читающихся как слева направо, так исправа налево равно 9*10*10=900 вариантов.

Пересекающиеся множества

Но бывает, что множества X и Yпересекаются, тогда пользуются формулой/>,где X и Y — множества, а /> - область пересечения.

/>Примеры задач

20 человек знают английский и 10 — немецкий,из них 5 знают и английский,и немецкий. Сколько Человек всего?

Ответ: 10+20-5=25 человек.

Также часто для наглядного решения задачи применяются круги Эйлера.Например:

/>Из100 туристов, отправляющихся в заграничное путешествие, немецким языком владеют30 человек, английским — 28, французским — 42. Английским и немецким одновременновладеют 8 человек, английским и французским — 10, немецким и французским — 5,всеми тремя языками — 3. Сколько туристов не владеют ни одним языком?

 Решение: Выразим условие этой задачи графически. Обозначимкругом тех, кто знает английский, другим кругом — тех, кто знает французский, итретьим кругом — тех, кто знают немецкий.

/>Всеми тремя языками владеют три туриста, значит, в общейчасти кругов вписываем число 3. Английским и французским языком владеют 10человек, а 3 из них владеют еще и немецким. Следовательно, только английским ифранцузским владеют 10-3=7 человек.

Аналогично получаем, что только английским и немецким владеют 8-3=5 человек, а немецким и французским 5-3=2 туриста. Вносим этиданные в соответствующие части.

/>Определим теперь, сколько человек владеют только одним изперечисленных языков. Немецкий знают 30 человек, но 5+3+2=10 из них владеют идругими языками, следовательно, только немецкий знают 20 человек. Аналогичнополучаем, что одним английским владеют 13 человек, а одним французским — 30 человек.

По условию задачи всего 100 туристов. 20+13+30+5+7+2+3=80 туристовзнают хотя бы один язык, следовательно, 20 человек не владеют ни одним изданных языков.

Размещениябез повторений.

Сколько можносоставить телефонных номеров из 6 цифр каждый, так чтобы все цифры былиразличны?

Это пример задачи на размещениебез повторений. Размещаются здесь 10 цифр по 6. А варианты, при которыходинаковые цифры стоят в разном порядке считаются разными.

Если X-множество, состоящие из nэлементов, m≤n, то размещением без повторений из n элементов множества Xпо m называется упорядоченное множество X, содержащее m элементов называетсяупорядоченное множество X, содержащее m элементов.

Количество всех размещений из n элементов по mобозначают

/>

n! — n-факториал (factorial анг. сомножитель) произведениечисел натурального ряда от 1 до какого либо числа n

n!=1*2*3*...*n       0!=1

Значит, ответ на вышепоставленную задачу будет

/>

Задача

Сколькими способами 4 юноши могут пригласить четырех изшести девушек на танец?

Решение: два юноши не могут одновременно пригласить одну и туже девушку. И варианты, при которых одни и те же девушки танцуют с разнымиюношами считаются, разными, поэтому:

/> 

Возможно 360 вариантов.

Перестановки без повторений

В случаеn=m (см. размещения без повторений) из n элементов по m  называется перестановкоймножества x.

Количествовсех перестановок из n элементов обозначают Pn.

Pn=n!

Действительно при n=m:

/>

Примеры задач

Сколькоразличных шестизначных чисел можно составить из цифр 0, 1, 2, 3, 4,5, еслицифры в числе не повторяются?

Решение:

1)      Найдемколичество всех перестановок из этих цифр: P6=6!=720

2)      0 не можетстоять впереди числа, поэтому от этого числа необходимо отнять количествоперестановок, при котором 0 стоит впереди. А это P5=5!=120.

P6-P5=720-120=600

Квартет

ПроказницаМартышка

Осел,

Козел,

Дакосолапый Мишка

Затеялииграть квартет

…

Стой,братцы стой! –

КричитМартышка, — погодите!

Какмузыке идти?

Ведь выне так сидите…

И так, и этакпересаживались – опять музыка на лад не идет.

Тут пущепрежнего пошли у низ раздоры

И споры,

Кому икак сидеть…

Вероятно,крыловские музыканты так и не перепробовали всех возможных мест. Однако способовне так уж и много. Сколько?

Здесь идетперестановка из четырех, значит, возможно

P4=4!=24варианта перестановок.

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

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

Всякоеподмножество X состоящее из m элементов, называется сочетанием из n элементовпо m.

Таким образом,количество вариантов при сочетании будет меньше количества размещений.

Число сочетанийиз n элементов по m обозначается />.

/>.

Примеры задач

/>Сколькотрехкнопочных комбинаций существует на кодовом замке (все три кнопки нажимаютсяодновременно), если на нем всего 10 цифр.

Решение:

Так как кнопкинажимаются одновременно, то выбор этих трех кнопок – сочетание. Отсюда возможно/>вариантов.

У одногочеловека 7 книг по математике, а у второго – 9. Сколькими способами они могутобменять друг у друга две книги на две книги.

Решение:

Так как надо порядок следования книг не имеет значения, то выбор 2ух книг — сочетание. Первый человек может выбрать 2 книги />/> способами. Второй человек можетвыбрать 2 книги />. Значит всего поправилу произведения возможно 21*36=756 вариантов.

При игре вдомино 4 игрока делят поровну 28 костей. Сколькими способами они могут это сделать?

Первый игрокделает выбор из 28 костей. Второй из 28-7=21 костей, третий 14, а четвертыйигрок забирает оставшиеся кости. Следовательно, возможно />.Размещения и сочетания с повторениями

Часто взадачах по комбинаторике встречаются множества, в которых какие-либо компонентыповторяются. Например: в задачах на числа – цифры. Для таких задач приразмещениях используется формула />, а длясочетаний />.

Примеры задач

Сколькотрехзначных чисел можно составить из цифр 1, 2, 3, 4, 5?

Решение.Так как порядок цифр в числе существенен, цифры могут повторяться, то это будутразмещения с повторениями из пяти элементов по три, а их число равно />.

Вкондитерском магазине продавались 4 сорта пироженных: эклеры, песочные,наполеоны и слоеные. Сколькими способами можно купить 7 пироженных.

Решение:Покупка не зависит от того, в каком порядке укладывают купленные пироженные в коробку.Покупки будут различными, если они отличаются количеством купленных пирожныххотя бы одного сорта. Следовательно, количество различных покупок равно числусочетаний четырех видов пироженных по семь — />.

Обезьянупосадили за пишущую машинку с 45 клавишами, определить число попыток, необходимыхдля того, чтобы она наверняка напечатала первую строку романа Л.Н. Толстого«Анна Каренина», если строка содержит 52 знака и повторений не будет?

Решение:порядок букв имеет значение. Буквы могут повторяться. Значит, всего есть /> вариантов.

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

/>/>,где n-количество всех элементов, n1,n2,…,nr-количествоодинаковых элементов.

Примеры задач

Сколькимиспособами можно переставить буквы слова «ананас»?

Решение:всего букв 6. Из них одинаковы n1«а»=3, n2«н»=2, n3«с»=1.Следовательно, число различных перестановок равно />.

/>Задачи для самостоятельного решения

Сколько перестановок можно сделать из букв слова«Миссисипи».

Ответ: 2520

  Имеется пять различных стульев и семь рулонов обивочнойткани различных цветов. Сколькими способами можно осуществить обивку стульев.

Ответ: 16807

На памятныесувениры в «Поле Чудес» спонсоры предлагают кофеварки, утюги, телефонныеаппараты, духи. Сколькими способами 9 участников игры могут получить эти сувениры?Сколькими способами могут быть выбраны 9 предметов для участников игры?

Ответ: 49, 220

Сколькимиспособами можно расставить на шахматной доске 8 ладей так, чтобы на одна из нихне могла бить другую?

Ответ: 40320

Сколько можетбыть случая выбора 2 карандашей и 3 ручек из пяти различных карандашей и шестиразличных ручек?

Ответ:200

Сколькоспособов раздачи карт на 4 человека существует в игре                 «Верю ‑ не верю»(карты раздаются полностью, 36 карт).

Ответ: />.

В течении 30дней сентября было 12 дождливых дней, 8 ветреных, 4 холодных, 5 дождливых иветреных, 3 дождливых и холодных, а один день был и дождливым, и ветреным, ихолодным. В течение скольких дней в сентябре стояла хорошая погода.

Ответ: 15

На ферме есть20 овец и 24 свиньи. Сколькими способами можно выбрать одну овцу и одну свинью?Если такой выбор уже сделан, сколькими способами можно сделать его еще раз?

Ответ: 480, 437

Сколькимиспособами можно выбрать гласную и согласную буквы из слова «здание»?

Ответ: 9

Сколькосуществует четных пятизначных чисел, начинающихся нечетной цифрой?

Ответ: 25000

В книжныймагазин  поступили романы Ф. Купера «Прерия», «Зверобой», «Шпион», «Пионеры»,«Следопыт» по одинаковой цене. Сколькими способами библиотека может закупить 17книг на выбранный чек?

Ответ:: 2985Список используемой литературы

Савина Л.Н.,Попырев А.В. «КОМБИНАТОРИКА» издательство Елабужский государственный педагогическийинститут 1999г

Халамайзер А.Я. «Математика? – Забавно!» издание автора 1989г

Интернет

http:\www.mathclub.zala.ru/0921.html

www.ronl.ru

Реферат: Комбинаторика

Реферат на тему:

Выполнил ученик 10 класса «В»

средней школы №53

Глухов Михаил Александрович

г. Набережные Челны

2002 г.Содержание

Из истории комбинаторики

Комбинаторика занимается различного вида соединениями, которые можно образовать из элементов конечного множества. Некоторые элементы комбинаторики были известны в Индии еще во II в. до н. э. Нидийцы умели вычислять числа, которые сейчас называют "сочетания". В XII в. Бхаскара вычислял некоторые виды сочетаний и перестановок. Предполагают, что индийские ученые изучали соединения в связи с применением их в поэтике, науке о структуре стиха и поэтических произведениях. Например, в связи с подсчетом возможных сочетаний ударных (долгих) и безударных (кратких) слогов стопы из n слогов. Как научная дисциплина, комбинаторика сформировалась в XVII в. В книге "Теория и практика арифметики" (1656 г.) французский автор А. Также посвящает сочетаниям и перестановкам целую главу.Б. Паскаль в "Трактате об арифметическом треугольнике" и в "Трактате о числовых порядках" (1665 г.) изложил учение о биномиальных коэффициентах. П. Ферма знал о связях математических квадратов и фигурных чисел с теорией соединений. Термин "комбинаторика" стал употребляться после опубликования Лейбницем в 1665 г. работы "Рассуждение о комбинаторном искусстве", в которой впервые дано научное обоснование теории сочетаний и перестановок. Изучением размещений впервые занимался Я. Бернулли во второй части своей книги "Ars conjectandi" (искусство предугадывания) в 1713 г. Современная символика сочетаний была предложена разными авторами учебных руководств только в XIX в.

Все разнообразие комбинаторных формул может быть выведено из двух основных утверждений, касающихся конечных множеств – правило суммы и правило произведения.

Правило суммы

Если конечные множества не пересекаются, то число элементов X U Y {или} равно сумме числа элементов множества X и числа элементов множества Y.

То есть, если на первой полке стоит X книг, а на второй Y, то выбрать книгу из первой или второй полки, можно X+Y способами.

Примеры задач

Ученик должен выполнить практическую работу по математике. Ему предложили на выбор 17 тем по алгебре и 13 тем по геометрии. Сколькими способами он может выбрать одну тему для практической работы?

Решение: X=17, Y=13

По правилу суммы X U Y=17+13=30 тем.

Имеется 5 билетов денежно-вещевой лотереи, 6 билетов спортлото и 10 билетов автомотолотереи. Сколькими способами можно выбрать один билет из спортлото или автомотолотереи?

Решение: Так как денежно-вещевая лотерея в выборе не участвует, то всего 6+10=16 вариантов.

Правило произведения

Если элемент X можно выбрать k способами, а элемент Y-m способами то пару (X,Y) можно выбрать k*m способами.

То есть, если на первой полке стоит 5 книг, а на второй 10, то выбрать одну книгу с первой полки и одну со второй можно 5*10=50 способами.

Примеры задач

Переплетчик должен переплести 12 различных книг в красный, зеленый и коричневые переплеты. Сколькими способами он может это сделать?

Решение: Имеется 12 книг и 3 цвета, значит по правилу произведения возможно 12*3=36 вариантов переплета.

Сколько существует пятизначных чисел, которые одинаково читаются слева направо и справа налево?

Решение: В таких числах последняя цифра будет такая же, как и первая, а предпоследняя - как и вторая. Третья цифра будет любой. Это можно представить в виде XYZYX , где Y и Z -любые цифры, а X - не ноль. Значит по правилу произведения количество цифр одинаково читающихся как слева направо, так и справа налево равно 9*10*10=900 вариантов.

Пересекающиеся множества

Но бывает, что множества X и Y пересекаются, тогда пользуются формулой, где X и Y - множества, а - область пересечения.

Примеры задач

20 человекзнаютанглийскийи 10 - немецкий, изних 5 знаютианглийский, инемецкий. СколькоЧеловеквсего?

Ответ: 10+20-5=25 человек.

Также часто для наглядного решения задачи применяются круги Эйлера. Например:

Из 100 туристов, отправляющихся в заграничное путешествие, немецким языком владеют 30 человек, английским - 28, французским - 42. Английским и немецким одновременно владеют 8 человек, английским и французским - 10, немецким и французским - 5, всеми тремя языками - 3. Сколько туристов не владеют ни одним языком?

Решение: Выразим условие этой задачи графически. Обозначим кругом тех, кто знает английский, другим кругом - тех, кто знает французский, и третьим кругом - тех, кто знают немецкий.

Всеми тремя языками владеют три туриста, значит, в общей части кругов вписываем число 3. Английским и французским языком владеют 10 человек, а 3 из них владеют еще и немецким. Следовательно, только английским и французским владеют 10-3=7 человек.

Аналогично получаем, что только английским и немецким владеют 8-3=5 человек, а немецким и французским 5-3=2 туриста. Вносим эти данные в соответствующие части.

Определим теперь, сколько человек владеют только одним из перечисленных языков. Немецкий знают 30 человек, но 5+3+2=10 из них владеют и другими языками, следовательно, только немецкий знают 20 человек. Аналогично получаем, что одним английским владеют 13 человек, а одним французским - 30 человек.

По условию задачи всего 100 туристов. 20+13+30+5+7+2+3=80 туристов знают хотя бы один язык, следовательно, 20 человек не владеют ни одним из данных языков.

Размещения без повторений.

Сколько можно составить телефонных номеров из 6 цифр каждый, так чтобы все цифры были различны?

Это пример задачи на размещение без повторений. Размещаются здесь 10 цифр по 6. А варианты, при которых одинаковые цифры стоят в разном порядке считаются разными.

Если X-множество, состоящие из n элементов, m≤n, то размещением без повторений из n элементов множества X по m называется упорядоченное множество X, содержащее m элементов называется упорядоченное множество X, содержащее m элементов.

Количество всех размещений из n элементов по m обозначают

n! - n-факториал (factorial анг. сомножитель) произведение чисел натурального ряда от 1 до какого либо числа n

n!=1*2*3*...*n 0!=1

Значит, ответ на вышепоставленную задачу будет

Задача

Сколькими способами 4 юноши могут пригласить четырех из шести девушек на танец?

Решение : два юноши не могут одновременно пригласить одну и ту же девушку. И варианты, при которых одни и те же девушки танцуют с разными юношами считаются, разными, поэтому:

Возможно 360 вариантов.

Перестановки без повторений

В случае n=m (см. размещения без повторений) из n элементов по m называется перестановкой множества x.

Количество всех перестановок из n элементов обозначают Pn.

Pn =n!

Действительно при n=m:

Примеры задач

Сколько различных шестизначных чисел можно составить из цифр 0, 1, 2, 3, 4,5, если цифры в числе не повторяются?

Решение:

1) Найдем количество всех перестановок из этих цифр: P6 =6!=720

2) 0 не может стоять впереди числа, поэтому от этого числа необходимо отнять количество перестановок, при котором 0 стоит впереди. А это P5 =5!=120.

P6 -P5 =720-120=600

Квартет

Проказница Мартышка

Осел,

Козел,

Да косолапый Мишка

Затеяли играть квартет

…

Стой, братцы стой! –

Кричит Мартышка, - погодите!

Как музыке идти?

Ведь вы не так сидите…

И так, и этак пересаживались – опять музыка на лад не идет.

Тут пуще прежнего пошли у низ раздоры

И споры,

Кому и как сидеть…

Вероятно, крыловские музыканты так и не перепробовали всех возможных мест. Однако способов не так уж и много. Сколько?

Здесь идет перестановка из четырех, значит, возможно

P4 =4!=24 варианта перестановок.

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

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

Всякое подмножество X состоящее из m элементов, называется сочетанием из n элементов по m.

Таким образом, количество вариантов при сочетании будет меньше количества размещений.

Число сочетаний из n элементов по m обозначается .

.

Примеры задач

Сколько трехкнопочных комбинаций существует на кодовом замке (все три кнопки нажимаются одновременно), если на нем всего 10 цифр.

Решение :

Так как кнопки нажимаются одновременно, то выбор этих трех кнопок – сочетание. Отсюда возможно вариантов.

У одного человека 7 книг по математике, а у второго – 9. Сколькими способами они могут обменять друг у друга две книги на две книги.

Решение:

Так как надо порядок следования книг не имеет значения, то выбор 2ух книг - сочетание. Первый человек может выбрать 2 книги способами. Второй человек может выбрать 2 книги . Значит всего по правилу произведения возможно 21*36=756 вариантов.

При игре в домино 4 игрока делят поровну 28 костей. Сколькими способами они могут это сделать?

Первый игрок делает выбор из 28 костей. Второй из 28-7=21 костей, третий 14, а четвертый игрок забирает оставшиеся кости. Следовательно, возможно .Размещения и сочетания с повторениями

Часто в задачах по комбинаторике встречаются множества, в которых какие-либо компоненты повторяются. Например: в задачах на числа – цифры. Для таких задач при размещениях используется формула , а для сочетаний .

Примеры задач

Сколько трехзначных чисел можно составить из цифр 1, 2, 3, 4, 5?

Решение . Так как порядок цифр в числе существенен, цифры могут повторяться, то это будут размещения с повторениями из пяти элементов по три, а их число равно .

В кондитерском магазине продавались 4 сорта пироженных: эклеры, песочные, наполеоны и слоеные. Сколькими способами можно купить 7 пироженных.

Решение : Покупка не зависит от того, в каком порядке укладывают купленные пироженные в коробку. Покупки будут различными, если они отличаются количеством купленных пирожных хотя бы одного сорта. Следовательно, количество различных покупок равно числу сочетаний четырех видов пироженных по семь - .

Обезьяну посадили за пишущую машинку с 45 клавишами, определить число попыток, необходимых для того, чтобы она наверняка напечатала первую строку романа Л.Н. Толстого «Анна Каренина», если строка содержит 52 знака и повторений не будет?

Решение : порядок букв имеет значение. Буквы могут повторяться. Значит, всего есть вариантов.

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

, где n-количество всех элементов, n1 ,n2 ,…,nr -количество одинаковых элементов.

Примеры задач

Сколькими способами можно переставить буквы слова «ананас»?

Решение : всего букв 6. Из них одинаковы n1 «а»=3, n2 «н»=2, n3 «с»=1. Следовательно, число различных перестановок равно .

Задачи для самостоятельного решения

Сколько перестановок можно сделать из букв слова «Миссисипи».

Ответ: 2520

Имеется пять различных стульев и семь рулонов обивочной ткани различных цветов. Сколькими способами можно осуществить обивку стульев.

Ответ: 16807

На памятные сувениры в «Поле Чудес» спонсоры предлагают кофеварки, утюги, телефонные аппараты, духи. Сколькими способами 9 участников игры могут получить эти сувениры? Сколькими способами могут быть выбраны 9 предметов для участников игры?

Ответ: 49 , 220

Сколькими способами можно расставить на шахматной доске 8 ладей так, чтобы на одна из них не могла бить другую?

Ответ: 40320

Сколько может быть случая выбора 2 карандашей и 3 ручек из пяти различных карандашей и шести различных ручек?

Ответ:200

Сколько способов раздачи карт на 4 человека существует в игре «Верю ‑ не верю» (карты раздаются полностью, 36 карт).

Ответ: .

В течении 30 дней сентября было 12 дождливых дней, 8 ветреных, 4 холодных, 5 дождливых и ветреных, 3 дождливых и холодных, а один день был и дождливым, и ветреным, и холодным. В течение скольких дней в сентябре стояла хорошая погода.

Ответ: 15

На ферме есть 20 овец и 24 свиньи. Сколькими способами можно выбрать одну овцу и одну свинью? Если такой выбор уже сделан, сколькими способами можно сделать его еще раз?

Ответ: 480, 437

Сколькими способами можно выбрать гласную и согласную буквы из слова «здание»?

Ответ: 9

Сколько существует четных пятизначных чисел, начинающихся нечетной цифрой?

Ответ: 25000

В книжный магазин поступили романы Ф. Купера «Прерия», «Зверобой», «Шпион», «Пионеры», «Следопыт» по одинаковой цене. Сколькими способами библиотека может закупить 17 книг на выбранный чек?

Ответ:: 2985Список используемой литературы

Савина Л.Н., Попырев А.В. «КОМБИНАТОРИКА» издательство Елабужский государственный педагогический институт 1999г

Халамайзер А. Я. «Математика? – Забавно!» издание автора 1989г

Интернет

http:\www.mathclub.zala.ru/09 21.html

www.yurii.ru

Смотрите также

• 
  Реферат планирование здравоохранения
• 
  Реферат пипин короткий
• 
  Гипотиреоз врожденный реферат
• 
  Реферат уравнение эйлера
• 
  Университет оксфорд реферат
• 
  Реферат этикет испании
• 
  Реферат про вольтера
• 
  Пифагорейский союз реферат
• 
  Лизосомные болезни реферат
• 
  Лазерные дальномеры реферат
• 
  Коэффициент вариации реферат