Основы комбинаторики

Научное общество учащихся Реферат Основы комбинаторики Выполнил:

ученик 10Б класса МОУСОШ № 169

Андреев Владислав Станиславович Нижний Новгород

2012год

Введение

Цели Актуальность Множества и факториалы Немного о картежах Задачи и разделы комбинаторики Размещения Перестановки Сочетание Обобщенные задачи Список литературы

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

Комбинаторика возникла в XVII в. Долгое время казалось, что комбинаторика лежит вне основного русла развития математики и ее приложений. Положение дел резко изменилось после появления быстродействующих вычислительных машин и связанного с этим расцвета конечной математики. Сейчас комбинаторные методы применяются в теории случайных процессов, статистике, математическом программировании, вычислительной математике, планировании экспериментов и т. д. В математике комбинаторика используется при изучении конечных геометрий, комбинаторной геометрии, теории представлений групп, и др.

Законы комбинирования и образования различных конфигураций объектов, получившей название комбинаторики. С задачами, в которых приходится выбирать те или иные предметы, располагать их в определенном порядке и отыскивать среди разных расположений наилучшие, люди столкнулись еще в доисторическую эпоху, выбирая наилучшие расположения охотников во время охоты, воинов во время битвы, инструментов во время работы. Определенным образом располагались украшения на одежде, узоры на керамике, перья в оперении стрелы. По мере усложнения производственных и общественных отношений все шире приходилось пользоваться общими понятиями о порядке, иерархии, группировании В том же направлении действовало развитие ремесел и торговли. Комбинаторные навыки оказались полезными и в часы досуга. Нельзя точно сказать, когда наряду с состязаниями в беге, метании диска, прыжках появились игры, требовавшие в первую очередь умения рассчитывать, составлять планы и опровергать планы противника.

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

Цели

1. Познакомить учащихся с основными понятиями комбинаторики

2. Познакомить с методами решения комбинаторных задач

3. Расширить круг знаний учащихся

4. Показать на практике решение задач

5. Познакомить с основными формулами комбинаторике

Актуальность

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

Множества и факториалы

Факториал:

Факториалом называется произведение n натуральных чисел от 1 до n. Обозначается n! Например: 2! = 2 1 = 2, 4! =. Условились считать 1! = 0, 0! = 1

Множества:

Множество — одно из ключевых понятий математики, в частности, теории множеств и логики.

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

Под «множеством» мы понимаем соединение в некое целое M определённых хорошо различимых предметов m нашего созерцания или нашего мышления (которые будут называться «элементами» множества M)

В математической логике и дискретной математике часто употребляемый синоним множества — алфавит. Множество может быть замкнутым и незамкнутым, полным и пустым, упорядоченным и неупорядоченным, счётным и несчётным, конечным и бесконечным. Более того, как в наивной, так и в формальной теориях множеств любой объект обычно считается множеством. Объекты, из которых состоит множество, называют элементами множества или точками множества. Множества чаще всего обозначают большими буквами латинского алфавита, его элементы — маленькими. Если, а — элемент множества А, то записывают, а? А (а принадлежит А). Если, а не является элементом множества А, то записывают, а? А (а не принадлежит А). В отличие от мультимножества каждый элемент множества уникален, и в множестве не может быть двух идентичных элементов: {6, 11} = {11, 6} = {11, 11, 6, 11}

Некоторые виды множеств и сходных объектов

Специальные множества

· Пустое множество — множество, не содержащее ни одного элемента.

· Универсальное множество (универсум) — множество, содержащее все мыслимые объекты.

· Упорядоченное множество — множество, на котором задано отношение порядка.

Сходные объекты

· Набор (в частности, упорядоченная пара) — совокупность конечного числа именованных объектов.

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

· Мультимножество — множество с кратными элементами.

· Пространство — множество с некоторой дополнительной структурой.

· Вектор — элемент линейного пространства, содержащий конечное число элементов некоторого поля в качестве координат. Порядок имеет значение, элементы могут повторяться.

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

· Нечёткое множество — математический объект, представляющий собой множество, принадлежность к которому представляет собой не отношение, а функцию. Иными словами, относительно элементов этого множества можно говорить «в какой мере» они в него входят, а не просто входят они в него или нет Над множествами, как и над многими другими математическими объектами, можно совершать различные операции, которые иногда называют теоретик множественными операциями или сеть - операциями. В результате операций из исходных множеств получаются новые.

Сравнение множеств

Множество A содержится во множестве B (множество B включает множество A), если каждый элемент A есть элемент B: В этом случае A называется подмножеством B, B — надмножеством A. Если и, то A называется собственным подмножеством B. Заметим, что. По определению. Два множества называются равными, если они являются подмножествами друг друга: Иногда для того, чтобы подчеркнуть, что множества могут быть равны, используется запись:

Немного о кортежах

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

Два кортежа называют равными в том и только том случае, когда они имеют одинаковую длину, а на соответствующих местах стоят одни и те же элементы.

В определении кортежа не уточнялось, могут ли множества иметь общие элементы. На первый взгляд, этого не следовало, допускать — если уж какой-нибудь элемент вытащен из мешка и занял свое место, то откуда же взять его еще раз? Можно считать, что каждый элемент изготовлен в достаточном количестве экземпляров и в случае необходимости может лежать в нескольких мешках. Поэтому в кортежах координаты могут повторяться, например, кортеж может иметь такой вид: (1, 2,1,3,4,4,6). Не исключен и такой случай, когда все множества совпадают. В этом случае можно считать, что у нас есть один мешок с элементами множества X, эти элементы извлекают из мешка, записывают, а потом кладут обратно в мешок. С кортежами мы встречаемся очень часто. Например, семизначные номера телефонов в Москве — это кортежи Длины 7, составленные из элементов множества X = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9},

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

Если элемент можно выбрать способами, из каждого выбора этого элемента следующий за ним можно выбрать способами… после выбора элемент выбирается способами, то кортеж () можно выбрать способами. Возьмем несколько конечных множеств, состоящих соответственно из элементов, и найдем сколько кортежей длины к можно составить из элементов этих множеств. Сначала наше число кортежей длины 1, составленных из элементов множества. Ясно, что их число равно. Возьмем теперь один из этих кортежей () и припишем к элементу справа по очереди все элементы множества. Получится n кортежей длины 2, у которых первая координата равна. Но вместо можно было бы взять любой другой элемент из. Поэтому получается раз по кортежа, а всего кортежей длины 2 или, как чаще говорят, пар. Из каждой такой пары получим троек, приписав к пе по очереди все элементы множества, а всего троек. Продолжая этот процесс, получим в конце концов кортежей длины k, составленных из элементов наших множеств. Когда множество бывает не задано, а определяется после выбора элемента множество определяется после выбора элементов и т. д. Но при этом, как бы мы ни выбрали элемент, выбор элемента возможен способами, при любом выборе элементов на третье место есть кандидатов и т. д. И в этом случае ответ получится тот же самый: общее число различных кортежей оказываете равным. Так как для подсчета числа всевозможных кортеже" приходится перемножать числа, то выведенный результат называют «правилом произведения» .

Попробуем, подсчитаем, например, сколько слов, содержащий букв, можно составить из 33 букв русского алфавита при условии, что любые две стоящие рядом буквы различны (например, слово «корова» допускается, а слово «колосс» нет). При этом, разумеется, мы будем писать не только слова, имеющие смысл, но и такие, например, бессмысленные, как «трнаук» и т. п. В этом случае на первое место у нас 33 кандидата. Но после того как первая буква выбрана, вторую можно выбрать лишь 32 способами — ведь повторять первую букву нельзя. На третье место тоже 32 кандидата — первую букву уже можно повторить, а вторую — нельзя. Также убеждаемся, что на все места, кроме первого, имеется 32 кандидата. А так как число этих мест равно 5, то получаем ответ 33−32−32−32−32−32 = 1 107 396 236.

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

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

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

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

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

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

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

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

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

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

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

Задачи комбинаторики.

1) Найти конфигурацию элементов, обладающую заранее заданными свойствами.

2) Доказать существование или отсутствие конфигурации с заданными свойствами.

3) Найти общее число конфигураций с заданными свойствами.

4) Описать все способы решения данной комбинаторной задачи, дать алгоритм их перечисления.

5) Ив всех решений данной комбинаторной задачи выбрать оптимальное по тем или иным параметрам.

Размещения

