Формула нахождения всех возможных вариантов. Элементы комбинаторики

Большинство формул комбинаторики используют понятие факториала. Термин «факториал» произошел от латинского слова factor («производящий») и обозначает созвучное действие - произведение.

Определение 5.1. Произведение п первых последовательных натуральных чисел называется п-факториал.

Обозначение: п.

Единственная формула для вычисления факториалов, которая будет использоваться, выражает определение факториалов:

Например: 4! = 1 2 3 4 = 24.

Особо оговариваются частные случаи значения факториала: 0! = 1 и 1! = 1.

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

Например: (3 - 2)! = 1! = 1. Ошибочно выполнять действия в ином порядке: 3! - 2! = 1 - 2*3-1-2 = 6- 2 = 4. Как видим 4 Ф 1 и, соответственно, (3 - 2)! Ф 3! - 2!.

Сокращать факториалы в дробном выражении можно, но тоже осторожно.

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

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

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

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

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

Пример 5.5

В семье четыре ребенка: Аия, Боря, Ваня, Галя. Они постоянно спорят между собой за лучшее место в машине, в кино, за столом. Родители, устав от разборок, постановили, что каждый следующий раз дети садятся по-разному. Через сколько раз придется повторить рассадку?

Решение

Пока детей было двое, то возможны были только две комбинации: А - Б, Б - А.

Когда подрос Ваня, его можно было разместить на трех местах но отношению к каждой из этих комбинаций: по бокам и между старшими детьми.

Для комбинации А - Б возможны три варианта: В - А - Б, А - Б - В, А-В - Б, и для комбинации Б - Л есть еще три варианта: В - Б - Л, Б - Л - В, Б - В - Л.

Всего два раза по три новые комбинации, что соответствует действию умножения 2 3.

Когда детей стало четыре, то по отношению к каждой из предыдущих (2 *3) = = 6 комбинаций четвертого ребенка можно было опять-таки разместить по бокам или на одном из двух мест между старшими тремя детьми, т.е. на одном из четырех мест. Например, для комбинации В - А - Б получится четыре новые комбинации:

Таким образом, вместо каждой из предыдущих (2 3) комбинаций получится четыре новые комбинации. Всего надо взять (2 - 3) раз по 4, что соответствует действию умножения: (2 3) 4, или можно записать 1 *2-3*4 = 4!.

Ответ : 24 раза.

Если же в описанной в примере семье появится пятый ребенок, то его можно уже будет посадить на одно из пяти мест: два но бокам и на три пропуска между старшими детьми, т.е. получится (1 *2*3* 4) *5 = 5! комбинаций и т.д.

В приведенном примере шла речь о том, как по-разному можно расположить п элементов, и получили ответ - п комбинаций. Такие комбинации называются перестановками.

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

Обозначение: Р п.

Утверждение 5.1. Число перестановок определяется по формуле Р п = п.

Теперь, после обоснования подсчета числа перестановок, естественно принять, что 0! = 1 и 1! = 1, поскольку одноэлементное и пустое множество можно представить (упорядочивай, не упорядочивай) только в одном виде.

Определение 5.3. Упорядоченные m-элементные подмножества данного множества из п элементов называются размещениями из п элементов по т.

Обозначение: А™, где п > т.

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

Пример 5.6

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

Решение

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

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

Ответ : 120 чисел.

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

Утверждение 5.2. Число размещений определяется по формулам

Обоснование. В первой формуле расписаны «почти 77!», но без первых сомножителей из (77-777)!. Во второй формуле из факториала убраны первые сомножители из (77-777)! при помощи деления.

Замечание. Л" = Р п, если 77 = 777.

Если не повторять каждый раз все рассуждения, а пользоваться готовой формулой (5.1), то решение примера 5.6 выглядит так: число элементов в исходном множестве п = 6, /7? = 3, упорядоченность записи элементов в подмножестве - важна. Тогда

Рассмотрим другую, но очень похожую задачу: сколько различных произведений из трех различных множителей можно составить, взяв в качестве множителей числа 1, 2, 3, 4, 5, 7?

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

Определение 5.4. Неупорядоченное т/7-элементное подмножество данного множества из п элементов называется сочетанием из п элементов

ПО 777.

Обозначение: С" 7 , где п > т.

Утверждение 5.3. Число сочетаний определяется по формуле

Обоснование. Неупорядоченных подмножеств из т элементов будет меньше, чем упорядоченных т -элементных подмножеств того же множества, во столько раз, сколько существует перестановок внутри каждого набора из т зафиксированных элементов. Уменьшение в несколько раз соответствует действию деления, поэтому

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

наличие совпадения числа элементов в множестве и числа элементов в подмножестве;
отличие подмножеств друг от друга по порядку записи элементов.

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

Таблица 5.2

Выбор формул для подсчета комбинаций без повторений

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

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

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

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

Представляем, как ведущий классного часа предлагает выбрать старосту класса, ответственного за дежурство по школе, за стенгазету, за организацию турпоходов, за культурную программу, подготовку всевозможных предметных недель и записывает на доске много всяких должностей, чтобы заинтересовать учащихся выбором наиболее адекватной должности, подавив позицию «лишь бы не меня». После опубликования должностей ведущий начинает собирать предложения, учитывает самоотводы и переходы на более предпочтительные должности. В результате на доске может оказаться несколько столбцов - списков фамилий, некоторые из которых будут отличаться не самими фамилиями, а лишь порядком их записи в соответствующем столбце. Далее начинается голосование, которое может собрать разное количество голосов под списками актива класса, отличающимися друг от друга только по порядку записи одних и тех же фамилий, но на разные должности. Разное количество голосов убеждает, что это были разные выборки, разные комбинации, пусть и из одинаковых фамилий, но по-разному упорядоченных. В связи с этим лучше ставить вопрос об упорядоченности подмножеств в алгоритме решения комбинаторных задач в следующей форме: «Могут ли отличаться подмножества друг от друга не только по содержанию, но и по порядку записи элементов?»

