Перестановки с ограничениями

[Whitaker]

Здравствуйте! Помогите пожалуйста разобраться.
Сколькими способами можно переставить цифры в числе 1234114546 так, чтобы никакие две одинаковые цифры не шли друг за другом?
Я так попытался его решить. В число 1234114545 цифры "1" и "4" входят по 3 раза, а цифры "2", "3", "5" и "6" входят по 1 разу. Воспользуемся формулой включений и исключений.
$N(\bar{1}\bar{4})=N-N(1)-N(4)+N(14)$, где $N(\bar{1}\bar{4})$ - количество, где нет блоков вида: "11" и "44" (т.е. количество чисел в которых две одинаковые цифры идут друг за другом),
$N(1), N(4)$ - количество чисел где есть блок вида "11" и блок вида "44", соответственно.
$N$-общее количество чисел.
Очевидно, что $N=P(3,3,1,1,1,1)=\frac{10!}{3!\cdot 3!}=100800,$ $N(1)=N(4)=P(1,1,3,1,1,1,1)=\frac{9!}{3!}=60480$. А вот величину $N(\bar{1}\bar{4})$ я что-то затрудняюсь найти.
Буду рад любой помощи.

[ewert]

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

$N(1)=N(4)=P(1,1,3,1,1,1,1)=\frac{9!}{3!}=60480$.

Не совсем так. При этом Вы дважды учитываете каждую комбинацию, в которой идут подряд все три единички (или четвёрки). Поэтому количество таких комбинаций, т.е. $\frac{8!}{3!}$, надо вычесть.

[Whitaker]

ewert в сообщении #471768 писал(а):

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

$N(1)=N(4)=P(1,1,3,1,1,1,1)=\frac{9!}{3!}=60480$.

Не совсем так. При этом Вы дважды учитываете каждую комбинацию, в которой идут подряд все три единички (или четвёрки). Поэтому количество таких комбинаций, т.е. $\frac{8!}{3!}$, надо вычесть.

Спасибо! Да я обнаружил свою ошибку. Но как найти величину $N(14)$? Я даже не догадываюсь как его найти.

[ewert]

Да в принципе так же, только несколько муторно. Возьмём за основу $8!$, имея в виду, что у нас восемь цифр: 1, 11, 4, 44 и все остальные. При этом мы по два раза учитываем комбинации, где есть 111 (но нет 444) и где наоборот, и по четыре раза -- комбинации, где есть и 111, и 444.

[Whitaker]

У меня получилось $N(14)=40320$. В итоге ответ к задаче у меня получилось такой: $N(\bar{1}\bar{4})=100800-60480-60480+40320=20160$. А ответ в книге 20040. Не понимаю где у меня ошибка.

[ewert]

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

У меня получилось $N(14)=40320$. В итоге ответ к задаче у меня получилось такой: $N(\bar{1}\bar{4})=100800-60480-60480+40320=20160$. А ответ в книге 20040.

Ни то, ни другое не верно. Правильно: $24240$.

Пусть $A_1$ -- событие, состоящее в том, что имеются соседние единички; тогда $A_1=D_1+T_1$, где $T_1$ означает, что единички строены и $D_1$ -- что есть сдвоенные единички, но нет строенных. Тогда $N(A_1)=\frac{9!}{3!}-\frac{8!}{3!}=53760$ (первая дробь--
это количество перестановок цифр $1,11,2,3,5,6,4,4,4,4$ с учётом неразличимости четвёрок; вторая-- аналогичное количество перестановок цифр $111,2,3,5,6,4,4,4,4$, которые при вычислении первой дроби учитывались дважды). Ясно, что $N(A_4)=N(A_1)$.

Далее, если интерпретировать $A_1A_2$ как перестановки цифр $1,11,4,44,2,3,5,6$, то $N(A_1A_2)=8!-N(D_1T_4)-N(D_4T_1)-3N(T_1T_4)$, поскольку при вычисления факториала комбинации $D_1T_4$ и $D_4T_1$ учитывались по два раза и комбинации $T_1T_4$ -- по четыре. Аналогично, $N(D_1T_4)=N(D_4T_1)=7!-2N(T_1T_4)$, т.к. при вычислении факториала комбинации $T_1T_4$ учитывались дважды, в то время как не должны были учитываться вовсе. Наконец, $N(T_1T_2)=6!$. Собираем всё вместе:

