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

Мастер-класс по теме «Элементы комбинаторики: перестановки, сочетания и размещения»

Разделы: Математика

Элементы комбинаторики: перестановки, сочетания, размещения.

“Число, положение и комбинация – три
взаимно пересекающиеся, но различные
сферы мысли, к которым можно
отнести все математические идеи”.
Джозеф Сильвестр (1844 г.)

Образовательные:

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

Развивающие:

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

Воспитывающая:

  • формировать активность личности студента, умение работать в группе, отвечать за свои поступки.

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

I. Организационный момент

Сообщение целей и задач занятия: В связи с тем, что по дисциплине “Математика” на 2 курсе специальности “Технология деревообработки” на тему “Основные понятия комбинаторика: перестановки, размещения, сочетания” отводится 2 часа, а рассмотреть нужно много материала, решать задачи, создать проект, вам было выдано задание на внеаудиторную самостоятельную работу следующее: в литературе по истории математики, в энциклопедиях, в учебниках и в интернете найти материал о разделе математики, имеющем звучное название “комбинаторика”. Слайды № 1–2. Презентация

В календарно-тематическом плане по дисциплине “Математика” на 2 курсе специальности “Технология деревообработки” на тему “Основные понятия комбинаторика: перестановки, размещения, сочетания” отводится 2 часа. Изучить теоретический материал, решить задачи разных видов за такой временной промежуток невозможно. Для достижения глубокого изучения материала было выдано задание на внеаудиторную самостоятельную работу: в литературе по истории математики, в энциклопедиях, в учебниках и в интернете найти материал о разделе математики, имеющем звучное название “комбинаторика”. Слайды № 1–2.

Вопросов для внеаудиторной самостоятельной работы выделено было три:

  1. Определения комбинаторики.
  2. Ученые – математики — первооткрыватели этого раздела.
  3. Применение комбинаторики в современной жизни.

Запись даты, темы урока.

II. Работа над темой занятия

Из глубокой древности до современного человечества дошли сведения о том, что уже тогда люди занимались выбором объектов и расположения их в том или ином порядке и увлекались составлением различных комбинаций. Так, например, в Древнем Китае увлекались составлением квадратов, в которых заданные числа располагали так, что их сумма по всем горизонталям, вертикалям и главным диагоналям была одной и той же (современная игра – задача “Судоку”). Такие задачи вы могли встречать в журналах и газетах. В частности, наша Мариинская газета “Вперед” довольно часто предлагает читателям такие задачи. В Древней Греции подобные задачи возникали в связи c такими играми, как шашки, шахматы, домино, карты и т.д.

Комбинаторика ставится самостоятельным разделом математики, по сути – самостоятельной наукой лишь во второй половине XVII века, — в период, когда возникла теория вероятностей.

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

Комбинаторика – самостоятельная ветвь математической науки. Cлайд № 3

Термин “КОМБИНАТОРИКА” происходит от латинского слова “combina”, что в переводе на русский означает – “сочетать”, “соединять” — слайд № 4.

Как трактует это слово Большой Энциклопедический Словарь?

Комбинаторика – это раздел математики, в котором изучаются простейшие “соединения”: перестановки, размещения, сочетания. Этот раздел иначе называют “комбинаторный анализ”.

Сегодня мы будем рассматривать перестановки, размещения, сочетания, как соединения, как комбинаторные конфигурации.

Разделы комбинаторики: перечислительная, структурная, вероятностная, топологическая – слайд № 5.

Давайте вспомним известное вам из детства сказание о том, как богатырь или другой добрый молодец, доехав до развилки трех дорог, читает на камне: “Вперед поедешь – голову сложишь, направо поедешь – коня потеряешь, налево поедешь – меча лишишься”. А дальше уже говорится, как он выходит из того положения, в которое попал в результате выбора. Но выбирать разные пути или варианты приходится и современному человеку. Эти пути и варианты складываются в самые разнообразные комбинации. И целый раздел математики, именуемый КОМБИНАТОРИКОЙ, занят поисками ответов на вопросы: сколько всего есть комбинаций в том или ином случае, как из всех этих комбинаций выбрать наилучшую – слайд № 6.

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

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