Определение требования упорядоченности подмножеств смущает студентов или, наоборот, преждевременно радует еще и тогда, когда в тексте фигурирует слово «порядок». Например, учитель берет коробку, в которой лежат пятнадцать карточек с буквами. Он достает из коробки по четыре карточки и раскладывает их ряд в алфавитном порядке. Требуется ли в данном сюжете упорядоченность выбираемых подмножеств? Обычно обязательно среди ответов присутствует радостное «Да!». Написано же, что есть алфавитный порядок в выбираемых четверках. Здесь выручает приведенная формулировка вопроса об упорядоченности. Среди выбранных четверок не будет наборов из одинаковых букв, но расположенных в разном порядке. Значит, подмножества не будут отличаться друг от друга по порядку записи элементов в них. Наборов будет столько же, сколько было бы, если бы их не выкладывали в ряд, а раскладывали бы по мешочкам, внутри которых между элементами порядка не будет. Такое количественное осмысление вопроса об упорядоченности элементов в комбинациях очень важно для комбинаторики.

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

Пример 5.7

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

Решение

Этап 1. Краткая словесная (вербальная) обработка: например, «выбрать три студента из десяти студентов».

Этап 2. Полная запись условия на языке математических символов.

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

Дано: п =...; т =...;

порядок: да /нет.

Для примера 5.8 эта заготовка заполнится следующим образом:

Дано: п = 10; т = 3;

порядок: нет.

На основе этой заготовки и табл. 5.2 выбор необходимой для решения задачи математической модели выполняется легко.

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

«Выбрать три студента из десяти студентов».

Дано: п - 10; т = 3;

порядок: нет.

Ответ: 120 комбинаций надо рассмотреть, чтобы сделать полный перебор вариантов.

Для более продвинутых пользователей табл. 5.2 можно расширить, добавив еще один параметр - повторное использование элементов в подмножестве (табл. 5.3).

Таблица 53

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

