Сколькими способами можно переставить буквы в слове "предупреждение" так, чтобы одинаковые буквы не стояли рядом? Есть такое решение, верно ли оно? link text

задан 19 Июн '17 0:00

изменен 19 Июн '17 0:01

С буквами "е" в опубликованном решении недоработочка.

(19 Июн '17 0:28) Амфибрахий

Рассуждение неверное. Решается совсем другая задача. Из общего числа вариантов вычитается непонятно что. У нас никакие одинаковые буквы не должны стоять рядом. В частности, не должно быть случая ЕЕ, для которого остальные буквы могут никак попарно не группироваться. Например, рассмотрим такой случай: ЕЕПРДУПРЖДЕНИЕ. Такой вариант нам не подходит, то есть он должен быть учтён при вычитании. Но этого не происходит. Поэтому рассуждение должно быть другим.

(19 Июн '17 0:32) falcao
10|600 символов нужно символов осталось
0

Подсчёт здесь не очень простой, но можно применить формулу включений и исключений.

Сделаем все 14 букв слова различными, вводя для одинаковых букв нижние индексы. Количество перестановок при этом увеличивается в $%4!2!^3$% раз; на эту величину в конце нужно будет всё разделить.

Введём множества $%A$%, $%B$%, $%C$%, $%D$% для тех перестановок (из общего количества $%14!$%), в которых имеются соседние буквы Е, П, Р, Д соответственно (с индексами). Найдём $%|A|$%. Для этого из общего числа перестановок нужно вычесть те, где буквы Е с индексами не идут подряд. Без букв Е у нас получается $%10!$% перестановок, и в каждой из них есть 11 мест, на которые можно вставить одну из четырёх букв Е. Букву Е с индексом 1 вставляем на любое из 11 мест, с индексом 2 -- на одно из оставшихся 10 мест, и так далее. Итого это даёт $%|A|=14!-10!\cdot11\cdot10\cdot9\cdot8$%.

Мощность каждого из множеств $%B$%, $%C$%, $%D$% легко вычислить следующим образом: если буквы, скажем, П, склеить, что можно сделать двумя способами, то получится 13 символов, которые переставляются $%13!$% способами. Итого $%|B|=|C|=|D|=2\cdot13!$%.

Рассмотрим попарные пересечения. Для случая $%BC$% склеиваем двумя способами каждую из двух пар букв. То, что получилось, переставляем $%12!$% способами. Итого $%|BC|=|BD|+|CD|=2^2\cdot12!$%. Теперь найдём мощность $%AB$%. Идея та же, что выше: буквы П склеиваем 2 способами; общее число таких перестановок равно $%13!$%. Из него вычитаем количество случаев, когда буквы Е не идут подряд. Без их участия будет $%9!$% вариантов, и далее 4 буквы вставляем на разные места 10, 9, 8, 7 способами соответственно. Итого $%|AB|=|AC|=|AD|=2(13!-9!\cdot10\cdot9\cdot8\cdot7)$%.

Для тройных пересечений будет $%|BCD|=2^3\cdot11!$% и $%|ABC|=|ABD|=|ACD|=2^2(12!-8!\cdot9\cdot8\cdot7\cdot6)$% по тому же принципу, что и выше. Наконец, $%|ABCD|=2^3(11!-7!\cdot8\cdot7\cdot6\cdot5)$%.

Теперь по формуле включений и исключений подсчитываем $%14!-(|A|+|B|+|C|+|D|)+(|AB|+|AC|+|AD|+|BC|+|BD|+|CD|)-$%

$%-(|ABC|+|ABD|+|ACD|+|BCD|)+|ABCD|$%. Подставляем то, что было найдено выше, получая $%14!-(14!-10!\cdot11\cdot10\cdot9\cdot8)-3\cdot2\cdot13!+3\cdot2^2\cdot12!+3\cdot2(13!-9!\cdot10\cdot9\cdot8\cdot7)-$%

$%-2^3\cdot11!-3\cdot2^2(12!-8!\cdot9\cdot8\cdot7\cdot6)+2^3(11!-7!\cdot8\cdot7\cdot6\cdot5)=19161999360=$%

$%=2^{11}3^3\cdot5\cdot7\cdot9901$%. Делим на $%4!2!^3=2^6\cdot3$%, и имеем в ответе $%2^53^2\cdot5\cdot7\cdot9901=99802080$%. Это примерно 22% от общего количества перестановок с повторениями.

ссылка

отвечен 19 Июн '17 4:12

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×81

задан
19 Июн '17 0:00

показан
428 раз

обновлен
19 Июн '17 4:12

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru