СПРОСИ ПРОФИ
👍
−1
👎 -19

Комбинаторика: способ рассадки людей на плацу

В нашем распоряжении 9 человек, в том числе двух национальностей: трое(3) австрийцев и четверо(4) болгар. То бишь остальные двое(2) неизвестной национальности.
Сколькими способами можно рассадить этих 9 человек так, чтобы ни одна из этих двух национальностей не сидели в паре возле себя?
Каждый человек различим.

дискретная математика высшая математика математика обучение     #1   16 фев 2022 20:47   Увидели: 35 клиентов, 336 специалистов   Ответить
👍
0
👎 0

как я решил это, но мне кажется что слишком просто...

все возможности 9!
когда Австралиец сидит возле себя 3! * 6!
когда Болгар сидит возле себя 4! * 5!
когда не сидит ни австралиец ни болгар 9! — (3! * 6!) — (4! * 5!) = 355680

  #2   16 фев 2022 21:02   Ответить
👍
+2
👎 2

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

👍
−1
👎 -1

На счёт второго, думал будет правильно так как запрещены комбинации АБАБ и БАБА но может быть АБДАБ где Д — человек неизвестной национальности.

  #4   16 фев 2022 22:28   Ответить
👍
+1
👎 1

Я так понял, что расставить их надо в ряд (а не по кругу).
Давайте австрийцев обозначим за А, болгар – за Б, неизвестных – за Н.
Найдём количество «шаблонов» из 9 символов А, Б, Н, где каждого символа нужное количество и ни один символ не стоит два раза подряд. Тогда итоговый ответ будет равен количеству таких шаблонов, умноженному на 2!, на 3! и на 4!, потому что чтобы получить ответ нужно выбрать шаблон, потом расставить неизвестных 2! способами, расставить австрийцев 3! способами и расставить болгар 4! способами.
Давайте будем считать различные шаблоны, где не стоят подряд два Б, но стоят подряд два А.
Обозначим за x количество таких шаблонов, где при этом первый и второй А стоят рядом, за y – где второй и третий А стоят рядом, за z – где все три А стоят рядом. Причём каждый интересующий нас шаблон входит либо только в первую из этих групп (шаблоны вида АА А), либо только во вторую (шаблоны вида А АА), либо во все три (шаблоны вида ААА).
Давайте обозначим за группу 0 символы до первого Б, за группу 1 – символы между первым и вторым Б, за группу 2 – между вторым и третьим Б, за группу 3 – между третьим и четвёртым Б, за группу 4 – после четвёртого Б. Заметим, что в рассматриваемых нами шаблонах группы 1, 2 и 3 должны быть не пустые.
Чтобы вычислить x, давайте мысленно склеим два первых А в шаблоне – в один (так как в этих шаблонах первые два А стоят подряд). Тогда x – это просто количество способов расставить два А и два Н по пяти группам так, что в группы 1, 2 и 3 попадёт хотя бы один символ. Для построения такого шаблона давайте сначала решим, сколько символов окажется в каждой группе, а потом назначим какой из этих символов является Н, а какой – А. Так как количество способов сделать второй шаг не зависит от выбора первого шага, то x будет равен произведению количества способов сделать первый шаг и количества способов сделать второй шаг. Количество способов сделать первый шаг – это количество способов распределить четыре символа по пяти группам так, что конкретные три группы должны оказаться непустыми. Давайте сразу положим по символу в те группы, которые должны оказаться непустыми, так как это всё равно придётся сделать. Значит количество способов сделать первый шаг равно количеству способов распределить оставшийся один символ в одну из пяти групп, это равно 5. Чтобы сделать второй шаг, нужно просто выбрать какие два из четырёх символов являются А, значит количество способов сделать второй шаг – это просто C_4_2 = 6. Таким образом x = 5 * 6 = 30.
Чтобы посчитать y, надо сделать всё то же самое, только склеивая мысленно второй и третий А, а не первый и второй. Получим, что y = x = 30.
Чтобы посчитать z, надо склеить все три А в один символ. Тогда z равно количеству способов расставить три символа по пяти группам, так чтобы три конкретные группы были непустыми (что конечно равно 1), умноженному на количество способов выбрать, какой из трёх символов является А (что конечно равно 3). Таким образом, z = 1 * 3 = 3.
Количество шаблонов, где Б не стоят подряд, а А – стоят, первого вида (АА А) равно x — z (те, что входят в x, но не входят в z). Аналогично, количество таких шаблонов второго вида (А АА) равно y — z. И количество таких шаблонов третьего вида (ААА) равно z. Значит количество шаблонов, где Б не стоят подряд, а А – стоят, равно x — z + y — z + z = x + y — z = 30 + 30 — 3 = 57.
Чтобы найти количество хороших шаблонов нужно вычесть полученное нами количество из общего количества шаблонов, где никакие Б не стоят подряд. Давайте обозначим последнее за t.
Найдём t с помощью тех же двух шагов: оно равно количеству способов расставить пять символов по пяти группам так, чтобы конкретные три группы были непустыми, умножить на количество способов выбрать из этих пяти символов три, которые будут являться А. Давайте опять же распределим три из пяти символов по одному в каждую непустую группу. Тогда количество способов сделать первый шаг равно количеству способов распределить оставшиеся два символа по пяти группам, при этом каждая группа может остаться пустой. Распределить n объектов по k возможно пустым группам – это известная задача, ответ на неё – C_n+k-1_n. В нашем случае это C_6_2 = 15. Количество способов сделать второй шаг – C_5_2 = 10. Итак, всего шаблонов, где два Б не стоят подряд – 15 * 10 = 150. Из них плохих – 57, значит хороших – 150 — 57 = 93.
Значит, ответ равен 93 * 2! * 3! * 4! = 26784.