Комбинации	Подмножества могут отличаться но порядку элементов?	Возможно повторное использование элементов в подмножествах?
Перестановки			Р п = п
Размещения			а;:,=
Сочетания			ш (п-т)т!
Размещения с повторениями			А„ = и""
Сочетания с повторениями			W _ (//2-1-/7-1)! " ~т!-(л- 1)!
Перестановки с повторениями		k Jповторов 1- го элемента, k 2 повторов 2- го элемента, k n повторов /7-го элемента.	Pn(k t,&2,= п V- k 2 ! *„!

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

Пример 5.8

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

Решение

Этап 1: «Выбрать шесть букв из шести букв».

Дано: п = 6; т = 6;

порядок: да;

повтор: да, к а = 3, к г = 2, k ? = 1

Поскольку на три вопроса таблицы ответ «да», то выбираем математическую модель с использованием подсчета числа перестановок с повторениями. Элемент «а» повторяется в исходном множестве три раза, а значит, и в шестиэлементных комбинациях повторно будет использоваться три раза. Аналогично элемент «р» имеет количество повторов, равное двум. Далее - самое простое. Поскольку математическая модель выбрана, остается правильно подставить значения неизвестных в формулу и выполнить необходимые вычисления:

Ответ : 60.

Вид формулы для подсчета числа перестановок с повторениями легко обосновать. Если бы все шесть букв были разные, то количество перестановок равнялось бы 6!. Но если в подмножествах могут фигурировать, например, три одинаковые буквы, то неважно, какая из этих одинаковых букв на каком месте, отведенном для этих букв, находится. А это значит, что количество перестановок с повторениями будет меньше количества бес- повторных перестановок во столько раз, сколько перестановок одинаковых элементов можно сделать, т.е. в /^-факториал раз. Поэтому в формуле числа перестановок с повторениями появился знаменатель в отличие от формулы бесповторных перестановок.

Цель занятия: уметь применять основные формулы комбинаторики и знать условия применения этих формул; знать свойства биномиальных коэффициентов и уметь определять разложение бинома при конкретных значениях n.

План занятия:

1. Число размещений.

2. Число перестановок.

3. Число сочетаний.

4. Повторения.

5. Бином Ньютона. Треугольник Паскаля.

Методические указания по изучению темы

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

Комбинаторика – область математики, в которой изучаются вопросы о том, сколько различных комбинаций, подчиненных тем или иным условиям, можно составить из элементов, принадлежащих данному множеству. Термин «комбинаторика» происходит от латинского слова combina – сочетать, соединять.

Пусть есть некоторое множество из n элементов: x 1, x 2, x 3, …, x n .

Из этого множества можно образовать различные подмножества, то есть выборки, каждая из которых содержит m элементов (0 ≤ m ≤ n). Различают упорядоченные выборки (размещения), перестановки и неупорядоченные выборки (сочетания).

Размещения

Размещениями n различных элементов по m элементов, которые отличаются либо составом элементов, либо их порядком.

Число размещений из n элементов по m элементов обозначают (А – первая буква французского слова arrangement, что означает размещение, приведение в порядок) и вычисляют по формуле:

Понятие факториала

Произведение n натуральных чисел от 1 до n обозначается символом n ! (n факториал), то есть

Например, 2!=

5!=

Заметим, что удобно рассчитывать 0!, полагая по определению, 0!=1.

Примеры:

Из последних двух формул следует, что

Пример.

В однокруговом турнире по футболу участвуют 8 команд. Сколько существует вариантов призовой тройки?

Решение : Так как порядок команд в призовой тройке важен, то мы имеем дело с размещениями. Тогда

(вариантов).

Пример.

Сколькими способами можно выбрать три лица на три различные должности из десяти кандидатов?

Решение:

(способов).

Пример.

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

(телефонных номеров).

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

Перестановками называют комбинации, состоящие из одних и тех же n различных элементов и отличающиеся только порядком их расположения.

Число всех возможных перестановок из n элементов обозначают P n (P – первая буква французского слова permutation, что означает перестановка) и вычисляют по формуле:

Пример.

В финальном забеге на 100 метров участвуют 8 спортсменов. Сколько существует вариантов протокола забега?

Решение:

В данном случае речь идёт обо всех перестановках из 8 элементов. Тогда (вариантов)

Пример.

Сколькими различными способами могут разместиться на скамейке10 человек?

Решение:

(способов)

Пример.

Сколькими способами можно разместить 7 лиц за столом, на котором поставлено 7 столовых приборов?

Решение:

(способов).

Сочетания

Сочетаниями называют комбинации, составленные из n различных элементов по m элементов, которые отличаются хотя бы одним элементом.

Число сочетаний вычисляют по формуле: (С - первая буква французского слова combinasion).

Пример.

Сколькими способами можно выбрать три лица на три одинаковые должности из десяти кандидатов?

Решение :

(способов).

Пример.

Сколькими способами можно выбрать три детали из ящика, содержащего 15 деталей?

Решение:

(способов).

Другой вид формул числа размещений и числа сочетаний

; , то есть .

Свойства числа сочетаний:

При решении задач комбинаторики используют следующие правила:

Правило суммы. Если некоторый объект А может быть выбран из совокупности объектов n способами, а другой объект В – k способами, то объект «либо А, либо В» можно выбрать n+k способами.

Правило произведения. Если некоторый объект А может быть выбран из совокупности объектов n способами и после каждого такого выбора другой объект В – k способами, то пара объектов (А, В) в указанном порядке может быть выбрана n×k способами.

Если некоторые элементы повторяются, то в этом случае комбинации с повторениями вычисляют по другим формулам.

Размещения с повторениями

Число размещений по m элементов с повторениями из n различных элементов равно n m ,то есть

Пример.

Из цифр 1,2,3,4,5 можно составить 5 3 =125 трехзначных чисел, если в одном и том же числе могут попадаться и одинаковые цифры.

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

Если среди n элементов есть n 1 элементов одного вида, n 2 элементов другого вида и т.д., то число перестановок с повторениями

где

Пример.

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

Решение:

Сочетания с повторениями

Число сочетаний с повторениями из n различных элементов по m элементов равно числу сочетаний без повторений из (n +m -1) различных элементов по m элементов:

Пример.

Найти число сочетаний с повторениями из четырех элементов a , b , c , d по 3 элемента.

Решение:

Искомое число будет

Бином Ньютона

Для произвольного положительного целого числа n справедлива следующая формула:

Это бином Ньютона. Коэффициенты называются биномиальными коэффициентами.

При n = 2 получим формулу ;

При n = 3 получим формулу .

Пример. Определить разложение при n=4.

Решение:

Биномиальные коэффициенты обладают рядом свойств:

2. ;

Рассмотрим следующий треугольник:

………………………….

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

……………………….

Это треугольник Паскаля. Он позволяет быстро найти значения биномиальных коэффициентов.

В русскоязычной литературе перестановки, составленные из n различных элементов выбором по m элементов, которые отличаются либо составом элементов, либо их порядком, обычно называют размещениями, а под перестановками понимают всю совокупность комбинаций, состоящих из одних и тех же n различных элементов и отличающихся только порядком их расположения. В этом смысле число всех возможных перестановок для множества из n различных элементов считается по формуле факториала Pn = n! или в Excel «=ФАКТР(N)» (см. рис. № 1)

Например, если ввести «=ПЕРЕСТ(3;2)», получим 6. Это 6 комбинации: (1,2), (2,1), (1,3), (3,1), (2,3), (3,2).

А вот встроенная функция «=ЧИСЛКОМБ(N;K)» выдает комбинаторную формулу, называемую у нас «Число сочетаний». В русскоязычной литературе так именуют перестановки, составленные из n различных элементов выбором по m элементов, которые отличаются только составом элементов, а порядок их выбора безразличен (см. рис, №4)

При использовании встроенных функций пользуйтесь «Справкой по этой функции». Например:

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

1. Вычислить:

2. Вычислить:

3. Вычислить:

4. Найти n , если 5С n 3 =

5. Найти n , если

6. Найти n , если

7. Найти n , если

8. Найти n , если , k n

9. Решить уравнение

10. Решить систему

11. Сколько можно составить сигналов из 6 флажков различного цвета, взятых по 2?

12. Сколькими способами можно выбрать четыре лица на четыре различные должности из девяти кандидатов?

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

14. В классе 10 учебных предметов и 5 разных уроков в день. Сколькими способами могут быть распределены уроки в один день?

15. Сколько можно записать четырёхзначных чисел, используя без повторения все 10 цифр?

16. Фирма производит выбор из девяти кандидатов на три различные должности. Сколько существует способов такого выбора?

17. В восьмом классе изучается 15 предметов. Сколькими способами можно составить расписание на среду, если известно, что в этот день должно быть 6 уроков?

18. В высшей лиге чемпионата страны по футболу 16 команд. Борьба идет за золотые, серебряные и бронзовые медали. Сколькими способами медали могут быть распределены между командами?

19. Сколькими способами можно разместить 9 лиц за столом, на котором поставлено 9 приборов?

20. На собрании выступят 6 ораторов. Сколькими способами их фамилии можно расположить в списке?

21. Сколько трехзначных чисел можно составить из цифр 1, 2, 3, если каждая цифра входит в изображение числа только один раз?

22. Сколькими различными способами можно расставить 10 различных книг на полке, чтобы определённые 4 книги стояли рядом?

23. В однокруговом турнире по футболу участвуют 8 команд. Сколько всего матчей будет сыграно?

24. Из 25 студентов нужно выбрать трех делегатов на конференцию. Сколькими способами это можно сделать?

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

26. В колоде 36 карт, из них 4 туза. Сколькими способами можно извлечь 6 карт так, чтобы среди них было 2 туза?

27. Комплексная бригада состоит из двух маляров, трёх штукатуров и одного столяра. Сколько различных бригад можно создать из рабочего коллектива, в котором 15 маляров, 10 штукатуров и 5 столяров?

28. В отборочном турнире за 3 путёвки на чемпионат мира участвуют 10 команд. Сколько существует вариантов «счастливой тройки»?

29. Из 12 человек выбирают четверых для назначения на 4 одинаковые должности. Сколькими способами можно сделать такой выбор?

30. Сколькими различными способами можно составить разведывательную группу из 3-х солдат и одного командира, если имеется 12 солдат и 3 командира?

31. На плоскости дано n точек, из которых никакие три не лежат на одной прямой. Найти число прямых, которые можно получить, соединяя точки попарно.

32. Буквы азбуки Морзе образуются как последовательность точек и тире. Сколько различных букв можно образовать, если использовать 5 символов?

33. Сколько существует различных семизначных телефонных номеров?

34. Пусть буквы некоторой азбуки образуются как последовательность точек, тире и пробелов. Сколько различных букв можно образовать, если использовать 5 символов?

35. При игре в бридж между четырьмя игроками распределяется колода карт в 52 листа по 13 карт каждому игроку. Сколько существует различных способов раздать карты?

36. В почтовом отделении продаются открытки пяти видов. Определить число способов покупки семи открыток.

37. Два коллекционера обмениваются марками. Найти число способов обмена, если первый коллекционер обменивает 3 марки, а второй – 6 марок. (Обмен происходит по одной марке).

38. У одного студента 6 книг по математике, а у другого – 5. Сколькими способами они могут обменять 2 книги одного на 2 книги другого?

39. Сколько различных перестановок букв можно сделать в словах: «замок», «ротор», «обороноспособность», «колокол», «семинар»?

40. Сколькими различными способами можно разместить в 9 клетках следующие 9 букв: а, а, а, б, б, б, в, в, в?

41. В автомашине 6 мест. Сколькими способами 6 человек могут сесть в эту машину, если занять место водителя могут только двое из них?

42. Сколькими способами из колоды в 52 карты можно извлечь 6 карт, содержащих туза и короля одной масти?

43. Определить разложение при n=5.

44. Определить разложение при n=8.

45. Найти член разложения , не содержащий x (то есть содержащий x в нулевой степени).

46. Найти шестой член разложения , если биномиальный коэффициент третьего от конца члена равен 45.

47. В разложении коэффициент третьего члена на 44 больше коэффициента второго члена. Найти свободный член, то есть член разложения, не зависящий от x (членом, не зависящим от x, будет тот, который содержит x в нулевой степени).

48. В разложении бинома найти члены, не содержащие иррациональности.

49. Найти номер того члена разложения , который содержит a и b в одинаковых степенях.

Практическое занятие №2

(интерактивное занятие в малых группах)

Булевы функции

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

План занятия:

1. Основные операции

2. Булевы функции от n переменных

3. Основные эквивалентности

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

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

Значительную роль комбинаторные методы играют и в чисто математических вопросах — теории групп и их представлений, изучении основ геометрии, неассоциативных алгебр и др.

Пример комбинаторной задачи. Сколько трёхзначных чисел можно составить из цифр 0, 2, 4, 6, 8, используя в записи числа каждую из них не более одного раза?

I способ. Постараемся выписать все такие числа. На первом месте может стоять любая цифра кроме 0. Например, 2. На втором месте любая цифра из 0, 4, 6 и 8. Пусть 0. Тогда в качестве третьей цифры можно выбрать любую из 4, 6, 8. Получаем три числа

Вместо 0 на второе место можно было поставить 4, тогда третье цифрой можно записать или 0, или 6, или 8:

Рассуждая аналогично, получаем ещё две тройки трёхзначных чисел с цифрой 2 на первом месте:

Других, кроме выписанных 12-ти, трёхзначных чисел с цифрой 2 на первом месте, и удовлетворяющих условию, нет.

Если на первом месте записать цифру 4, а остальные выбирать из цифр 0, 2, 6, 8, то получим ещё 12 чисел:

По столько же трёхзначных чисел можно составить с цифрой 6 на первом месте и цифрой 8 на первом месте. Значит, искомое количество:

Вот эти числа:

204, 206, 208, 240, 246, 248, 260, 264, 268, 280, 284, 286;

402, 406, 408, 420, 426, 428, 460, 462, 468, 480, 482, 486;

602, 604, 608, 620, 624, 628, 640, 642, 648, 680, 682, 684;

802, 804, 806, 820, 824, 826, 840, 842, 846, 860, 862, 864.

Ответ: 48. ◄

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

Правила сложения и умножения

Комбинаторное правило сложения (правило "или") — одно из основных правил комбинаторики, утверждающее, что, если имеется n элементов и элемент A 1 можно выбрать m 1 способами, элемент A 2 можно выбрать m 2 A n можно выбрать m n способами, то выбрать или A 1 , или A 2 , или, и так далее, A n можно

m 1 + m 2 + ... + m n

способами.

Например, выбрать подарок ребёнку из 9 машинок, 7 плюшевых медведей и 3 железных дорог можно

способами.

Ответ: 19. ◄

Правило умножения (правило "и") — ещё одно из важных правил комбинаторики. Согласно ему, если элемент A 1 можно выбрать m 1 способами, элемент A 2 можно выбрать m 2 способами и так далее, элемент A n можно выбрать m n способами, то набор элементов (A 1 , A 2 , ... , A n ) можно выбрать

m 1 · m 2 · ... · m n

способами.

Например.

1) Выбрать ребёнку в подарок машинку, плюшевого медведя и железную дорогу, выбирая из 9 машинок, 7 плюшевых медведей и 3 железных дорог, можно

9 · 7 · 3 = 189

способами.

Ответ: 189.

2) Воспользуемся правилом умножения для решения задачи, уже рассмотренной выше: Сколько трёхзначных чисел можно составить из цифр 0, 2, 4, 6, 8, используя в записи числа каждую из них не более одного раза?

