2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

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



Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3
 
 Re: Способы рассадки, комбинаторика
Сообщение08.03.2015, 11:11 
Заслуженный участник
Аватара пользователя


18/01/13
11660
Казань
А что, непременно надо использовать включения-исключения? Мне больше понравилась идея
svv в сообщении #985183 писал(а):
Обозначим национальность первого сидящего цифрой 1, второго сидящего цифрой 2, оставшуюся цифрой 3.
Потом все умножается на $3!\cdot 3!\cdot 3!C_3^2$

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

 Профиль  
                  
 
 Re: Способы рассадки, комбинаторика
Сообщение08.03.2015, 11:25 


29/04/14
139
provincialka в сообщении #987317 писал(а):
А что, непременно надо использовать включения-исключения? Мне больше понравилась идея
Цитата:
Обозначим национальность первого сидящего цифрой 1, второго сидящего цифрой 2, оставшуюся цифрой 3.


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

 Профиль  
                  
 
 Re: Способы рассадки, комбинаторика
Сообщение08.03.2015, 11:30 
Заслуженный участник
Аватара пользователя


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

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

 Профиль  
                  
 
 Re: Способы рассадки, комбинаторика
Сообщение08.03.2015, 12:48 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Способы рассадки, комбинаторика
Сообщение10.03.2015, 11:39 


29/04/14
139
grizzly в сообщении #987330 писал(а):
Но если долго не даётся, лучше сделать паузу и отвлечься на другие вопросы. А через какое-то время снова вернуться к задаче.

Возвращаемся :wink:
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 $$

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

 Профиль  
                  
 
 Re: Способы рассадки, комбинаторика
Сообщение10.03.2015, 13:50 
Заслуженный участник
Аватара пользователя


09/09/14
5462
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 --

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

 Профиль  
                  
 
 Re: Способы рассадки, комбинаторика
Сообщение10.03.2015, 14:19 
Заслуженный участник
Аватара пользователя


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

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

 Профиль  
                  
 
 Re: Способы рассадки, комбинаторика
Сообщение10.03.2015, 14:45 
Заслуженный участник


23/07/08
7637
Харьков

(Оффтоп)

ex-math в сообщении #988189 писал(а):
Теперь добавляйте турок.
Гюнеш, Йылмаз, Акбулут, на выход!

 Профиль  
                  
 
 Re: Способы рассадки, комбинаторика
Сообщение11.03.2015, 12:13 


29/04/14
139
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 писал(а):
некоторые перестановки считаются дважды (те, где есть тройки).

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

 Профиль  
                  
 
 Re: Способы рассадки, комбинаторика
Сообщение11.03.2015, 12:47 
Заслуженный участник
Аватара пользователя


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

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

xolodec в сообщении #988658 писал(а):
Мне кажется у вас есть неверные формулы для расчета количества случаев.
...

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

 Профиль  
                  
 
 Re: Способы рассадки, комбинаторика
Сообщение11.03.2015, 20:13 


29/04/14
139
Да, действительно, "переключился", Вы правы!
Спасибо Вам еще раз, без Вас я бы не справился :-)

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 41 ]  На страницу Пред.  1, 2, 3

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group