2014 dxdy logo

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

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


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


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

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

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

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

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



Начать новую тему Ответить на тему
 
 Комбинаторная задачка
Сообщение24.10.2011, 10:15 
Аватара пользователя


12/01/11
1320
Москва
Здравствуйте уважаемые!
Помогите пожалуйста разобраться с такой задачкой.
В шеренгу построены $m$ французов и $n$ англичан так, что рядом с каждым стоит хотя бы один его соотечественник. Покажите, что число таких расстановок равно
$m!n!\Big[1+(C_{m-2}^{0}+C_{m-3}^{1})(C_{n-2}^{0}+C_{n-3}^{1})+(C_{m-3}^{1}+C_{m-4}^{2})(C_{n-3}^{1}+C_{n-4}^{2})+(C_{m-4}^{2}+C_{m-5}^{3})(C_{n-4}^{2}+C_{n-5}^{3})+\dots \Big]$
Вот моя попытка решения: В каждой допустимой перестановке англичане и французы стоят группами, состоящими не менее из двух человек. Подсчитаем сколькими способами можно разбить $n$ англичан на $p$ упорядоченных групп, так чтобы каждая группа содержала не менее двух человек. Это можно реализовать $C_{n-p-1}^{p-1}$ способами. Так как порядок важен, то умножим еще на $n!$ и получим $n!C_{n-p-1}^{p-1}$. Точно также $m$ французов можно разбить на $s$ упорядоченных групп, так чтобы каждая группа содержала не менее двух человек $m!C_{m-s-1}^{s-1}$ способами.
К сожалению дальше как делать я пока не знаю.

С уважением, Whitaker.

 Профиль  
                  
 
 Re: Комбинаторная задачка
Сообщение24.10.2011, 14:15 
Заслуженный участник


23/07/08
10609
Crna Gora
Вот стоит группа французов, за ней группа англичан, за ней группа французов, за ней группа англичан, и за ней группа французов, последняя. Давайте такое обозначать FEFEF, или еще короче 5F (число -- количество групп, буква -- с кого начинается шеренга).

Заметьте, что имеются следующие взаимоисключающие варианты, и других нет:
FE
EF
FEF
EFE
FEFE
EFEF
FEFEF
EFEFE
и т.д.
Задача теперь сводится к вычислению количества расстановок для каждого такого варианта, с последующим суммированием.

Выберем один такой вариант, например 7E=EFEFEFE. Пусть сначала есть 2 отдельные шеренги -- $m$ французов и $n$ англичан, в которых люди уже как-то построены. Теперь мы хотим, не меняя относительного порядка соотечественников, объединить эти шеренги в одну интернациональную. Для этого нужно выбрать 3 англичан и 2 французов, причем выбранные не должны быть в своей шеренге 1-м, 2-м и последним, и не должны стоять подряд. Понятно, почему надо делать именно такой выбор? Ясно, как на основе этого выбора однозначно объединить шеренги?

 Профиль  
                  
 
 Re: Комбинаторная задачка
Сообщение24.10.2011, 15:44 
Аватара пользователя


12/01/11
1320
Москва
Уважаемый svv прочитав ваш пост у меня возник следующий вопрос:
1) Почему вы не рассматриваете расстановки в которых E и E стоят рядом? Например EEFEF.
Или это тоже самое, что и EFEF?
P.S. А вообще то, что я написал в самом первом посту у меня правильно? Я вообще правильно рассуждаю?

 Профиль  
                  
 
 Re: Комбинаторная задачка
Сообщение24.10.2011, 15:51 
Заслуженный участник


02/08/10
629
Whitaker в сообщении #495654 писал(а):
1) Почему вы не рассматриваете расстановки в которых E и E стоят рядом? Например EEFEF.
Или это тоже самое, что и EFEF?

E - это не один англичанин, а группа их, то есть группа таких, что слева и справа от них стоят французы. Поэтому ситуации ЕЕ отбрасываются в принципе)

 Профиль  
                  
 
 Re: Комбинаторная задачка
Сообщение24.10.2011, 15:53 
Заслуженный участник


