сколькими способами можно рассадить 4 человек за одним столом
Рассадка гостей
Добрый вечер! У меня есть задача:
Несколько человек садятся за круглый стол. Будем считать, что два способа рассадки совпадают, если каждый человек имеет одних и тех же соседей в обоих случаях. Сколькими различными способами можно посадить четырех человек? А семь человек? Во скольких случаях два данных человека из семи оказываются соседями? Во скольких случаях данный человек (из семи) имеет двух данных соседей?
Мой вариант решения для 4-х гостей: 4*3*2*1 Это же неправильно? Расскажите пожалуйста как это делать? Спасибо!
Добавлено через 16 часов 37 минут
Никто не подскажет?((
Перебор вариантов приглашения гостей на день рождения
Добрый день Прошу помочь в решении. День бьюсь, не могу понять пока решения. Задача следующая.
Распределение (рассадка) сотрудников по рабочим местам
Приветствую всех гением, спасите мой мозг! Не давно столкнулся с такой проблемой: Есть excel файл с.
Задача про гостей
Задача: представьте, что вы намерены пригласить к себе шестерых гостей, но за вашим столом могут.
Скрипт IP гостей сайта
Подскажите что в index.php дописать что бы в текстовый документ записывались ip гостей сайта и.
Решение
и для n = 2 окончательно
решения:
для 4-х гостей:
kristi1, Возьмем рассадку A. В нее приходит человек и создает n новых рассадок, пусть это будет множество RA. Все они разные с точки зрения соседства.
Теперь возьмем другую рассадку B (она отличается от A). Снова приходит этот тип и создает множество RB. Но не факт, что множества RA и RB не пересекаются, т.е. что нет одинаковых с точки зрения соседства. Т.е. я просто не знаю, как это доказывать.
Плюс, мои результаты не совпадают с результатами 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 минуты
Кажется, можно доказать, что если какие-то рассадки из RA и RB совпадают, то совпадают и A с B
Методическая разработка «УЧИМСЯ РЕШАТЬ ЗАДАЧИ ПО КОМБИНАТОРИКЕ»
УЧИМСЯ РЕШАТЬ ЗАДАЧИ ПО КОМБИНАТОРИКЕ
Перестановками называют комбинации, состоящие из одних и тех же различных объектов и отличающиеся только порядком их расположения. Количество всех возможных перестановок выражается формулой
Отличительной особенностью перестановок является то, что в каждой из них участвует ВСЁ множество, то есть, все объектов.
Сколькими способами можно рассадить 5 человек за столом?
Решение : используем формулу количества перестановок:
Ответ : 120 способами
Сколько четырёхзначных чисел можно составить из четырёх карточек с цифрами 0, 5, 7, 9?
В учебниках обычно даётся лаконичное и не очень понятное определение сочетаний, поэтому, в моих устах формулировка будет не особо рациональной, но, надеюсь, доходчивой:
Сочетаниями называют различные комбинации из объектов, которые выбраны из множества
различных объектов, и которые отличаются друг от друга хотя бы одним объектом. Иными словами, отдельно взятое сочетание – это уникальная выборка из
элементов, в которой не важен их порядок (расположение). Общее же количество таких уникальных сочетаний рассчитывается по формуле
.
В ящике находится 15 деталей. Сколькими способами можно взять 4 детали?
В задаче речь идёт о выборке из 4-х деталей, в которой не имеет значения их «дальнейшая судьба» – грубо говоря, «просто выбрали 4 штуки и всё». Таким образом, у нас имеют место сочетания деталей. Считаем их количество:
способами можно взять 4 детали из ящика.
Ещё раз: что это значит? Это значит, что из набора 15-ти различных деталей можно составить одну тысячу триста шестьдесят пять уникальных сочетания 4-х деталей. То есть, каждая такая комбинация из 4-х деталей будет отличаться от других комбинаций хотя бы одной деталью.
Ответ : 1365 способами
Формуле необходимо уделить самое пристальное внимание, поскольку она является «хитом» комбинаторики. При этом полезно понимать и без всяких вычислений записывать «крайние» значения:
. Применительно к разобранной задаче:
– единственным способом можно взять ни одной детали;
способами можно взять 1 деталь (любую из 15-ти);
способами можно взять 14 деталей (при этом какая-то одна из 15-ти останется в ящике);
– единственным способом можно взять все пятнадцать деталей.
Сколькими способами из колоды в 36 карт можно выбрать 3 карты?
Боря, Дима и Володя сели играть в «очко». Сколькими способами им можно сдать по одной карте? (колода содержит 36 карт)
Решение : здесь важно не только то, какие три карты будут извлечены из колоды, но и то, КАК они будут распределены между игроками. По формуле размещений:
способами можно раздать 3 карты игрокам.
Есть и другая схема решения, которая, с моей точки зрения, даже понятнее:
способами можно извлечь 3 карты из колоды.
КП, 9Ч, 7Ч;
КП, 7Ч, 9Ч;
9Ч, КП, 7Ч;
9Ч, 7Ч, КП;
7Ч, КП, 9Ч;
7Ч, 9Ч, КП.
И аналогичный факт справедлив для любого уникального набора из 3-х карт. А таких наборов, не забываем, мы насчитали .
Найденное количество сочетаний следует умножить на шесть:
способами можно сдать по одной карте 3-м игрокам.
В студенческой группе 23 человека. Сколькими способами можно выбрать старосту и его заместителя?
Правило сложения и правило умножения комбинаций
Студенческая группа состоит из 23 человек, среди которых 10 юношей и 13 девушек. Сколькими способами можно выбрать 2-х человек одного пола?
Решение : в данном случае не годится подсчёт количества сочетаний , поскольку множество комбинаций из 2-х человек включает в себя и разнополые пары.
Условие «выбрать 2-х человек одного пола» подразумевает, что необходимо выбрать двух юношей или двух девушек, и уже сама словесная формулировка указывает на верный путь решения:
способами можно выбрать 2-х юношей;
способами можно выбрать 2-х девушек.
Таким образом, двух человек одного пола (без разницы – юношей или девушек) можно выбрать: способами.
Сколько существует трёхзначных чисел, которые делятся на 5?
Решение : для наглядности обозначим данное число тремя звёздочками: ***
Комбинации будем считать по разрядам – слева направо :
В разряд сотен можно записать любую из цифр (1, 2, 3, 4, 5, 6, 7, 8 или 9). Ноль не годится, так как в этом случае число перестаёт быть трёхзначным.
А вот в разряд десятков («посерединке») можно выбрать любую из 10-ти цифр: .
По условию, число должно делиться на 5. Число делится на 5, если оно заканчивается на 5 либо на 0. Таким образом, в младшем разряде нас устраивают 2 цифры.
Итого, существует : трёхзначных чисел, которые делятся на 5.
При этом произведение расшифровывается так: «9 способами можно выбрать цифру в разряд сотен и 10 способами выбрать цифру в разряд десятков и 2 способами в разряд единиц »
Или ещё проще: « каждая из 9-ти цифр в разряде сотен комбинируется с каждой из 10-ти цифр разряда десятков и с каждой из двух цифр в разряде единиц ».
Практическое занятие на тему «Основные комбинаторные конфигурации»
Практическое занятие (2ч.)
Тема: Основные комбинаторные конфигурации .
научить применять комбинаторные конфигурации при решении задач;
сформировать умение находить нужную комбинаторную формулу при решении задачи;
формирование самостоятельности студента на занятии.
Математика / приложение к газете «Первое сентября», №15, 2004 г.
Стойлова Л.П. Математика.-М.: Изд. Центр Академия, 1997.
Прикладная комбинаторная математика.
Вариативная самостоятельная работа.
Повторение основных формул необходимых при решении комбинаторных задач.
Размещения с повторениями.
Задача 1. Сколько различных четырехзначных чи сел можно составить из цифр 2, 6, 7, 8 и 9, если каждая цифра может входить в комбинацию несколько раз?
Решение. Здесь порядок цифр существенен (2678 или 6278 — это разные числа). Поэтому имеем дело с кортежем длины 4 (четырехзначное число), каждый элемент которого можно выбрать пятью способами (цифр дано пять). Поэтому число различных комби наций равно 4 5 = 1024.
Задача 2. На референдуме предложены четыре вопроса, на которые надо ответить «да» или «нет». Сколько есть возможностей заполнения бюллетеня (на все вопросы надо дать ответ)?
Решение. Получаем кортеж длины 4 (столько во просов в бюллетене), каждый элемент может быть вы бран двумя способами («да» или «нет»). Поэтому число различных возможностей равно 2 4 =16.
Задача 3 . Неудовлетворенные решением Париса Гера, Афина и Афродита обратились к трем мудре цам с просьбой назвать прекраснейшую из них. Каж дый из мудрецов высказал свое мнение. Сколько мог ло возникнуть вариантов ответа на поставленный во прос у этой тройки?
Решение. Здесь вновь кортеж длиной 3 (три муд реца), каждый элемент которого может быть выбран шестью способами. Поэтому число различных возмож ностей равно 6 3 = 216.
Задача 5. На железнодорожной станции имеется я семафоров. Сколько может быть дано различных сигналов при помощи этих семафоров, если каждый семафор имеет три состояния: горит либо зеленый, либо желтый, либо красный свет.
Задачи для домашней работы
Сколько букв русского алфавита можно зако дировать, используя лишь комбинации точек и тире, содержащие только три знака?
Переплетчик должен переплести 12 различных книг в красный, зеленый и коричневый переплеты. Сколькими способами он может это сделать?
Задача 1. Из спортивного клуба, насчитывающего 30 членов, надо составить команду из четырех чело век для участия в эстафете на 100 + 200 + 400 + 800 (м). Сколькими способами это можно сделать?
Решение. Имеем кортежи длиной 4. Ни один элемент не может входить дважды (один бегун на один отрезок дистанции). Значит,
А 4 30 = =27·28·29·30 = 657 720.
Решение. Имеем кортежи длиной 3 (у треугольника три вершины). Ни один элемент не может входить дважды. Значит,
А 3 5=
Задачи для домашней работы
Сколько всего различных пятизначных чисел, не содержащих нуля?
В классе изучают девять предметов. Скольки ми способами можно составить расписание на поне дельник, если в этот день должно быть шесть разных уроков?
Перестановка без повторений.
Задача 1. Сколькими способами можно перестав лять друг с другом цифры 1, 2, 3 и 4?
Задача 2. За столом пять мест. Сколькими спосо бами можно рассадить пятерых гостей?
Задача 3. У Лены есть восемь разных красок. Она хочет написать ими слова «Новый Год». Сколькими способами она может это сделать, если каждая буква должна быть раскрашена одним цветом и все восемь букв должны быть разными по цвету?
Перестановка с повторениями.
Задача 1. У мамы два яблока и три груши. Каж дый день в течение пяти дней она дает сыну по одно му фрукту. Сколькими способами это может быть сделано?
Решение. Р(2, 3) = 10.
Задача 2. Сколькими способами можно положить 28 различных открыток в четыре одинаковых кон верта так, чтобы в каждом конверте было по семь открыток?
Решение. Пометим конверты цифрами 1, 2, 3 и 4. Тогда число различных раскладок равно
Р(7, 7, 7,7)=.
Сотрем пометки. Теперь конверты можно произволь но переставлять друг с другом, не меняя результата раскладки (теперь они неотличимы друг от друга). Так как число различных перестановок четырех кон вертов равно
Р 4 = 4!, то число различных раскладок уменьшается в
Р 4 = 4! раз и поэтому оно равно
Ответ:
Задачи для домашней работы
Сколько различных слов можно получить, пе реставляя буквы слова «ингредиент»?
Сколькими способами можно посадить за круг лый стол пять мужчин и пять женщин так, чтобы никакие два лица одного пола не сидели рядом?
Автомобильные номера состоят из четырех цифр и трех букв. Найдите число таких номеров, если используются 32 буквы русского алфавита.
Сочетание с повторениями.
Задача 1. В кондитерском отделе продаются пи рожные четырех сортов: наполеоны, эклеры, песочные и слоеные. Сколькими способами можно купить семь пирожных?
Решение. Здесь рассматриваются сочетания с по вторениями из 4 (четыре вида пирожных) по 7 (столько пирожных покупают). Значит,
Ответ: 120 способов.
Задача 2. В почтовом отделении продают открыт ки 10 видов. Сколькими способами можно купить в нем 12 открыток?
Решение. Здесь рассматриваются сочетания с по вторениями из 10 по 12. Имеем
Сочетания без повторений.
Задача 1. Сколькими способами в игре «Спортло то» можно выбрать шесть номеров из 49?
Решение. Здесь рассматриваются сочетания без повторения (одно число может быть по правилам игры выбрано не более одного раза) из 49 по 6.
Решение. Здесь рассматриваются сочетания без повторений.
Задача 3. Дама сдавала в багаж семь предметов, Все они оказались украденными, но два каких-либо (по ее выбору) ей согласились поискать. Сколько у нее есть возможностей выбрать два любимых предме та?
Задача 4. В прошлые века процветала генуэзская лотерея, сохранившаяся в некоторых странах и поныне. Участники этой лотереи покупали билеты, на которых стояло число от 1 до 90. Можно было ку пить и билеты, на которых было сразу 2, 3, 4 и 5 чисел. В день розыгрыша лотереи из мешка, содержащего жетоны с числами от 1 до 90, вынимали пять жетонов. Выигрывали те, у которых все номера на билетах были среди вынутых. Если участник лотереи покупал билет с одним из чисел, то он получал при выигрыше в 15 раз больше стоимости билета; если с двумя числами (амбо), то в 270 раз больше, если с тремя числами (терн) – в 5500 раз больше, если в четырьмя числами (катерн) – 75000 раз больше, а если с пятью числами (квин) – в 1000 000 раз больше, чем стоит билет. Каково отношение «счастливых» билетов при игре, когда участник купил билет с одним числом?
Решение. Общее число исходов находится из формулы сочетаний без повторений:
С 5 90 =
Если участник купил билет с одним номером, то для выигрыша необходимо, чтобы один из вынутых номеров совпал с номером на билете. Остальные 4 номера могут быть благоприятными. Но эти 4 номера выбираются из оставшихся 89 номеров. Поэтому число благоприятных комбинаций к общему числу комбинаций равно
Ответ:
Задачи для домашней работы
Сочетайте, каково отношение «счастливых» билетов при игре, когда участник купил билет с двумя числами.
Сколькими способами можно составить набор из восьми пирожных, если имеется четыре сорта пирожных?
В классе имеется шесть сильных математиков. Сколькими способами из них можно составить команду на районную олимпиаду по математике, если от класса можно послать команду из четырех человек?
Методические указания для выполнения практической работы «Решение задач по комбинаторике».
Министерство образования и науки Самарской области
Государственное бюджетное образовательное
учреждение среднего профессионального образования
«Тольяттинский политехнический техникум»
Зам. директора по УР
__ _________ 20__ г.
для выполнения практической работы №1
«Решение задач по комбинаторике»
дисциплина Теория вероятностей и математическая статистика
специальностей: 09.02.06 Сетевое и системное администрирование
09.02.07 Информационные системы и программирование
от ___ _____20__ № ____
Руководитель УПО №2
________ Л.Г. Светличная
Методические указания разработаны Захаровой С.В. – преподавателем
математических дисциплин ГБПОУ СО «ТПК».
Методические указания предназначены для студентов второго курса дневного отделения специальностей 09.02.06 «Сетевое и системное администрирование», 09.02.07 «Информационные системы и программирование». Методические указания составлены в соответствии с рабочей программой и могут быть использованы с целью формирования практических умений и навыков при изучении темы «Комбинаторика».
Практическая работа №1
Тема: «Решение задач по комбинаторике»
В результате выполнения практической работы студент должен:
Краткие теоретические сведения
1 а) Перестановки По определению, считают, что 0!=1,1!=1.
б) Перестановки с повторениями
Пример 1. Сколько слов можно получить, переставляя буквы в слове ГОРА?
1) Что делаем с буквами (меняем местами – значит перестановки)
2) Повторяются ли буквы (нет – значит перестановки без повторения)
Решение.
Пример 2. Сколько слов можно получить, переставляя буквы в слове ИНСТИТУТ?
1) Что делаем с буквами (меняем местами – значит перестановки)
2) Повторяются ли буквы (да – значит перестановки с повторениями)
2 а) Сочетания
б) Сочетания с повторениями
Пример 1. Сколькими способами из колоды в 36 карт можно выбрать 3 карты?
2) Порядок важен? (нет – значит сочетания)
3) Повторяться могу? (нет – значит сочетания без повторений)
Решение.
Пример 2. В кондитерском магазине продавались 4 сорта пирожных: наполеоны, эклеры, песочные и картошка. Сколькими способами можно купить 7 пирожных?
2) Порядок важен? (нет – значит сочетания)
3) Повторяться могу? (да – значит сочетания с повторениями)
3 а) Размещения
б) Размещения с повторениями
Пример 1. Сколько различных 3-х значных цифр можно составить из 2,4,6,8, если цифры не повторяются?
2) Порядок важен? (да – значит размещения)
3) Цифры повторяются (нет)
Решение.
Пример 2. Сколько различных 3-х значных цифр можно составить из 2,4,6,8?
2) Порядок важен? (да – значит размещения)
3) Цифры повторяются (да – значит размещения с повторениями)
Решение.
Образец решения задач
Перестановки, сочетания и размещения без повторения
1. Сколько четырёхзначных чисел можно составить из четырёх карточек с цифрами 1, 5, 7, 9?
2. Сколько трёхзначных чисел можно составить из четырёх карточек с цифрами 1, 5, 7, 9, если цифры не повторяются?
3. Сколькими способами из колоды в 36 карт можно выбрать 3 карты?
4. Сколькими способами из колоды в 36 карт можно выбрать 1 даму и 2 туза?
5. Сколькими способами можно рассадить 6 человек за столом?
6. Сколькими способами можно рассадить 3 мальчика и 3 девочки за столом?
7. Сколькими способами можно рассадить в 2 ряда 3 мальчика и 3 девочки?
8. Студенческая группа состоит из 23 человек, среди которых 10 юношей и 13 девушек. Сколькими способами можно выбрать 2-х человек одного пола?
9. У Васи дома живут 4 кота.
а) сколькими способами можно рассадить котов по углам комнаты?
б) сколькими способами можно отпустить гулять котов?
в) сколькими способами Вася может взять на руки 2-х котов (одного
на левую, другого – на правую)?
10. Группу из 20 студентов нужно разделить на 3 бригады, причем в первую бригаду должны входить 3 человека, во вторую — 5 и в третью — 12. Сколькими способами это можно сделать.
11. Для участия в команде тренер отбирает 5 мальчиков из 10. Сколькими способами он может сформировать команду, если 2 определенных мальчика должны войти в команду? (2 мальчика точно входят, т.е. осталось выбрать 3 из 8)
12. В шахматном турнире принимали участие 15 шахматистов, причем каждый из них сыграл только одну партию с каждым из остальных. Сколько всего партий было сыграно в этом турнире?
13. Сколько различных дробей можно составить из чисел 3, 5, 7, 11, 13, 17 так, чтобы в каждую дробь входили 2 различных числа?
14. Имеется 3 фрукта. Сколькими способами можно взять хотя бы один фрукт?
Перестановки, сочетания и размещения с повторениями
15. Алексей занимается спортом, причём 4 дня в неделю – лёгкой атлетикой, 2 дня – силовыми упражнениями и 1 день отдыхает. Сколькими способами он может составить себе расписание занятий на неделю?
16. Сколькими способами можно расставить белые фигуры (2 ладьи, 2 коня, 2 слона, ферзь и король) на первой линии шахматной доски?
17. В кошельке находится достаточно большое количество рублей, 2-х, 5-ти и десятирублёвых монет. Сколькими способами можно извлечь три монеты из кошелька?
18. В коробке лежат шары трех цветов—красного, синего и зеленого. Шары одного цвета считаются одинаковыми. Вопрос: сколькими способами можно составить набор из двух шаров?
19. Возьмем буквы Б, А, Р. Какие размещения из этих букв, взятых по две, можно получить? Сколько таких наборов получиться, если: 1) буквы в наборе не повторяются; 2) буквы могут повторяться?
1)
2)
20. Сколько существует четырёхзначных пин-кодов?
Задания для самостоятельного решения
Практическая работа №1
Тема: «Решение задач по комбинаторике»
3. Сколькими способами можно разместить восемь пассажиров в три вагона?
4. Из учащихся пяти 11 классов нужно выбрать двоих дежурных. Сколько пар дежурных можно составить (ученики в паре не должны быть из одного класса)?
5. Сколько различных двузначных чисел можно составить при помощи цифр 4, 7, 9? (Цифры в записи числа не повторяются).
6. Сколько различных трёхзначных чисел можно составить с помощью цифр 1, 3, 7?
7. Саша, Петя, Денис, Оля, Настя часто ходят в кафе. Каждый раз, обедая там, они рассаживаются по-разному. Сколько дней друзья смогут это сделать без повторения?
8. Секретный замок состоит из 3 барабанов, на каждом из которых можно выбрать цифры от 0 до 9. Сколько различных вариантов выбора шифра существует?
10. В начале игры каждому игроку раздается 6 карт из колоды, в которой 36 различных карт. Сколько существует различных комбинаций карт, которые игрок может получить в начале игры?
11. В 8 “а” классе лучше всех математику знают 5 учеников: Вася, Дима, Олег, Катя и Аня. На олимпиаду по математике нужно отправить пару, состоящую из 1 мальчика и 1 девочки. Сколькими способами учительница может эту пару выбрать?
12. На прививку в медпункт отправились 7 друзей. Сколькими разными способами они могут встать в очередь у медицинского кабинета?
14. В лифт 12-этажного дома сели 3 пассажира. Каждый независимо от других с одинаковой вероятностью может выйти на любом (начиная со 2-го) этаже. Сколькими способами люди могут выйти на разных этажах?
15. Сколько нечетных трёхзначных чисел можно составить из цифр 3, 4, 8, 6? (Цифры в записи числа не могут повторяться).
1 Формулы комбинаторики: перестановки, размещения и сочетания с повторениями и без.