II способ.

0 не может стоять первым, значит первую цифру нужно выбрать из 2, 4, 6, 8 — 4 способа;

второй цифрой может быть любая из четырёх оставшихся — 4 способа;

третью цифру можно выбрать среди трёх оставшихся — 3 способа.

Итак, искомое количество трёхзначных чисел:

4 · 4 · 3 = 48.

Ответ: 48. ◄

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

Множество из n элементов называется упорядоченным , если каждому его элементу поставлено в соответствие натуральное число от 1 до n .

Перестановкой из n элементов называется любое упорядоченное множество из n элементов.

Например, из 4 элементов ♦ ♣ ♠ можно составить следующие 24 перестановки:

♦ ♣ ♠	♦ ♣ ♠	♣ ♦ ♠	♠ ♦ ♣
♦ ♠ ♣	♦ ♠ ♣	♣ ♦ ♠	♠ ♦ ♣
♦ ♣ ♠	♣ ♦ ♠	♣ ♦ ♠	♠ ♦ ♣
♦ ♣ ♠	♣ ♠ ♦	♣ ♠ ♦	♠ ♣ ♦
♦ ♠ ♣	♠ ♦ ♣	♣ ♠ ♦	♠ ♣ ♦
♦ ♠ ♣	♠ ♣ ♦	♣ ♠ ♦	♠ ♣ ♦