Перестановки-соединения, которые можно составить из n предметов, меняя всеми возможными способами их порядок; число их

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

Число n при этом называется порядком перестановки – слайд № 7–10.

Произведение всех натуральных чисел от n до единицы, обозначают символом n! (Читается “эн — факториал”). Используя знак факториала, можно, например, записать:

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 данных, различающихся либо порядком предметов, либо самими предметами; число их.

В комбинаторике размещением называется расположение “предметов” на некоторых “местах” при условии, что каждое место занято в точности одним предметом и все предметы различны.

В отличие от сочетаний размещения учитывают порядок следования предметов. Так, например, наборы и являются различными, хотя состоят из одних и тех же элементов <1,2,3>(то есть, совпадают как сочетания).

Термин “Размещение” употребил впервые Якоб Бернулли в книге “Искусство предположений”.

Примеры решения задач:

Задача № 1. Сколько можно составить телефонных номеров из 6 цифр каждый, так чтобы все цифры были различны? Это пример задачи на размещение без повторений.

Размещаются здесь десять цифр по 6. Значит, ответ на выше поставленную задачу будет:

Задача № 2. В группе ТД – 21 обучается 24 студентов. Сколькими способами можно составить график дежурства по техникуму, если группа дежурных состоит из трех студентов?

Читать еще:  Дыхательная гимнастика Стрельниковой: уникальная методика оздоровления! Дыхательная гимнастика по Стрельниковой. Парадоксально, но эффективно

Решение: число способов равно числу размещений из 24 элементов по 3, т.е. равно А24 3 . По формуле находим

Ответ: 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.

10. Лютикас В.С. Факультативный курс по математике: Теория вероятностей, Москва, “ Просвещение”, 1990.

11. Гнеденко Б.В., Хинчин А.Я. Элементарное введение в теорию вероятностей. — 6-е изд. — М.: Наука, 1964.

12. Андреева Е. В. “Комбинаторные задачи”, Москва, “Чистые пруды”, 2005 г.

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

1. Элементы комбинаторики.

2. Общие правила комбинаторики.

3. Генеральная совокупность без повторений и выборки без повторений.

4. Применение графов (схем) при решении комбинаторных задач.

1. Комбинаторика и ее возникновение.

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

Комбинаторика возникла в XVI веке. В жизни привилегированных слоев тогдашнего общества большое место занимали азартные игры (карты, кости). Широко были распространены лотереи. Первоначально комбинаторные задачи касались в основном азартных игр: сколькими способами можно получить данное число очков, бросая 2 или 3 кости или сколькими способами можно получить 2-ух королей в некоторой карточной игре. Эти и другие проблемы азартных игр являлись движущей силой в развитии комбинаторики и далее в развитии теории вероятностей.

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

Теоретическое исследование вопросов комбинаторики предприняли в XVII веке французские математики Блез Паскаль и Ферма. Исходным пунктом их исследований были так же проблемы азартных игр.

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

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

2. Общие правила комбинаторики.

Правило суммы: Если некоторый объект А может быть выбран m способами, а объект В- k способами, то объект «либо А, либо В» можно выбрать m + k способами.

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

Распределим эти n шариков по двум ящикам: в первый- m шариков, во второй- k шариков. Произвольным образом из произвольно выбранного ящика вынимается 1 шарик. Сколькими способами это можно сделать?

Решение: Из первого ящика шарик можно вынуть m способами, из второго- k способами. Тогда всего способов m+k=n .

В морском семафоре каждой букве алфавита соответствует определенное положение относительно тела сигнальщика двух флажков. Сколько таких сигналов может быть?

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

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

1. Сколько двузначных чисел существует?

Решение: Число десятков может быть обозначено любой цифрой от 1 до 9. Число единиц может быть обозначено любой цифрой от 0 до 9. Если число десятков равно 1, то число единиц может быть любым (от 0 до 9). Таким образом, существует 10 двузначных чисел, с числом десятков- 1. Аналогично рассуждаем и для любого другого числа десятков. Тогда можно посчитать, что существует 9 *10 = 90 двузначных чисел.

