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

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

В школьном курсе понятие «круговые перестановки» встречается в 7 классе в учебнике по алгебре в разделе «Для тех, кому интересно» [3].

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

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

Из истории комбинаторики

Комбинаторика занимается различного вида соединениями, которые можно образовать из элементов конечного множества. Некоторые элементы комбинаторики были известны в Индии еще во II в. до н. э. Индийцы умели вычислять числа, которые сейчас называют “сочетания”. В ХII в. Бхаскара вычислял некоторые виды сочетаний и перестановок. Предполагают, что индийские ученые изучали соединения в связи с применением их в поэтике, науке о структуре стиха и поэтических произведениях. Например, в связи с подсчетом возможных сочетаний ударных (долгих) и безударных (кратких) слогов стопы из п слогов. Как научная дисциплина, комбинаторика сформировалась в Х V II в. В книге “Теория и практика арифметики” (1656 г.) французский автор Андре Таке также посвящает сочетаниям и перестановкам целую главу.

Б. Паскаль в “Трактате об арифметическом треугольнике” и в “Трактате о числовых порядках” (1665 г.) изложил учение о биномиальных коэффициентах. П. Ферма знал о связях математических квадратов и фигурных чисел с теорией соединений. Термин “комбинаторика” стал употребляться после опубликования Лейбницем в 1665 г. работы “Рассуждение о комбинаторном искусстве”, в которой впервые дано научное обоснование теории сочетаний и перестановок. Изучением размещений впервые занимался Я. Бернулли во второй части своей книги “Аг s соп j ес t ап d i” (искусство предугадывания) в 1713 г. Современная символика сочетаний была предложена разными авторами учебных руководств только в ХIХ в [4].

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

Каждое расположение элементов множества в определенном порядке называют перестановкой. Рассмотрим задачу: В турнире четверо участников. Сколькими способами могут быть распределены места между ними?

Будем рассуждать в соответствии с правилом умножения. Первое место может занять любой из четырех участников. При этом второе место может занять любой из трех оставшихся, третье любой из двух оставшихся, а на четвертом месте останется последний участник. Значит, места между участниками могут быть распределены 4 ۰ 3 ۰ 2 ۰ 1 = 24 способами. Решив задачу, мы фактически подсчитали число перестановок для множества из четырех элементов. Рассуждая точно так же, можно показать, что для множества из пяти элементов число перестановок равно 5 ۰ 4 ۰ 3 ۰ 2 ۰ 1, а для множества из десяти элементов это число равно 10 ۰ 9 ۰ 8 ۰ 7 ۰ б ۰ 5 ۰ 4 ۰ 3 ۰ 2 ۰ 1.

Вообще если множество содержит п элементов, то число перестановок равно произведению п(п – 1)(п – 2) ۰…۰ 2 ۰ 1. Множители в этом произведении можно записать в обратном порядке: 1 ۰ 2 ۰ . ۰ (п – 2)(п – 1)п.

Такие произведения бывают очень длинными и часто выражаются огромными числами. Однако в математике есть специальный символ для их обозначения. Произведение всех натуральных чисел от 1 до п обозначают п! (читают: «п факториал»). Значение выражения п! можно найти для любого натурального числа п (при этом считают, что 1! = 1).

Факториалы растут удивительно быстро. Можно понаблюдать за их изменением, рассмотрев таблицу, в которой приведены факториалы чисел от 1 до 10:

Источник

Глава 10. Комбинаторика. Комбинаторные конфигурации

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

Число всех функций (при отсутствии ограничений), или число всех возможных способов разместить П Предметов по Т Ящикам называется, Числом размещений И обозначается U(M,N).

Каждый из N предметов можно разместить M способами.

При игре в кости бросаются две кости и выпавшие на верхних гранях очки скла­дываются. Какова вероятность выбросить 12 очков? Каждый возможный исход соответствует функции F: <1,2>® <1,2,3,4,5,6>(аргумент — номер кости, ре­зультат — очки на верхней грани). Таким образом, всего возможно U(6,2) = 62 = 36 различных исходов. Из них только один (6 + 6) дает двенадцать очков. Вероятность 1/36.

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

Число инъективных функций, или число всех возможных способов разместить П Предметов по M ящикам, не более чем по одному в ящик, называется Числом размещений без повторений И обозначается А(M, п) или [M]n, или (M)n.

ТЕОРЕМА

Ящик для первого предмета можно выбрать M способами, для второго — M — 1 способами, и т. д. Таким образом,

По определению считают, что А(Т, N) = 0 при П > Т И А(Т, 0) = 1.

В некоторых видах спортивных соревнований исходом является определение участников, занявших первое, второе и третье места. Сколько возможно раз­личных исходов, если в соревновании участвуют П Участников? Каждый воз­можный исход соответствует функции F: <1,2,3>® <1..N> (аргумент — номер призового места, результат — номер участника). Таким образом, всего возможно А(П,3) = П(П — 1)(N — 2) различных исходов.

Число взаимнооднозначных функций, или Число перестановок п Предметов, обо­значается Р(П).

Последовательность E = (E1. Em) непустых подмножеств множества Е (E Ì 2E, Ei Ì Е, Ei ¹ Æ) называется Цепочкой В Е, Если