◄

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

P 1 = 1; P 2 = 2; P 3 = 6; P 4 = 24.

Вообще, число всевозможных перестановок из n элементов равно произведению всех натуральных чисел от 1 до n , то есть n ! (читается "эн факториал"):

P n = 1 · 2 · 3 · ... · (n - 1 ) · n = n !.

Для P n справедлива рекуррентная формула:

P n = n · P n - 1 .

Значение факториала определено не только для натуральных чисел, но и для 0:

0! = 1 .

Таблица факториалов целых чисел от 0 до 10
n		1	2	3	4	5	6	7	8	9	10
n !	1	1	2	6	24	120	720	5 040	40 320	362 880	3 628 800

Например, сколькими способами 5 мальчиков и 5 девочек могут занять в театре места в одном ряду с 1-го по 10-е место, если никакие два мальчика и никакие две девочки не сидят рядом?

Возможны два случая с одинаковым количеством способов: 1) мальчики — на нечётных местах, девочки на чётных и 2) наоборот.

Рассмотрим первый случай. Мальчики по нечётным местам могут сесть

P 5 = 120

способами. Столько способов и для девочек на чётных местах. Согласно правилу умножения, мальчики — на нечётных местах, девочки на чётных могут расположиться

120 · 120 = 14 400

способами. Значит, всего способов

14 400 + 14 400 = 28 800.

Ответ: 28 800. ◄

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

Перестановкой с повторениями из n элементов, среди которых k разных, при этом насчитывается n 1 неразличимых элементов первого типа, n 2 неразличимых элементов второго типа и так далее, n k неразличимых элементов k -го типа (где n 1 + n 2 + … + n k = n ), называется любое расположение этих элементов по n различным местам.

Число перестановок с повторениями длины n из k разных элементов, взятых соответственно по n 1 , n 2 , …, n k раз каждый обозначается и вычисляется следующим образом:$$P_{n_1,n_2, ... , n_k}=\frac{n!}{n_1!n_2! ... n_k!}~.$$

Например, сколько различных десятизначных чисел можно составить из цифр: 1, 2, 2, 3, 3, 3, 4, 4, 4, 4?

В данном случае: n = 10, n 1 = 1, n 2 = 2, n 3 = 3, n 4 = 4,$$P_{1, 2, 3, 4}=\frac{10!}{1!2! 3! 4!}=\frac{10!}{1!2! 3! 4!}=12~600.$$

Ответ: 12 600. ◄

Размещения

Размещением из n элементов по m (m ≤ n) m элементов, взятых в определённом порядке из данных n элементов.

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

Например, составим все размещения из четырёх элементов A, B, C, D по два элемента:

A B; A C;A D;

B A; B C; B D;

C A; C В; C D;

D A; D В; D C.

◄

Число всех размещений из n элементов по m обозначают $A_n^m$ (читается: "А из n по m ") и вычисляется по любой из формул:$$A_n^m=n\cdot (n-1)\cdot (n-2)\cdot ...\cdot (n-m+1)\\A_n^m=\frac{n!}{(n-m)!}$$

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

1) Воспользуемся понятием размещений из n элементов по m для решения задачи, уже дважды рассмотренной ранее: Сколько трёхзначных чисел можно составить из цифр 0, 2, 4, 6, 8, используя в записи числа каждую из них не более одного раза?

II I способ.

Первую цифру можно выбрать четырьмя способами из набора 2, 4, 6, 8. В каждом из этих случаев количество пар второй и третей цифры равно числу размещений из 4 оставшихся цифр по 2. Значит искомое количество трёхзначных чисел равно:$$4\cdot A_4^2=4\cdot \frac{4!}{(4-2)!}=4\cdot \frac{4!}{2!}=4\cdot (3\cdot 4)=48.$$Ответ: 48.

2) Для полёта в космос необходимо укомплектовать экипаж из шести человек. В него должны входить: командир корабля, первый и второй его помощники, два бортинженера, один из которых старший, и один врач. Командный состав выбирается из 20 лётчиков, бортинженеры — из 15 специалистов, а врач — из 5 медиков. Сколькими способами можно укомплектовать экипаж?

Поскольку в выборе командного состава важен порядок, то командира и двух его помощников можно выбрать $A_{20}^3$ способами. Порядок бортинженеров тоже важен, значит, для их выбора существует $A_{15}^2$ способов. Врач всего один, для его выбора существует 5 способов. Воспользуемся комбинаторным правилом умножения и найдём количество возможных экипажей корабля:$$A_{20}^3\cdot A_{15}^2\cdot 5=\frac{20!}{17!}\cdot \frac{15!}{13!}\cdot 5=(18\cdot 19\cdot 20)\cdot (14\cdot 15)\cdot 5=7~182~000.$$Ответ: 7 182 000. ◄

