2014 dxdy logo

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

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


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


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

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

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

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

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



Начать новую тему Ответить на тему На страницу 1, 2, 3  След.
 
 Способы рассадки, комбинаторика
Сообщение01.03.2015, 12:54 


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

Решение
Пусть
$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) $ и наоборот.
Помогите распутаться, пожалуйста.

 Профиль  
                  
 
 Re: Способы рассадки, комбинаторика
Сообщение01.03.2015, 19:18 


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

 Профиль  
                  
 
 Re: Способы рассадки, комбинаторика
Сообщение02.03.2015, 07:34 


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

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


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

2. Обозначения ваши не очень четко описаны. Во-первых, у вас в скобках одна буква, а в формуле -- по две и по три. Например,
xolodec в сообщении #984066 писал(а):
$N(b,b,a)$ - количество случаев, когда вместе рядом сидят три соотечественника, еще одна тройка других соотечественников сидит рядом и еще одна пара третьих соотечественников сидит рядом.
Здесь имеется в виду, что "по три" и "по два" могут сидеть любые национальности?

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

-- 02.03.2015, 12:33 --

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

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

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


29/04/14
139
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 $ способам, если я не ошибся в вычислении длинной формулы из его решения.

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


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

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


24/02/12
1842
Москва
provincialka в сообщении #984613 писал(а):
А нельзя сделать так
Нет, так не выйдет, потому что между двумя англичанами может так никто и не вклиниться. По идее, Ваше решение должно давать завышенный результат.

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


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

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


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

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


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

 Профиль  
                  
 
 Re: Способы рассадки, комбинаторика
Сообщение03.03.2015, 18:56 


29/04/14
139
ex-math в сообщении #985109 писал(а):
упростить решение Виленкина не получится.

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

svv в сообщении #985121 писал(а):
Bertrand, Williams, Dubois, Güneş, Taylor, Yılmaz, Moreau, Johnson, Akbulut.

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

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


23/07/08
10626
Crna Gora
Для информации. Обозначим национальность первого сидящего цифрой 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 писал(а):
А откуда, если не секрет, это достоверно известно?
Да, мне это известно достоверно, только никак обосновать я это не могу. :D
Обратите внимание, что фамилии хорошо различимы и сразу видно, кто есть кто.

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


18/01/13
12044
Казань
xolodec в сообщении #985178 писал(а):
А почему все-таки формула включений-исключений в этой задаче принимает такой вид?

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

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

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


09/09/14
6328
svv в сообщении #985183 писал(а):
посмотрите, может, ошибся при наборе

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

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


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

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

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



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

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


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

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