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

[ex-math]

Но 187344 не делится на 216. Значит, неправильно посчитано.

[grizzly]

В формуле Виленкина досадная опечатка. В пятом слагаемом точно так же, как и в третьем, и в точности по тем же причинам, должен быть (но пропущен) множитель $(C_3^2)^3=27$. Всего делов-то. Но сама логика рассуждений вполне зачётная. Ответ у svv правильный.

PS. Я вот всегда ругаюсь, когда кто-то решает и не доводит до окончательного ответа. Это, как минимум, означает, что не была сделана проверка на правдоподобие.

[ex-math]

Мне кажется, что рассуждения Виленкина можно упростить, если не различать людей одной национальности. Тогда можно будет получить 174 и останется лишь умножить на 216.

[grizzly]

Если не вникать в методологию учебных задач и не смотреть в сторону обобщений, то в случае:

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

если не различать людей одной национальности.

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

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

[xolodec]

grizzly в сообщении #985343 писал(а):

В формуле Виленкина досадная опечатка

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

Для информации. Обозначим национальность первого сидящего цифрой 1, второго сидящего цифрой 2, оставшуюся цифрой 3. Существует всего $29$ вариантов правильного чередования национальностей, начинающихся с 12 (т.е. каждая встречается три раза и соседние национальности разные)

Спасибо ВСЕМ огромное! В самой задаче, благодаря Вам, разобрался.
Спасибо еще раз!

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

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

Вот это я как раз и не могу понять.

Цитата:

При вычитании этих случаев мы вычтем по два раза те рассадки, где две национальности сидят попарно или одна, но трое радом.

Мы также вычтем трижды не только эти случаи, но и, как минимум:
- событие $aaa$, то есть все случаи, когда три пары сидят рядом
- событие $bbb$
Также дважды вычитаем все случаи: $aa, baa$.

Как нужно думать, что бы самостоятельно составить такую формулу включений и исключений?
Обычные рассуждения, приводимые для обычного случая формулы включений - исключений, здесь не годятся:

$$N(a'_1a'_2a'_3b'_1b'_2b'_3) = N - 3N(a) - 3N(b) +3N(aa) + 9N(ab) + 3N(bb) - N(aaa) - 9N(abb) - 9N(aab) - N(bbb) + $$

$$+ 3N(aaab) + 9N(aabb) +3N(abbb) - 3N(aaabb) - 3N(aabbb) + N(aaabbb)$$

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

[ex-math]

grizzly
Согласен, короче не получится.

[grizzly]

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

Как нужно думать, что бы самостоятельно составить такую формулу включений и исключений?

Мне, наверное, проще всех здесь ответить на этот вопрос -- задачи на включения/исключения (да и подобные комбинаторные вообще) я последний раз решал лет 20 тому и, естественно, ничего не помнил, кроме общих принципов. (Тему не люблю, а разобраться решил исключительно из уважения к Автору книги.)

Какое-то базовое понимание техники / методики всё же необходимо -- надеюсь, об этом речь в Вашем вопросе не идёт. Мой ответ не претендует на универсальную полезность, поэтому под катом.

(Ход решения)

С первого подхода мне показалось, что вообще в такой сумасшедшей формуле можно потерять повторы / утроения и т.п. Я решил проверить это на примерах попроще, которые можно легко перепроверить в уме или с карандашом. Взял 2 национальности по 2 человека. Решается просто и быстро получилось, что всё как у Автора. Потом взял 2 по 3. Разобравшись с этим, я уже понял, как для подобных вариантов работают включения/исключения и вернувшись к задаче убедился, что в решении ничего не потеряно и не добавлено лишнего (в плане перечисления пунктов). Когда рассматривал вариант 2 по 3, обнаружил, что в этом варианте слагаемое, аналогичное пятому, не участвует (оно уже было учтено в качестве третьего слагаемого) и сразу понял (из соображений симметрии), что в нём чего-то не хватает.

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

[xolodec]

grizzly
Спасибо Вам большое, я попробую так, как Вы сказали. Думаю, что разберусь. Очень постараюсь

[xolodec]

Вы знаете, я уже бьюсь 4 день с этой задачей, исписал целую стопку листов, запутывался и распутывался много много раз, но пришел в конце концов к тому, что задачу с 2 национальностями (по 3 человека в каждой) я также не могу сам себе обосновать.
Я знаю формулу, согласно которой выражается решение, но обьяснить ее не могу.
Пусть всего вариантов $6! = 720$
Понятно, что нужно вычесть из этих вариантов все, в которых есть хотя бы одна пара. Таких вариантов $C^1_2N(a) = C^1_2 C^2_3 2! 5! = 1440$
Понятно также, что $N(a) = C^2_3 2! 5! = 720$, то есть число всех возможных перестановок, таких, что существует хотя бы одна пара точно такое же, как и общее количество перестановок всех элементов ($6! = 720$). Сразу же кажется, что это не так, потому что существуют две перестановки, в которых нет пары
ФАФАФА, АФАФАФ.
Кроме того, число $N(a)$ при делении на $3!3!$ должно давать число способов, которыми можно рассадить 2 национальности по три человека (люди внутри национальности неразличимы) причем так, чтобы была хотя бы одна пара. Как хорошо видно, $720 / 36 = 20$, а число вышеупомянутых способов равно 16.
Я наткнулся на это через 4 дня и 10 исписанных страниц. И пока не могу это объяснить.
Я также не могу объяснить, почему число $6! - C^1_2N(a) + N(a,a) = 144 $ больше, чем правильный ответ на исходный вопрос (всего 72 возможности такой рассадки). Ведь это значит, что мы не вычли чего то? но чего мы не вычли?