Понятно, что, если m = n , то$$A_n^m=A_n^n=P_n=n!.$$

Справедливо также, что, если m = n - 1 , то$$A_n^{n-1}=A_n^n=P_n=n!.$$

Размещения с повторениями

Помимо обычных размещений бывают и размещения с повторениями или выборки с возвращением .

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

Размещения с повторениями обозначаются $\overline{A}_n^m$ и, согласно правилу умножения, вычисляются по формуле$$\overline{A}_n^m=n^m.$$Заметим, что здесь допустим случай, когда m > n , то есть выбранных объектов больше, чем их всего имеется. Это неудивительно: каждый объект после "использования" возвращается обратно и может быть использован повторно.

Например, количество вариантов шестизначного пароля, в котором каждый знак является цифрой от 0 до 9 или буквой латинского алфавита (одна и та же строчная и прописная буква — один символ) и может повторяться, равно:$$\overline{A}_{10+26}^6=\overline{A}_{36}^6=36^6=2~176~782~336.$$Если же строчные и прописные буквы считаются различными символами (как это обычно и бывает), то количество возможных паролей становится ещё более колоссальным:$$\overline{A}_{10+26+26}^6=\overline{A}_{62}^6=62^6=56~800~235~584.$$

◄

Сочетания

Сочетанием из n элементов по m (m ≤ n) называется любое множество, состоящее из m элементов, выбранных из данных n элементов.

В отличии от размещений в сочетаниях не имеет значения, в каком порядке указаны элементы. Два сочетания из n элементов по m считаются различными, если они различаются хотя бы одним элементом.

Например, составим все сочетания из четырёх элементов A, B, C, D по два элемента:

A B; A C;A D;

B C; B D;

C D .

◄

Число всех сочетаний из n элементов по m обозначают $C_n^m$ (читается: "C из n по m ") и вычисляется по любой из формул:$$C_n^m=\frac{A_n^m}{P_m}$$$$C_n^m=\frac{n\cdot (n-1)\cdot (n-2)~\cdot~ ...~\cdot~ (n-m+1)}{1\cdot2\cdot3~\cdot~...~\cdot ~m}$$$$C_n^m=\frac{n!}{m!\cdot (n-m)!}.$$

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

1) Бригада, занимающаяся ремонтом школы, состоит из 12 маляров и 5 плотников. Из них для ремонта физкультурного зала надо выделить 4 маляров и 2 плотников. Сколькими способами можно это сделать?

Так как порядок маляров в каждой выбранной четвёрке и порядок плотников в каждой выбранной паре не имеет значения, то, согласно комбинаторному правилу умножения, искомое количество способов равно:$$C_{12}^4 \cdot C_5^2 =\frac{12!}{4!\cdot 8!}\cdot \frac{5!}{2!\cdot 3!}=\frac{9\cdot10\cdot11\cdot12}{1\cdot2\cdot3\cdot4}\cdot \frac{4\cdot5}{1\cdot 2}=4~950.$$Ответ: 4 950. ◄

2) В классе обучаются 30 учащихся, среди которых 13 мальчиков и 17 девочек. Сколькими способами можно сформировать команду из 7 учащихся этого класса, если в неё должна входить хотя бы одна девочка?

Количество всех возможных команд по 7 человек из класса равно $C_{30}^7$. Количество команд в которых только мальчики — $C_{13}^7$. Значит, количество команд, в которых есть хотя бы одна девочка, равно:$$C_{30}^7 - C_{13}^7 =\frac{30!}{7!\cdot 23!} - \frac{13!}{7!\cdot 6!}=2~035~800-1~716=2~034~084.$$Ответ: 2 034 084. ◄

Сочетания с повторениями

Помимо обычных сочетаний рассматривают сочетания с повторениями .

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

Принципиальное отличие от размещений с повторениями заключается в том, что в данном случае элементы списка не нумеруются. Например, список "A, С, A, В" и список "А, А, В, С" считаются одинаковыми.

Сочетания с повторениями обозначаются $\overline{C}_n^m$ и вычисляются по формуле$$\overline{C}_n^m=P_{m,~n-1}=\frac{(m+n-1)!}{m!\cdot (n-1)!}.$$И ещё один способ записи той же формулы:$$\overline{C}_n^m=C_{m+n-1}^m=\frac{(m+n-1)!}{m!\cdot (n-1)!}.$$Заметим, что подобно размещениям с повторениями, допустим случай, когда m > n , то есть выбранных объектов больше, чем их всего имеется. Действительно, каждый объект после "использования" возвращается обратно и может быть использован снова и снова.

Например, выясним сколькими способами можно купить 7 пирожных в кондитерском отделе, если в продаже 4 их сорта?

Естественно полагать, что количество пирожных каждого вида не меньше 7, и при желании можно купить только пирожные одного из них. Так как порядок в котором кладут купленные пирожные в коробку не важен, то имеем дело с сочетаниями с повторениями. Так как нужно выбрать 7 пирожных из 4 его видов, то искомое количество способов равно:$$\overline{C}_4^7=\frac{(7+4-1)!}{7!\cdot (4-1)!}=\frac{10!}{7!\cdot 3!}=\frac{8\cdot 9\cdot 10}{1\cdot 2\cdot 3}=120.$$

Ответ: 120. ◄

Бином Ньютона и биномиальные коэффициенты

Равенство$$(x+a)^n=C_n^0x^na^0+C_n^1x^{n-1}a^1+...+C_n^mx^{n-m}a^m+...+C_n^nx^0a^n$$называют биномом Ньютона или формулой Ньютона . Правая часть равенства называется биномиальным разложением в сумму , а коэффициенты $C_n^0,~C_n^1,~...~,~C_n^n$ — биномиальными коэффициентами .

