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

[provincialka]

А что, непременно надо использовать включения-исключения? Мне больше понравилась идея

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

Обозначим национальность первого сидящего цифрой 1, второго сидящего цифрой 2, оставшуюся цифрой 3.

Потом все умножается на $3!\cdot 3!\cdot 3!C_3^2$

Для двух национальностей такой подход дает ответ мгновенно. Для трех -- можно построить дерево вариантов.

[xolodec]

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

А что, непременно надо использовать включения-исключения? Мне больше понравилась идея

Цитата:

Обозначим национальность первого сидящего цифрой 1, второго сидящего цифрой 2, оставшуюся цифрой 3.

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

[grizzly]

provincialka
Насколько я понимаю, ТС стремится в этой теме не просто решить задачу, а именно разобраться в одном из стандартных подходов к решению. Да, задача сложная для самостоятельного решения, но здесь нужно по меньшей мере суметь уверенно прочитать решение из учебника.
В этом стремлении разобраться я на 100% поддерживаю ТС. Но если долго не даётся, лучше сделать паузу и отвлечься на другие вопросы. А через какое-то время снова вернуться к задаче.

PS. Вижу, ТС уже ответил и подтвердил мои предположения, но я всё же оставлю здесь это своё мнение в его поддержку.

[ex-math]

xolodec
С парами Вы вроде разобрались.
Рассмотрите тройку. Вы уже поняли, что при вычитании "одной пары", вы эту тройку вычли дважды, значит, нужно прибавить.
Рассмотрите тройку плюс пару. Сколько раз Вы вычитаете ее, когда вычитаете "одну пару"? Сколько раз прибавляете, когда прибавляете "две пары"? Сколько раз прибавляете, когда прибавляете "одну тройку"? Что нужно сделать, чтобы компенсировать несоответствие?
Легче рассматривать случаи в порядке "нарастания" -- сначала одна пара, потом две пары или тройка, потом тройка и пара, потом две тройки. В этом случае новый тип комбинации затрагивает только уже рассмотренные.

[xolodec]

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

Но если долго не даётся, лучше сделать паузу и отвлечься на другие вопросы. А через какое-то время снова вернуться к задаче.

Возвращаемся

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

при вычитании "одной пары", вы эту тройку вычли дважды, значит, нужно прибавить.

Да, но из-за того, что при вычитании двух одиночных пар, я получу пересечение, в которое войдут дважды случаи тройки, поэтому $b_1b_2$ входит четырежды:

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

$C^1_2N(a) \to a_1,~a_2,~2a_1a_2,~3b_1a_2,~3a_1b_2,~4b_1b_2 $

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

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

Трижды, опять же, согласно тому, что

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

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

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

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

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

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

$$-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 $$

Можете подсказать мне, пожалуйста, где я ошибся в этой таблице ?

[grizzly]

xolodec
Теперь я уже запутался в Ваших обозначениях. Давайте на этот раз поступим следующим образом. Чуть упростим задачу и я приведу Вам её решение. Вы разберётесь в решении, обозначениях и формулах, а тогда ещё раз перепишете Вашу табличку. Так получится быстрее и пользы будет больше.

Задача та же, но у нас 5 человек: 3 Англичанина и 2 Француза.
Обозначения:
буква "a" с индексом A (или F) -- событие "2 англичанина (2 француза) рядом".
буква "б" с индексом A -- событие "3 англичанина рядом".
Распишем все случаи.
1) $N = 5!$
2) $N(a_A) = C_3^2\cdot 2!\cdot 4!$ Это выражение включает в себя все $N(a_A,a_F)$ и, кроме этого, все $N(b_A)$ в нём учтены дважды.
3) $N(a_F) = 2!\cdot 4!$ Это выражение включает в себя все $N(a_A,a_F)$.
4) $N(a_A,a_F) = 2!\cdot 2!\cdot C_3^2\cdot 3!$ Это выражение включает в себя все $N(b_A,a_F)$.
5) $N(b_A) = 2!\cdot C_3^2\cdot 3!$ Это выражение включает в себя все $N(b_A,a_F)$.
6) $N(b_A,a_F)=3!\cdot 2!\cdot 2!$

Ответ рассчитаем пошагово с пояснениями:
Шаг 1. Отнимем от всех возможных вариантов случаи, когда рядом сидят 2 англичанина или 2 француза:

$$N-[N(a_A)+N(a_F)]$$

Шаг 2. Но из описаний выше для 2) и 3) видим, что отнимая мы дважды отняли $N(a_A,a_F)$ и $N(b_A)$. Исправим это, вернув по одному экземпляру каждого на место:

$$N-\Big[[N(a_A)+N(a_F)]-[N(a_A,a_F)+N(b_A)]\Big]$$

Шаг 3. Теперь из описаний 4) и 5) видим, что мы здесь дважды вернули на место $N(b_A,a_F)$. Исправим это:

$$N-\Big[[N(a_A)+N(a_F)]-[N(a_A,a_F)+N(b_A)-N(b_A, a_F)]\Big]$$

Больше ничего неучтённого не осталось.

-- 10.03.2015, 14:54 --

Жду от Вас сначала подтверждения понимания этого решения (или вопросов). Затем -- распишете по аналогии с моими пунктами Вашу табличку.

[ex-math]

