Способы рассадки, комбинаторика

[xolodec]

Задача:
Есть три англичанина, три француза, три турка.
Сколькими способами можно посадить их на одну скамью так, чтобы никакие ДВА соотечественника не сидели рядом?

Решение
Пусть
$N(a) $ - количество способов, при котором пара соотечественников сидит рядом
$N(b) $ - количество способов, при котором тройка соотечественников сидит рядом

Тогда решение выражается следующей формулой (по ответу):

$$ N(a'_1, a'_2, a'_3) = N - C^1_3 N(a) + C^2_3 N(a,a) + C^1_3 N(b) - N(a,a,a) - C^1_3 C^1_2 N(b,a) + C^2_3 N(b,b) + $$

$$ + C^1_3 N(b,a,a) - C^1_3 N(b,b,a) + N(b,b,b) $$

где $N$ - общее количество перестановок из 9 человек, а, допустим, $N(b,b,a)$ - количество случаев, когда вместе рядом сидят три соотечественника, еще одна тройка других соотечественников сидит рядом и еще одна пара третьих соотечественников сидит ряодм.

Вопрос:
Я никак не могу понять, почему формула включений-исключений в этой задаче такая странная ? Никак не могу сообразить, как правильно понимать в задаче, что из чего нужно вычитать ?
Обычно с этой формулой все просто, есть набор свойств $a_1, a_2, a_3$ которыми предмет может обладать или не обладать. и формула принимает вид

$$ N(a'_1, a'_2, a'_3) = N - N(a_1) - N(a_2) - N(a_3) + N(a_1, a_2) + N(a_2, a_3) + N(a_1, a_3) - N(a_1, a_2, a_3) $$

Однако в этой задаче все сложнее, потому что в $N(b_1) $ входят случаи $N(a_1) $ и наоборот.
Помогите распутаться, пожалуйста.

[function]

А элементарные рассуждения с правилом произведения разве здесь не помогут?

[xolodec]

Нет, не должны помочь, потому что здесь каждое событие включено в какое либо.
Или, по крайней мере, я не представляю как можно в этой задаче обойтись только правилом произведения.

[provincialka]

1. Что считается разными рассадками? Различимы ли между собой соотечественники, или нам нужно расставить просто буквы АААФФФТТТ?

2. Обозначения ваши не очень четко описаны. Во-первых, у вас в скобках одна буква, а в формуле -- по две и по три. Например,

xolodec в сообщении #984066 писал(а):

$N(b,b,a)$ - количество случаев, когда вместе рядом сидят три соотечественника, еще одна тройка других соотечественников сидит рядом и еще одна пара третьих соотечественников сидит рядом.

Здесь имеется в виду, что "по три" и "по два" могут сидеть любые национальности?

3. Вы сами придумали так распределять случаи? Система выглядит слегка запутанной.

-- 02.03.2015, 12:33 --

А нельзя сделать так. Посадим трех англичан (1 способ) между и рядом с ними есть 4 места, куда можно посадить французов. Сколько способов?
Сидит 6 человек, между и рядом с ними 7 мест, чтобы посадить турок. Сколько способов?

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

[xolodec]

provincialka в сообщении #984613 писал(а):

1. Что считается разными рассадками? Различимы ли между собой соотечественники, или нам нужно расставить просто буквы АААФФФТТТ?

Национальности и соотечественники различимы между собой. То есть количество всех способов рассадки одной тройки и одной пары $N(b,a) = 3! \cdot 2! \cdot 6! \cdot C^2_3 $ - то есть $N(b,a)$ включает случаи, когда вместе сидят две тройки и две двойки.

provincialka в сообщении #984613 писал(а):

2. Обозначения ваши не очень четко описаны. Во-первых, у вас в скобках одна буква, а в формуле -- по две и по три. Например, xolodec в сообщении #984066

писал(а):
$N(b,b,a)$ - количество случаев, когда вместе рядом сидят три соотечественника, еще одна тройка других соотечественников сидит рядом и еще одна пара третьих соотечественников сидит рядом. Здесь имеется в виду, что "по три" и "по два" могут сидеть любые национальности?

Да, конечно! "по три" и "по два" могут сидеть любые национальности, количество таких выборов по два и по три определяется коэффициентом $C^1_3$ в формуле

xolodec в сообщении #984066 писал(а):

Тогда решение выражается следующей формулой (по ответу):

$$ N(a'_1, a'_2, a'_3) = N - C^1_3 N(a) + C^2_3 N(a,a) + C^1_3 N(b) - N(a,a,a) - C^1_3 C^1_2 N(b,a) + C^2_3 N(b,b) + $$

$$ + C^1_3 N(b,a,a) - C^1_3 N(b,b,a) + N(b,b,b) $$

То есть $C^1_3$ способом мы можем выбрать национальность, в которой будет двойка, а остальные национальности сядут по три.

provincialka в сообщении #984613 писал(а):

3. Вы сами придумали так распределять случаи? Система выглядит слегка запутанной.

Нет, не сам. Это задача из сборника Виленкина. Решение там представляется следующее:

Его то я и пытаюсь понять, но не выходит.

provincialka в сообщении #984613 писал(а):

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

Хороший способ. Получится $ 3! \cdot A^3_4 \cdot A^3_7 = 30240 $. Странно, но решение Виленкина приводит к $187 344 $ способам, если я не ошибся в вычислении длинной формулы из его решения.

[xolodec]

Может кто нибудь объяснить логику Виленкина? Я правда не могу понять, согласно какой логике он производит рассадку и включения-исключения.
Почему его решение не совпадает с тем, которое напрашивается, если рассмотреть рассадку соотечественников с пробелами между ними?
Оригинальная формулировка (слово в слово) задачи звучит так: сколькими способами можно посадить рядом 3 англичан, 3 французов, 3 турок таким образом, чтобы никакие два соотечественника не сидели рядом.
Может я просто что то в формулировке изначального условия в этой теме упустил.

[ex-math]

provincialka в сообщении #984613 писал(а):

А нельзя сделать так

Нет, так не выйдет, потому что между двумя англичанами может так никто и не вклиниться. По идее, Ваше решение должно давать завышенный результат.

[provincialka]

ex-math
Точно. Может, тогда так.
1. Сажаем англичан
2. Сажаем французов. Рассматриваем два случая
а) есть англичане рядом (одна пара, больше не получится). Между ними сажаем турка и рассаживаем двух оставшихся.
б) нет англичан рядом. Рассаживаем трех турок.

[ex-math]

provincialka
Могут быть и все англичане рядом, а французы по бокам. Турками потом разделить.
Гадкая задача. Похоже, упростить решение Виленкина не получится.

[svv]

Кстати, фамилии персонажей — Bertrand, Williams, Dubois, Güneş, Taylor, Yılmaz, Moreau, Johnson, Akbulut.

[xolodec]

ex-math в сообщении #985109 писал(а):

упростить решение Виленкина не получится.

А почему все-таки формула включений-исключений в этой задаче принимает такой вид?
Я понимаю, что наверное это плохо спрашивать таким образом, но мне правда очень хочется понять эту задачу, понять принцип, по которому Виленкин ставит $+$ или $-$ перед очередным количеством случаев.

svv в сообщении #985121 писал(а):

Bertrand, Williams, Dubois, Güneş, Taylor, Yılmaz, Moreau, Johnson, Akbulut.

А откуда, если не секрет, это достоверно известно?

[svv]

Для информации. Обозначим национальность первого сидящего цифрой 1, второго сидящего цифрой 2, оставшуюся цифрой 3. Существует всего $29$ вариантов правильного чередования национальностей, начинающихся с 12 (т.е. каждая встречается три раза и соседние национальности разные):
121231323 121232313 121312323 121313232 121321323 121323123
121323132 121323213 121323231 123121323 123123123 123123132
123123213 123123231 123131232 123132123 123132132 123132312
123132321 123212313 123213123 123213132 123213213 123213231
123231213 123231231 123231312 123231321 123232131

Существует $6$ способов сопоставить цифрам 1 и 2 различные национальности из множества {А,Ф,Т} (тем самым и национальность 3 определится). Поэтому существует $29\cdot 6=174$ варианта правильной расстановки национальностей, т.е. букв А,Ф,Т.

При каждой расстановке букв можно $6$ способами рассадить англичан, $6$ способами французов и $6$ способами турок. Поэтому всего способов расстановки $174\cdot 6^3=37584$. Это ответ задачи.

Страшная формула с факториалами из Виленкина мне непонятна ни с какой точки зрения.
Я набрал в WolframAlpha выражение
9!-9*2!*8!+27(2!)^2*7!+3*3!*7!-(2!)^3*6!-18*3!*2!*6!+3*(3!)^2*5!+27*3!*(2!)^2*5-9*(3!)^2*2!*4!+(3!)^4
(посмотрите, может, ошибся при наборе с Вашего скана?)
WolframAlpha выдал 112824.
Но ведь это число, не говоря о том, что оно слишком большое (треть от $9!$), даже на $6^3=216$ не делится! А, по-моему, должно.

xolodec в сообщении #985178 писал(а):

А откуда, если не секрет, это достоверно известно?

Да, мне это известно достоверно, только никак обосновать я это не могу.
Обратите внимание, что фамилии хорошо различимы и сразу видно, кто есть кто.

[provincialka]

xolodec в сообщении #985178 писал(а):

А почему все-таки формула включений-исключений в этой задаче принимает такой вид?

Формула очень длинная. Попробую объяснить кусочек.
$N$ -- общее количество рассадок
$N(a)$ -- число рассадок, при которых два человека одной национальности сидят рядом. При этом национальность можно выбрать любую из трех, поэтому $N(a)$ умножается на $C_3^1$.
При вычитании этих случаев мы вычтем по два раза те рассадки, где две национальности сидят попарно или одна, но трое радом. В обоих случаях есть две пары, и мы посчитаем их дважды. Поэтому надо вернуть их количество. Этим "занимаются" два следующих слагаемых "с плюсом".

Ну и дальше рассуждения аналогичны. Лень читать.

[grizzly]

svv в сообщении #985183 писал(а):

посмотрите, может, ошибся при наборе

в третьем слагаемом справа стоит 5 вместо 5!
У ТС это было правильно посчитано.

[svv]

grizzly, спасибо.
Но тем хуже для ответа из книги!
Ведь таких расстановок букв АААФФФТТТ, в которых хотя бы две одинаковые стоят рядом, гораздо больше ($1506$), чем таких, где одинаковые рядом не стоят ($174$). Всего различных расстановок $1680$. Умножив на количество способов разместить англичан, французов и турок, «вписываясь» в уже заданную расстановку национальностей ($216$), получим $362880=9!$ — это для проверки. Т.е. среди всех перестановок 9 персон те, которые удовлетворяют условиям, составляют лишь около 10%, но никак не половину.