Сколькими способами можно переставить цифры в числе 1 234 114 546 так, чтобы никакие две одинаковые цифры не шли друг за другом?

задан 29 Сен '19 23:28

10|600 символов нужно символов осталось
1

Можно решить задачу с помощью вывода рекуррентных формул. Метод включений-исключений тут тоже применим.

Формулу для числа перестановок с повторениями считаем известной и применяем без пояснений. Общее число вариантов равно P(3,3,1,1,1,1)=10!/(3!3!)=100800. Найдём число вариантов, когда две единицы идут подряд. Прежде всего, если 111 идут подряд, то поставить 111 можно на одно из 8 мест, а дальше продолжить P(3,1,1,1,1)=7!/3! способами, что даёт 8!/3!=6720. Далее, 11 размещаем 9 способами, на оставшихся символах имеем P(3,1,1,1,1,1)=8! перестановок с повторениями, и в итоге имеем 9!/3!=60480 способов, где случай трёх единиц подряд учтён дважды. Это значит, что перестановок, в которых имеется 11, будет 60480-6720=53760. Столько же перестановок, где имеется 44.

Эти величины надо вычесть (исключить), а затем прибавить (включить) число вариантов, где есть и 11, и 44. Если 11 встретилось левее 44, то правее 11 уже не встретится. Поэтому мы имеем два симметричных случая. Будем подсчитывать число вариантов вида ...11...44... , а потом эту величину удвоим.

Введём множества M(111,444), M(11,444), M(111,44), M(11,44) с понятным смыслом символики. Скажем, M(11,444) означает число перестановок, в которых встречается 11, а правее встречается 444. Легко видеть, что |M(111,444)|=4!C_6^2=360. Мы склеиваем 111 и 444, получаем 6 символов, выбирая 15 способами 2 места для их размещения. На оставшихся 4 местах размещаем 2, 3, 5, 6.

Теперь находим мощность M(11,444). Здесь после склейки символов 7, выбор двух мест осуществляется 21 способом, затем перестановка на 5 символах. Получается 2520, и далее надо вычесть 360. Это даёт |M(11,444)|=2520-360=2160. Такая же мощность у M(111,44).

Для случая M(11,44) мы в начале имеем 6!C_8^2=20160. В соответствии со сказанным выше, |M(11,44)|=20160-2x2520+360=15480 по формуле включений и исключений. То же число будет для симметричного случая M(44,11).

Применяя ту же формулу к начальной ситуации, имеем 100800-2x53760+2x15480=24240. Если взять случайную перестановку, то вероятность отсутствия в ней подряд идущих одинаковых символов составит чуть более 24%.

Тут довольно легко обсчитаться, поэтому вычисления желательно перепроверить.

ссылка

отвечен 1 Окт '19 2:40

изменен 2 Окт '19 3:13

Тут можно не просто легко общаться, но и не заметить две четверки:D можете, пожалуйста, описать реккурентный способ подсчёта?

(1 Окт '19 10:31) Hybridrainbow

@Hybridrainbow: а что насчёт двух четвёрок? Их тут в наборе имеется три, как и единиц.

Рекуррентный способ устроен примерно так. Пусть нам даны кратности букв. Обозначим число подходящих вариантов через Q(3,3,1,1,1,1). Если первая буква одна из однократных, то далее будет Q(3,3,1,1,1) с коэффициентом 4. Если первая буква 3-кратная, то далее берём Q(3,2,1,1,1,1), вычитая из неё P(3,1,1,1,1,1), где P -- обычное число перестановок с повторениями. Здесь коэффициент при разности равен 2. Это даёт рекурсивный алгоритм.

(1 Окт '19 10:46) falcao

@Hybridrainbow: я перепроверил свои вычисления несколькими способами. Обнаружил небольшую арифметическую ошибку, и сейчас её исправил. Окончательный ответ там 24240.

(2 Окт '19 3:14) falcao
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×1,463
×16

задан
29 Сен '19 23:28

показан
958 раз

обновлен
2 Окт '19 3:14

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

по почте:

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

по RSS:

Ответы

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

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