3.Понятие соединения, перестановки, сочетания, размещения.
Комбинаторика — раздел математики, в котором изучаются вопросы о том, сколько различ комбинаций, подчиненных тем или иным условиям, можно составить из заданных объектов.
Соединение (комбинация) – некоторый тип совокупности элементов. Каждое соединение, характеризуется составом и порядком. Состав мб постоянным или переменным, а порядок мб упорядоченным или неупорядоченным.
Размещением из n-элементов по m, наз. Упорядоченное множество m элементов, взятых из n-эл.
ПР: Пусть даны шесть цифр: 1;2;3;4;5; 6. Определить сколько трехзначных чисел можно составить из этих цифр.
Решение. Если цифры могут повторяться, то . Если не повторяются, то
Перестановкой из n-эл, наз упорядоченное множество из этих эл.
ПР: 30 книг стоит на книжной полке, из них 27 различных книг и одного автора три книги. Сколькими способами можно расставить эти книги на полке так, чтобы книги одного автора стояли рядом?
Решение.Будем считать три книги одного автора за одну книгу, тогда число перестановок будет Р28. А три книги можно переставлять между собой Р3 способами, тогда по правилу произведения имеем, что искомое число способов равно:Р3*Р28 =3!*28!
Сочетанием из n-элементов по m, наз неупорядоченное подмножество m-эл, взятых из n-эл.
ПР: В группе из 27 студентов нужно выбрать трех дежурных. Сколькими способами можно это сделать?
Решение. Так как порядок студентов не важен,.
При решении задач комбинаторики используют следующие правила:
Правило суммы. Если некоторый объект А может быть выбран из совокупности объектов m способами, а другой объект В может быть выбран n способами, то выбрать либо А, либо В можно m + n способами.
Правило произведения. Если объект А можно выбрать из совокупности объектов m способами и после каждого такого выбора объект В можно выбрать n способами, то пара объектов (А, В) в указанном порядке может быть выбрана m*n способами.
ПР: Наряд студентки состоит из блузки, юбки и туфель. Девушка имеет в своем гардеробе четыре блузки, пять юбок и трое туфель. Сколько нарядов может иметь студентка? Пусть сначала студентка выбирает блузку. Этот выбор может быть совершен четырьмя способами, так как студентка имеет четыре блузки, затем пятью способами произойдет выбор юбки и тремя способами выбор туфель. По принципу умножения получается 4*5*3=60 нарядов (комбинаций).
4. Классическое опред. Вероят соб. Статистическое опред. Вероят. Соб. Геометрическая вероятность.
КЛАССИЧ: СС –
Достоверное событие (Ω), событие, которое обязательно происходит в результате испытания, вероятность достоверного события равна единице:Р(Ω)=1; невозможное событие (знак пустого множества), не происходит ни при каком исходе случайного эксперимента, вероятность невозможного события равна нулю.
Предположим, проводится подбрасывание монеты. В результате этого эксперимента обязательно произойдет одно из следующих событий:
А: монета упадет орлом;
В: монета упадет решкой;
С: монета упадет на ребро;
Т.е. система {А;В;С}является полной группой событий.
СС называются несовместными в данном испытании, если никакие два из них не могут появиться вместе.
Вероятностью события
A называют отношение числа m благоприятствующих этому событию исходов к общему числу n всех равновозможных несовместных элементарных исходов, образующих полную группу Р(А)= m / n.Св-ва:
1.Вер достоверного события =1.
2.Вер невозможного события =0
3.Вер СС есть положительное число, заключенное между нулем и единицей.
Итак, вероятность любого события удовлетворяет двойному неравенству 0≤Р(А)≤1.
СТАТИСТИЧ: При статистич опред в качестве вер соб принимают его относительную частоту: W(A)=m/n
где m — число испытаний, в которых событие A наступило, n — общее число произведённых испытаний.
ПР: В некотором районе зарегистрировано рождение с начала года 1248 младенцев, из них 645 мальчиков. Какова вероятность рождения мальчика в данном районе? За вероятность принимаем относительную частоту рождения мальчиков. W = 645/1248 ≈ 0,517
ГЕОМЕТРИЧ: Пусть некоторая n-мерная фигура (отрезок, плоская фигура, пространственная фигура) составляет часть другой n-мерной фигуры. Если предположить, что вероятность попадания точки на эту фигуру пропорциональна её мере (длине, площади, объёму) и не зависит от взаимного расположения меньшей и большей фигур, то вероятность попадания точки на эту фигуру определяется равенствами P=l/L,P=s/S, P=v/V, где l(L), s(S), v(V) — длина, площадь и объём меньшей и большей n-мерных фигур соответственно.
ПР: На плоскости начерчены две окружности радиусами 2 и 7 см,одна внутри другой. Найти вероятность того, что точка, брошенная наудачу в большой круг, попадет также и в малый круг.
P = s/S = πr2/πR2 = 22/72 = 4/49 ≈ 0,082
studfiles.net
Мастер-класс по теме «Элементы комбинаторики: перестановки, сочетания и размещения»
Разделы: Математика
Класс:
Элементы комбинаторики: перестановки, сочетания, размещения.
“Число, положение и комбинация – три
взаимно пересекающиеся, но различные
сферы мысли, к которым можно
отнести все математические идеи”.
Джозеф Сильвестр (1844 г.)
Цели занятия.
Образовательные:
- познакомить студентов с новым разделом математики: «Комбинаторика», с его историей, основными понятиями и задачами, использованием в практических целях и в жизни человека;
- способствовать созданию учебного проекта как показатель качественного изучения темы занятия.
Развивающие:
- развивать аналитические способности, логическое мышление,
- индивидуальные способности каждого студента, создавая комфортную психологическую обстановку для каждого студента при обучении и создании проекта.
Воспитывающая:
- формировать активность личности студента, умение работать в группе, отвечать за свои поступки.
Оборудование: компьютеры, проектор, экран, презентация, электронные и на бумажных носителях тесты, задачи “Судоку”, кубики Рубика, папки для ВСР (внеаудиторная самостоятельная работа), рабочие тетради, чистые ватманы, калькуляторы, цветная бумага, клей, ножницы, фломастеры.
Ход занятия
I. Организационный момент
ПерекличкаСообщение целей и задач занятия: В связи с тем, что по дисциплине “Математика” на 2 курсе специальности “Технология деревообработки” на тему “Основные понятия комбинаторика: перестановки, размещения, сочетания” отводится 2 часа, а рассмотреть нужно много материала, решать задачи, создать проект, вам было выдано задание на внеаудиторную самостоятельную работу следующее: в литературе по истории математики, в энциклопедиях, в учебниках и в интернете найти материал о разделе математики, имеющем звучное название “комбинаторика”. Слайды № 1–2. Презентация
В календарно-тематическом плане по дисциплине “Математика” на 2 курсе специальности “Технология деревообработки” на тему “Основные понятия комбинаторика: перестановки, размещения, сочетания” отводится 2 часа. Изучить теоретический материал, решить задачи разных видов за такой временной промежуток невозможно. Для достижения глубокого изучения материала было выдано задание на внеаудиторную самостоятельную работу: в литературе по истории математики, в энциклопедиях, в учебниках и в интернете найти материал о разделе математики, имеющем звучное название “комбинаторика”.
Вопросов для внеаудиторной самостоятельной работы выделено было три:
- Определения комбинаторики.
- Ученые – математики — первооткрыватели этого раздела.
- Применение комбинаторики в современной жизни.
Запись даты, темы урока.
II. Работа над темой занятия
Вступление:
Из глубокой древности до современного человечества дошли сведения о том, что уже тогда люди занимались выбором объектов и расположения их в том или ином порядке и увлекались составлением различных комбинаций. Так, например, в Древнем Китае увлекались составлением квадратов, в которых заданные числа располагали так, что их сумма по всем горизонталям, вертикалям и главным диагоналям была одной и той же (современная игра – задача “Судоку”). Такие задачи вы могли встречать в журналах и газетах. В частности, наша Мариинская газета “Вперед” довольно часто предлагает читателям такие задачи. В Древней Греции подобные задачи возникали в связи c такими играми, как шашки, шахматы, домино, карты и т.д.
Комбинаторика ставится самостоятельным разделом математики, по сути – самостоятельной наукой лишь во второй половине XVII века, — в период, когда возникла теория вероятностей.
Таким образом, — комбинаторика – это самостоятельный раздел математики, в котором изучаются вопросы о том, сколько различных комбинаций, подчинённых тем или условиям, можно составить из заданных объектов.
Комбинаторика – самостоятельная ветвь математической науки. Cлайд № 3
Термин “КОМБИНАТОРИКА” происходит от латинского слова “combina”, что в переводе на русский означает – “сочетать”, “соединять” — слайд № 4.
Как трактует это слово Большой Энциклопедический Словарь?
Комбинаторика – это раздел математики, в котором изучаются простейшие “соединения”: перестановки, размещения, сочетания. Этот раздел иначе называют “комбинаторный анализ”.
Сегодня мы будем рассматривать перестановки, размещения, сочетания, как соединения, как комбинаторные конфигурации.
Разделы комбинаторики: перечислительная, структурная, вероятностная, топологическая – слайд № 5.
Давайте вспомним известное вам из детства сказание о том, как богатырь или другой добрый молодец, доехав до развилки трех дорог, читает на камне: “Вперед поедешь – голову сложишь, направо поедешь – коня потеряешь, налево поедешь – меча лишишься”. А дальше уже говорится, как он выходит из того положения, в которое попал в результате выбора. Но выбирать разные пути или варианты приходится и современному человеку. Эти пути и варианты складываются в самые разнообразные комбинации. И целый раздел математики, именуемый КОМБИНАТОРИКОЙ, занят поисками ответов на вопросы: сколько всего есть комбинаций в том или ином случае, как из всех этих комбинаций выбрать наилучшую – слайд № 6.
Итак, комбинаторика – раздел математики, в котором изучается, сколько различных комбинаций, подчиненных тем или иным условиям, можно составить из заданных объектов.
Задачей комбинаторики можно считать задачу размещения объектов по специальным правилам и нахождение числа способов таких размещений.
Перестановки-соединения, которые можно составить из n предметов, меняя всеми возможными способами их порядок; число их
Количество всех перестановок из n элементов обозначают
Число n при этом называется порядком перестановки – слайд № 7–10.
Произведение всех натуральных чисел от n до единицы, обозначают символом n! (Читается “эн - факториал”). Используя знак факториала, можно, например, записать:
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
Термин “перестановки” употребил впервые Якоб Бернулли в книге “Искусство предположений”.
Примеры решения задач:
Задача №1. Сколькими способами 7 книг разных авторов можно расставить на полке в один ряд?
Перестановками называют комбинации, состоящие из одних и тех же п различных элементов и отличающиеся только порядком их расположения. Число всех возможных перестановок обозначается Рп и оно равно п!, т.е. Рп = п!, где п! = 1 * 2 * 3 * … п.
Решение: Р7 = 7!, где 7! = 1 * 2 * 3 * 4 * 5 * 6 * 7 =5040, значит существует 5040 способов осуществить расстановку книг.
Ответ: 5040 способов.
Задача № 2 (о квартете)
В знаменитой басне Крылова “Квартет” “Проказница мартышка, Осел, Козел да косолапый Мишка” исследовали влияние взаимного расположения музыкантов на качество исполнения.
Зададим вопрос: Сколько существует способов, чтобы рассадить четырех музыкантов?
Решение: на слайде
Размещения – соединения, содержащие по m предметов из числа n данных, различающихся либо порядком предметов, либо самими предметами; число их.
Cлайды № 11–13.
В комбинаторике размещением называется расположение “предметов” на некоторых “местах” при условии, что каждое место занято в точности одним предметом и все предметы различны.
В отличие от сочетаний размещения учитывают порядок следования предметов. Так, например, наборы < 2,1,3 > и < 3,2,1 > являются различными, хотя состоят из одних и тех же элементов {1,2,3} (то есть, совпадают как сочетания).
Термин “Размещение” употребил впервые Якоб Бернулли в книге “Искусство предположений”.
Примеры решения задач:
Задача № 1. Сколько можно составить телефонных номеров из 6 цифр каждый, так чтобы все цифры были различны? Это пример задачи на размещение без повторений.
Размещаются здесь десять цифр по 6. Значит, ответ на выше поставленную задачу будет:
Ответ:151200 способов
Задача № 2. В группе ТД – 21 обучается 24 студентов. Сколькими способами можно составить график дежурства по техникуму, если группа дежурных состоит из трех студентов?
Решение: число способов равно числу размещений из 24 элементов по 3, т.е. равно А243. По формуле находим
Ответ: 12144 способа
Сочетания-соединения, содержащие по m предметов из n, различающиеся друг от друга, по крайней мере, одним предметом; число их .
Таким образом, количество вариантов при сочетании будет меньше количества размещений. Cлайды № 14–16.
В комбинаторике сочетанием из n по m называется набор m элементов, выбранных из данных n элементов. Наборы, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми, этим сочетания отличаются от размещений.
Термин “сочетание” впервые встречается у Блеза Паскаля в 1665 году.
Примеры решения задач:
Задача №1. Сколько трехкнопочных комбинаций существует на кодовом замке (все три кнопки нажимаются одновременно), если на нем всего 10 цифр?
Решение: Так как кнопки нажимаются одновременно, то выбор этих кнопок – сочетание. Отсюда возможно
Ответ: 120 вариантов.
Задача № 2. Сколько экзаменационных комиссий, состоящих из 3 членов, можно образовать из 10 преподавателей?
Решение: По формуле находим:
комиссий
Ответ: 120 комиссий.
Библиографическая справка – слайд № 17.
Общее у всех этих задач то, что их решением занимается отдельная область математики, называемая комбинаторикой. “Особая примета” комбинаторных задач – вопрос, который всегда можно сформулировать так, чтобы он начинался словами: “Сколькими способами…?”. Cлайд № 18.
3. Решение задач: тексты задач с решениями в приложении 1 – начало на слайде № 19.
4. Исторические сведения о комбинаторике на слайдах № 20–21 (частично даны сведения при изучении темы, остальные данные для проекта студенты возьмут из материалов для ВСР).
5. Связи комбинаторики на слайдах № 22–31 (частично даны сведения при изучении темы, остальные данные для проекта студенты возьмут из материалов для ВСР).
6. Выдвижение гипотезы. Гипотеза – это научное предположение, выдвигаемое для объяснения каких-нибудь явлений, вообще – предположение, требующее подтверждения.
Выдвигается гипотеза: Комбинаторика интересна и имеет широкий спектр практической направленности — слайд № 32.
7. Метод проектов: три группы студентов и группа преподавателей выполняют проект по теме: “Комбинаторика”, используя знания, полученные на занятии, а также материалы, подготовленные по заданию на ВСР: различные определения комбинаторики, ученые – математики - первооткрыватели этого раздела, применение комбинаторики в современной жизни.
8. Защита проектов: при защите проекта сделать вывод: подтверждает ли проект выдвинутую гипотезу или опровергает.
9. Тестирование: Часть студентов тестируется на компьютерах, остальные – на бумажных носителях по теме занятия. По мере выполнения тестов студенты решают задачу “Судока” или собирают кубик Рубика.
10. При выходе из кабинета каждый студент выбирает прямоугольник по цвету, соответствующему надписями “всё понятно и усвоено”, “трудно и не всё понятно”, “не понятно и не усвоено”, и опускает в соответствующий конверт.
Информационные ресурсы
1. Фадеев Д.К., Никулин М.С., Соколовский. Элементы высшей математики для школьников. Москва. “Наука”, 1987 год.
2. Грэхем Р., Кнут Д.А., Паташник О. Конкретная математика.. Москва “Мир”, 1998 г.
3. Богомолов Н.В. Практические занятия по математике: Учеб. Пособие для техникумов, Москва. “Высшая Школа, 1983.
4. Перельман Я.И. “Занимательная алгебра. Занимательная геометрия, Москва, АСТ “Астрель”, 2002 год.
5. Савин А.П. “Энциклопедический словарь юного математика”, Москва “Педагогика”, 1985.
6. Сканави М.И. “Сборник задач по математике для поступающих в вузы”, Москва, “Высшая школа”, 1998 г.
7. Вентцель Е.С. Теория вероятностей. – 4-е изд. - М.: Наука, 1969.
8. Элементы теории вероятностей. Математика. Приложение к газете «Первое сентября», № 41, 42.
9. http//portfolio.1september.ru
10. Лютикас В.С. Факультативный курс по математике: Теория вероятностей, Москва, “ Просвещение”, 1990.
11. Гнеденко Б.В., Хинчин А.Я. Элементарное введение в теорию вероятностей. — 6-е изд. — М.: Наука, 1964.
12. Андреева Е. В. “Комбинаторные задачи”, Москва, “Чистые пруды”, 2005 г.
Приложение 1
20.06.2011
urok.1sept.ru
Перестановки, размещения и сочетания с повторениями
Поиск Лекций
До сих пор мы рассматривали случаи, когда все объекты были попарно различны. Если же часть предметов набора будут совпадать число перестановок, сочетаний и размещений будет вычисляться по-другому.
//Перестановки с повторениями.
Если некоторые из переставляемых предметов одинаковы, то суммарное число получается меньше, т. к. часть комбинаций совпадает друг с другом.
Например, требуется определить различные размещения букв в слове Миссисипи. Предположим сначала, что все буквы различны. В таком случае существовало бы 11! способов размещения 11 букв. Теперь обратим внимание, что буква «и» встречается четыре раза. Тогда все 11! комбинаций можно разбить на группы, элементы которых буду отличаться только расположением буквы «и» (наппр: «М и1 с с и2 с и3 п и4 », «М и2 с с и1 с и3 п и4 »…). В каждой группе будет по 4! комбинаций (по числу перестановок буквы и) . Сейчас они подсчитаны, как различные, хотя это не так. Значит каждым 4! комбинациям из 11! соответствует только одна перестановка. Тогда число перестановок, с учётом того, что все буквы «и» одинаковы будет 11!/4! . Размышляя аналогично относительно остальных повторяющихся букв (с — входит 3 раза — делить на 3!…), получаем
Рассмотрим общий случай. Пусть у нас есть объекты k различных типов и из них n1 объектов первого типа, n2 объектов второго типа … nk объектов типа №k. Рассуждая таким же образом, как и при решении предыдущей задачи задачи, получим формулу для подсчёта числа перестановок с повторениями.
//Размещения с повторениями.
Говорят, что рассматриваются размещения с повторениями, когда имеется набор объектов нескольких типов, каждый тип содержит все себе достаточно объектов заполнения всех мест размещения и порядок заполнения мест важен.
Например, необходимо сколько номеров автобусных билетов можно составить, если номер каждого билета состоит из 4-х цифр от 1 до 7. Заметим, что каждую цифру можно использовать в номере билета неограниченное число раз (номера типа 7777 и 7772 допустимы). Порядок цифр в номере важен (номера 7772 и 2777 различны). Каждую цифру можно выбрать 7 способами. Т. к. выбор каждой следующей следующей цифры не зависит от результата выбора предыдущей, для подсчёта всех возможных вариантов воспользуемся правилом произведения. Получим
Теперь, рассуждая аналогично для m разновидностей объектов и n мест размещения получим формулу для размещений с повторениями
//Сочетания с повторениями.
Говорят, что рассматриваются размещения с повторениями, когда имеется набор объектов нескольких типов, каждый тип содержит все себе достаточно объектов заполнения всех мест размещения и порядок заполнения мест не важен.
Предположим, что комитет состоит из восьми человек. При принятии решения они голосуют «за», «против» или воздерживаются от голосования. Сколько возможных исходов голосования по данному решению? Если интересует вопрос, кто и как голосовал, тогда речь идет о числе перестановок, когда для каждого голосующего имеются три варианта ответа, что дает 3^8 возможных исходов голосования. Допустим, что нас интересует только общий результат голосования. голосование можно изобразить, например, в виде ЗЗППВВВВ, где два голоса «за», два «против» и четыре воздержавшихся. Далее можно строить разбиение голосов, например, 33|ПП|ВВВВ. Поскольку порядок расположения голосов понятен, можно перейти к записи хх|хх|хххх, изображающей 33|ПП|ВВВВ. Таким образом, запись хх||хххххх будет представлять два голоса «за» и четыре воздержавшихся, а запись хххххххх|| будет соответствовать голосованию «за» всех восьми членов комитета. Таким образом, установлено
взаимно однозначное соответствие между возможными исходами голосования и различными способами размещения восьми знаков х и двух знаков |. Но это ни что иное, как количество способов выбора двух мест из десяти для знака | или, что эквивалентно, количество способов выбора восьми мест из десяти для размещения знака х. Следовательно, существуют
вариантов голосования
Предположим, что n объектов выбираются из k типов объектов с неограниченным повторением. Пусть аi — объект типа i, тогда, как и в предыдущей задаче можно записать:
a1a1a1…a1a1|a2 a2 a2 …a2|…akakak…ak
Поскольку место расположения каждого типа понятно, то выборку можно записать в виде
xxx…xx|xxx…xx|…xxx…xx
Заметим, что разделителей | на один меньше, чем количество типов. Таким образом, имеем n объектов и k — 1 разделителей, образующих и n + k — 1 мест для размещения х или |. Поскольку существует С(n + k — 1, n) = С(n + k — 1, k — 1) способов выбора места для знака х или, что эквивалентно, для знака |, то существуют C(n + k — 1, n) = С(n + k — 1, k — 1) различных способов выбора n из k типов объектов с неограниченным повторением.
При решении конкретной задачи надо сначала выяснить, не решается ли она непосредственно применением правил суммы или произведения. Если решение окажется затруднительным, то следует составить математическую схему решения задачи, определить, допустимы, ли повторения и выяснить о какой комбинации в ней идёт речь.
Задачи
Задача №1.
Сколькими способами на шахмотной доске можно расположить 2 белых и 2 чёрных ладьи так, ч.б. они не «били» друг друга ( мат олимпиада 8класс 🙂 ) (5-10 мин)
Долго рисовать…
64 * ( 14*С((64 — 22), 2) + (64 — 15) * С(36, 2) )
Задача №2
Человек покупает 12 игрушек для своих четверых детей. Сколькими способами можно распределить игрушки, что-бы всем детям досталось поровну (4 шт).
Для первого ребёнка существует С(12,3) способов выбрать игрушки. Для второго С(9,3), для третьего С(6, 3), для четвёртого С(3,3) =1. И по правилу произведения Q=С(12,3)*С(9,3)*С(6, 3)*1
Задача №3
Укротитель хищных зверей хочет вывести на арену колонной 5 львов и 4 тигра, при этом нельзя, что бы два тигра шли друг за другом. Сколькими способами это можно сделать
Поставим сначала всех львов так, чтобы между ними был промежуток. Это можно сделать 5! Между львами получили 6 свободных мест. Теперь только осталось распределить эти места между 4 тиграми А(6,4) = 360. Искомое число способов по правилу произведения А(6,4)*5!
Задача №4
Сколько существует чисел, меньших 10000 и таких, что сумма цифр равна 12?
12=1+1+1+1+1+1+1+1+1+1+1+1
Если в числе две значащие цифры.
1+1+1+1+1 / 1+1+1+1+1+1+1 — пример 2-х значащих цифр (57)
Число различных положений знака / — С(10,1)=10
Числа <10000 c двумя значащими цифрами:
хх
хх0
хх00
Всего таких чисел С(10,1)*3
Если в числе три значащие цифры.
1+1+1+1+1 +1 / 1+1+1 / 1 +1+1 — пример 2-х значащих цифр (633)
Число различных положений знака / — С(10,2)
Числа <10000 c тремя значащими цифрами:
ххх
ххх0
….
Всего чисел С(10,1)*3+С(10,2)*2+С(10,3)
Задача №5
Если многоугольник имеет n сторон, то сколько у него диагоналей?
Т.е. сколькими способами можно провести диагональ? Кажущаяся на первый взгляд несколько непонятной задача решается просто: каждая диагональ эквивалентна сочетанию двух вершин многоугольника. При этом не забываем о том, что стороны многоугольника также входят в общее число сочетаний вершин по 2.
Т.е. число диагоналей равно числу сочетаний вершин по 2: C(n,2) — n.
Проверим:
Для треугольника:
Для четырехугольника:
Для пятиугольника:
Задаче №6
У профессора Кренка в группе 20 студентов. Согласно критерию, известному лишь ему одному, он решил поставить две оценки А, три оценки В, десять С, три D и две оценки F. Сколькими способами он может поставить оценки студентам?
Судя по всему, этот критерий — это гауссово распределение со средним где-то в районе тройбана (C) 😉 Кроме того, кого-то мне этот Кренк напоминает…
Задача на перестановки с повторениями. Общее число их вычисляем следующим образом:
Задача №7
Сколько существует решений уравнения
таких, что
Эта задача эквивалентна следующей:
1+1+1+1+1+1+1+1+1+1+1+1 = 12
Нужно расставить три разделителя на место плюсов. Число способов равно C(12,3) = 220
Задача №8
Показать, что коэффициент при в разложении равен C(n,m)
(n раз)
Для получения слагаемого нужно при перемножении скобок взять a ровно m раз. После приведения подобных членов коэффициент при этом слагаемом будет равен числу способов такого выбора. Считая все скобки (и выбираемые из них символы) разными, получаем, что искомое количество способов равно как раз C(n,m)
Задача 1. Определите сколькими способами можно выбрать 10 шаров из 9 красных, 7 черных, 6 белых и 11 синих шаров.
Решение
Если считать, что шаров бесконечно, то таких комбинаций . Однако у нас шаров некоторых цветов < 10. Значит из полученного числа надо удалить комбинации.
1) где более 9 красных шаров. То есть 10 — такая комбинация одна.
2) где более 7 черных шаров. То есть от 8 до 10 . Таких комбинаций — заполняем 8 мест черными , а остальные места шарами любого цвета.
3) где более 6 белых шаров. То есть от 7 до 10 . Таких комбинаций — заполняем 7 мест белыми , а остальные места шарами любого цвета.
Итого:
Задача 2. Сколько нечетных целых чисел находятся между числами 100 и 1000?
Решение
Пусть S — множество нечетных целых чисел между 100 и 1000. Для пусть — подмножество множества S такое, что i является последней цифрой его элементов. Для каждого i существуют 9 вариантов выбора первой цифры и 10 вариантов выбора второй цифры, так что каждое множество Si содержит 90 элементов. . поэтому между 100 и 1000 есть 450 нечетных чисел.
Задача 3. Берутся все перестановки из 5 чисел 1, 2, 3, 4, 5. Во скольких из них ни одно число не стоит на своем месте?
Решение проводится методом включения/исключения. Обозначим через ( ) свойство перестановки, заключающееся в том, что число стоит на своем месте, а через — количество перестановок, обладающих этим свойством. Точно так же через обозначим количество перестановок, одновременно обладающих свойствами и и т. д. Наконец, через обозначим количество перестановок, не обладающих ни одним из свойств (1), (2), (3), (4), (5), т. е. перестановок, в которых ни одно число не стоит на своем месте.
По формуле включений и исключений имеем:
Здесь — общее число всех перестановок из 5 элементов.
В данном случае задача облегчается тем, что свойства (1), (2), (3), (4), (5) совершенно равноправны. Поэтому ясно, например, что Точно так же имеем В последнем случае число пар равно Аналогично имеем троек, четверок и пятерок.
Поэтому предыдущую формулу можно переписать так:
Задача 4.Сколько существует различных четырехзначных положительных чисел, если, по крайней мере, две цифры в числе совпадают? Числа, начинающиеся с нуля (например, 0001) не считаем четырехзначными.
Решение.
Всего четырехзначных целых чисел существует 9000. Определим, сколько существует четырехзначных чисел с различными цифрами. Очевидно, первую цифру можно выбрать 9 способами. Вторую цифру — также 9 способами (т.к. появляется возможность выбрать 0), третью — 8 способами, четвертую — 7 способами. Если вычесть число четырехзначных чисел с разными цифрами из общего числа четырехзначных чисел, получим искомое число:
Задача 5.По пустыне идет караван из 9 верблюдов. Путешествие длится много дней, и наконец, всем надоедает видеть впереди себя одного и того же верблюда. Сколькими способами можно переставить верблюдов так, чтобы впереди каждого верблюда шел другой, чем раньше?
Решение. Такие перестановки наверняка существуют (например, можно переставить верблюдов в обратном порядке). Для решения задачи перенумеруем верблюдов в первоначальном порядке от конца каравана к началу числами 1, 2, 3, 4, 5, 6, 7, 8, 9. Таким образом, последний верблюд получает номер 1, предпоследний — 2 и т д. Нам нужно найти все перестановки из чисел 1, 2, 3, 4, 5, 6, 7, 8, 9, в которых не встретится ни одна из пар (1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 7), (7, 8), (8, 9). Для решения снова используем формулу включений и исключений. Сосчитаем сначала, во сколько перестановок входит пара (1,2). Мы можем считать эту пару за один элемент. Поэтому общее число элементов будет 8, а не 9, и число перестановок, содержащих (1,2), равно Тот же результат получаем для всех 8 пар.
Теперь рассмотрим перестановки, содержащие данные две пары. В этом случае объединяем элементы, входящие в каждую из этих парю. При этом если обе пары содержат общий элемент, то объединяем все три элемента. Иначе объединяем элементы по 2. В обоих случаях после объединения получаем 7 новых элементов, которые можно переставить способами. А две пары можно выбрать способами.
Совершенно так же доказывается, что количество перестановок, содержащих данные k пар, равно По формуле включений и исключений получаем:
Задача 6.
Сколькими способами на шахмотной доске можно расположить 2 белых и 2 чёрных ладьи так, ч.б. они не «били» друг друга ( мат олимпиада 8класс 🙂 ) (5-10 мин)
Долго рисовать…
Решение.
64 * ( 14*С((64 — 22), 2) + (64 — 15) * С(36, 2) )
Задача 7.
Человек покупает 12 игрушек для своих четверых детей. Сколькими способами можно распределить игрушки, что-бы всем детям досталось поровну (4 шт).
Решение.
Для первого ребёнка существует С(12,3) способов выбрать игрушки. Для второго С(9,3), для третьего С(6, 3), для четвёртого С(3,3) =1. И по правилу произведения Q=С(12,3)*С(9,3)*С(6, 3)*1
Задача 8.
Укротитель хищных зверей хочет вывести на арену колонной 5 львов и 4 тигра, при этом нельзя, что бы два тигра шли друг за другом. Сколькими способами это можно сделать
Поставим сначала всех львов так, чтобы между ними был промежуток. Это можно сделать 5! Между львами получили 6 свободных мест. Теперь только осталось распределить эти места между 4 тиграми А(6,4) = 360. Искомое число способов по правилу произведения А(6,4)*5!
Рекомендуемые страницы:
Поиск по сайту
poisk-ru.ru
Размещения, перестановки, сочетания
Основные понятия комбинаторики. Множества. Перестановки. Сочетания. Размещения. Разбиения. Понятие алгоритма и сложность алгоритмов.
Два основных правила комбинаторики
Для строгого вывода всех формул используются два основных правила комбинаторики:
Правило умножения (правило «и»). Согласно ему, если элемент A можно выбрать n способами, и при любом выборе A элемент B можно выбрать m способами, то пару A и B можно выбрать n·m способами.
Это правило обобщается на произвольную длину последовательности.
Правило сложения (правило «или»). Оно утверждает, что, если элемент A можно выбрать n способами, а элемент B можно выбрать m способами, то выбрать A или B можно n + m способами.
Эти правила нужны и для решения задач.
Понятие факториал также рапространяется на ноль: 0! = 1, так как считается, что пустое множество можно упорядочить единственным способом.
Размещения, перестановки, сочетания
Пусть у нас есть множество из трех элементов . Какими способами мы можем выбрать из этих элементов два? .
Определение. Размещениями множества из различных элементов по элементов называются комбинации, которые составлены из данных элементов по элементов и отличаются либо самими элементами, либо порядком элементов.
Размещениями из n элементов по m (мест) называются такие выборки, которые имея по m элементов, выбранных из числа данных n элементов, отличаются одна от другой либо составом элементов, либо порядком их расположения.
Число размещений из n по m обозначается Anm и определяется по формуле
Anm =n·(n− 1)·(n− 2)·…·(n−m+ 1) =n!/(n − m)!
Число всех размещений множества из элементов по элементов обозначается через (от начальной буквы французского слова “arrangement”, что означает размещение), где и .
Теорема. Число размещений множества из элементов по элементов равно
Определение. Перестановкой множества из элементов называется расположение элементов в определенном порядке.
Так, все различные перестановки множества из трех элементов — это
Очевидно, перестановки можно считать частным случаем размещений при .
Число всех перестановок из элементов обозначается (от начальной буквы французского слова “permutation”, что значит “перестановка”, “перемещение”). Следовательно, число всех различных перестановок вычисляется по формуле
Похожие статьи:
poznayka.org
Размещения, перестановки, сочетания с повторениями. Формула включения – исключения | Учеба-Легко.РФ
Размещения с повторениями
Определение. Отображение множества первых натуральных чисел в данное множество , называется размещением с повторениями, составленным из данных элементов по .
Размещения с повторениями называются также конечными последовательностями.
Два размещения с повторениями одинаковы тогда и только тогда, когда на одинаковых местах находятся одни и те же элементы.
Если в размещении с повторениями некоторый элемент ставится в соответствие различным натуральным числам, т.е., иначе говоря, данный элемент занимает различных мест, то говорят, что этот элемент повторяется в размещении раз.
Пример. Всевозможные размещения с повторениями из трех элементов по 2:
Теорема. Число всевозможных размещений с повторениями из элементов по равно
Доказательство. По индукции. При теорема верна, так как сами элементы составляют всевозможные размещения элементов по одному, то число этих размещений равно .
Предположим, что число размещений с повторениями из элементов по равно . Составим из данных элементов всевозможные размещения с повторениями по элементу. Во всяком размещении с повторениями по элементу
первые элементов
образуют некоторое размещение с повторениями из по элементов. В качестве последнего -го элемента может быть взят любой из элементов. При различных выборах получаются различные размещения. Кроме того, два различные размещения -го порядка дают два различные размещения -го порядка.
Таким образом, число всех размещений -го порядка равно
Задача. Имеется различных книг, каждая в экземплярах. Сколькими способами может быть сделан выбор книг из числа данных?
Перестановки с повторениями
Всякое размещение с повторениями, в котором элемент повторяется раз, элемент повторяется раз и т.д. элемент повторяется раз, где , , , — данные числа, называется перестановкой с повторениями порядка
в которой данные элементы повторяются соответственно , , раз.
Теорема. Число различных перестановок с повторениями из элементов , в которых элементы повторяются соответственно раз, равно
Доказательство. Если мы будем считать все элементов перестановки с повторениями различными, то всего различных вариантов перестановок элементов — . Однако среди этих перестановок не все различны. В самом деле, все элементы мы можем переставлять местами друг с другом, и от этого перестановка не изменится. Точно так же, можем переставлять элементы , , , . Таким образом, всякая перестановка может быть записана способами. Следовательно, число различных перестановок с повторениями равно
Задача. Дано различных предметов. Сколькими способами можно разбить эти предметы на 3 группы так, чтобы первая группа содержала предметов, вторая предметов, а третья предметов?
Сочетания с повторениями
Определение. Если каждому элементу некоторого конечного множества поставлено в соответствие целое неотрицательное число — кратность данного элемента, то говорят, что задано сочетание с повторениями. Сумма кратностей всех элементов называется порядком сочетания.
Всякое сочетание с повторениями -го порядка, составленное из множества, содержащего элементов, называется также сочетанием с повторением из элементов по .
Если — кратности элементов , то по определению есть порядок сочетания
Теорема. Число сочетаний с повторениями из элементов по выражается формулой
Пример. В кондитерском магазине продавались 4 сорта пирожных: наполеоны, эклеры, песочные и картошка. Сколькими способами можно купить 7 пирожных?
Решение. Положим пирожные в коробку, а чтобы они не перепутались, разделим их картонными разделителями. Нужно 3 разделителя. Обозначения: 0 (картонки-разделители) и 1 — пирожные. Примерная покупка: 1110101101 — три наполеона, 1 эклер, 2 песочных и 1 картошка.
Итак два класса объектов 1 (7 штук) и 0 (3 штуки) — покупка — 10 объектов.
Два способа рассуждения:
(1) задача сводится к выбору мест для 7 пирожных (или для 3 разделителей) среди 10 объектов.
(2) другой способ рассуждения (эквивалентный). Надо разбить 10 мест на две группы: для 7 пирожных и 3 разделителей.
В чем особенность: объекты повторяются, причем один эклер на вкус неотличим от другого. Отсюда название: сочетания с повторениями. Можно представлять себе, что пирожные непрерывно пекут, так что они не переводятся, сколько ни ешь. Это совсем другая ситуация, чем в обычных сочетаниях!!!
Пусть заданы два числа: — число выбираемых элементов, и — число типов элементов, из которых производится выбор. Число сочетаний с повторениями из элементов типов равно числу способов выбора мест для собственно выбираемых элементов различных классов, или, что то же: для разделителей между ними.
Итак, основная формула:
Задача. Имеется одинаковых предметов. Сколькими способами можно распределить эти предметы между лицами?
Сочетания с повторениями с дополнительными условиями
Сколько существует сочетания с повторениями таких, что в них обязательно входят элементы фиксированных типов?
Сразу возьмем по одному элементу указанного типа, и тогда уже сразу окажутся заняты мест. Остальные мест можно заполнять элементами прежних типов.
В частности, пусть число типов — числа выбранных элементов. Сколько существует сочетаний с повторениями, так что представлены хотя бы по одному все типы элементов?
Пример. шаров размещаются по ящикам. Сколько существует способов разместить их так, что пустых ящиков нет?
Решение. Пусть нолики — шарики, а единички — стенки ящиков (потребуется единичек). Две единички сразу кладем по краям.
Теперь положим между ними шарики-нолики, а далее нужно заполнить некоторые промежутки между ними так, чтобы между любыми двумя ноликами находилась не более одной единички. Значит, из промежутков между шариками нужно
выбрать места для единичек. Всего таких способов .
Метод координат. Подсчет числа путей
Рассмотрим координатную сетку: двигаясь по ней, помечаем каждый перекресток — производим суммирование числа возможных путей, ведущих на каждый перекресток. Получаем известный треугольник Паскаля.
Поскольку на перекресток на уровне (считая сверху и принимая верхний уровень за нулевой) ведет путей (число способов выбрать движений направо вниз из общего числа движений вниз), то свойство суммирования путей на перекрестке можно записать как
По прежнему остается справедливым свойство симметрии .
Формула включения — исключения
Определение. Число элементов множества называется мощностью множества и обозначается .
Теорема. Пусть даны множества . Тогда количество элементов в объединении этих множеств можно найти по формуле:
Доказательство проводится по индукции. Пусть . Нужно доказать формулу
Действительно, множество состоит из всех элементов множества и тех элементов множества , которые не содержатся в множестве . Тогда, сложив количества элементов во множествах и , мы два
раза посчитаем количество элементов, общих для множеств и .
Предположим, что формула включения — исключения справедлива для множеств.
Докажем ее для множеств. Множество можно представить в виде
Тогда получаем (первое равенство по формуле включения — исключения для двух множеств):
Используя формулу
и формулу включения — исключения для множеств, получаем
В эту формулу подставляем выражение, полученное ранее, и теорема доказана.
uclg.ru