Свойства биномиальных коэффициентов:

$~~~~~~~~1.~~C_n^0=C_n^n=1\\ ~~~~~~~~2.~~C_n^m=C_n^{n-m}\\ ~~~~~~~~3.~~C_n^m=C_{n-1}^{m-1}+C_{n-1}^{m}\\ ~~~~~~~~4.~~C_n^0+C_n^1+C_n^2+~...~+C_n^n=2^n\\ ~~~~~~~~5.~~C_n^0+C_n^2+C_n^4+~... =C_n^1+C_n^3+C_n^5+~...=2^{n-1}\\ ~~~~~~~~6.~~C_n^n+C_{n+1}^n+C_{n+2}^n+~...~+C_{n+m-1}^n=C_{n+m}^{n+1}\\ $

Свойства биномиального разложения:

1. Число всех членов разложения на единицу больше показателя степени бинома,

то есть равно n + 1 .

2. Сумма показателей степеней x и a каждого члена разложения равна показателю степени бинома,

то есть (n - m) + m = n .

3. Общий член разложения (обозначается T n +1 ) имеет вид$$T_{n+1}=C_n^m x^{n-m}a^m,~~~~m=0,~1,~2,~...~,~n.$$

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

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

					$C_0^0$
				$C_1^0$		$C_1^1$
			$C_2^0$		$C_2^1$		$C_2^2$
		$C_3^0$		$C_3^1$		$C_3^2$		$C_3^3$
	$C_4^0$		$C_4^1$		$C_4^2$		$C_4^3$		$C_4^4$
$C_5^0$		$C_5^1$		$C_5^2$		$C_5^3$		$C_5^4$		$C_5^5$
	. . .				. . .				. . .

В этом треугольнике крайние числа в каждой строке равны 1. Действительно, $C_n^0=C_n^n=1$. А каждое не крайнее число равно сумме двух чисел предыдущей строки, стоящих над ним: $C_n^m=C_{n-1}^{m-1}+C_{n-1}^{m}$.

Таким образом, этот треугольник предлагает ещё один (рекуррентный) способ вычисления чисел $C_n^m$:

n = 0									1
n = 1								1		1
n = 2							1		2		1
n = 3						1		3		3		1
n = 4					1		4		6		4		1
n = 5				1		5		10		10		5		1
n = 6			1		6		15		20		15		6		1
n = 7		1		7		21		35		35		21		7		1
n = 8	1		8		28		56		70		56		28		8		1
...				...				...		...				...

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

Рождение комбинаторики как раздела связано с трудами Б. Паскаля и П. Ферма по теории азартных игр. Большой вклад в развитие комбинаторных методов внесли Г.В. Лейбниц, Я. Бернулли и Л. Эйлер.

Французский философ, писатель, математик и физик Блез Паскаль (1623–1662) рано проявил свои выдающиеся математические способности. Круг математических интересов Паскаля был весьма разнообразен. Паскаль доказал одну
из основных теорем проективной геометрии (теорема Паскаля), сконструировал суммирующую машину (арифмометр Паскаля), дал способ вычисления биномиальных коэффициентов (треугольник Паскаля), впервые точно определил и применил для доказательства метод математической индукции, сделал существенный шаг в развитии анализа бесконечно малых, сыграл важную роль в зарождении теории вероятности. В гидростатике Паскаль установил ее основной закон (закон Паскаля). “Письма к провинциалу” Паскаля явились шедевром французской классической прозы.

Готфрид Вильгельм Лейбниц (1646–1716) — немецкий философ, математик, физик и изобретатель, юрист, историк, языковед. В математике наряду с И. Ньютоном разработал дифференциальное и интегральное исчисление. Важный вклад внес в комбинаторику. С его именем, в частности, связаны теоретико-числовые задачи.

Готфрид Вильгельм Лейбниц имел мало внушительную внешность и поэтому производил впечатление довольно невзрачного человека. Однажды в Париже он зашел в книжную лавку в надежде приобрести книгу своего знакомого философа. На вопрос посетителя об этой книге книготорговец, осмотрев его с головы до ног, насмешливо бросил: “Зачем она вам? Неужели вы способны читать такие книги?” Не успел ученый ответить, как в лавку вошел сам автор книги со словами: “Великому Лейбницу привет и уважение!” Продавец никак не мог взять втолк, что перед ним действительно знаменитый Лейбниц, книги которого пользовались большим спросом среди ученых.

В дальнейшем важную роль будет играть следующая

Лемма. Пусть в множестве элементов, а в множестве — элементов. Тогда число всех различных пар , где будет равно .

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

Размещения, перестановки, сочетания

Пусть у нас есть множество из трех элементов . Какими способами мы можем выбрать из этих элементов два? .

Определение. Размещениями множества из различных элементов по элементов называются комбинации, которые составлены из данных элементов по > элементов и отличаются либо самими элементами, либо порядком элементов.

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

Теорема. Число размещений множества из элементов по элементов равно

Доказательство. Пусть у нас есть элементы . Пусть — возможные размещения. Будем строить эти размещения последовательно. Сначала определим — первый элемент размещения. Из данной совокупности элементов его можно выбрать различными способами. После выбора первого элемента для второго элемента остается способов выбора и т.д. Так как каждый такой выбор дает новое размещение, то все эти выборы можно свободно комбинировать между собой. Поэтому имеем:

Пример. Сколькими способами можно составить флаг, состоящий из трех горизонтальных полос различных цветов, если имеется материал пяти цветов?

Решение. Искомое число трехполосных флагов:

Определение. Перестановкой множества из элементов называется расположение элементов в определенном порядке.

Так, все различные перестановки множества из трех элементов — это

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

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

Решение. Искомое число расстановки ладей

По определению!

Определение. Сочетаниями из различных элементов по элементов называются комбинации, которые составлены из данных элементов по элементов и отличаются хотя бы одним элементом (иначе говоря, -элементные подмножества данного множества из элементов).