23/07/08
10609
Crna Gora
Совершенно верно, такое следует обозначать EFEF.
E и F -- это не единичные люди, а максимальная группа идущих подряд людей одной национальности.
В таком случае, например, слева от самого левого в своей группе француза либо стоит англичанин, либо вообще никого.
Принимая такое определение, мы избавляемся от неоднозначностей вроде "это группа из 25 англичан? -- или это группа из 14 англичан и другая стоящая рядом группа из 11 англичан?"

 Профиль  
                  
 
 Re: Комбинаторная задачка
Сообщение24.10.2011, 16:43 
Аватара пользователя


12/01/11
1320
Москва
svv в сообщении #495638 писал(а):
Для этого нужно выбрать 3 англичан и 2 французов, причем выбранные не должны быть в своей шеренге 1-м, 2-м и последним, и не должны стоять подряд. Понятно, почему надо делать именно такой выбор? Ясно, как на основе этого выбора однозначно объединить шеренги?

Можете это прокомментировать?
Мне кажется, что это не нужно.

 Профиль  
                  
 
 Re: Комбинаторная задачка
Сообщение24.10.2011, 17:08 
Заслуженный участник


23/07/08
10609
Crna Gora
У нас есть 30 французов и 20 англичан.
Французы выстроились в свою шеренгу, англичане выстроились в свою шеренгу.
Нумеруем французов по порядку в своей шеренге. Нумеруем англичан по порядку в своей шеренге.
Выбираем "модель расстановки" EFEFEFE.
Выбираем трех англичан: 7, 11, 18.
Выбираем двух французов: 5, 24.
Получаем (по алгоритму, который Вы можете сформулировать сами) такое расположение в общей шеренге:
Англичане с 1 по 6
Французы с 1 по 4
Англичане с 7 по 10
Французы с 5 по 23
Англичане с 11 по 17
Французы с 24 по 30
Англичане с 18 по 20
Получается, что любая расстановка в задаче однозначно получается следующими действиями:
1) Выбираем расположение французов в своей шеренге и англичан в своей (соответственно $m!$ и $n!$ вариантов, вот откуда в ответе общий множитель $m!n!$).
2) Выбираем "модель расстановки" (например, FEFEFEF, вот откуда в ответе сумма -- это суммирование по всем моделям).
3) Выбираем в зависимости от модели некоторое количество человек в обеих шеренгах, соответствующее количеству английских и французских групп. Выбор должен удовлетворять некоторым условиям (см. выше), но радует то, что выбор среди французов и англичан независим (вот почему в сумме стоят произведения $C_{m...}$ и $C_{n...}$).
4) Применяем однозначный алгоритм объединения шеренг (который Вам предлагается сформулировать, хотя бы для себя).

 Профиль  
                  
 
 Re: Комбинаторная задачка
Сообщение24.10.2011, 17:29 
Аватара пользователя


12/01/11
1320
Москва
Я все свои мысли напишу на бумажке и через некоторое время, наверное завтра напишу здесь свое решение к задаче. К сожалению, сегодня нет возможности сделать всё это.
Благодарю Вас svv за ценные подсказки. :-)

 Профиль  
                  
 
 Re: Комбинаторная задачка
Сообщение25.10.2011, 15:35 
Аватара пользователя


12/01/11
1320
Москва
Здравствуйте svv! Я решил задачку рассмотрев 4 таких случая.
Пусть Ф-группа французов, а А-группа англичан.
1)ФАФА....ФА
2)АФАФ...АФ
3)ФАФА...АФ
4)АФАФ...ФА
Для каждого из них я нашел результаты просуммировал их и сделал арифметические преобразования и получил тот же самый ответ, что и в книге.
Вопрос может показаться глупым, но этот же вопрос я задавал вчера, но всё-таки я не понял.
Вот почему например группу ФФА мы рассматриваем как группу ФА? Хотелось бы это понять. :oops:

 Профиль  
                  
 
 Re: Комбинаторная задачка
Сообщение25.10.2011, 15:46 
Аватара пользователя


11/08/11
1135
Whitaker
Стоят двое французов. Потом ноль англичан. Потом еще три француза. Потом еще ноль англичан. Потом восемь французов. Встречный вопрос: какие вообще могут быть аргументы против того, чтобы рассматривать это все как одну группу из тринадцати французов? :roll:

 Профиль  
                  
 
 Re: Комбинаторная задачка