2. Имеется 2 ящика. В одном лежит m разноцветных кубиков, а в другом- k разноцветных шариков. Сколькими способами можно выбрать пару «Кубик-шарик»?

Решение: Выбор шарика не зависит от выбора кубика, и наоборот. Поэтому, число способов, которыми можно выбрать данную пару равно m *k .

3. Генеральная совокупность без повторений и выборки без повторений.

Генеральная совокупность без повторений— это набор некоторого конечного числа различных элементов a1 , a2, a3, . an.

Читать еще:  Предмет и функции деловой этики. Деловая этика, определение, предмет, задачи принципы

Пример: Набор из n разноцветных лоскутков.

Выборкой объема k ( k n ) называется группа из m элементов данной генеральной совокупности.

Пример: Пестрая лента, сшитая из m разноцветных лоскутков, выбранных из данных n .

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

число размещений из n по k .

Число размещений из n по k можно определить следующим способом: первый объект выборки можно выбрать n способами, далее второй объект можно выбрать n -1 способом и т.д.

Преобразовав данную формулу, имеем:

Следует помнить, что 0!=1.

1. В первой группе класса А первенства по футболу участвует 17 команд. Разыгрываются медали: золото, серебро и бронза. Сколькими способами они могут быть разыграны?

Решение: Комбинации команд-победителей отличаются друг от друга составом и порядком следования элементов, т.е. являются размещениями из 17 по 3.

2. Научное общество состоит из 25-ти человек. Необходимо выбрать президента общества, вице-президента, ученого секретаря и казначея. Сколькими способами это можно сделать?

Решение: Комбинации руководящего состава общества отличаются друг от друга составом и порядком следования элементов, т.е. являются размещениями из 25 по 4.

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

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

Решение: Имеем перестановки из 5 элементов.

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

число сочетаний из n по k

Элементы каждого из сочетаний можно расставить способами. Тогда

1. Если в полуфинале первенства по шахматам участвует 20 человек, а в финал выходят лишь трое, то сколькими способам и можно определить эту тройку?

Решение: В данном случае порядок, в котором располагается эта тройка, не существенен. Поэтому тройки, вышедшие в финал, являются сочетаниями из 20 по 3.

Решение: В данном случае порядок, в котором располагается эта тройка, не существенен. Поэтому тройки делегатов являются сочетаниями из 10 по 3.

4. Применение графов (схем) при решении комбинаторных задач.

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

При составлении команд космического корабля учитывается вопрос и психологической совместимости участников путешествия. Необходимо составить команду космического корабля из 3 человек: командира, инженера и врача. На место командира есть 4 кандидата: a1, a2, a3, a4 . На место инженера- 3: b1, b2, b3. На место врача- 3: c1, c2, c3 . Проведенная проверка показала, что командир a1 психологически совместим с инженерами b1 и b3 и врачами c 1 и c3 . Командир a2 — с инженерами b1 и b2. и всеми врачами. Командир a3 — с инженерами b1 и b2 и врачами c 1 и c3 . Командир a4-со всеми инженерами и врачом c2. Кроме того, инженер b1 не совместим с врачом c3 , b2— с врачом c1 и b3— с врачом c2. Сколькими способами при этих условиях может быть составлена команда корабля?

Перестановки, размещения и сочетания. Формулы.

Чтобы в материале было легче ориентироваться, добавлю содержание данной темы:

Введение. Множества и выборки.

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

Для работы нам понадобятся кое-какие вспомогательные сведения. Начнём с такого фундаментального математического понятия как множество. Подробно понятие множества было раскрыто в теме «Понятие множества. Способы задания множеств».

Очень краткий рассказ про множества: показатьскрыть

Если вкратце: множеством именуют некую совокупность объектов. Записывают множества в фигурных скобках. Порядок записи элементов роли не играет; повторения элементов не допускаются. Например, множество цифр числа 11115555999 будет таким: $<1,5,9 >$. Множество согласных букв в слове «тигрёнок» таково: $<т, г, р, н, к>$. Запись $5in A$ означает, что элемент 5 принадлежит множеству $A=<1,5,9 >$. Количество элементов в конечном множестве называют мощностью этого множества и обозначают $|A|$. Например, для множества $A=<1,5,9 >$, содержащего 3 элемента, имеем: $|A|=3$.