В комбинаторике размещением называется расположение «предметов» на некоторых «местах» при условии, что каждое место занято в точности одним предметом и все предметы различны. Более формально, размещением (из n по k) называется упорядоченный набор из k различных элементов некоторого n-элементного множества. Количество размещений из n по k обозначается Например, — это 4-элементное размещение 6-элементного множества {1,2,3,4,5,6}. В отличие от сочетаний, размещения учитывают порядок следования предметов. Так, например, наборы < 2,1,3 > и < 3,2,1 > являются различными, хотя состоят из одних и тех же элементов {1,2,3} (то есть совпадают как сочетания).

Множества, ... из элементов которых составляются кортежи, могут иметь общие элементы. В частности, все они могут совпадать с одним и тем же множеством X, со — держащим n элементов. Кортежи длины k, составленные из элементов n — множества X, называют размещениями с повторениями из n элементов по k, а их число обозначают

Формула:

Доказательство: Из правила произведения сразу вытекает, что число размещений с повторениями из n элементов по k равно произведению k сомножителей, каждый из которых равен n. А все вместе .

Теперь рассмотрим размещение без повторений: при k. n, k — натуральные числа Доказательство: Если то в правой часте будет k множителей, если k = 1, то. Введем Метод математической индукции по k.

6) При k = 1 равенство выполняется, так как

7) Предположим что и для k = j это равенство справедливо, то

8) Теперь нужно доказать что для k = j +1 равенство тоже справедливо По нашему предположению, выбрать группу изn элементов по j можно способами Присоединить к каждой выбранной группе из j элементов ещё один элемент из основания (n — j) способами то есть Поэтому для любого справедливо это равенство (по принципу математической индукции). Доказано.

Выедем другую формулу: (при тех же условиях) Доказательство: умножив числитель и знаменатель на (п — к)…1. В числителе получится произведение всех чисел от 1 до n. Что является n!, а в знаменателе станет (nk)!.

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

Задача № 1.В высшей лиге первенства России по футболу участвуют 16 команд. Разыгрываются 3 медали: золотая, серебряная и бронзовая. Перед началом первенства был объявлен конкурс знатоков, в котором требовалось указать распределение медалей. Сколько различных ответов можно дать на этот вопрос?

Во-первых, ясно, что здесь мы имеем дело с кортежами длины 3, а не с множествами из 3 элементов — ведь одно дело, когда золотую медаль получил «Арарат», а серебряную — киевское «Динамо», а другое, когда они меняются ролями и чемпионом страны становится «Динамо». Но в рассматриваемой задаче есть своеобразные черты, ведь теперь ни один элемент не может дважды встретиться в кортеже победителей: одна и та же команда не может получить, например, и золото, и бронзу. Поэтому нам надо решить такую задачу: найти число кортежей длины 3, составленных из 16 команд, в которых ни одна команда не повторяется дважды. Золотую медаль может, вообще говоря, получить любая из 16 команд (мяч, как известно, круглый…). Но если какая-нибудь команда завоевала золотые медали, то на второе место претендуют 15 команд — все, кроме чемпиона. А после распределения золотой и серебряной Медалей остаются лишь 14 претендентов на бронзовые медали. По правилу произведения выводим, что число различных кортежей, удовлетворяющих поставленным требованиям, равно 16−15−14 = 3 360.

Задача № 2. Число букв на каждом диске равно 12, а число дисков равно 5. Сколько неудачных попыток может быть сделано человеком, не знающим секретного слова и подбирающим его наудачу?

Из условия Задачи видно, что порядок выбираемы* букв существен (можно набрать на первом диске букву «а», а на втором букву «б», а можно— набрать эти же буквы в обратном порядке). Поэтому мы имеем здесь дело с кортежами. При этом никаких ограничений на эти кортежи не наложено. Так как по условию каждая буква может быть выбрана 12 способами, а длина кортежей равна 5, то по формуле получаем, это число и будет числом комбинаций. Значит, неудачных попыток может быть 248 831. Ответ: 248 831.

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

В комбинаторике перестановка из n элементов — это расположение их в определённом порядке. Таким, образом, различные перестановка из n элементов соответствует различным расположение (в том или ином порядке) этих n элементов. Количество перестановок из n элементов обозначают. Пусть дан кортеж длины n, составленный из элементов множества X = {}, причем буква входит в этот кортеж раз, …, буква — раз. Тогда