Сообщение25.10.2011, 15:56 
Аватара пользователя


12/01/11
1320
Москва
INGELRII
Никаких аргументов нет вроде. Их вполне свободно можно рассматривать как единую группу из 13 французов.

 Профиль  
                  
 
 Re: Комбинаторная задачка
Сообщение25.10.2011, 21:36 
Заслуженный участник


23/07/08
10609
Crna Gora
INGELRII писал(а):
Потом ноль англичан.
:-) Сейчас только заметил, что эти англичане просто повсюду. Только почему-то чаще всего в нулевом количестве. :-)

Whitaker писал(а):
Вот почему например группу ФФА мы рассматриваем как группу ФА?
Самый простой ответ -- мы так определяем группы в данной задаче.
Вот стоит шеренга из французов и англичан. Выбираем человека, пусть это француз. Смотрим, кто его сосед слева и кто сосед справа. Если тоже француз, объединяем его с исходным в непрерывную последовательность французов, т.е. не перемежаемую англичанами. Делаем это пока либо не встретится англичанин, либо не закончится шеренга. То, что получилось -- нерасширяемая непрерывная последовательность французов. Ее и называем группой -- это наши E и F. По этому построению, справа от самого правого француза в группе уже не может стоять еще один француз, иначе он тоже был бы присоединен к группе. Поэтому и исключается возможность рядом стоящих EE или FF.

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

Допустим, Вы все-таки желаете знать, что будет, если допустить смежные EE или FF. Это напоминает диалог из книги Литлвуда "Математическая смесь":
Учитель: «Предположим, что х есть число овец в задаче».
Ученик: «Но, господин учитель, предположим, что х не есть число овец».

Итак, разрешаем EE и даже FFFF. Пусть все англичане перенумерованы, и Вы видите, что подряд стоят семь англичан с номерами 3,5,2,7,6,1,4. Вы вправе сказать, что видите здесь две группы англичан: (3,5,2) и (7,6,1,4), и посчитать это за расстановку. Но я скажу, что вижу здесь две другие группы: (3,5,2,7,6) и (1,4). И эту же последовательность людей воспринимаю как три группы: (3,5),(2,7),(6,1,4). Считать ли все перечисленные варианты группировки за отдельные расстановки? Если да, тогда для 7 человек мы получим количество расстановок много больше 7 факториал. Если нет, то, значит, чаще всего выделенные в какой-то расстановке несколько групп за отдельную расстановку считать не надо, потому что такое расположение людей скорее всего уже было посчитано при другом их разбиении на группы.

Допустим, мы все-таки хотим научиться пересчитывать такие "группировки". Тогда имеет смысл ввести понятие эквивалентные группировки -- которые отличаются не порядком расстановки, а просто способом объединения в группы. Например, (3,5),(2,7),(6,1,4) и (3,5,2),(7,6,1,4) эквивалентны, а (3,1,4),(2,5,6,7) и (3,1),(2,4,5,6,7) не эквивалентны. Множество всех эквивалентных группировок образует класс эквивалентности. Наверное, понятно, что нам надо на самом деле пересчитать не количество всех способов объединения в группы при всех перестановках, а только количество классов эквивалентности.

Так вот, количество классов эквивалентности легко пересчитать, если каждому классу сопоставить ту самую группу, о которой мы говорили вначале, т.е. нерасширяемую непрерывную последовательность людей одной национальности. Например:
(3,5),(2,7),(6,1,4) -- входит в класс 3527614
(3,5,2),(7,6,1,4) -- входит в класс 3527614
(3,1),(2,4,5,6,7) -- входит в класс 3124567
Иными словами, мы в каждом классе эквивалентности выбираем одного представителя -- разбиение на одну (нерасширяемую) группу, например, (3,5,2,7,6,1,4). И пересчитываем количество таких представителей.
Таким образом, мы приходим к пересчету тех групп, с которых начинали. А кроме них, выходит, ничего и не нужно.

 Профиль  
                  
 
 Re: Комбинаторная задачка
Сообщение25.10.2011, 23:04 
Аватара пользователя


12/01/11
1320
Москва
svv очень Вам благодарен за Ваш ответ! Получил ответы на все свои вопросы! Благодарю всех за помощь!

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 13 ] 

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



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

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


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

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