Количество перестановок $D,D,D,O,O,O,G,G,G$ такой, что нет двух $D$ смежные и нет двух $G$ смежные
У меня следующая проблема. Я уже решил это, но я не доволен своим решением. Я надеюсь на более удачное решение, и, возможно, кто-нибудь сможет с этим помочь. Есть ли способ решить эту проблему, используя только метод звезд / столбцов?
Вычислите количество способов переставить все буквы из $D,D,D,O,O,O,G,G,G$ такой, что нет двух $D$ смежные и нет двух $G$ смежные.
Моя попытка.
За $k=2,3$, позволять $\Delta_k$ обозначим множество перестановок только st $k$ из $D$ смежны, и пусть $\Gamma_k$ обозначим множество перестановок только st $k$ из $G$смежные. Позволять$U$ - множество всех перестановок без каких-либо условий.
потом $$|U|=\frac{(3+3+3)!}{3!3!3!}=1680.$$ У нас есть $$|\Delta_3|=\frac{(1+3+3)!}{1!3!3!}=140$$ (в виде $\Delta_3$ это набор перестановок $DDD,O,O,O,G,G,G$), и $$|\Delta_2|+2|\Delta_3|=\frac{(1+1+3+3)!}{1!1!3!3!}=1120$$ поскольку это число учитывает перестановки $DD,D,O,O,O,G,G,G$. Следовательно$$|\Delta_2|=1120-2(140)=840.$$ так же $|\Gamma_3|=140$ и $|\Gamma_2|=840$.
Мы хотим найти $|\Delta_i\cap\Gamma_j|$. поскольку$\Delta_3\cap\Gamma_3$ это набор перестановок $DDD,O,O,O,GGG$, $$|\Delta_3\cap\Gamma_3|=\frac{(1+3+1)!}{1!3!1!}=20.$$ поскольку $|\Delta_2\cap\Gamma_3|+2|\Delta_3\cap\Gamma_3|$ считает перестановки $DD,D,O,O,O,GGG$, у нас есть $$|\Delta_2\cap\Gamma_3|+2|\Delta_3\cap\Gamma_3|=\frac{(1+1+3+1)!}{1!1!3!1!}=120$$ так $$|\Delta_2\cap\Gamma_3|=120-2(20)=80.$$ так же $|\Delta_3\cap\Gamma_2|=80$.
Теперь мы хотим найти $|\Delta_2\cap\Gamma_2|$. поскольку$|\Delta_2\cap\Gamma_2|+2|\Delta_3\cap\Gamma_2|+2|\Delta_2\cap\Gamma_3|+4|\Delta_2\cap\Gamma_3|$ подсчитывает количество перестановок $DD,D,O,O,O,GG,G$, мы получили $$|\Delta_2\cap\Gamma_2|+2|\Delta_3\cap\Gamma_2|+2|\Delta_2\cap\Gamma_3|+4|\Delta_2\cap\Gamma_3|=\frac{(1+1+3+1+1)!}{1!1!3!1!1!}=840.$$ Следовательно $$|\Delta_2\cap\Gamma_2|=840-2(80)-2(80)-4(20)=440.$$
По принципу включения-исключения имеем $$|\Delta_2\cup\Delta_3\cup\Gamma_2\cup\Gamma_3|=\sum_{k=2}^3|\Delta_k|+\sum_{k=2}^3|\Gamma_k|-\sum_{i=2}^3\sum_{j=2}^3|\Delta_i\cap \Gamma_j|.$$ Следовательно $$|\Delta_2\cup\Delta_3\cup\Gamma_2\cup\Gamma_3|=2(840)+2(140)-(440+80+80+20)=1340.$$ Вопрос касается размера $U\setminus(\Delta_2\cup\Delta_3\cup\Gamma_2\cup\Gamma_3)$, который $$|U|-|\Delta_2\cup\Delta_3\cup\Gamma_2\cup\Gamma_3|=1680-1340=340.$$
Ответы
Я не знаю, есть ли более удобный способ сделать это, но он может быть проще, даже если использовать ваш подход.
Перестановки «DD DGGGOO O» охватывают все случаи соседних D и смежных G, за исключением случаев, когда G являются смежными, а D - нет.
$i)$ Перестановки "DD DGGGOO O" $= \dfrac{8!}{3!3!} - \dfrac{7!}{3!3!} = 980$
[ Вычитание необходимо для того, чтобы смежные DD D и D DD считались разными. Таким образом, перестановки DDD учитываются дважды, и их нужно удалить один раз. ]
$ $
$ii)$ Перестановки "GG GOO O" и размещение $3$ D в $3$ несмежных $6$ места
$$= \dfrac{5!}{3!}.{^6}C_3 - \dfrac{4!}{3!}.{^5}C_3 = 360$$
[ Вычитание необходимо, чтобы смежные GG G и G GG считались разными. Итак, перестановки GGG и размещение D в$3$ снаружи $5$места были подсчитаны дважды и должны быть отсчитаны один раз. ]
$ $
Это дает вам желаемое $= 1680 - 980 - 360 = 340$
Я начинаю с повторения и небольшого изменения проблемы, а затем решаю ее в этой новой форме; переход к исходной задаче канонический.
Проблема. Рассмотрим множество$S=S(d+4)=\{x_1, x_2, x_3, y_1, y_2, y_3, z_1, \ldots, z_{d-2}\}$. Перестановка$S$ называется $x,y$- смежные бесплатные (а позже типа$(1,1)$) если нет двух $x$и не два $y$соседние. Определите количество$x,y$-смежные свободные перестановки.
Обратите внимание, что элементы $x_1$, $x_2$, и $x_3$ рассматриваются как отдельные элементы (и то же самое для $y$s).
Переход от задачи к исходному вопросу дается очевидной формулой$$ \frac{\text{number of $х, у$-adjacent free permutations of $S$}} {3!\, 3!\, (d-2)!} $$ в котором мы берем $d=3$.
Решение склоняется к рекурсивным алгебраическим вычислениям (модель - треугольник Паскаля). С положительной стороны, мы могли бы быть довольны рекурсивными формулами (обобщения, вычисления других подобных чисел ...). С другой стороны, будут громоздкие летные указатели во всех направлениях.
Обозначения и описание решения. Позволять$S^{a,b}\subset S$ быть подмножеством $$ S^{a,b} = \{ x_1,\ldots,x_a, y_1, \ldots, y_b, z_1, \ldots, z_{d-2}\} \subset S $$ с участием $1\leq a,b\leq3$. Оно имеет$d+a+b-2$элементы. Обозначим через$P_{(i,j)}^{a,b}$, с участием $i\leq a$ и $j\leq b$, множество перестановок $S^{a,b}$ с точно $i$ смежный $x$и $j$ смежный $y$'s, называемые перестановками типа $(i,j)$. Ясно, что множество всех перестановок$S^{a,b}$ является $$ \bigcup_{\substack{1\leq i\leq a\\1\leq j\leq b}} P_{(i,j)}^{a,b}. $$ Мы хотим вычислить $N_{(1,1)}^{3,3}$, кардинал $P_{(1,1)}^{3,3}$. Идея состоит в том, чтобы выполнять вычисления рекурсивно, используя следующую фильтрацию$S^{3,3}$: $$ S^{1,1} \subset S^{2,1} \subset S^{3,1} \subset S^{3,2} \subset S^{3,3}. $$ Каждый $N_{(i,j)}^{a,b}$ соответствующий подмножеству $S^{a,b}$ в фильтрации выражается в виде линейной комбинации с целыми коэффициентами всех $N$из предыдущего подмножества. Как только коэффициенты определены (с использованием комбинаторики конструкции) для всех этих переходов, проблема решена.
Нахождение коэффициентов. Начнем с того, что мы ищем:$$ N_{(1,1)}^{3,3} = d\,N_{(1,1)}^{3,2} + N_{(2,1)}^{3,2}. $$Все остальные коэффициенты в этом случае равны нулю. Объяснение состоит в том, что перестановка$S^{3,3}$ типа $(1,1)$ может быть выдан только при перестановке $S^{3,2}$ который относится к типу $(1,1)$ или типа $(2,1)$. Для перестановки в первом случае ровно$d=d+4-4$ позиции (из $d+4$) где $y_3$ может быть вставлен (рядом ни с одним $y_1$ ни $y_2$). В последнем случае,$y_3$ должен быть вставлен между двумя соседними $x$с.
Мы продолжим с формулами для $N_{(1,1)}^{3,2}$ и $N_{(2,1)}^{3,2}$ используя отрывок из $S^{3,1}$ к $S^{3,2}$в нашей фильтрации. Формула для$N_{(1,1)}^{3,2}$ почти такой же, как и предыдущий: $$ N_{(1,1)}^{3,2} = (d+3-2)\,N_{(1,1)}^{3,1} + N_{(2,1)}^{3,1} = (d+1)\,N_{(1,1)}^{3,1} + N_{(2,1)}^{3,1}. $$ Формула для $N_{(2,1)}^{3,2}$сложнее. Он читает$$ N_{(2,1)}^{3,2} = 0\,N_{(1,1)}^{3,1} + (d+3-3)\,N_{(2,1)}^{3,1} + 2N_{(3,1)}^{3,1} \\ = d\,N_{(2,1)}^{3,1} + 2N_{(3,1)}^{3,1}. $$ Коэффициент $d+3-3$ приходит из следующего наблюдения: если тип $(2,1)$ перестановка $S^{3,2}$ оформляется в виде $(2,1)$ перестановка $S^{3,1}$, тогда $y_2$ точно $d+3-3$ возможные места для вставки: $d+3$ это общее количество мест и $y_2$ не может занимать место между соседними $x$'s ни одно из двух мест, прилегающих к $y_1$.
Глядя на две последние формулы, отметим, что отныне нам нужны все $N$соответствует оставшимся подмножествам фильтрации. Но их меньше, и формулы легче вычислить. Получаем последовательно:
за $S^{2,1}\subset S^{3,1}$ $$ N_{(1,1)}^{3,1} = (d+2-4)\,N_{(1,1)}^{2,1} + 0\,N_{(2,1)}^{2,1} $$ $$ N_{(2,1)}^{3,1} = 4\,N_{(1,1)}^{2,1} + (d+2-3)\,N_{(2,1)}^{2,1} $$ $$ N_{(3,1)}^{3,1} = 0\,N_{(1,1)}^{2,1} + 3\,N_{(2,1)}^{2,1} $$
за $S^{1,1}\subset S^{2,1}$ $$ N_{(1,1)}^{2,1} = (d+1-2)\,N_{(1,1)}^{1,1} \quad\text{and}\quad N_{(2,1)}^{2,1} = 2\,N_{(1,1)}^{1,1}. $$
Вычисления Теперь, чтобы получить$N_{(1,1)}^{3,3}$ достаточно вернуться назад, начиная с $N_{(1,1)}^{1,1}=d!$. Выполним вычисления, подчеркнув их алгоритмический характер. Я надеюсь, что приведенные ниже обозначения не требуют пояснений.
За $S^{2,1}$: $$ \begin{array}{c||c|cr} & (1,1) && result/d! \\ \hline (1,1) & d-1 && (d-1) \\ (2,1) & 2 && 2 \end{array} $$
За $S^{3,1}$: $$ \begin{array}{c||c|c|cr} & (1,1) & (2,1) && result/d! \\ \hline (1,1) & d-2 & 0 && (d-2)(d-1) \\ (2,1) & 4 & d-1 && 6(d-1) \\ (3,1) & 0 & 3 && 6 \end{array} $$
За $S^{3,2}$ (неполная таблица): $$ \begin{array}{c||c|c|c|cr} & (1,1) & (2,1) & (3,1) && result/d! \\ \hline (1,1) & d+1 & 1 & 0 && (d-1)(d^2-d+4) \\ (2,1) & 0 & d & 2 && 6(d^2-d+2) \end{array} $$
Так $$ \begin{split} N_{(1,1)}^{3,3} &= d\,N_{(1,1)}^{3,2} + N_{(2,1)}^{3,2} \\ &= \big( (d^2-d)(d^2-d+4) + 6(d^2-d+2) \big)\,d! \\ &= \big( (d^2-d)^2 + 10(d^2-d) + 12 \big)\,d! \\ &= \big( (d^2-d+4)(d^2-d+6) - 12 \big)\,d!. \end{split} $$
В частности, ответ на первоначальный вопрос: $$ \frac{(5^2-5+4)(5^2-5+6)-12}{3!\,3!}\,\frac{5!}{3!} = 20\,\frac{2\cdot26-1}{3} = 340. $$