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

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

В школьном курсе понятие «круговые перестановки» встречается в 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 Промежутков, в которые можно рассаживать вновь прибывших. Таким образом, это можно сделать

Источник

Комбинаторная задача. Способы рассадить людей за столом.

Сколькими способами можно рассадить гостей за столом
Здравствуйте еще раз. Неделю назад писал олимпиаду по программированию. И попалась такая задачка.

Сколькими способами можно рассадить 6 человек за столом по кругу
Добрый день. Есть задача: Сколькими способами можно рассадить 6 человек за столом: а) в ряд; б) по.

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

Сколькими способами можно рассадить за круглым столом 5 мужчин и 5 женщин?
Сколькими способами можно рассадить за круглым столом 5 мужчин и 5 женщин: 1) чтобы никакие два.

Решение

А какая разница: круг или ряд? Есть n мужчин и n женщин. Есть круглый стол с 2*n местами. Мы их (места) нумеруем. На парные места, например, садим мужчин.
Тогда, на 2-е место можно посадить одного из n мужчин, на 4-е — одного из n-1 мужчин, на 6-е — одного из n-2 мужчин, . на (2n-2)-е — одного из 2 мужчин, на 2n-е — последнего что останется.
Всего n*(n-1)*(n-2)*. *2*1=n!
Аналогично, для непарных мест и для женщин. Тоже n! способов.
Потом можно еще садить мужчин на непарные, а женщин на парные.
Всего 2*n!*n! способов.

Или я что-то не так понял в условии задачи?

Добавлено через 1 час 51 минуту
Понял. Имеется ввиду, что разные «рассадки» будут тогда, когда хотя бы у одного человека хотя бы один из соседей отличается. Тогда в случае, когда все пересядут на одно место вправо, будет та же «рассадка».
Тогда 2*n!*n!/n=2*n!*(n-1)!

Есть 10 людей ,где 1 жених ,1 невеста ,нужно рассадить 6 людей в ряд так , чтобы среди них были жених и невеста
сколько комбинаций ? я думал что ответ 1*1*7*6*5*4, но говорят ответ другой .

Сколькими способами можно рассадить этих людей?
3)среди 12 людей есть трое знакомых. Сколькими способами можно рассадить этих людей, чтобы знакомые.

Сколькими способами можно рассадить этих людей?
На скамейке сидит 14 человек, среди которых три семьи: Петренко (4 чел.), Васюки (3 чел.) и.

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

Определить количество сочетания людей за круглым столом
За столом сидят n кол-во магов(n — всегда четное). Вместе они выбирают себе по паре и одновременно.

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

Источник

Рассадка гостей

Добрый вечер! У меня есть задача:

Несколько человек садятся за круглый стол. Будем считать, что два способа рассадки совпадают, если каждый человек имеет одних и тех же соседей в обоих случаях. Сколькими различными способами можно посадить четырех человек? А семь человек? Во скольких случаях два данных человека из семи оказываются соседями? Во скольких случаях данный человек (из семи) имеет двух данных соседей?

Мой вариант решения для 4-х гостей: 4*3*2*1 Это же неправильно? Расскажите пожалуйста как это делать? Спасибо!

Добавлено через 16 часов 37 минут
Никто не подскажет?((

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

Распределение (рассадка) сотрудников по рабочим местам
Приветствую всех гением, спасите мой мозг! Не давно столкнулся с такой проблемой: Есть excel файл с.

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

Скрипт IP гостей сайта
Подскажите что в index.php дописать что бы в текстовый документ записывались ip гостей сайта и.

Решение

гостей всего — m
соседей у одного гостя — n (всегда равно 2)
разных пар двух соседей для одного гостя — число сочетаний из (m — 1) по n

и для n = 2 окончательно

решения:
для 4-х гостей:

в формуле не учитывается «сторона соседства» — «слева Маша, справа Даша» и «слева Даша, справа Маша» считаются одним вариантом.
очевидно, что количество способов рассадки при учёте «сторон соседства» будет вдвое большим.

kristi1, Возьмем рассадку A. В нее приходит человек и создает n новых рассадок, пусть это будет множество R_A. Все они разные с точки зрения соседства.
Теперь возьмем другую рассадку B (она отличается от A). Снова приходит этот тип и создает множество R_B. Но не факт, что множества R_A и R_B не пересекаются, т.е. что нет одинаковых с точки зрения соседства. Т.е. я просто не знаю, как это доказывать.
Плюс, мои результаты не совпадают с результатами Notortep, что наводит на мысль, что скорее всего я ошибаюсь

Добавлено через 43 минуты
Чтобы проверить свои предположения, обратился к эксперементу. Написал программку перебора.
Вот результат
F(3) = 1
F(4) = 3
F(5) = 12
F(6) = 60
F(7) = 360
F(8) = 2520
Выходит, моя формула правильная!
Правда и программа может содержать ошибки, но она такая простенькая!
Плюс совпадение для n=3, n=4 утешают.

Добавлено через 4 минуты
Кажется, можно доказать, что если какие-то рассадки из R_A и R_B совпадают, то совпадают и A с B

Источник