Если переставлять в этом кортеже буквы, будут получаться новые кортежи, имеющие тот же состав, т. е. такие, что буква входит в них раз,.. ., буква, а входит раз. Называют такие кортежи перестановками с повторениями из букв,.. .,, имеющие состав (,.. .,). Число таких перестановок обозначим Р (,.. .,). Формула № 1:

Доказательство: (n — натуральное число) Метод математической индукции:

n = 1

Предположим что n = k тогда

Докажем, что тогда для n = k +1 эта формула справедлива то есть Что бы получить всевозможные перестановки из элементов. На первое место поставим (j = 1, 2, 3, …, k +1) а за ними остальные k элементов расположены всеми возможными способами. Количество перестановок во k элементов по предположению будет равно

т. к = (k+1), то и

Доказано.

Формула № 2:

Доказательство:

.

а из этого следует что

т.к n! =

Доказано.

формула перестановок с повторениями № 3.

Доказательство:

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

Но n чисел можно переставлять друг с другом n! способами.

Поэтому число различных перестановок букв, имеющих состав (,.. .,). т. е. Р (,.. .,) (по определению), в раз меньше, чем n!, где

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

Задача № 1Сколькими способами можно расставить п ладей на (п х п)-доске, так, чтобы они не били друг друга!

Каждый способ задается чисел 1, 2,... ., п — указываются номера горизонталей занятых полей на первой, второй,. .. , n-й вертикалях.

Но число Значит, ладьи можно расставить n! способами. При п = 8 получаем 8! = 1−2-3- .4.5.6−7.8 = 40 320 способов. Ответ 40 320.

Задача№ 2 В слове " мама" четыре буквы. Сколько перестановок можно совершить?:

Решение: Возможные перестановки: мама, маам, ммаа, амам, аамм, амма Чтобы понять, почему Так случилось, поставим в соответствие цифрам 1 и 2 букву «м», а цифрам 3 и 4 — букву «а». Тогда, например, перестановке 1234 будет соответствовать слово ммаа, а перестановке 1324 — слово мама. Но слово ммаа соответствует не только перестановке 1234, но и еще трем перестановкам: 2134, 1243 и 2143.

Пусть цифры 1 и 2 меняются местами, то в соответствующем слове меняются местами две буквы «м», а потому само слово остается неизменным. Неизменным оно остается и при взаимной перестановке цифр 3 и 4 — при этом в слове меняются местами две буквы «а» .

Всего получается 4 перестановки цифр, отвечающие одному и тому же слову.

Вот эти четверки перестановок:

1234 2134 1243 2143

1324 2314 1423 2413

1342 2341 1432 2431

3214 3124 4213 4123

3142 S241 4132 4231

3412 3421 4312 4321

Отсюда видно, что все множество из 24 перестановок цифр 1, 2, 3, 4 распадается на четверки, дающие одно и то же слово. Поэтому число различных слов равно 4!/4 = 6.

Сочетания

В комбинаторике сочетанием из n по k называется набор k элементов, выбранных из данных n элементов. Наборы, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми, этим сочетания отличаются от размещений. Число сочетаний из n элементов по k обозначаются Так, например, наборы (3-элементные сочетания, подмножества, k = 3) {2, 1, 3} и {3, 2, 1} 6-элементного множества {1, 2, 3, 4, 5, 6} (n = 6) являются одинаковыми (однако, как размещения были бы разными) и состоят из одних и тех же элементов {1,2,3}. В общем случае число, показывающее, сколькими способами можно выбрать k элементов из множества, содержащего n различных элементов, стоит на пересечении k-й диагонали и n-й строки треугольника Паскаля. если кортежи имеют одинаковый состав, то такие картежи называются эквивалентными. На сколько классов эквивалентности тогда разбивается при этом вся совокупность кортежей длины из n элементов Эти классы и будут называться сочетаниями с повторениями из n элементов по k, а их число обозначают .

Основные формулы:

Формула № 1

при

Доказательство:

Вычисляя число размещений, мы получим пары, отличающиеся порядком элементов, Из двух элементов можно составить две перестановки упорядоченных пар, поэтому, так как число размещений, умноженному на число перестановок внутри группы. Для любого количество размещений из n элементов поk можно вычислить по формуле. Действительно из n элементов можно составить групп по k элементов, а в каждой группе можно выполнить перестановок. Таким образом число всех размещений равно произведению числа группи числа перестановок внутри этих групп Отсюда следует что ч.т.д.