Цепочка E называется Полной Цепочкой в Е, Если |E| = |Е|. Сколько существует полных цепочек? Очевидно, что в полной цепочке каждое следующее подмноже­ство Ei+1 получено из предыдущего подмножества Ei Добавлением ровно одного элемента из Е И, таким образом, |E1| = 1, |E2| = 2, . |Ет| = |Е| = т. Следова­тельно, полная цепочка определяется порядком, в котором элементы Е Добавля­ются для образования очередного элемента полной цепочки. Отсюда количество полных цепочек — это количество перестановок элементов множества Е, Рав­ное M!.

Число строго монотонных функций, или число размещений П Неразличимых предметов по Т Ящикам, не более чем по одному в ящик, то есть число способов выбрать из m ящиков N ящиков с предметами, называется Числом сочетаний И обозначается С(Т, п) или или .

ТЕОРЕМА

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

2. Число сочетаний является числом строго монотонных функций, потому что строго монотонная функция F: 1..п ® L..M определяется набором своих значений, причем 1£ F(1) M.

В начале игры в домино каждому играющему выдается 7 костей из имеющихся 28 различных костей. Сколько существует различных комбинаций костей, которые игрок может получить в начале игры? Очевидно, что искомое число равно числу 7-элементных подмножеств 28-элементного множества. Имеем:

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

Число монотонных функций, или число размещений N неразличимых предме­тов по M ящикам, называется Числом сочетаний с повторениями И обозначается V(M, N).

Сколькими способами можно рассадить N Вновь прибывших гостей среди M Го­стей, уже сидящих за круглым столом? Очевидно, что между то сидящими за круглым столом гостями имеется M Промежутков, в которые можно рассаживать вновь прибывших. Таким образом, это можно сделать

Источник

Теоретическая часть

Лабораторная работа №1. Случайные события

«Классическое определение вероятности. Основные формулы комбинаторики».

Теоретическая часть.

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

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

Р(А)=

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

Перестановки отличаются друг от друга только порядком входящих в них элементов. Количество перестановок из n элементов:

Пример 1: Сколькими способами можно рассадить 10 человек за круглым столом, если имеет значение только порядок соседей.

Отметим, что вращение людей вокруг стола не меняет их взаимного расположения, поскольку соседи справа и слева остаются прежними. Если место за столом уникально, то существует 10! Способов рассадить людей за столом. Существует 10 вращений вокруг стола, поэтому делим на 10 и получаем 9! Способов рассадить людей за круглым столом, если значение имеет только порядок соседей.

Пусть М – множество, состоящее из n элементов.

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

Число размещений из n по m элементов:

Пример 2: Сколько различных четырехзначных чисел можно образовать из цифр 1, 2, …, 9, если все цифры различны.

Сочетанием из n элементов по m или неупорядоченной (n,m)­­– выборкой, называется любое подмножество множества M, состоящее из m элементов.

Надо заметить, что количество сочетаний отличается от числа размещений количеством перестановок каждого сочетания, то есть

Пример 3: Сколько существует вариантов выбора 5 карт трефовой масти из колоды, состоящей из 54 карт.

В колоде имеется 13 треф, из которых выбирается 5, поэтому

Пусть множество М разбито на k таких различных типов, что имеется n₁ неразличимых объектов типа 1, n₂ неразличимых объектов типа 2, и, вообще, n_i неразличимых объектов типа i (i=1,2,3,…,k), тогда количество различных размещений элементов множества:

Пример 4: Сколькими способами можно расставить на полке 12 книг, из которых 4 одинаковых учебника по математике, 6 одинаковых по информатике, 2 одинаковых по химии.

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

– количество размещений из n элементов по m с повторениями.

– количество сочетаний из n элементов по m с повторениями.

Пример 5: Сколько различных четырехзначных чисел можно образовать из цифр 1, 2, …, 9.

Так как нет ограничения на повторение цифр, то существует

Теорема: Если необходимо выбрать хотя бы по одному объекту из n по m с повторением, то количество различных сочетаний равно

Пример 6: Если в булочной продается 10 видов различных пончиков, то сколькими способами можно выбрать 12 пончиков.

Поскольку 12 пончиков выбираются из 10 видов с повторениями, то

Пример 7: Если в булочной продается 10 видов различных пончиков, то сколькими способами можно выбрать 12 пончиков, если необходимо выбрать хотя бы по одному пончику каждого вида .

Поскольку 12 пончиков выбираются из 10 видов с повторениями, то

Пример 8: Найдем количество различных решений уравнения

, где каждое слагаемое в левой части – неотрицательное число.

Это эквивалентно вопросу о том, сколько существует выборок вида

, где имеется объектов типа и

, но количество таких выборок — это количество различных сочетаний из 25 элементов по 5 элементов с повторениями. Итак, существуют

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

Чтобы создать программный модуль:

1. Введите выражение, которое будет находится слева от знака присваивания (имя функции);

2. Вызовите на экран панель Programming (программирование);

3. Нажмите на кнопку Add line[1] необходимое число раз;

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

Для подсчета факториала необходимо организовать цикл. В среде MathCad это можно сделать с помощью оператора for и ранжирванной переменной, которая пробегает некоторое множество значений.

Фрагмент документа MathCad для подсчета факториала приведен ниже.

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

Пример решения задачи на подсчет вероятности в среде МathCad:

Источник