«Число, положение и комбинаторика – три взаимно пересекающиеся, но различные сферы мысли, к которым можно отнести все математические идеи» Джозеф Сильвестр (1844 г.) КОМБИНАТОРИКА
Комбинаторика – самостоятельная ветвь математической науки
КОМБИНАТОРИКА - это раздел математики, в котором изучаются простейшие «соединения»: перестановки, размещения, сочетания. (Большой Энциклопедический Словарь) - происходит от латинского слова «combina», что в переводе на русский означает – «сочетать», «соединять».
«Вперед поедешь – голову сложишь, направо поедешь – коня потеряешь, налево поедешь – меча лишишься.
n-факториал- это произведение всех натуральных чисел от до единицы до n. Обозначают n!=n·(n-1)·(n-2)·…·3·2·1. n-факториал- это произведение всех натуральных чисел от до единицы до n. Обозначают n!=n·(n-1)·(n-2)·…·3·2·1.
1! = 1, 2! = 2 · 1 = 2, 3! = 3 ·2·1 = 6, 4! = 4·3·2·1 = 24, 5! = 5·4·3·2·1 = 120. Необходимо знать, что 0!=1
Рассмотрим таблицу первых десяти значений n! n n!
Перестановки – Р n =1 ·2 ·3 ·… ·n Р n = n! Перестановки – соединения, которые можно составить из n предметов, меняя всеми возможными способами их порядок; Р n =1 ·2 ·3 ·… ·n Обозначают Р n =n! Число n называется порядком перестановки.
Задача 1 Сколькими способами 7 книг разных авторов можно расставить на полке в один ряд?
Решение: Р 7 = 7!= 1 · 2 · 3 · 4 · 5 · 6 · 7 =5040, Ответ: 5040 способов.
Задача 2 Квартет Проказница Мартышка Осёл, Козёл, Да косолапый Мишка Затеяли играть квартет … Стой, братцы стой! – Кричит Мартышка, - погодите! Как музыке идти? Ведь вы не так сидите… И так, и этак пересаживались – опять музыка на лад не идет. Вот пуще прежнего пошли у них разборы И споры, Кому и как сидеть… Сколькими способами можно рассадить четырех музыкантов?
Решение: P 4 = 4! = 1 · 2 · 3 · 4 = 24
Задача 3 Имеется 10 книг, среди которых есть трехтомник одного автора. Сколькими способами можно расставить эти книги на полке, если книги трехтомника должны находится вместе, но в любом порядке?
Решение: P 8 · Р 3 = 8! ·3! = Ответ:
Задача 4 Из цифр 0, 2, 4 и 5 образованы четырехзначные числа. Найдите количество всех таких чисел, если в них нет одинаковых цифр.
Решение: Из четырех цифр можно составить P 4 = 4! Р 3 =3! Р 4 – Р 3 =4!-3!=4·3!-3!=3·3!=18 Ответ: 18
Задача 5 Из цифр 1, 2, 3, 4, 5 составьте множество всех возможных пятизначных чисел без повторения цифр. Сколько среди этих пятизначных чисел таких, которые:
а) начинаются с цифры 5 Решение: Р 4 = 4! = 24 Ответ: 24
б) не начинаются с цифры 1; Решение: Р 5 = 5! 4! 5! - 4! = 5·4! -4!=44!=4-4·3·2·1 =96. Ответ: 96
в) начинаются с 23; Решение: Р 3 = 3! = 3 ·2 ·1=6 Ответ: 6
г) не начинаются с 452; Решение: Р 2 = 2 · 1 = 2 Р 5 = 5! = 5 · 4 ·3 ·2 ·1 = 120 5!-2!=118 Ответ: 118
д) четные. Решение: 4! 4!+4!=2 ·4!=2 ·4 ·3 ·2 ·1=48 Ответ: 48
Спасибо за внимание
Размещения и сочетания
В отделении 12 солдат. Каким числом способов можно составить наряд из двух человек, если один из них в наряде старший? Задача 2. В отделении 12 солдат. Каким числом способов можно составить наряд из двух человек, если один из них в наряде старший?
12 способов выбрать старшего 11 способов выбрать его помощника · 12 · 11=132
Задача 3. Для праздника в детском саду дети раскрашивали флажки в разные цвета. Верхнюю половину флажка красили в один цвет, а нижнюю в другой. Для раскраски у них имелись синяя, красная, желтая и зеленая краски. Сколько различных двухцветных флажков могли подготовить дети к празднику?
1 способ. 4 ·3=12 всего 12 различных флажков
2 способ.
3 способ. (с,к)(к,с)(ж,с)(з,ж) (с,ж)(к,ж)(ж,к)(з,с) (с,з)(к,з)(ж,з)(з,к) всего 12 различных флажков
Составим из элементов множества всевозможные пары, чтобы в каждой паре элементы не повторялись
(а,b)(b,a)(c,a)(d,a) (a,c)(b,c)(c,d)(d,b) (a,d)(b,d)(c,b)(d,c)
Определение 1. Множество с заданным порядком расположения элементов называют упорядоченным множеством.
Определение 2. В комбинаторике конечные упорядоченные множества называются размещениями.
Размещением из n элементов по k, где k n, называют упорядоченное множество, содержащее k элементов. Вычисляется по формуле Размещением из n элементов по k, где k n, называют упорядоченное множество, содержащее k элементов. Вычисляется по формуле
Теорема. Число размещений из n элементов по k равно или, домножив числитель и знаменатель на (n-k)! получим, что
Вычислим число, где
n k
Задача 4. Сколько можно составить телефонных номеров из 6 цифр каждый, так чтобы все цифры были различны?
Задача 5. Сколькими способами четверо юношей могут пригласить четырех из шести девушек на танец?
Задача 6. В 9 классе обучается 24 ученика. Сколькими способами можно составить график дежурства по классу, если группа дежурных состоит из трех учеников?
Решение задачи: Ответ: число способов равно числу размещений из 24 по 3, т.е способа.
Задача 7. В магазине есть пять сортов печенья, шесть сортов конфет, четыре сорта шоколада. Сколько различных подарков может предложить магазин, если в подарок входит два различных вида угощения (печенья, конфет, шоколада) различных сортов (по одному).
5·6=30 различных подарков, состоящих только из конфет и печенья 5·4=20 различных подарков, состоящих только из шоколада и печенья 4·6=24 различных подарков, состоящих только из конфет и шоколада =74 – число различных подарков
Определение. Рассмотрим конечные множества A 1, А 2, А 3,..., Ак, количество различных элементов в каждом из которых соответственно равно n 1, n 2, n 3,…n k, причем у них нет общих элементов. Тогда общее число различных элементов в их объединении равно сумме чисел элементов в каждом из множеств:
Определение. В комбинаторике конечные множества называют сочетаниями
Определение. Число всех способов выбрать k элементов из n данных элементов без учета порядка называют числом сочетаний из n элементов по k и обозначают.
Теорема. Число сочетаний из n элементов по k равно
a) при k=1:
б) при k=2:
в) при k=0:
Рассмотрим таблицу значений при
n k
n k
n k
ab a+b
336
10515
012345Σ 01 1= = = = = =2 5 n k
Теорема. Число всех подмножеств, образованных из элементов множества, состоящего из n элементов, равно
Задача 7. Сколько трехкнопочных комбинаций существует на кодовом замке (все три кнопки нажимаются одновременно), если на нем всего 10 цифр?
Решение задачи: Ответ: число способов равно числу сочетаний из 10 по 3, т.е. 120 способов.
Задача Ученикам дали список из 10 учебников, которые рекомендуется использовать для подготовки к экзамену. Сколькими способами ученик может выбрать из них 4 книги? Сколькими способами ученик может выбрать из них 4 книги?
Решение задачи: Ответ: число способов равно числу сочетаний из 10 по 4, т.е. 30 способов.
Спасибо за внимание.
Размещениями из n элементов по k с повторениями называются всевозможные соединения по k элементов, взятых из данных n элементов и отличающихся либо самими элементами, либо их порядком
Задача 1. Сколько различных двузначных чисел можно образовать из цифр 1, 3 и 4?
Решение : На первое место мы можем поставить 3 числа, на второе тоже 3 и на третье – 3, значит
Перестановкой из n элементов называется упорядоченное множество, содержащее n заданных элементов, из которых некоторые повторяются раз
Задача 2. Сколько семизначных чисел можно составить из цифр 1, 2, 3, 4, 5, если число может содержать цифры 2, 3, 4 и 5 по одному разу, а цифру 1 -три раза?
Решение : 7!=5040 3!=6 Ответ: 840 двузначных чисел.
Сочетаниями с повторениями из n элементов по k элементов называются неупорядоченные множества по k элементов из n элементов, причем любой элемент может повторятся до k раз.
Задача 3. На спектакле в Михайловском театре по время антракта Катя зашла в буфет и увидела на витрине четыре вида пирожных: эклеры, буше, наполеон и миндальные. Она купила 10 пирожных. Сколькими способами она могла это сделать?
Решение : Ответ: 715 способами Катя может купить 10 пирожных.
Порядок важен? нет Повторения есть? нет Сочетания да Сочетания с повторениями да Нужно выбрать все n элементов? нет Повторения есть? нет Размещения да Размещения с повторениями Да Повторения есть? нет Перестановки да Перестановки с повторениями
Задача 1 Сколько шестизначных кодов для открывания замка можно составить из цифр 2, 3, 5 и трех букв А, В и С, если в коде не должны повторяться ни буквы, ни цифры.
Решение: 6! Р 6 =6!=720 Ответ: 720
Задача. Сколько разных слов можно образовать из слова « папа »?
Решение : 4!=24 2!=2 Ответ: 6 слов.
Задача. Сколько существует треугольников, длина сторон которых 5, 6, 7, 8, 9?
Порядок важен? нет Повторения есть? да Сочетания с повторениями
Ответ: 35 треугольников.
Задача. Сколько слов можно получить из слова « барабашка »?
Порядок важен? да Нужно выбрать все n элементов? Да Повторения есть? да Перестановки с повторениями
Ответ: 210 слов.
Библиографическая справка Термины «перестановки» и «размещения» впервые употребил Якоб Бернулли в книге «Искусство предположений». Термин «сочетания»впервые встречается у Блеза Паскаля в 1665 году.
Решение задач: Задача 1: В соревнованиях участвуют 12 команд. Сколько существует вариантов распределения призовых (I, II, III) мест? Задача 2: Студенты Женя, Сергей, Коля, Наташа и Ольга побежали на перемене к теннисному столу, за которым уже шла игра. Сколькими способами подбежавшие студенты могут занять очередь для игры в настольный теннис? Задача 3: В 9 классе учатся 7 учеников, в 10 – 9, а в 11 – 8 учеников. Для работы на пришкольном участке надо выделить двух учеников из 9 класса, трех – из 10 класса и одного – из 11 класса. Сколько существует способов выбора учеников для работы на пришкольном участке? Решение задач: Задача 1: В соревнованиях участвуют 12 команд. Сколько существует вариантов распределения призовых (I, II, III) мест? Задача 2: Студенты Женя, Сергей, Коля, Наташа и Ольга побежали на перемене к теннисному столу, за которым уже шла игра. Сколькими способами подбежавшие студенты могут занять очередь для игры в настольный теннис? Задача 3: В 9 классе учатся 7 учеников, в 10 – 9, а в 11 – 8 учеников. Для работы на пришкольном участке надо выделить двух учеников из 9 класса, трех – из 10 класса и одного – из 11 класса. Сколько существует способов выбора учеников для работы на пришкольном участке?
Особая примета комбинаторных задач - вопрос, который начинался словами «Сколькими способами…?» Особая примета комбинаторных задач - вопрос, который начинался словами «Сколькими способами…?»
Исторические сведения Комбинаторика как наука стала развиваться в XIII в. параллельно с возникновением теории вероятностей. Первые научные исследования по этой теме принадлежат итальянским ученым Дж. Кардано, Н. Чарталье ( ), Г. Галилею ( ) и французским ученым Б.Пискамо ( ) и П. Ферма. Комбинаторику, как самостоятельный раздел математики, первым стал рассматривать немецкий ученый Г. Лейбниц в своей работе «Об искусстве комбинаторики», опубликованной в 1666 г. Он также впервые ввел термин «Комбинаторика».
Исторические сведения Дата рождения: 1 июля 1646 г. Место рождения: Лейпциг, Германия Дата смерти:14 ноября 1716 г. Место смерти: Ганновер, Германия Школа/традиция: рационализм Направление: Европейская философия Основные интересы: Метафизика, эпистемология, наука, математика. Лейбниц Готфрид Вильгельм