Формула № 2

Вывод формулы:

Формула № 3

Доказательство: Любой состав кортежа длины k из n элементов имеет вид, — неотрицательные целые числа, сумма которых равна k. Заменяя каждое из чисел k, соответствующим количеством единиц о разделяя пулями единицы, отвечающие различным числам, получаем кортеж из n — 1 нулей и k единиц. При этом каждому составу отвечает одна и только одна запись с помощью нулей и единиц, а каждая такая запись задает один и только один состав. Поэтому число различных составов равно числу перестановок с повторениями из n — 1 нулей и k единиц, т. е.

Некоторые свойства сочетаний:

Свойство№ 1

Вывод свойства

Свойство № 2

Вывод свойства (пользуясь формулой№ 2)

Свойство № 3

Доказательство (пользуясь формулами№ 2 и№ 3)

k-1, чтобы получить равенство Свойство № 4

Доказательство (пользуясь формулой № 2)

следовательно

Треугольник Паскаля — арифметический треугольник, образованный биномиальными коэффициентами. Назван в честь Блеза Паскаля. Если очертить треугольник Паскаля, то получится равнобедренный треугольник. В этом треугольнике на вершине и по бокам стоят единицы. Каждое число равно сумме двух, расположенных над ним чисел. Продолжать треугольник можно бесконечно. Строки треугольника симметричны относительно вертикальной оси^[1]. Имеет применение в теории вероятности и обладает занимательными свойствами.

Свойство треугольника:

Свойство№ 1

При составлении арифметического треугольника каждое число n-й строки участвует в образовании двух чисел (n + 1)-й строки — стоящего слева и стоящего справа от него. Поэтому если сложить числа (n + 1)-й строки через одно, то в полученную сумму войдут по одному разу все числа n-й строки. Складывать числа через одно можно двумя способами — начав с первого числа строки или начав со второго числа. В обоих случаях получится одна и та же сумма, равная сумме чисел в n-й строке. Следовательно Свойство№ 2 (следствие из свойства№ 1)

Из свойства№ 1следует, что сумма чисел (n + 1)-й строки вдвое больше суммы чисел n-й строки. Иными словами, при переходе к следующей строке арифметического треугольника сумма чисел в строке удваивается. Но в первой строке стоит только одно число 1, а потому для нее сумма равна 1. Поэтому в (n + 1)-й строке сумма чисел равна. следовательно:

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

Зaдача № 1Извесно, что имеется 13 983 810 различных способов заполнения карточки " Спортлото" , а выиграли номера 1, 2, 3, 4, 5,6. Сколько лиц выиграли в эту игру?

Решение: Угадать все: удастся только 1так как =1Запишем пары, на первом месте которых стоит один из 6 заменяемых номеров, а на втором — тот номер, которым он заменяется.

(1,7) ,(1,8).. .(1,49)

(2,7) ,(2,8).. .(2,49)

…

(6,7) ,(6,8). .. (6,49)

Пара (1, 7) обозначает, что вместо правильной комбинации {1, 2, 3, 4, 5, 6} участник лотереи зачеркнул номера {7, 2, 3, 4, 5, 6}, угадав лишь 5 номеров. Из таблицы видно, что число возможностей ошибиться один и только один раз равно 6?43 = 258. Значит, 258 участников угадают 5 номеров. Таким же образом мы определяем, что 4 номера угадают =13 545 человек — сначала надо из 6 верных номеров выбрать какие-нибудь 2 (это делается способами), а затем заменить их парой номеров, выбранной из 43 несчастливых номеров (а это можно сделать способами).Комбинируя каждый способ выбора первой пары с каждым способом выбора заменяющей ее пары, тогда совпадут 3 цифры уодна цифра учеловек и не одной цифры у .

Ответ угадает всё -1 угадает 5 цифр — 258, угадает 4цифры — 13 545, угадает 3- 246 820, угадают 2 цифры — человек, 1 цифру-, не угадает не одной.

Задача№ 2 Путник хочет попасть из пункта, А в пункт В кратчайшим путем, т. е. двигаясь все время или " слева направо" , или " снизу вверх" . Сколькими путями он может добраться из, А в В?

