Комбинаторная задачка

[Whitaker]

Здравствуйте уважаемые!
Помогите пожалуйста разобраться с такой задачкой.
В шеренгу построены $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.

[svv]

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

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

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

[Whitaker]

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

[MrDindows]

Whitaker в сообщении #495654 писал(а):

1) Почему вы не рассматриваете расстановки в которых E и E стоят рядом? Например EEFEF.
Или это тоже самое, что и EFEF?

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

[svv]

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

[Whitaker]

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

Для этого нужно выбрать 3 англичан и 2 французов, причем выбранные не должны быть в своей шеренге 1-м, 2-м и последним, и не должны стоять подряд. Понятно, почему надо делать именно такой выбор? Ясно, как на основе этого выбора однозначно объединить шеренги?

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

[svv]

У нас есть 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) Применяем однозначный алгоритм объединения шеренг (который Вам предлагается сформулировать, хотя бы для себя).

[Whitaker]

Я все свои мысли напишу на бумажке и через некоторое время, наверное завтра напишу здесь свое решение к задаче. К сожалению, сегодня нет возможности сделать всё это.
Благодарю Вас svv за ценные подсказки.

[Whitaker]

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

[INGELRII]

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

[Whitaker]

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

[svv]

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). И пересчитываем количество таких представителей.
Таким образом, мы приходим к пересчету тех групп, с которых начинали. А кроме них, выходит, ничего и не нужно.

[Whitaker]

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