xolodec
Все верно с точностью до опечатки в четвертой строке: $b_1a_2$ должно быть. Также можно не различать национальности и писать просто $ab$, так как выбор национальности у Вас зашит в биномиальных коэффициентах -- получится короче. Как видите, все вычлось ровно по одному разу. Молодец!

Теперь добавляйте турок.

[svv]

(Оффтоп)

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

Теперь добавляйте турок.

Гюнеш, Йылмаз, Акбулут, на выход!

[xolodec]

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

Теперь я уже запутался в Ваших обозначениях

В приведенной табличке я обозначал следующим образом:
$N(a)$ - количество случаев, в которых есть хотя бы одна пара
$N(b)$ - количество случаев, в которых есть хотя бы одна тройка
$N(b,a)$ - количество случаев, в которых есть хотя бы одна тройка и хотя бы одна двойка.
Индексов у $a,~b$ нет, потому что все случаи симметричны (это учитывается биномиальными коэффициентами). Все, что после стрелки -- это все именованные случаи, которые входят в выражение слева от стрелки.

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

$-C^1_2N(a) \to a_1,~a_2,~2a_1a_2,~3b_1a_2,~3a_1b_2,~4b_1b_2 $

Здесь, действительно

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

можно не различать национальности и писать просто $ab$,

но мне так было понятней, поэтому я так писал.

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

Жду от Вас сначала подтверждения понимания этого решения (или вопросов). Затем -- распишете по аналогии с моими пунктами Вашу табличку.

В первую очередь, я Вам искренне благодарен за решение, я его полностью понял.
Спасибо Вам большое, что не пожалели времени на данную задачу, мне это очень помогло!
Я думал точно также, как и в приведенном Вами решений и даже в приведенной мной таблице, как оказалось, (спасибо,ex-math), все верно.

Распишем все случаи для задачи с тремя 3 Англичанинами и 3 Французами.

1) $N = 6!$
2) $N(a_A) = C_3^2\cdot 2! \cdot 5!$ Это выражение включает в себя все $N(a_A, a_F)$ и, кроме этого, все $N(b_A)$ в нём учтены дважды.
3) $N(a_F) = C_3^2\cdot 2!\cdot 5!$ Это выражение включает в себя все $N(a_A,a_F)$ и все $N(b_F)$ в нём учтены дважды.
4) $ N(a_A,a_F) = 2!\cdot 2!\cdot C_3^2 \cdot C_3^2 \cdot 4! $ Это выражение включает в себя все $N(b_A,a_F)$, $N(a_A,b_F)$ по два раза и четыржды $N(b_A,b_F).
5) $N(b_A) = 3!\cdot 4!$ это выражение включает в себя все $N(b_A,a_F),~N(b_A,b_F)$.
6) $N(b_F) = 3!\cdot 4!$ это выражение включает в себя все $N(a_A,b_F),~N(b_A,b_F)$.
7) $N(b_A,a_F)=3!\cdot C_3^2 \cdot 2!\cdot 3!$ это выражение включает в себя дважды $N(b_A,b_F)$.
8) $N(a_A,b_F)=3!\cdot C_3^2 \cdot 2!\cdot 3!$ это выражение включает в себя дважды $N(b_A,b_F)$.
9) $N(b_A,b_F)=3!\cdot 3!\cdot 2!$

Мне кажется у вас есть неверные формулы для расчета количества случаев.

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

3) $N(a_F) = 2!\cdot 4!$ Это выражение включает в себя все $N(a_A,a_F)$.
4) $ N(a_A,a_F) = 2!\cdot 2!\cdot C_3^2\cdot 3!$ Это выражение включает в себя все $N(b_A,a_F)$.
5) $N(b_A) = 2!\cdot C_3^2\cdot 3!$ Это выражение включает в себя все $N(b_A,a_F)$.
6) $N(b_A,a_F)=3!\cdot 2!\cdot 2!$

Должно быть, наверное, так:
3) $N(a_F) = C_3^2\cdot 2!\cdot 4!$ Это выражение включает в себя все $N(a_A,a_F)$.
4) $ N(a_A,a_F) = 2!\cdot 2!\cdot C_3^2\cdot C_3^2\cdot 3!$ Это выражение включает в себя все $N(b_A,a_F)$.
5) $N(b_A) = 3! \cdot 3!$ Это выражение включает в себя все $N(b_A,a_F)$.
6) $N(b_A,a_F)=3!\cdot 2!\cdot C_3^2 \cdot 2! $

Теперь я понял формулу окончательно.

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

xolodecТеперь добавляйте турок.

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

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

некоторые перестановки считаются дважды (те, где есть тройки).

Спасибо всем большое!

[grizzly]

Здорово! Теперь видно, что туман у вас рассеялся. Теперь даже если попадутся случайные ошибки по невнимательности, это совсем мелочи. Понимание на порядок важнее, чем подобранная или угаданная формула.

Спасибо и вам за терпение, здоровое упрямство и взаимное стремление к пониманию.

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

Мне кажется у вас есть неверные формулы для расчета количества случаев.
...

Да нет. Это вы ненароком переключились на свою задачу с тремя французами (в моей было только два).

[xolodec]

Да, действительно, "переключился", Вы правы!
Спасибо Вам еще раз, без Вас я бы не справился