Решение. Ясно, что, каким бы путем ни шел путник, он пройдет через (n + k) перекрестков (считая точку А, но не считая точки В). На каждом перекрестке он может идти или направо, или вверх. В соответствии с этим все перекрестки делятся на два класса: «перекрестки направо» и «перекрестки вверх». При этом направо путник идет k раз, а вверх n раз. Значит, чтобы однозначно восстановить его путь, надо знать лишь те k случаев, когда он идет направо. Но их можно выбрать из общего числа (n + k) перекрестков способами. Поэтому число искомых путей равно

Обобщённые задачи

Задача № 1 Чемпионат России по шахматам проводится в один круг. Сколько играется партий, если участвуют 18 шахматистов?

Решение: В каждой партии разыгрывается одно очко. Предположим, что все партии закончатся вничью. Тогда каждый участник наберет 17:2 = 8,5 очков. А всего очков, а значит, и партий — 18· 8,5 = 153. Ответ: 153 партии

Задача №2 У людоеда в подвале томятся 25 пленников. а) Сколькими способами он может выбрать трех из них себе на завтрак, обед и ужин? Порядок важен. б) А сколько есть способов выбрать троих, чтобы отпустить на свободу?

Решение: а) На завтрак людоед может предпочесть любого из 25 человек, на обед — любого из 24 оставшихся, а на ужин — кого-то из 23 оставшихся счастливчиков. Всего получаем 25· 24·23 = 13 800 способов. б) Заметим, что в предыдущем пункте каждую тройку пленников мы посчитали 3· 2·1 = 6 раз. Поскольку теперь их порядок нам неважен, то ответом будет число 13 800: 6 = 2300. Ответ: а) 13 800 способами; б) 2300 способов

Задача №3Рота состоит из трех офицеров, шести сержантов и 60 рядовых. Сколькими способами можно выделить из них отряд, состоящий из офицера, двух сержантов и 20рядовых?

Решение: Двух сержантов из шести можно выбрать способами, а 20 рядовых из 60 — способами. Ответ: способами

Задача № 4 Сколькими способами можно разбить 10 человек на две баскетбольные команды по 5 человек в каждой?

Решение Первую команду можно выбрать способами. Этот выбор полностью определяет вторую команду. Однако при таком подсчете каждая пара команд А и В учитывается дважды: один раз, когда в качестве первой команды выбирается команда А, и второй, — когда в качестве первой команды выбирается команда В. Значит, полученный результат надо разделить пополам. Ответ: 7560 способами.

Задача № 5 а) Из класса, в котором учатся 30 человек, нужно выбрать двоих школьников для участия в математической олимпиаде. Сколькими способами это можно сделать? б) Сколькими способами можно выбрать команду из трех школьников в том же классе?

Решение

а) Первого ученика можно выбрать 30 способами, второго, независимо от выбора первого ученика, — 29 способами. При этом каждая пара учитывается дважды. Поэтому всего способов 30· 29: 2. б) Аналогично получаем 30· 29·28 вариантов последовательного выбора трех учеников. При этом каждая команда учтена 3! = 6 раз. Поэтому число способов выбрать команду равно Ответ: а) 435 способами; б) 4060 способами.

Задача № 6 В парламенте 30 депутатов. Каждые два из них либо дружат, либо враждуют, причем каждый дружит ровно с 6 другими. Каждые 3 депутата образуют комиссию. Найдите общее число комиссий, в которых все три члена попарно дружат или все трое попарно враждуют.

Решение множество факториал комбинаторика размещение

Обозначим депутатов точками. Соединим точки красным отрезком, если соответствующие депутаты дружат, и синим — если враждуют. Нам нужно найти число одноцветных треугольников с вершинами в данных точках. Число всех треугольников равно Подсчитаем сначала число не одноцветных треугольников. В каждом таком треугольнике ровно 2 угла, в которых сходятся красный и синий отрезки (назовем такие углы разноцветными). В одноцветных треугольниках разноцветных углов нет. В каждой вершине по условию сходятся 6 красных и 23 синих отрезка, т. е. имеется 6· 23 = 138 разноцветных углов с фиксированной вершиной. Общее количество не одноцветных треугольников, таким образом, равно 138· 30: 2 = 2070. А число одноцветных треугольников равно 4060 — 2070 = 1990. Ответ:1990 комиссий.