[provincialka]

Внимательно не проверяла, но вы тройки учли?

[ex-math]

Когда Вы считаете "хотя бы одну пару", некоторые перестановки считаются дважды (те, где есть тройки).
Ответ не тот, потому что надо учесть тройки и тройку-пару.

[grizzly]

xolodec
Приведите, пожалуйста, полную запись формулами ответа для задачи "2 национальности по 2 человека". Вы её решили?

[xolodec]

grizzly в сообщении #987143 писал(а):

Приведите, пожалуйста, полную запись формулами ответа для задачи "2 национальности по 2 человека". Вы её решили?

Да, конечно, решил.
$N(a'_1, a'_2) = N! - C^1_2 N(a) + N(a,a) = 4! - 2\cdot 2! \cdot 3! + 2^3 = 8$
Могу даже сказать, как выглядит формула для двух национальностей по 3 человека.
$N! - C^1_2 N(a) + N(a,a) - C^1_2~N(b,a) + C^1_2~N(b) + N(b,b) $
Эта формула дает правильный ответ в 72 способа.

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

Внимательно не проверяла, но вы тройки учли?

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

Когда Вы считаете "хотя бы одну пару", некоторые перестановки считаются дважды (те, где есть тройки)

Случай $N(a)$ подсчитывает перестановку всех возможных вариантов из $A_2AFF'F''$, где за $A_2$ обозначена пара $A'A''$. В этих перестановках действительно есть повторяющиеся, потому что мы сначала выбираем из трех $A_i$ две, затем переставляем эти две внутри всеми способами, затем переставляем пять объектов всеми способами. Действительно все эти перестановки пересекаются по тем событиям, в которых все $AAA$ стоят рядом.
Спасибо большое!
Буду дальше думать, как точно подсчитать количество таких пересечений (кажется, из перестановок $AA'A''$ в $N(a)$ повторяется каждая расстановка дважды) и как себе объяснить дальнейшую формулу.
Еще раз спасибо!

[grizzly]

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

Да, конечно, решил.

Спасибо! И по Вашему ответу я вижу, что Вы правильно поняли полученные здесь сегодня небольшие подсказки.

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

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

Нет, пока не можете :) Это формула та, да не та. Все слагаемые свалены в кучу безо всякой логики. Если слагаемые не стоят в правильном порядке, я точно знаю, что Вы не поняли решения.

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

Действительно все эти перестановки пересекаются по тем событиям, в которых все $AAA$ стоят рядом.

Да. Но у Вас это по-прежнему в тумане.
Ответьте, пжл, ещё на такой вопрос:
Вы понимаете, что в Ваших обозначениях $C^1_2N(a)$ это в точности то же, что $N(a_A)+N(a_F)$? И что последние пересекаются по $N(a_A, a_F)$, а значит это попадает в сумму дважды?
Это в дополнение к сказанному Вами, что $N(b_A)\subset N(a_A)$ и учитывается в нём дважды.
Если такое объяснение Вам понятнее, попробуйте по этой логике пройти от самого начала до самого конца.

[xolodec]

grizzly в сообщении #987203 писал(а):

Вы понимаете, что в Ваших обозначениях $C^1_2N(a)$ это в точности то же, что $N(a_A)+N(a_F)$? И что последние пересекаются по $N(a_A, a_F)$, а значит это попадает в сумму дважды?

Да, конечно, понимаю!

grizzly в сообщении #987203 писал(а):

у Вас это по-прежнему в тумане.

Что верно, то верно. Но я пока не сдаюсь, надеюсь рассеется через некоторое время

grizzly в сообщении #987203 писал(а):

что $N(b_A)\subset N(a_A)$ и учитывается в нём дважды.

Вот этого долго не понимал. Теперь понял, но никак не могу разобраться, как посчитать число таких повторений без ручного перебора? Как вообще заметить, что они дважды повторяются?
Я выписал все возможные случаи выбора двух человек из трех, перестановки этих двух внутри пары и перестановки 5 объектов, среди которых одна "склеенная" пара. По моим результатам, в каждой $N(a_i)$ дважды входят все слагаемые, которые содержат $b_i$.
То есть:
$C^1_2N(a) \to a_1,~a_2,~2a_1a_2,~3b_1a_2,~3a_1b_2,~4b_1b_2 $
Аналогично я попытался выписать и
$N(a,a) \to a_1a_2,~2b_1a_2,~2a_1b_2,~4(?)b_1b_2$
$C^1_2N(b) \to b_1a_2,~a_1b_2,~2b_1b_2$
$C^1_2N(b,a) \to b_1a_1,~a_1b_2,~4(?)b_1b_2$
$N(b,b) \to b_1b_2$
Знаю, что неправильно посчитал количество $b_1b_2$ в некоторых случаях. Пока не могу придумать, как их посчитать правильно и найти, где я ошибся с ними. "Туман" тут у меня.

P.S. Неужели в таких случаях всегда настолько трудоемко составление формулы включений и исключений? или это просто для меня сложно? Это же нужно составить таблицу со всеми возожными сочетаниями $a,b$ и напротив каждого $N()$ написать сколько туда и чего входит. Это же при увеличении числа "наций" становится очень трудоемкой задачей.