$N(A_1A_2)=8!-2(7!-2N(T_1T_4))-3N(T_1T_4)=8!-2\cdot7!+6!=30960.$

Теперь подсчитываем количество комбинаций, в которых, наоборот, соседние цифры не совпадают:

$N(\overline{A_1+A_2})=\frac{10!}{3!\,3!}-N(A_1)-N(A_2)+N(A_1A_2)=100800-53760-53760+30960=24240.$

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

[Whitaker]

ewert в сообщении #472004 писал(а):

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

(первая дробь--
это количество перестановок цифр $1,11,2,3,5,6,4,4,4,4$ с учётом неразличимости четвёрок; вторая-- аналогичное количество перестановок цифр $111,2,3,5,6,4,4,4,4$, которые при вычислении первой дроби учитывались дважды).

Наверное вы здесь хотели написать только три четверки, а написали их 4 раза?

[ewert]

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

Наверное вы здесь хотели написать только три четверки, а написали их 4 раза?

Разумеется. Я ведь хоть в какой-то степени, да математик; и, следовательно, складывать палки или там камушки не умею.

В оправдание приведу анонсированный ранее альтернативный (прямой) способ подсчёта.

Цифры $2356$ можно переставлять между собой в каком угодно порядке. В пять позиций между ними и по краям надо вставлять группы из единиц и четвёрок. Количество комбинаций таких групп не то чтобы мало, но и не безумно велико; их нетрудно перебрать явно.

$\begin{tabular}{|l|l|l|}\hline \ Ширины\ &\ Вариантов\ &\ Способов\ \\ \ щелей\ &\ расположения\ &\ размещения 1 и 4\ \\ \hline $\ 6\ $&$\ 5\ $&$\ 2\ $\\ \hline $\ 5+1\ $&$\ C_5^2\cdot2=20\ $&$\ 2\ $\\ \hline $\ 4+2\ $&$\ C_5^2\cdot2=20\ $&$\ 2\cdot2=4\ $\\ \hline $\ 4+1+1\ $&$\ C_5^3\cdot3=30\ $&$\ 2\cdot2=4\ $\\ \hline $\ 3+3\ $&$\ C_5^2=10\ $&$\ 2\ $\\ \hline $\ 3+2+1\ $&$\ C_5^3\cdot3!=60\ $&$\ 2\cdot2=4\ $\\ \hline $\ 3+1+1+1\ $&$\ C_5^4\cdot4=20\ $&$\ 2\cdot3=6\ $\\ \hline $\ 2+2+2\ $&$\ C_5^3=10\ $&$\ 2\cdot2\cdot2=8\ $\\ \hline $\ 2+2+1+1\ $&$\ C_5^4\cdot C_4^2=30\ $&$\ 2\cdot2\cdot2=8\ $\\ \hline $\ 2+1+1+1+1\ $&$\ 5\ $&$\ 2\cdot C_4^2=12\ $\\ \hline \end{tabular}$

Например, строчка $3+2+1$ означает, что в одной щели компактно располагаются три единицы и четвёрки, в другой -- две и в третьей -- одна. Положения этих щелей могут быть выбраны $C_5^3$ способами, для каждого из которых есть $3!$ варианта перестановки объёмов. В любом случае тройная и двойная щели заполняются двумя способами независимо друг от друга (поскольку единички и четвёрки обязаны чередоваться), после чего одинарная щель заполняется автоматически.

Теперь собираем всё вместе:

$10+40+80+120+20+240+120+80+240+60=1010.$

И остаётся лишь умножить на количество $4!=24$ способов переставить цифры $2356$ между собой; окончательный результат: $24240$ способов.

[Whitaker]

Спасибо! Я всё посмотрел. Значит, в книге ответ неверный. А он был 20040.