👍
0
👎 0

Александр, здравствуйте.
Извиняюсь, мне кажется, у Вас ошибка где-то в расчёте числа шаблонов.
Соображения такие:
1) В симметричных шаблонах по центру А, с каждого края 2Б+A+Н, поэтому их всего 12.
2) Несимметричные шаблоны разбиваются на пары
Значит общее количество шаблонов должно быть чётным.

👍
+1
👎 1

В моём решении нигде не фигурировало общее количество шаблонов. Я считал количество шаблонов, где Б не стоят подряд, а затем вычел из него количество шаблонов, где Б не стоят подряд, а А – стоят.
Как я понял, вы написали про все шаблоны, которые есть. Если вы хотели написать про шаблоны, где ни А, ни Б не стоят подряд, то вместо числа 12 правильно было бы написать 5, и получается, что количество хороших шаблонов нечётно, что сходится с моим решением.

👍
0
👎 0

Я только что проверил на компьютере, хороших шаблонов 93, как я говорил.

👍
0
👎 0

Да, извиняюсь, Вы правы — про 12 это я дал маху.
Посчитал, действительно 93 получается.

👍
0
👎 0

1) На плацу можно по-разному расставлять людей.

2) Если считать, что речь идёт о расстановке в ряд.
Самое простое, что придумал.
Рассмотрим одного из неизвестных. Если его можно выгнать и пары не образуется — выгоняем. Если вокруг него австрийцы — назначаем его болгаром и наоборот.
После этого то же самое делаем со вторым.

В итоге получится одна из 4-ёх расстановок национальностей, причём она однозначно определяется по изначальной.
Дальше для каждого случая достаточно аккуратно посмотреть, где могли стоять неизвестные.

Задайте свой вопрос по высшей математике
профессионалам

Сейчас онлайн 75 репетиторов по высшей математике
Получите ответ профи быстро и бесплатно

Другие вопросы на эту тему:

👍
0
👎 06

Задачи по комбинаторике, про людей, карты и вынимание шаров из урны   6 ответов

В аудитории, состоящей из 8 рядов по 10 человек в каждом, случайным образом рассадили 20 человек. Найти вероятность того, что первый ряд окажется пустым.
В аудитории, состоящей из 8 рядов по 10 человек в каждом, случайным образом рассадили 50 человек. Найти вероятность того, что первый ряд окажется занят целиком.
В аудитории, состоящей из 8 рядов по 10 человек в каждом, случайным образом рассадили 40 человек. Найти вероятность того, что…

  26 сен 2021 11:45  
👍
0
👎 05

Комбинаторика: рассадка людей за столом   5 ответов

За длинным столом рассаживают p мужчин и q женщин.
Сколько есть возможных положений, где все мужчины сидят вместе?

Я взяла для примера 3-х мужчин и 2-х женщин, для того, чтобы было легче расписать всевозможные получающиеся комбинации.
И действительно получается 36 различных случаев рассадить мужчин рядом друг с другом, но вот формула p!*(q+1)! = 3!*3! = 36 хотя конечно же и правильная, только как-то тяжело логически усваивается у меня…
  20 июн 2017 16:27  
👍
0
👎 05

Комбинаторика   5 ответов

Лифт с 12 пассажирами может останавливаться на 16 этажах. Выходят группами по 3, 4 и 5 человек (не более одной группы на каждом этаже). Сколькими способами можно выбрать этажи?

  08 сен 2021 23:07  
👍
−1
👎 -13

Комбинаторика   3 ответа

В колледже студентов изучают математику или экономику. 200 человек – математику, 150 экономику. Сколько студентов в колледже, если

а) 20 студентов изучают оба предмета,

б) ни один из математиков не изучает экономику,

в) каждый экономист изучает математику?

  08 сен 2021 23:07  
👍
−1
👎 -13

Комбинаторика, отбор команды   3 ответа

Из 30 участников секции 16 играют в шашки, 18 — в шахматы, 9 — в шашки и в шахматы, остальные в нарды. Для участия в соревнованиях по трем видам отбирают трех человек. Сколько способов получить команду, в которой каждый умеет играть только в одну игру?

  08 сен 2021 18:03  
ASK.PROFI.RU © 2020-2022