Задача№ 7 Сколькими способами можно выбрать четырех человек на четыре различные должности, если имеется девять кандидатов на эти должности?

Решение

Ответ 3024 способами.

Задача № 8 В школе изучают 2n предметов. Все ученики учатся на 4 и 5. Никакие два ученика не учатся одинаково, ни про каких двух нельзя сказать, что один из них учится лучше другого. Доказать, что число учеников в школе не больше . (Мы считаем, что ученик p учится лучше ученика q, если у p оценки по всем предметам не ниже, чем у q, а по некоторым предметам — выше.)

Решение Немного изменим условие: пусть в школе учатся 22n учеников со всевозможными наборами пятерок и четверок. Выберем из них максимальную группу A попарно несравнимых учеников (в смысле условия задачи). Мы докажем, что эта группа состоит в точности из всех учеников, которые имеют ровно n пятерок (их ровно). Отсюда, очевидно, следует утверждение исходной задачи. Выделим в A подгруппу B, состоящую из учеников с наименьшим числом k пятерок. Пусть k < n. Рассмотрим группу C всех учеников, каждый из которых имеет пятерки ровно по k + 1 предмету, причем он (учится) лучше одного из учеников группы B. Очевидно ни один из них не входит в A, и мы можем заменить группу B на группу C. Докажем, что число c учеников группы C больше, чем число b учеников группы B. Пусть каждый ученик группы B пожмет руку всем ученикам из C, которые лучше него (таких учеников ровно 2n — k). Всего будет сделано (2n — k) b > (k + 1) b рукопожатий. Действительно, 2k + 1? 2(n — 1) + 1 < 2n. С другой стороны, каждый ученик из C пожал руки не более, чем k + 1 ученику, следовательно, (k + 1) c > (k + 1) b, то есть c > b. Итак, заменив группу B на группу C, мы увеличим группу A, что противоречит ее максимальности. Противоречие доказывает, что k? n. Симметричным образом, доказывается, что в A нет учеников с числом пятерок, большим n. Следовательно, A состоит только из учеников с n пятерками, и (снова в силу максимальности) туда должны попасть все такие ученики.

Задача № 9 Имеется 20 человек — 10 юношей и 10 девушек. Сколько существует способов составить компанию, в которой было бы одинаковое число юношей и девушек?

Решение Каждой такой компании сопоставьте множество из 10 человек, в которое входят все девушки, вошедшие в компанию, и все юноши, не вошедшие в нее. Пусть имеется некоторая компания из k юношей и k девушек. Поставим ей в соответствие множество из 10 человек, в которое включим k девушек, вошедших в компанию, и 10 — k юношей, не вошедших в нее. Установленное соответствие, очевидно, является взаимно-однозначным. Таким образом, искомое число равно числу способов выбрать 10 человек из 20-ти. Ответ способов.

Задача № 10 Международная комиссия состоит из 9 человек. Материалы комиссии хранятся в сейфе. Сколько замков должен иметь сейф, сколько ключей для них нужно изготовить и как их разделить между членами комиссии, чтобы доступ к сейфу был возможен тогда и только тогда, когда соберутся не менее 6 членов комиссии?

Решение По условию, любые 5 человек сейф открыть не могут. Значит, у них нет ключа от некоторого замка. При этом любой другой член комиссии должен этот ключ иметь. Поэтому нужно поставить замков. 4 ключа от каждого замка отдаются некоторой четверке членов комиссии, причем разные ключи раздаются разным четверкам. Ответ126 замков, по 4 ключа к каждому замку

1.Виленкин Н. Я. «Популярная комбинаторика». — М.: Наука, 1969. — 328с.

2. Раизер Г. Дж. «Комбинаторная математика»

3. Цыганов Ш. «Комбинаторика от, А до Я» Математика. — 2001

4. Семеновых А. «Комбинаторика» //Математика. — 2004

5. Дихтярь М., Эргле Е. «Исторические комбинаторные задачи и комбинаторные модели» //Математика. — 2007.

6.С. М. Никольский, М. К. Потапов учебник 10 класса «Алгебра и начало анализа» — 2009

7.http://combinatorica.narod.ru/second.htm

8. Гнеденко Б. В., Журбенко, И. Г. Теория вероятностей и комбинаторика //Математика в школе. — 2007