Рассмотрим некое непустое конечное множество $U$, мощность которого равна $n$, $|U|=n$ (т.е. в множестве $U$ имеется $n$ элементов). Введём такое понятие, как выборка (некоторые авторы именуют её кортежем). Под выборкой объема $k$ из $n$ элементов (сокращённо $(n,k)$-выборкой) будем понимать набор элементов $(a_1, a_2,ldots, a_k)$, где $a_iin U$. Выборка называется упорядоченной, если в ней задан порядок следования элементов. Две упорядоченные выборки, различающиеся лишь порядком элементов, являются различными. Если порядок следования элементов выборки не является существенным, то выборку именуют неупорядоченной.

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

Для примера рассмотрим множество $U=$. Множество $U$ содержит 5 элементов, т.е. $|U|=5$. Выборка без повторений может быть такой: $(a,b,c)$. Данная выборка содержит 3 элемента, т.е. объём этой выборки равен 3. Иными словами, это $(5,3)$-выборка.

Выборка с повторениями может быть такой: $(a,a,a,a,a,c,c,d)$. Она содержит 8 элементов, т.е. объём её равен 8. Иными словами, это $(5,8)$-выборка.

Рассмотрим ещё две $(5,3)$-выборки: $(a,b,b)$ и $(b,a,b)$. Если мы полагаем наши выборки неупорядоченными, то выборка $(a,b,b)$ равна выборке $(b,a,b)$, т.е. $(a,b,b)=(b,a,b)$. Если мы полагаем наши выборки упорядоченными, то $(a,b,b)neq(b,a,b)$.

Рассмотрим ещё один пример, немного менее абстрактный 🙂 Предположим, в корзине лежат шесть конфет, причём все они различны. Если первой конфете поставить в соответствие цифру 1, второй конфете – цифру 2 и так далее, то с конфетами в корзине можно сопоставить такое множество: $U=<1,2,3,4,5,6>$. Представьте, что мы наугад запускаем руку в корзинку с целью вытащить три конфеты. Вытащенные конфеты – это и есть выборка. Так как мы вытаскиваем 3 конфеты из 6, то получаем (6,3)-выборку. Порядок расположения конфет в ладони совершенно несущественен, поэтому эта выборка является неупорядоченной. Ну, и так как все конфеты различны, то выборка без повторений. Итак, в данной ситуации говорим о неупорядоченной (6,3)-выборке без повторений.

Теперь подойдём с иной стороны. Представим себе, что мы находимся на фабрике по производству конфет, и на этой фабрике производятся конфеты четырёх сортов. Множество $U$ в этой ситуации таково: $U=<1,2,3,4 >$ (каждая цифра отвечает за свой сорт конфет). Теперь вообразим, что все конфеты ссыпаются в единый жёлоб, около которого мы и стоим. И, подставив ладони, из этого потока отбираем 20 конфет. Конфеты в горсти – это и есть выборка. Играет ли роль порядок расположения конфет в горсти? Естественно, нет, поэтому выборка неупорядоченная. Всего 4 сорта конфет, а мы отбираем двадцать штук из общего потока – повторения сортов неизбежны. При этом выборки могут быть самыми различными: у нас даже могут оказаться все конфеты одного сорта. Следовательно, в этой ситуации мы имеем дело с неупорядоченной (4,20)-выборкой с повторениями.

Рассмотрим ещё пару примеров. Пусть на кубиках написаны различные 7 букв: к, о, н, ф, е, т, а. Эти буквы образуют множество $U=<к,о,н,ф,е,т,а>$. Допустим, из данных кубиков мы хотим составить «слова» из 5 букв. Буквы этих слов (к примеру, «конфе», «тенко» и так далее) образуют (7,5)-выборки: $(к,о,н,ф,е)$, $(т,е,н,к,о)$ и т.д. Очевидно, что порядок следования букв в такой выборке важен. Например, слова «нокфт» и «кфтон» различны (хотя состоят из одних и тех же букв), ибо в них не совпадает порядок букв. Повторений букв в таких «словах» нет, ибо в наличии только семь кубиков. Итак, набор букв каждого слова представляет собой упорядоченную (7,5)-выборку без повторений.

