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

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

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

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

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

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

Я так понял, что расставить их надо в ряд (а не по кругу).
Давайте австрийцев обозначим за А, болгар – за Б, неизвестных – за Н.
Найдём количество «шаблонов» из 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.

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

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

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

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

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

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

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

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

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

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

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

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

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