Как видим, в сочетаниях в отличие от размещений не учитывается порядок элементов. Число всех сочетаний из элементов по элементов в каждом обозначается (от начальной буквы французского слова “combinasion”, что значит “сочетание”).

Числа

Все сочетания из множества по два — .

Свойства чисел {\sf C}_n^k

Действительно, каждому -элементному подмножеству данного -элементного множества соответствует одно и только одно -элементное подмножество того же множества.

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

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

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

Теорема.

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

1 способ. Выбираем первый член последовательности, затем второй, третий и т.д. член

2 способ. Выберем сначала элементов из данного множества, а затем расположим их в некотором порядке

Домножим числитель и знаменатель этой дроби на :

Пример. Сколькими способами можно в игре “Спортлото” выбрать 5 номеров из 36?

Искомое число способов

Задачи.

1. Номера машин состоят из 3 букв русского алфавита (33 буквы) и 4 цифр. Сколько существует различных номеров автомашин?
2. На рояле 88 клавиш. Сколькими способами можно извлечь последовательно 6 звуков?
3. Сколько есть шестизначных чисел, делящихся на 5?
4. Сколькими способами можно разложить 7 разных монет в три кармана?
5. Сколько можно составить пятизначных чисел, в десятичной записи которых хотя бы один раз встречается цифра 5?
6. Сколькими способами можно усадить 20 человек за круглым столом, считая способы одинаковыми, если их можно получить один из другого движением по кругу?
7. Сколько есть пятизначных чисел, делящихся на 5, в записи которых нет одинаковых цифр?
8. На клетчатой бумаге со стороной клетки 1 см нарисована окружность радиуса 100 см, не проходящая через вершины клеток и не касающаяся сторон клеток. Сколько клеток может пересекать эта окружность?
9. Сколькими способами можно расставить в ряд числа так, чтобы числа стояли рядом и притом шли в порядке возрастания?
10. Сколько пятизначных чисел можно составить из цифр , если каждую цифру можно использовать только один раз?
11. Из слова РОТ перестановкой букв можно получить еще такие слова: ТОР, ОРТ, ОТР, ТРО, РТО. Их называют анаграммами. Сколько анаграмм можно составить из слова ЛОГАРИФМ?
12. Назовем разбиением натурального числа представление его в виде суммы натуральных чисел. Вот, например, все разбиения числа :

Разбиения считаются разными, если они отличаются либо числами, либо порядком слагаемых.

Сколько существует различных разбиений числа на слагаемых?
13. Сколько существует трехзначных чисел с невозрастающим порядком цифр?
14. Сколько существует четырехзначных чисел с невозрастающим порядком цифр?
15. Сколькими способами можно рассадить в ряд 17 человек, чтобы и оказались рядом?
16. девочек и мальчиков рассаживаются произвольным образом в ряду из мест. Сколькими способами можно их рассадить так, чтобы никакие две девочки не сидели рядом?
17. девочек и мальчиков рассаживаются произвольным образом в ряду из мест. Сколькими способами можно их рассадить так, чтобы все девочки сидели рядом?

Рождение комбинаторики как раздела математикисвязано с трудами Б. Паскаля и П. Ферма по теории азартных игр. Большой вклад в развитие комбинаторных методов внесли Г.В. Лейбниц, Я. Бернулли и Л. Эйлер.

Французский философ, писатель, математик и физик Блез Паскаль (1623–1662) рано проявил свои выдающиеся математические способности. Круг математических интересов Паскаля был весьма разнообразен. Паскаль доказал одну из основных теорем проективной геометрии (теорема Паскаля), сконструировал суммирующую машину (арифмометр Паскаля), дал способ вычисления биномиальных коэффициентов (треугольник Паскаля), впервые точно определил и применил для доказательства метод математической индукции, сделал существенный шаг в развитии анализа бесконечно малых, сыграл важную роль в зарождении теории вероятности. В гидростатике Паскаль установил ее основной закон (закон Паскаля). “Письма к провинциалу” Паскаля явились шедевром французской классической прозы.

Готфрид Вильгельм Лейбниц (1646–1716) - немецкий философ, математик, физик и изобретатель, юрист, историк, языковед. В математике наряду с И. Ньютоном разработал дифференциальное и интегральное исчисление. Важный вклад внес в комбинаторику. С его именем, в частности, связаны теоретико-числовые задачи.

В дальнейшем важную роль будет играть следующая

Лемма. Пусть в множестве элементов, а в множестве-элементов. Тогда число всех различных пар, гдебудет равно.

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

Размещения, перестановки, сочетания

Пусть у нас есть множество из трех элементов . Какими способами мы можем выбрать из этих элементов два?.

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

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

Теорема. Число размещений множества из элементов поэлементов равно

Доказательство. Пусть у нас есть элементы . Пусть- возможные размещения. Будем строить эти размещения последовательно. Сначала определим- первый элемент размещения. Из данной совокупностиэлементов его можно выбратьразличными способами. После выбора первого элементадля второго элементаостаетсяспособов выбора и т.д. Так как каждый такой выбор дает новое размещение, то все эти выборы можно свободно комбинировать между собой. Поэтому имеем:

Решение. Искомое число трехполосных флагов:

Так, все различные перестановки множества из трех элементов - это

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

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

					\(C_0^0\)
				\(C_1^0\)		\(C_1^1\)
			\(C_2^0\)		\(C_2^1\)		\(C_2^2\)
		\(C_3^0\)		\(C_3^1\)		\(C_3^2\)		\(C_3^3\)
	\(C_4^0\)		\(C_4^1\)		\(C_4^2\)		\(C_4^3\)		\(C_4^4\)
\(C_5^0\)		\(C_5^1\)		\(C_5^2\)		\(C_5^3\)		\(C_5^4\)		\(C_5^5\)
	. . .				. . .				. . .

bogemasamara.ru