Читать еще:  Компенсация за неиспользованный отпуск при работе. Расторжение трудового договора

Еще один пример: мы составляем всевозможные восьмизначные числа из четырёх цифр 1, 5, 7, 8. Например, 11111111, 15518877, 88881111 и так далее. Множество $U$ таково: $U=<1,5,7,8>$. Цифры каждого составленного числа образуют (4,8)-выборку. Порядок следования цифр в числе важен, т.е. выборка упорядоченная. Повторения допускаются, поэтому здесь мы имеем дело с упорядоченной (4,8)-выборкой с повторениями.

Размещения без повторений из $n$ элементов по $k$

Так как элементы в рассматриваемой выборке повторяться не могут, то мы не можем отобрать в выборку больше элементов, чем есть в исходном множестве. Следовательно, для таких выборок верно неравенство: $n≥ k$. Количество размещений без повторений из $n$ элементов по $k$ определяется следующей формулой:

Запись «n!» (читается «эн факториал») обозначает произведение всех чисел от 1 до n, т.е.

$$ n!=1cdot2cdot 3cdot ldotscdot n $$

По определению полагается, что $0!=1!=1$. Для примера найдём 5!:

$$ 5!=1cdot 2cdot 3cdot 4cdot 5=120. $$

Алфавит состоит из множества символов $E=<+,*,0,1,f>$. Определим количество таких трёхсимвольных слов в этом алфавите, которые не содержат повторяющихся букв.

Под трёхсимвольными словами будем понимать выражения вида «+*0» или «0f1». В множестве $E$ пять элементов, поэтому буквы трехсимвольных слов образуют (5,3)-выборки. Первый вопрос: эти выборки упорядочены или нет? Слова, которые отличаются лишь порядком букв, полагаются различными, поэтому порядок элементов в выборке важен. Значит, выборка является упорядоченной. Второй вопрос: допускаются повторения или нет? Ответ на этот вопрос даёт условие: слова не должны содержать повторяющихся букв. Подводим итоги: буквы каждого слова, удовлетворяющего условию задачи, образуют упорядоченную (5,3)-выборку без повторений. Иными словами, буквы каждого слова образуют размещение без повторений из 5 элементов по 3. Вот примеры таких размещений:

Нас же интересует общее количество этих размещений. Согласно формуле (1) количество размещений без повторений из 5 элементов по 3 будет таким:

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

Размещения с повторениями из $n$ элементов по $k$

Количество размещений с повторениями из $n$ элементов по $k$ определяется следующей формулой:

Сколько пятизначных чисел можно составить из множества цифр $<5,7,2>$?

Из данного набора цифр можно составить пятизначные числа 55555, 75222 и так далее. Цифры каждого такого числа образуют (3,5)-выборку: $(5,5,5,5,5)$, $(7,5,2,2,2)$. Зададимся вопросом: что это за выборки? Во-первых, цифры в числах могут повторяться, поэтому мы имеем дело с выборками с повторениями. Во-вторых, порядок расположения цифр в числе важен. Например, 27755 и 77255 – разные числа. Следовательно, мы имеем дело с упорядоченными (3,5)-выборками с повторениями. Общее количество таких выборок (т.е. общее количество искомых пятизначных чисел) найдём с помощью формулы (2):

Следовательно, из заданных цифр можно составить 243 пятизначных числа.

Перестановки без повторений из $n$ элементов

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

Эту формулу, кстати, легко получить, если учесть, что $P_n=A_^$. Тогда получим:

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

Пусть первому мороженому соответствует цифра 1, второму – цифра 2 и так далее. Мы получим множество $U=<1,2,3,4,5>$, которое будет представлять содержимое морозилки. Порядок съедения может быть таким: $(2,1,3,5,4)$ или таким: $(5,4,3,1,2)$. Каждый подобный набор есть (5,5)-выборка. Она будет упорядоченной и без повторений. Иными словами, каждая такая выборка есть перестановка из 5 элементов исходного множества. Согласно формуле (3) общее количество этих перестановок таково:

Следовательно, существует 120 порядков выбора очередности съедения.

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

Общее количество перестановок с повторениями определяется формулой:

Слова составляются на основе алфавита $U=$. Сколько различных слов из семи символов может быть составлено, если в этих словах буква «a» должна повторяться 2 раза; буква «b» – 1 раз, а буква «d» – 4 раза?

Вот примеры искомых слов: «aabdddd», «daddabd» и так далее. Буквы каждого слова образуют (3,7)-выборку с повторениями: $(a,a,b,d,d,d,d)$, $(d,a,d,d,a,b,d)$ и т.д. Каждая такая выборка состоит из двух элементов «a», одного элемента «b» и четырёх элементов «d». Иными словами, $k_1=2$, $k_2=1$, $k_3=4$. Общее количество повторений всех символов, естественно, равно объёму выборки, т.е. $k=k_1+k_2+k_3=7$. Подставляя эти данные в формулу (4), будем иметь:

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

Сочетания без повторений из $n$ элементов по $k$

Общее количество сочетаний без повторений из $n$ элементов по $k$ определяется формулой:

В корзине размещены карточки, на которых написаны целые числа от 1 до 10. Из корзины вынимают 4 карточки и суммируют числа, написанные на них. Сколько различных наборов карточек можно вытащить из корзины?

Итак, в данной задаче исходное множество таково: $U=<1,2,3,4,5,6,7,8,9,10>$. Из этого множества мы выбираем четыре элемента (т.е., четыре карточки из корзины). Номера вытащенных элементов образуют (10,4)-выборку. Повторения в этой выборке не допускаются, так как номера всех карточек различны. Вопрос вот в чём: порядок выбора карточек играет роль или нет? Т.е., к примеру, равны ли выборки $(1,2,7,10)$ и $(10,2,1,7)$ или не равны? Тут нужно обратиться к условию задачи. Карточки вынимаются для того, чтобы потом найти сумму элементов. А это значит, что порядок карточек не важен, так как от перемены мест слагаемых сумма не изменится. Например, выборке $(1,2,7,10)$ и выборке $(10,2,1,7)$ будет соответствовать одно и то же число $1+2+7+10=10+2+1+7=20$. Вывод: из условия задачи следует, что мы имеем дело с неупорядоченными выборками. Т.е. нам нужно найти общее количество неупорядоченных (10,4)-выборок без повторений. Иными словами, нам нужно найти количество сочетаний из 10 элементов по 4. Используем для этого формулу (5):

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

Сочетания с повторениями из $n$ элементов по $k$

Общее количество сочетаний с повторениями из $n$ элементов по $k$ определяется формулой:

Представьте себе, что мы находимся на конфетном заводе, – прямо возле конвейера, по которому движутся конфеты четырёх сортов. Мы запускаем руки в этот поток и вытаскиваем двадцать штук. Сколько всего различных «конфетных комбинаций» может оказаться в горсти?

Если принять, что первому сорту соответствует число 1, второму сорту – число 2 и так далее, то исходное множество в нашей задаче таково: $U=<1,2,3,4>$. Из этого множества мы выбираем 20 элементов (т.е., те самые 20 конфет с конвейера). Пригоршня конфет образует (4,20)-выборку. Естественно, повторения сортов будут. Вопрос в том, играет роль порядок расположения элементов в выборке или нет? Из условия задачи следует, что порядок расположения элементов роли не играет. Нам нет разницы, будут ли в горсти располагаться сначала 15 леденцов, а потом 4 шоколадных конфеты, или сначала 4 шоколадных конфеты, а уж потом 15 леденцов. Итак, мы имеем дело с неупорядоченной (4,20) выборкой с повторениями. Чтобы найти общее количество этих выборок используем формулу (6):

Следовательно, общее количество искомых комбинаций равно 1771.

Источники:

http://urok.1sept.ru/%D1%81%D1%82%D0%B0%D1%82%D1%8C%D0%B8/595703/
http://www.sites.google.com/site/teoriaveroyatnosti/teoria/elementy-kombinatoriki
http://math1.ru/education/raznoe/combinatorics.html

Ссылка на основную публикацию
Статьи на тему:

Adblock
detector